akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int H, W, K;

char A[805][805];
int depth[805][805] = {};
bool found[805][805] = {};

void bfs(int posx, int posy);

int main() {

	scanf("%d %d %d", &H, &W, &K);

	int i, j;

	int startx, starty;

	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			scanf(" %c", &A[i][j]);
			if (A[i][j] == 'S') { startx = j; starty = i; }
		}
	}

	bfs(startx, starty);

	int ans = 114514;

	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (found[i][j] && depth[i][j] <= K) {
				if (i == 0 || i == H - 1 || j == 0 || j == W - 1) {
					ans = 1;
				}
				else {
					int tmp = min(min(min(H - 1 - i, i), W - 1 - j), j);
					if (tmp%K == 0) {
						ans = min(ans, 1 + (tmp / K));
					}
					else {
						ans = min(ans, 2 + (tmp / K));
					}
				}
			}
		}
	}
	printf("%d\n", ans);

	return 0;
}
void bfs(int posx, int posy) {
	queue<pair<int, int> >q;

	q.push(make_pair(posy, posx));
	found[posy][posx] = 1;

	while (!q.empty()) {
		pair<int, int>p = q.front();
		q.pop();
		if (p.first > 0) {
			if (!found[p.first - 1][p.second] && A[p.first - 1][p.second] != '#') {
				q.push(make_pair(p.first - 1, p.second));
				found[p.first - 1][p.second] = true;
				depth[p.first - 1][p.second] = depth[p.first][p.second] + 1;
			}
		}
		if (p.first < H - 1) {
			//下を調査
			if (!found[p.first + 1][p.second] && A[p.first + 1][p.second] != '#') {
				q.push(make_pair(p.first + 1, p.second));
				found[p.first + 1][p.second] = true;
				depth[p.first + 1][p.second] = depth[p.first][p.second] + 1;
			}
		}
		if (p.second > 0) {
			//左を調査
			if (!found[p.first][p.second - 1] && A[p.first][p.second - 1] != '#') {
				q.push(make_pair(p.first, p.second - 1));
				found[p.first][p.second - 1] = true;
				depth[p.first][p.second - 1] = depth[p.first][p.second] + 1;
			}
		}
		if (p.second < W - 1) {
			//右を調査
			if (!found[p.first][p.second + 1] && A[p.first][p.second + 1] != '#') {
				q.push(make_pair(p.first, p.second + 1));
				found[p.first][p.second + 1] = true;
				depth[p.first][p.second + 1] = depth[p.first][p.second] + 1;
			}
		}
	}

}

Measured memory_bytes: 4096
#include<stdio.h>
int main(){
  int x,y,z,n;
  scanf("%d", &x);
  scanf("%d", &y);
  scanf("%d", &z);
  if( x<=y || y<=x ){
    if(x<y){
      n=y;
    }
    else if(x>y){
      n=x;
    }
    else{
      n=x;
    }
  }
  if( z%n != 0){
    printf("%d\n", (z/n) + 1);
  }
  else{
  printf("%d\n", z/n);
  }
  return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python3
import math

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    round = int(math.log2(K)) + 1

    dv = []
    for _ in range(round):
        l = [0] * N
        dv.append(l)
    
    for n in range(N):
        dv[0][n] = A[n] - 1
    
    for k in range(1, round):
        for n in range(N):
            dv[k][n] = dv[k - 1][dv[k - 1][n]]
    
    a = []
    for i in range(round):
        if K>>i & 1:
            a.append(i)

    now = 0
    for i in a:
        now = dv[i][now]
    print(now + 1)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 174716
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int long long
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    
    int a,b,c,x,y; cin >> a >> b >> c >> x >> y;
    int ans = 0;
    int m = min(x,y);
    ans += m*min(a+b,c*2);
    if(x < y) ans += (y-m)*min(b,c*2);
    else if(x > y) ans += (x-m)*min(a,c*2);
    ANS;

    return 0;
}

Measured memory_bytes: 256
import sys
from collections import Counter


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.n = n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

    def max_root(self):
        roots = []
        for i in range(self.n):
            roots.append(self._root(i))
        cnt = Counter(roots)
        return cnt.most_common(1)[0][1]


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        uf.union(a - 1, b - 1)
    print(uf.max_root())


if __name__ == "__main__":
    main()


Measured memory_bytes: 34116
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    Q, H, S, D = map(int,input().split())
    N = int(input())
    print((N//2)*min(Q*8,H*4,S*2,D)+(N%2)*min(Q*4,H*2,S))
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n;
  R n;
  ll a[n],b[n],c[n-1];
  rep(i,n) R a[i];
  rep(i,n) R b[i];
  rep(i,n-1) R c[i];
  rep(i,n) a[i]--;
  ll ans=0;
  rrep(i,n) {
    ans+=b[a[i]];
    if(i+1<n&&a[i]+1==a[i+1]) ans+=c[a[i]];
  }
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#else
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 119 << 23 | 1;
class {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> h(n + 1), no(n + 1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 0; i < m; ++i) {
      int u, v;
      cin >> u >> v;
      if (h[u] > h[v]) {
        no[v] = 1;
      } else if (h[v] > h[u]) {
        no[u] = 1;
      } else {
        no[u] = no[v] = 1;
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
      if (!no[i])
        ans++;
    cout << ans;
  }
} NSPACE;
int main() {
  FPEN;
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  NSPACE.solve();
}

Measured memory_bytes: 3988
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<vector>
#define inf 2147483647
#define rep(i,a,b) for(int i=a;i<b;i++)
#define  rr read()
#define ll long long
#define repb(i,a,b) for(int i=a;i<=b;i++)
#define CloseIo   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
int read()
{
    char ch = getchar();
	int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int main()
{
int a=rr,b=rr,c=rr;
if(a>b)swap(a,b);
if(c>a&&b>c)
printf("Yes\n");
else
printf("No\n"); 
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll h, w;
    char s[1100][1100];
    ll dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    ll d[1100][1100];

    cin >> h >> w;
    deque<pair<ll, ll>> dq;
    memset(d, -1, sizeof(d));
    rep(i, 0, h) rep(j, 0, w) {
        cin >> s[i][j];
        if(s[i][j] == '#') {
            dq.emplace_back(i, j);
            d[i][j] = 0;
        }
    }

    while(!dq.empty()) {
        auto p = dq.front();
        dq.pop_front();
        rep(i, 0, 4) {
            ll nx = p.first + dx[i], ny = p.second + dy[i];
            if (0 <= nx && nx < h && 0 <= ny && ny < w && d[nx][ny] == -1 && s[nx][ny] == '.') {
                d[nx][ny] = d[p.first][p.second] + 1;
                dq.emplace_back(nx, ny);
            }
        }
    }

    ll ans = 0;
    rep(i, 0, h) rep(j, 0, w) chmax(ans, d[i][j]);
    cout << ans << endl;
}

Measured memory_bytes: 27188
r,c=gets.split(" ").map(&:to_i)
h = Array.new(r+1).map{Array.new(c+1,0)} 

for i in 1..r

a= gets.split.map(&:to_i)
    for j in 1..c
    h[i-1][j-1] = a[j-1]
    h[i-1][c] += a[j-1]
    h[r][j-1] += a[j-1]
    h[r][c] += a[j-1]
    end
end
for i in 0..r
    for j in 0..c
      print " " unless j == 0
      print h[i][j]
    end
    print "\n"
  end



Measured memory_bytes: 7032
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
#define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/






int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cout.precision(10); cout << fixed;
#ifdef LOCAL
  freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
  string s; cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '?') s[i] = 'D';
  }
  cout << s << endl;






/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
  return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


Measured memory_bytes: 3380
import collections
N=int(input())
ss=['' for i in range(N)]

for i in range(N):
    ss[i]=''.join(sorted(str(input())))

cc=collections.Counter(ss)
ans=0
values, counts = zip(*cc.most_common())
counts=list(counts)

for i in range(len(counts)):
    if counts[i]==1:
        break
    else:
        ans+=counts[i]*(counts[i]-1)/2

print(int(ans))

Measured memory_bytes: 35768
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
//O(N or NlogN)
//2*10^5だから
//stoiで判定は桁数大きいので破滅しそう
//単調性はないので尺取りとかにぶたんではなさそう?
//2019の倍数の次の桁が0ならこれも2019の倍数になる
//任意の数に一桁付け足したら2019の倍数になるわけではない。が、そういうやつが存在
long long modpow(long long x,long long n,long long mod){
    long long res = 1;
    while(n > 0) {
        if(n & 1) (res *= x) %= mod;
        (x *= x) %= mod;
        n>>=1;
    }
    return res;
}
int main() {
string s;
cin >> s;
ll n = s.size();
ll num[n];
ll ans = 0;
ll sum[n+1];
sum[0] = 0;
for (ll i = 0; i < n;i++){
    num[i] = s[i] - '0';
}
reverse(num, num + n);

for (ll i = 0; i < n; i++) {
    sum[i + 1] = (sum[i] + num[i] * modpow(10, i, 2019));//右から構築
    sum[i + 1] %= 2019;
}
map<ll, ll> mp;
for (auto i : sum) mp[i]++;
for(auto i:mp){
    ans += i.second * (i.second - 1) / 2;
}
cout << ans << endl;
}


Measured memory_bytes: 6720
#include <stdio.h>

const int MAX = 100000;

struct Rectangle{ int H,W; };

void printRectangle(struct Rectangle rec){
  for(int i=0;i<rec.H;i++){
    for(int j=0;j<rec.W;j++) printf("#");
    printf("\n");
  }
}

int main(){
  struct Rectangle recs[MAX];
  int length = 0;
  for(int i=0;i<MAX;i++){
    scanf("%d",&recs[i].H);
    scanf("%d",&recs[i].W);
    if(recs[i].H == 0 && recs[i].W == 0){
      break;
    } else {
      length++;
    }
  }

  for(int i=0;i<length;i++){
    printRectangle(recs[i]);
    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 2608
#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define ppc(a) __builtin_popcount(a)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int mod=1;
template<typename T=int>
T gi() {
	T x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
string to_string(string s) { return '"'+s+'"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b?"true":"false"); }
template<typename A,typename B> string to_string(pair<A,B> p) {
	return "("+to_string(p.fi)+","+to_string(p.se)+")";
}
template<typename T> string to_string(T v) {
	int fst=1;string ret="{";
	for(auto x:v) {
		if(!fst) ret+=",";
		fst=0,ret+=to_string(x);
	}
	ret+="}";return ret;
}
void dbg_out() { cerr<<endl; }
template<typename Head,typename... Tail> void dbg_out(Head H,Tail... T) {
	cerr<<" "<<to_string(H);
	dbg_out(T...);
}
#define dbg(...) cerr<<"{"<<#__VA_ARGS__<<"}:",dbg_out(__VA_ARGS__)

template<typename T>
int qpow(int a,T b) {
	int ret=1;
	while(b) {
		if(b&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod,b>>=1;
	}
	return ret;
}

int erase(int x,int y) {
	return (x&((1<<y)-1))|((x>>(y+1)<<y));
}

int insert(int x,int y,int z) {
	return (x&((1<<y)-1))|(z<<y)|(x>>y<<(y+1));
}

vector<int> solve(int A,int B,int n) {
	if(n==1) {
		return {A,B};
	}
	int p=0;
	for(int i=0;i<n;i++)
		if((A>>i&1)!=(B>>i&1)) { p=i;break; }
	int C=p==0?A^2:A^1;
	auto l=solve(erase(A,p),erase(C,p),n-1);
	auto r=solve(erase(C,p),erase(B,p),n-1);
	vector<int> ret;
	for(auto x:l) ret.pb(insert(x,p,A>>p&1));
	for(auto x:r) ret.pb(insert(x,p,B>>p&1));
	return ret;
}

int n,a,b;

int main() {
	n=gi(),a=gi(),b=gi();
	if(ppc(a^b)&1) {
		puts("YES");
		auto ans=solve(a,b,n);
		for(auto x:ans) printf("%d ",x);
	}
	else puts("NO");
	return 0;
}


Measured memory_bytes: 1756
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define mod 1000000007
#define _mod 1000000009
#define base 67
#define _base 73

const int N = 500003;

string s, t, g;
pair<int,int> m[N << 2];
pair<int,int> ht;
pair<int,int> hs[N << 2];
int legit[N];
int vis[N];

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> s >> t;
	int S = s.size(), T = t.size();
	g = s;
	while(g.size() < T)
		g += s;
	g += s;
	// generate power
	m[0].first = m[0].second = 1;
	for(int i = 1 ; i < (N << 2) ; i ++)
		m[i].first = m[i - 1].first * base % mod, m[i].second = m[i - 1].second * _base % _mod;
	// generate hash for t
	t = '~' + t;
	for(int i = 1 ; i <= T ; i ++)
		ht.first = (ht.first + (t[i] - 'a' + 1) * m[i].first) % mod, ht.second = (ht.second + (t[i] - 'a' + 1) * m[i].second) % _mod;
	// generate hash for g
	g = '~' + g;
	for(int i = 1 ; i < g.size() ; i ++)
		hs[i].first = (hs[i - 1].first + (g[i] - 'a' + 1) * m[i].first) % mod, hs[i].second = (hs[i - 1].second + (g[i] - 'a' + 1) * m[i].second) % _mod;
	// legitimate
	for(int i = 1 ; i <= S ; i ++){
		pair<int,int> pre;
		pre.first = (hs[i + T - 1].first - hs[i - 1].first) % mod;
		if(pre.first < 0) pre.first += mod;
		pre.second = (hs[i + T - 1].second - hs[i - 1].second) % _mod;
		if(pre.second < 0) pre.second += _mod;
		if(pre.first == (ht.first * m[i - 1].first % mod) && pre.second == (ht.second * m[i - 1].second % _mod))
			legit[i - 1] = true;
	}
	int ans = 0;
	for(int i = 0 ; i < S ; i ++){
		//cout << "examine " << i << endl;
		if(!vis[i] && legit[i]){
			int u = (i + T)%S;
			int cnt = 1;
			while(!vis[u] && legit[u]){
				//cout << "forward " << u << endl;
				cnt ++;
				vis[u] = 1;
				u = (u + T)%S;
			}
			if(vis[u]) return cout << "-1", 0;
			u = ((i - T) % S);
			if(u < 0) u += S;
			while(!vis[u] && legit[u]){
				//cout << "backward " << u << endl;
				cnt ++;
				vis[u] = 1;
				u = (u - T)%S;
				if(u < 0) u += S;
			}
			if(vis[u]) return cout << "-1", 0;
			ans = max(ans, cnt);
		}
	}
	cout << ans;
}


Measured memory_bytes: 66932
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
#include <queue>
#include <set>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

const int maxi = 1e6+10;
string s;
vector<int> v[maxi];
int n;
ll a[maxi];
size_t dp[100005][13];

size_t solve() {
  int i,j,ki;
  size_t res = 0;

  cin >> s;
  n = s.length();

  dp[0][0] = 1;
  for ( i = 0; i < n; i++) {
    int c;
    if (s[i] == '?') c = -1;
    else c = s[i] - '0';

    for ( j = 0; j < 10; j++) {
      if(c != -1 && c != j) continue;
      for( ki = 0; ki < 13; ki++) {
        dp[i+1][(ki * 10 + j) % 13] += dp[i][ki];
      }
    }
    for(j=0; j < 13 ; j++) dp[i+1][j] %= MOD;
  }
  res = dp[n][5];

  printf("%llu\n", res);
  return 0;
}

int main () {
  solve();
}


Measured memory_bytes: 35712
import sys
sys.setrecursionlimit(10**5+5)
from collections import defaultdict,deque
input = sys.stdin.readline
class LCA:

    def __init__(self,n):
        self.size = n+1
        self.bitlen = n.bit_length()
        self.lca = [[0]*self.size for i in range(self.bitlen)]
        self.depth = [-1]*self.size
        self.dis = [-1]*self.size
        self.depth[1] = 0
        self.dis[1] = 0
    def make(self,root):
        q = deque([root])
        while q:
            now = q.popleft()
            for nex,c,w in e[now]:
                if self.depth[nex]>= 0:
                    continue
                self.depth[nex] = self.depth[now]+1
                self.dis[nex] = self.dis[now]+w
                self.lca[0][nex] = now
                q.append(nex)
        for i in range(1,self.bitlen):
            for j in range(self.size):
                if self.lca[i-1][j] > 0:
                    self.lca[i][j] = self.lca[i-1][self.lca[i-1][j]]
    
    def search(self,x,y):
        dx = self.depth[x]
        dy = self.depth[y]
        if dx < dy:
            x,y = y,x
            dx,dy = dy,dx
        dif = dx-dy
        while dif:
            s = dif & (-dif)
            x = self.lca[s.bit_length()-1][x]
            dif -= s
        if x == y:
            return x
        for i in range(self.bitlen-1,-1,-1):
            if self.lca[i][x] != self.lca[i][y]:
                x = self.lca[i][x]
                y = self.lca[i][y]
        
        return self.lca[0][x]

n,q = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c,d = map(int,input().split())
    e[a].append((b,c,d))
    e[b].append((a,c,d))
    
lca = LCA(n)
lca.make(1)

Q = [[] for i in range(n+1)]
ans = []
for i in range(q):
    x,y,u,v = map(int,input().split())
    a = lca.search(u,v)
    ans.append(lca.dis[u]+lca.dis[v]-2*lca.dis[a])
    Q[u].append((x,y,i,1))
    Q[v].append((x,y,i,1))
    Q[a].append((x,y,i,-2))


count = defaultdict(int)
weight = defaultdict(int)
def dfs1(now,p):
    for x,y,ind,z in Q[now]:
        ans[ind] += z*(y*count[x]-weight[x])
    for nex,c,w in e[now]:
        if nex == p:
            continue
        count[c] += 1
        weight[c] += w
        dfs1(nex,now)
        count[c] -= 1
        weight[c] -= w
    
dfs1(1,0)

for i in ans:
    print(i)

Measured memory_bytes: 765164
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int main(){
    int n;
    vector<int> v;
    vector<int> dp(n);
    cin>>n;
    for(int i=0;i<n;i++){
        int h;
        cin>>h;
        v.push_back(h);
    }
    dp[0]=0;
    dp[1]=abs(v[0]-v[1]);
    for(int i=2;i<v.size();i++){
        dp[i] = min(dp[i-1]+abs(v[i]-v[i-1]),dp[i-2]+abs(v[i]-v[i-2]));
        //cout<<dp[i]<<" ";
    }
    //cout<<endl;
    cout<<dp[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 17276
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second
 
using namespace std;
typedef pair<int,int> P;
 
const int MOD=1000000007;
int INF=100100100100100;
 
signed main(){
  //string s;cin>>s;
  int n;cin>>n;n++;
  string s=to_string(n);
  int a=s[0]-'0';
  cout<<a-1+9*(s.length()-1)<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {

	int n, m; cin >> n >> m;

	vector<int> a(n);
	double sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}

	double v = (double) 1 / (4 * m);
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (sum * v <= a[i]) cnt++;
	}

	if (m <= cnt) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

void printvec(vector<int> A, int N)
{
  for(int i = 0; i < N - 1; i++) {
    cout << A[i] << " ";
  }
  cout << A[N - 1] << endl;
}

void insertionSort(vector<int> A, int N)
{
  for(int i = 1; i < N; i++) {
    printvec(A, N);
    int v = A[i];
    int j = i - 1;
    while(j >= 0 && A[j] > v){
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = v;
  }
  printvec(A, N);
}

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  insertionSort(A, N);
  return 0;
}

Measured memory_bytes: 3124
#include <iostream>
using namespace std;
int cnt;
int nums[101];

int main(void)
{
    int i, j;
    int a, b, c;
    cin >> a >> b >> c;
    nums[a] = nums[b] = nums[c] = 1;

    for (i = 0; i <= 100; i++)
    {
	if(nums[i] != 0) cnt++;
        
    }

    cout << cnt << endl;



    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		sc.nextLine();
		String s = sc.nextLine();

		int[] sum = new int[s.length()];
		for (int i = 1; i < s.length(); i++) {
			sum[i] = sum[i - 1];
			if (s.charAt(i) == 'C' && s.charAt(i - 1) == 'A') sum[i]++;
		}

		while (q-- > 0) {
			int l = sc.nextInt();
			int r = sc.nextInt();
			System.out.println(sum[r - 1] - sum[l - 1]);
		}
	}
}


Measured memory_bytes: 66320
#include <iostream>
#include <vector>

using namespace std;


int main()
{
	int h;
	int d[15][10];

	
	while (cin >> h && h){

		for (int i = 0; i < h; i++){
			for (int j = 0; j < 5; j++){
				cin >> d[i][j];
			}
		}

		int score = 0;
		bool ef = true;
		while (ef){
			ef = false;
			for (int i = 0; i < h; i++){
				int c = 0;
				vector<int> v;
				for (int j = 1; j < 5; j++){
					if (d[i][j] && d[i][j] == d[i][j - 1]){
						c++;
						if (c == 2){
							for (int k = j; k >= j - 2; k--){
								v.push_back(k);
							}
						}
						if (c > 2){
							v.push_back(j);
						}
					}
					else{
						c = 0;
					}
				}
				if (v.size())ef = true;
				for (int j = 0; j < v.size(); j++){
					score += d[i][v[j]];
					d[i][v[j]] = 0;
				}
			}

			bool f = true;
			while (f){
				f = false;
				for (int i = 0; i < h - 1; i++){
					for (int j = 0; j < 5; j++){
						if (d[i][j] && d[i + 1][j] == 0){
							d[i + 1][j] = d[i][j];
							d[i][j] = 0;
							f = true;
						}
					}
				}
			}
		}

		cout << score << endl;
	}

	return 0;
}

Measured memory_bytes: 1208
#include<iostream>
using namespace std;
int main(void)
{
  long long n, a, b;
  cin>>n>>a>>b;
  long long pre;
  long long next;
  long long ans=0;
  cin>>pre;
  for(int i=0; i<n-1; i++)
    {
      cin>>next;
      ans+=min((next-pre)*a, b);
      pre=next;
    }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a,b,x;
    cin>>a>>b;
    if(a==b or (a+b)%2==0)
    {
        x=(a+b)/2;
        cout<<x<<endl;
    }
    else
    {
        cout<<"IMPOSSIBLE"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE RankNTypes #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
-- import Control.Monad.ST
-- import Debug.Trace
-- trace _ = id

solve :: Int -> Int -> Int -> [(Int,Int)] -> Int
solve bH bW bN rcs = vResults VU.! bN
  where

  vWall = VU.fromListN (bN+1) (sort rcs ++ [(bH, bW)])

  vFact = VU.fromListN (bH+bW+1) $ scanl mMul 1 [1..(bH+bW)]
  vInvFact = VU.map mInv vFact

  combi n r = (vFact VU.! n) `mMul` (vInvFact VU.! r)
                             `mMul` (vInvFact VU.! (n-r))

  numPaths (r1,c1) (r2,c2)
    | r1 <= r2 && c1 <= c2 = combi ((r2-r1) + (c2-c1)) (r2-r1)
    | otherwise            = 0

  vResults = VU.create $ do
    vec <- VUM.new (bN+1)
    forM_ [0..bN] $ \i -> do
      let wi = vWall VU.! i
          f j = (mMul (numPaths (vWall VU.! j) wi)) <$> VUM.read vec j
      newVal <- (mSub (numPaths (1,1) wi)) <$> mSumM (map f [0 .. i-1])
      VUM.write vec i newVal
    return vec

-------------------------------------------------------------------------------

mPrime = 10^9 + 7

mAdd :: Int -> Int -> Int
mAdd x y = let w = x + y in if w < mPrime then w else w - mPrime

-- mSub x y = (x - y) `mod` mPrime    -- ok even if x < y
mSub :: Int -> Int -> Int
mSub x y = let w = x - y in if w >= 0 then w else w + mPrime

mMul :: Int -> Int -> Int
mMul x y = (x * y) `mod` mPrime

mInv :: Int -> Int
mInv x = let (_, a, _) = eGCD x mPrime in if a < 0 then a + mPrime else a

-- eGCD a b = (g,s,t) ==> g = (a,b) = a*s + b*t
eGCD :: Int -> Int -> (Int,Int,Int)
eGCD 0 b = (b, 0, 1)
eGCD a b = let (g, s, t) = eGCD (b `mod` a) a
           in (g, t - (b `div` a) * s, s)

lzFold' :: Monad m => (b -> a -> b) -> b -> [m a] -> m b
lzFold' op b0 = sub b0 where
  sub !acc [] = return acc
  sub !acc (ma:mas) = ma >>= (\a -> sub (op acc a) mas)

mSumM :: Monad m => [m Int] -> m Int
mSumM = lzFold' mAdd 0

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Int
tmain cont =
  let remLines0 = map B.words (B.lines cont)
      [bs_bH,bs_bW,bs_bN]:remLines1 = remLines0
      bH = readBInt bs_bH
      bW = readBInt bs_bW
      bN = readBInt bs_bN
      rcs = map (\[x1,x2] -> (readBInt x1,readBInt x2)) remLines1
  in solve bH bW bN rcs

outAnswer :: Int -> IO ()
outAnswer = putStrLn . show

main :: IO ()
main = outAnswer . tmain =<< B.getContents


-------------------------------------------------------------------------------

inp1 = "3 4 2\n2 2\n1 4\n"
inp2 = "5 2 2\n2 1\n4 2\n"
inp3 = "5 5 4\n3 1\n3 5\n1 3\n5 3\n"
inp4 = "100000 100000 1\n50000 50000\n"
tv1 = tmain $ B.pack inp1
tv2 = tmain $ B.pack inp2
tv3 = tmain $ B.pack inp3
tv4 = tmain $ B.pack inp4
test1 = tv1 == 3
test2 = tv2 == 0
test3 = tv3 == 24
test4 = tv4 == 123445622
alltest = test1 && test2 && test3 && test4



Measured memory_bytes: 6268
### constant

INF = Float::INFINITY

### classes

class Pt
  attr_accessor :x, :y

  def initialize() end
  def initialize(_x, _y) @x = _x; @y = _y end

  def ==(pt) @x == pt.x && @y == pt.y end
  def +(pt) Pt.new(@x + pt.x, @y + pt.y) end
  def -(pt) Pt.new(@x - pt.x, @y - pt.y) end
  def -@() Pt.new(-@x, -@y) end
  def *(t) Pt.new(@x * t, @y * t) end
  def /(t) Pt.new(@x / t, @y / t) end
  def dot(v) @x * v.x + @y * v.y end
  def cross(v) @x * v.y - @y * v.x end
  def d2() @x * @x + @y * @y end
  def d() Math.sqrt(d2()) end
  def normalize() self / d() end
  def to_s() "(#{@x},#{@y})" end
  def to_a() [@x, @y] end
end

### subroutines

def cutlen(x, ys, k)
  miny = INF
  maxy = -INF
  for i in (0...k)
    pt0 = ys[i]
    pt1 = ys[(i + 1) % k]
    v = pt1 - pt0
    if v.x != 0.0 && (pt0.x <= x && x <= pt1.x || pt1.x <= x && x <= pt0.x)
      y = v.y * (x - pt0.x) / v.x + pt0.y
      miny = y if miny > y
      maxy = y if maxy < y
    end
  end

  (maxy >= miny) ? maxy - miny : 0.0
end

### main

loop do
  m, n = gets.split.map(&:to_i)
  break if (m | n) == 0

  xys = m.times.map{Pt.new(*gets.split.map(&:to_f))}
  xzs = n.times.map{Pt.new(*gets.split.map(&:to_f))}
  #p [xys.map{|pt| pt.to_s}, xzs.map{|pt| pt.to_s}]

  xmin0 = xys.map{|pt| pt.x}.min
  xmax0 = xys.map{|pt| pt.x}.max
  xmin1 = xzs.map{|pt| pt.x}.min
  xmax1 = xzs.map{|pt| pt.x}.max

  xs = (xys.map{|pt| pt.x} + xzs.map{|pt| pt.x}).sort.uniq
  nxs = xs.length
  #p [xmin0, xmax0, xmin1, xmax1]
  #p xs

  dys = nxs.times.map{0.0}
  dzs = nxs.times.map{0.0}
  for i in (0...nxs)
    xi = xs[i]
    if xmin0 <= xi && xi <= xmax0
      dys[i] = cutlen(xi, xys, m)
    end
    if xmin1 <= xi && xi <= xmax1
      dzs[i] = cutlen(xi, xzs, n)
    end
  end
  #p [dys, dzs]
  
  vol = 0.0

  (0...nxs).each_cons(2) do |i0, i1|
    x0 = xs[i0]
    x1 = xs[i1]
    if xmin0 <= x0 && x1 <= xmax0 && xmin1 <= x0 && x1 <= xmax1
      dy0 = dys[i0]
      dz0 = dzs[i0]
      dy1 = dys[i1]
      dz1 = dzs[i1]
      v = (x1 - x0) * (dy0 * dz1 + dy1 * dz0 + 2 * (dy0 * dz0 + dy1 * dz1)) / 6
      vol += v
    end
  end

  puts vol
end

Measured memory_bytes: 6136
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
 
ll dp[2097152];
ll arr[25][25];
ll n;
ll m=1000000000+7;
 
 
ll solve(ll mask)
{
	ll j=__builtin_popcount(mask);
	
	if(j==n) return 1;
	
	if(dp[mask]!=-1)return dp[mask];
	
	ll ans=0;
 
	for(int i=0;i<n;i++)
	{
		if(arr[j][i] && !(mask&(1<<i)))
		{
			ans=(ans%m+solve(mask|(1<<i))%m)%m;
			
		}
	}
	dp[mask]=ans;
	
	return dp[mask];
	
}
 
 
int main()
{
memset(dp,-1,sizeof(dp));
cin>>n;
for(int i=0;i<n;i++)
{
	for(int j=0;j<n;j++)
	{
		cin>>arr[i][j];
	}
}
cout<<solve(0)<<endl;
 
	
	
} 

Measured memory_bytes: 16640
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647
#define dset(n) cout << fixed << setprecision(n)

int main() {
  kyun;
  int n;
  cin >> n;
  dset(10);
  vector<ind> data(n);
  rep(i,n) cin >> data[i];
  ind ans = 0;
  rep(i,n) ans += 1/data[i];
  cout << 1/ans;
  hinata;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int64_t G=167167167167;
int64_t H=G*-1;


int main() {
  int A,B,Q;
  cin>>A>>B>>Q;
  vector<int64_t> p(A+2);
  vector<int64_t> q(B+2);
  for(int i=1;i<=A;i++){
    cin>>p[i];
  }
  for(int i=1;i<=B;i++){
    cin>>q[i];
  }
  p[0]=H;
  q[0]=H;
  p[A+1]=G;
  q[B+1]=G;
  for(int i=0;i<Q;i++){
    int64_t N;
    cin>>N;
    int64_t LP,LQ,RP,RQ;
    int a,b;
    a=lower_bound(p.begin(),p.end(),N)-p.begin();
    b=lower_bound(q.begin(),q.end(),N)-q.begin();
    LP=N-p[a-1];
    RP=p[a]-N;
    LQ=N-q[b-1];
    RQ=q[b]-N;
    int64_t Z=min(min(max(LP,LQ),max(RP,RQ)),min(min(LP,RQ)*2+max(LP,RQ),min(RP,LQ)*2+max(RP,LQ)));
    cout<<Z<<endl;
  }
}

Measured memory_bytes: 4756
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
#include <cassert>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
 
#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)
 
typedef long long ll;
typedef pair<int, int> pii;

int val[3];

string line;
int pos;
char get() { return pos<line.size()?line[pos++]:'$'; }
void unget() { pos--; }

int bnot(int x) { return 2-x; }
int band(int x, int y) { return min(x, y); }
int bor(int x, int y) { return max(x, y); }

int formula()
{
	char c = get();
	switch (c) {
	case '0': case '1': case '2':
		return c-'0';
	case 'P': return val[0];
	case 'Q': return val[1];
	case 'R': return val[2];
	case '-': return bnot(formula());
	case '(': {
				  int a = formula();
				  char op = get();
				  int b = formula();
				  int ans = op=='*'?band(a, b):bor(a, b);
				  get();
				  return ans;
			  }
	}
}

int main()
{
	for (;;) {
		cin >> line;
		if (line[0] == '.') break;

		int cnt = 0;
		for (int i = 0; i < 3*3*3; i++) {
			pos = 0;
			for (int j = 0, t = i; j < 3; j++, t /= 3)
				val[j] = t%3;
			if (formula() == 2)
				cnt++;
		}

		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    string str;
    cin >> str;
    if(str.length() < 4)
    {
        cout << "No" << endl;
        return 0;
    }
    if(str[0] == 'Y' && str[1] == 'A' && str[2] == 'K' && str[3] == 'I')
        cout << "Yes" <<endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
# ANSHUL GAUTAM
# IIIT-D

from math import *
from string import *
from itertools import *
from copy import *

N,T = map(int, input().split())
minn = 999999999
for n in range(N):
	c,t = map(int, input().split())
	if(t <= T):
		minn = min(minn,c)
if(minn == 999999999):
	print("TLE")
else:
	print(minn)

Measured memory_bytes: 3832
#include <bits/stdc++.h>
// #include <atcoder/all>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define rFORe(i, a, n) for(int (i) = (int)(n); (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 1, (n))
#define REPo(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rREPe(i, n) rFORe((i), 1, (n))
#define rREPo(i, n) rFORe((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define vc(T) vector<T>
#define vv(T) vc(vc(T))
using namespace std;
// using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using pll = pair<ll,ll>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// auto mod int
// const int mod = 1000000007;
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
  int n, k;
  cin >> n >> k;
  vp lr(k);
  REP(i, k) cin >> lr[i].first >> lr[i].second;
  vc(mint) dp(n+1);
  vl imo(n);
  dp[0] = 1;
  mint sum = 0;
  REP(i, n) {
    sum += dp[i];
    REP(j, k) {
      int l = min(i + lr[j].first, n);
      int r = min(i + lr[j].second+1, n);
      dp[l] += sum;
      dp[r] -= sum;
    }
    // REPo(t, n) printf("%lld%c", dp[t], (t==n ? '\n' : ' '));
  }

  cout << dp[n-1] << endl;

  return 0;
}

Measured memory_bytes: 6368
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
	int s,w;
	cin>>s>>w;
	
	if(s>w){
		cout<<"safe"<<endl;
	}else{
		cout<<"unsafe"<<endl;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  
  // フレームの上枠
  for(int i = 0; i < (W + 2); ++i) cout << "#";
  cout << "" << endl;
  
  for(int i = 0; i < H; ++i)
  {
    cout << "#";
    string a = "";
    cin >> a;
    cout << a;
    cout << "#" << endl;
  }

  // フレームの下枠
  for(int i = 0; i < (W + 2); ++i) cout << "#";
  cout << "" << endl;
  
  return 0;
 
}

Measured memory_bytes: 256
#include<stdio.h>

int a,b;

int main(void){
    scanf("%d%d",&a,&b);
    if(a>0)
		puts("Positive");
    else if(b>=0)
		puts("Zero");
    else if((a&1)^(b&1))
		puts("Positive");
    else
		puts("Negative");
    return 0;
}

Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define VECV(a,n,m) vector<vector<int>> a(n, vector<int>(m));
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
bool f(string s){
  bool ans=true;
  rep(i,s.size()/2){
    if(s[i]!=s[s.size()/2+i]){
      ans=false;
      break;
    }
  }
  return ans;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  ll Y;
  cin>>N>>Y;
  rep(i,N+1){
  	rep(j,N-i+1){
    	if(10000*i+5000*j+1000*(N-i-j)==Y){
        	cout<<i<<" "<<j<<" "<<N-i-j<<endl;
            return 0;
        }
    }
  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
int N, A,x[50];
vector<int> p, m;
int zero = 0,psum[2501], msum[2501];
signed main()
{
	cin >> N >> A;
	for (int i = 0; i < N; i++){
		cin >> x[i];
		if (x[i]>A) p.push_back(x[i]-A);
		else if (x[i] < A) m.push_back(abs(x[i]-A));
		else zero++;
	}
	psum[0] = 1;
	for (int i = 0; i < p.size(); i++)
		for (int k = 2500 - p[i]; k >= 0; k--)
			psum[k + p[i]] += psum[k];
	msum[0] = 1;
	for (int i = 0; i < m.size(); i++)
		for (int k = 2500 - m[i]; k >= 0; k--)
			msum[k + m[i]] += msum[k];
	int result = -1;
	for (int i = 0; i <= 2500; i++)
		result += psum[i] * msum[i] * ((ll)1 << zero);
	cout<<result;
	return 0;
}

Measured memory_bytes: 256
string = str(input())
lis = []

for s in string:
  lis.append(int(s))
  
ans = 0
itr = 0
j = 0
for i in lis:
  if len(lis) == 1:
    break
    
  if itr == 0:
    itr += 1
    j = i
    continue
    
  if  j == i:
    ans += 1
    if i == 1:
      j = 0
    else:
      j = 1
  else:
    j = i
    continue

print(ans)
    

Measured memory_bytes: 3956
#include<iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  int A[201];
  for (int i=0;i<N;i++) cin >> A[i];
  int counter = 0;
  bool flg = true;
  while (true){
    for (int i=0;i<N;i++){
      if (A[i]%2==0) A[i] /= 2;
      else flg = false;
    }
    if (flg) counter++;
    else break;
  }
  cout << counter << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define sz(x) int(x.size())

typedef long long ll;

using namespace std;

static const int MAX = 100002;

int main(int argc, const char * argv[]) {
    // input from txt
    
    /////////
    //write//
    /////////
    
    int n;
    ll *a, *b;
    a = new ll[MAX];
    b = new ll[MAX];
    cin >> n;
    rep(i, n+1)cin >> a[i];
    rep(i, n)cin >> b[i];
    b[n+1] = 0;
    
    ll res = 0;
    rep(i, n){
        if(b[i]>a[i]){
            res+=a[i];
            b[i]-=a[i];
            if(a[i+1]>b[i]){
                a[i+1]-=b[i];
                res+=b[i];
            }else{
                res+=a[i+1];
                a[i+1]=0;
            }
        }
        else{
            res += b[i];
        }
    }
    
    cout << res << endl;
    
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;

int main(){
  int n;
  cin >> n;
  long long a[n], tmp;
  for (int i = 0; i < n; i++){
    cin >> tmp;
    a[i] = tmp - (i + 1);
  }
  sort(a, a + n);
  long long answer, count=0;
  if (n % 2 == 1)
    answer = a[n / 2];
  else
    answer = (a[n / 2 - 1] + a[n / 2]) / 2;
  for (int i = 0; i < n; i++)
    count += abs(a[i] - answer);
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int N, a, b, ans;
    cin >> N;
    for (int i = 0; i < N; i++){
        if (i == 0) {
            cin >> a;
            ans = a;
            continue;
        }
        cin >> a;
        ans = __gcd(ans, a);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
S = input()
K = int(input())

oz = ord("z")

ans = ""

for s in S[:-1]:
    if s != "a" and oz+1-ord(s) <= K:
        K -= oz+1-ord(s)
        ans += "a"
    else:
        ans += s

ans += chr(((ord(S[-1])-ord("a")+K)%26)+ord("a"))

print(ans)

Measured memory_bytes: 9392
n = int(input())
a_list = list(map(int, input().split()))  # n個の数字がリストに格納される

num = 0
for i in range(len(a_list) - 1):
    if a_list[i] > a_list[i+1]:
        num += a_list[i] - a_list[i+1]
        a_list[i+1] = a_list[i]
    else:
        continue

print(num)

Measured memory_bytes: 32208