akhauriyash/Code-Regression huggingface dataset:
import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;sc.hasNext();) {
			String formula = sc.nextLine();
			String[] str = formula.split("\\+|=");
			boolean f = true;
			for(String s: str) f &= !(s.length() != 1 && s.charAt(0) == 'X');
			int i=0;
			for(i=f? 0: 1;i<10;i++) {
				if(isequal(formula, i)) break;
			}
			System.out.println((i==10? "NA": i));
		}
	}
	
	boolean isequal(String formula, int i) {
		String[] s = formula.replace('X', (char) (i+'0')).split("\\+|=");
		BigInteger v1 = new BigInteger(s[0]);
		BigInteger v2 = new BigInteger(s[1]);
		BigInteger v3 = new BigInteger(s[2]);
		
		return v1.add(v2).compareTo(v3) == 0;
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 12000
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
//#include<unordered_map>//イテレータあるけど順序保持しないmap
//#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<valarray>//なんとなく追加
//メモ：表示桁数を大きくする　　cout << fixed << setprecision(20) << cm << endl;
using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define PI acos(-1.0)
#define answer(ans) cout<<ans<<endl;
#define input(N) cin >> N ;

signed main() {
int N,ans;
string T;
cin >> N;
ans=1000-N%1000;
if(ans==1000){
    ans=0;
}


answer(ans);
return 0;
}



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

using namespace std;

int a, b;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> a >> b;

    if(a >= 13)
        cout << b;
    else if(a >= 6)
        cout << b / 2;
    else
        cout << 0;

    return 0;
}


Measured memory_bytes: 256
package main
import (
    "fmt"
    "os"
    "bufio"
    "strconv"
    "sort"
)
var sc = bufio.NewScanner(os.Stdin)


func main() {
    sc.Split(bufio.ScanWords)
    // code goes here
    
    a, b, k := int(nextInt()), int(nextInt()), int(nextInt())
    var m []int
    
    for i := a; i <= b && i < a+k; i += 1 {
        m = append(m, i)
    }
    for i := b; a <= i && b-k < i; i -= 1 {
        m = append(m, i)
    }
    
    sort.Ints(m)
    
    last := 0
    for _, e := range m {
        if last != e {
            fmt.Println(e)
        }
        last = e
    }
    
}



func nextInt() int64 {
    sc.Scan()
    v, e := strconv.ParseInt(sc.Text(), 10, 64)
    if e != nil {
        panic(e)
    }
    return v
}
func nextString() string {
    sc.Scan()
    return sc.Text()
}
func nextFloat() float64 {
    sc.Scan()
    v, e := strconv.ParseFloat(sc.Text(), 64)
    if e != nil {
        panic(e)
    }
    return v
}

Measured memory_bytes: 640
x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
ap = sorted(p)[a-x:]
aq = sorted(q)[b-y:]
r = sorted(r, reverse = True)

i,j,k = 0,0,0
flag = True

while k < c:
    if flag:
        if ap[i] <= aq[j]:
            if ap[i] <= r[k]:
                ap[i] = r[k]
                i += 1
                k += 1
                if i == x:
                    flag = False
                    continue
                continue
            else:
                break
        else:
            if aq[j] <= r[k]:
                aq[j] = r[k]
                j += 1
                k += 1
                if j == y:
                    flag = False
                    continue
                continue
    else:
        if i == x:
            if aq[j] <= r[k]:
                aq[j] = r[k]
                j += 1
                k += 1
                if j == y:
                    break
                continue
        else:
            if ap[i] <= r[k]:
                ap[i] = r[k]
                i += 1
                k += 1
                if i == x:
                    break
                continue
    
    break

ans = sum(ap) + sum(aq)
print(ans)


Measured memory_bytes: 29600
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
#include <cassert>
#include <random>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

void cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
//-----------------------ここから-----------
int main(void){
    ll n, x, m;
    cin >> n >> x >> m;
    vector<ll> visited(m, 0);
    ll dbeforel = 0;
    ll sbeforel = 0;
    ll dwhilel = 0;
    ll swhilel = 0;
    ll s = 0;
    ll now = x;
    while(true){
        visited[now] = true;
        ll next = now * now % m;
        if(visited[next]){
            s = next;
            break;
        }
        now = next;
    }

    bool f = false;
    now = x;
    ll nowd = 1;
    ll nows = x;
    while(true){
        ll next = now * now % m;
        if(!f && next == s){
            dbeforel = nowd;
            sbeforel = nows;
            f = true;
        } else if(f && next == s){
            dwhilel = nowd - dbeforel;
            swhilel = nows - sbeforel;
            break;
        }
        nows += next;
        now = next;
        nowd++;
    }

    ll ans = 0;
    ll tn = n;
    tn -= dbeforel;
    ans += sbeforel;
    ll div = tn / dwhilel;
    ll rem = tn % dwhilel;
    ans += div * swhilel;
    now = s;
    ll cnt = 0;
    while(cnt < rem){
        ans += now;
        ll next = now * now % m;
        now = next;
        cnt++;
    }
    cout << ans << endl;

}



Measured memory_bytes: 4048
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)
int const inf = 1<<29;

struct MCF {
    typedef int Weight;
    typedef int Capacity;
    struct Edge;
    int n;
    vector<vector<Edge> > g;
    vector<int> level, iter;

    struct Edge {
        int dst;
        Capacity cap, cap_orig;
        int revEdge;
        bool isRev;
        Edge(int dst, Capacity cap, int revEdge, bool isRev)
        :dst(dst), cap(cap), cap_orig(cap), revEdge(revEdge), isRev(isRev) {}
    };

    MCF(int n_)
    : n(n_), g(vector<vector<Edge> >(n_)), level(n_), iter(n_) {}

    void add_edge(int src, int dst, Capacity cap) {
        g[src].push_back(Edge(dst, cap, g[dst].size(), false));
        g[dst].push_back(Edge(src, 0, g[src].size() - 1, true));
    }

    void bfs(int s) {
        fill(all(level), -1);
        queue<Weight> q;
        level[s] = 0;
        q.push(s);
        while (q.size()) {
            int v = q.front(); q.pop();
            for(int i = 0; i < (int)g[v].size(); i++){
                Edge& e = g[v][i];
                if (e.cap > 0 && level[e.dst] < 0) {
                    level[e.dst] = level[v] + 1;
                    q.push(e.dst);
                }
            }
        }
    }

    Capacity dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < (int)g[v].size(); i++) {
            Edge &e = g[v][i];
            if (e.cap > 0 && level[v] < level[e.dst]) {
                int d = dfs(e.dst, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.dst][e.revEdge].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    // src->dstへの最大フローを流す
    Capacity max_flow(int src, int dst) {
        int flow = 0;
        while(1){
            bfs(src);
            if (level[dst] < 0) return flow;
            fill(all(iter), 0);
            int f;
            while ((f = dfs(src, dst, inf)) > 0) {
                flow += f;
            }
        }
    }
};

int main(){
    int n,m;
    while(cin>>n>>m && n|m){
        vector<int> a(n), b(m);
        rep(i,n)cin>>a[i];
        rep(i,m)cin>>b[i];
        MCF mcf(n+m+2);
        int s=n+m, t=n+m+1;
        rep(i,m)mcf.add_edge(i+n,t,1);
        rep(i,n){
            mcf.add_edge(s,i,1);
            rep(j,m)if(__gcd(a[i],b[j])!=1)mcf.add_edge(i,n+j,1);
        }
        cout << mcf.max_flow(s,t) << endl;
    }
}

Measured memory_bytes: 8316
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Console;
class Z { static void Main() => new K(); }
class K
{
	int[] G => ReadLine().Split().Select(int.Parse).ToArray();
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	int V, Mod;
	List<int>[] es;
	void Solve()
	{
		var I = G;
		V = I[0];
		Mod = I[1];
		es = new List<int>[V];
		for (var u = 0; u < V; u++) es[u] = new List<int>();
		for (var e = 0; e < V - 1; e++)
		{
			I = G;
			es[I[0] - 1].Add(I[1] - 1);
			es[I[1] - 1].Add(I[0] - 1);
		}
		var dp0 = DFS0(0, V);
		var dp1 = DFS1(0, dp0);
		for (var u = 0; u < V; u++) WriteLine(dp0[u] * (dp1[u] + 1) % Mod);
	}
	long[] DFS0(int u, int p)
	{
		var dp0 = new long[V];
		var st = new Stack<A0>();
		st.Push(new A0(u, p));
		while (st.Count > 0)
		{
			var f = st.Pop();
			if (f.p >= 0)
			{
				es[f.u].Remove(f.p);
				st.Push(new A0(f.u, -1));
				foreach (var v in es[f.u]) st.Push(new A0(v, f.u));
			}
			else
			{
				dp0[f.u] = 1L;
				foreach (var v in es[f.u]) dp0[f.u] = dp0[f.u] * (dp0[v] + 1) % Mod;
			}
		}
		return dp0;
	}
	long[] DFS1(int u, long[] dp0)
	{
		var dp1 = new long[V];
		var st = new Stack<int>();
		st.Push(u);
		var x = new long[V + 1]; x[0] = 1;
		var y = new long[V + 1];
		while (st.Count > 0)
		{
			u = st.Pop();
			var W = es[u].Count;
			y[W] = 1;
			for (var i = 0; i < W; i++) x[i + 1] = x[i] * (dp0[es[u][i]] + 1) % Mod;
			for (var i = W - 1; i >= 1; i--) y[i] = y[i + 1] * (dp0[es[u][i]] + 1) % Mod;
			for (var i = 0; i < W; i++) dp1[es[u][i]] = (dp1[u] + 1) * x[i] % Mod * y[i + 1] % Mod;
			foreach (var v in es[u]) st.Push(v);
		}
		return dp1;
	}
}
struct A0 { public int u, p; public A0(int u, int p) { this.u = u; this.p = p; } }


Measured memory_bytes: 35080
def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S))]
    for i in range(len(S) - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            SL[i + 1] = SL[i] + 1
        else:
            SL[i + 1] = SL[i]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r - 1] - SL[l - 1])
    for a in ans:
        print(a)


main()


Measured memory_bytes: 10312
import bisect
n,K = map(str,input().split(" "))
D = list(map(int,input().split(" ")))
N = list(n)

D_bar = []
for i in range(10):
	if not i in D:
		D_bar.append(i)

mv = str(D_bar[0])
ld = 10 - int(K)
l = len(N)
index = -1
for i in range(l):
	if int(N[i]) in D:
		index = i
		break

if index == (-1):
	print(n)
	exit(0)

for i in range(index,-1,-1):
	p = bisect.bisect_left(D_bar,int(N[i]))
	if p == ld:
		N[i] = mv
		if i == 0:
			m = str(D_bar[0]) if D_bar[0] != 0 else str(D_bar[1])
			N[0] = mv
			N.insert(0,m)
		else:
			N[i-1] = str(int(N[i-1]) + 1)
	else:
		N[i] = str(D_bar[p])
		break

for i in range(index+1,len(N)):
	N[i] = mv
print(''.join(N))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int he[N],ne[N<<1],e[N<<1],cnt,bit[N],mark[N],ans,n;
void dfs(int x,int fa){
    for (int i=he[x];i;i=ne[i]){
        if (e[i]!=fa) dfs(e[i],x);
    }
    int S1=0,S2=0,S3=0;
    for (int i=he[x];i;i=ne[i]){
        S3=S1&bit[e[i]];
        S2|=S3;
        S1|=bit[e[i]];
    }
    S1^=S2;
    for (int i=0;i<20;i++){
        if ((1<<i)>S2 && !(S1&(1<<i))){
            mark[x]=i;
            ans=max(ans,i);
            break;
        }
    }
    bit[x]=(S1>>mark[x])<<mark[x];
    bit[x]|=(1<<mark[x]);
}
void add(int u,int v){ne[++cnt]=he[u];he[u]=cnt;e[cnt]=v;}
int main(){
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        int u,v; scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
long long dp[5555][5555],p[5555],score[5555],loop[5555];
int main()
{
	long long n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>p[i];
		p[i]--;
	}
	for(int i=0;i<n;i++)
		cin>>score[i];
	for(int i=0;i<n;i++){
		int cn=i;
		for(int j=1;j<=n;j++){
			cn=p[cn];
			dp[i][j]=dp[i][j-1]+score[cn];
			if(cn==i){
				loop[i]=j;
				break;
			}
		}
	}
	long long ans=-1e18;
	for(int i=0;i<n;i++)
		for(int j=1;j<=min(loop[i],k);j++)
			if(dp[i][loop[i]]>0){
				ans=max(ans,dp[i][j]+(k-j)/loop[i]*dp[i][loop[i]]);
			}
			else
				ans=max(ans,dp[i][j]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 219048
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sync ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MOD  1000000007 
int powm(int base,int exp,int mod=MOD) {int ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
int32_t main()
{
	int a,b;
	cin>>a>>b;
	for(int i=1;i<=3;i++)
		if(i!=a && i!=b)
		{
			cout<<i<<endl;
			break;
		}
}


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

int main() {
  char a;
  cin >> a;

  if (a == 'a' || a == 'i' || a == 'u' || a == 'e' || a == 'o') {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    vector<vector<int>> adj(n);
    rep(i, n) {
        int u, k, v;
        cin>>u>>k; u--;
        rep(j, k) {
            cin>>v; v--;
            adj[u].push_back(v);
        }
    }

    vector<int> dist(n, -1);
    queue<P> q;
    q.push(P(0, 0));
    while (!q.empty()) {
        P p = q.front(); q.pop();
        int v = p.first;
        if (dist[v] != -1) continue;
        int d = p.second;
        dist[v] = d;
        for (auto e : adj[v]) {
            q.push(P(e, d + 1));
        }
    }
    rep(i, n) cout<<i + 1<<" "<<dist[i]<<endl;
}


Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define REP(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
#define FI first
#define SE second
#define PB push_back
#define EB emplace_back
#define SZ(x) (int)(x).size()
#define BN(x) ((1<<x)-1)
#define DUP(x,y) (((x)+(y)-1)/(y))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main () {
  ll X, Y; cin >> X >> Y;

  ll A = X;
  ll ans = 1LL;
  while (A*2<=Y) {
    A *= 2LL;
    ans++;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func main() {
	n := nextInt()
	S := make([]string, n)
	for i := 0; i < n; i++ {
		S[i] = nextString()
	}

	var ans []rune
	for r := 'a'; r <= 'z'; r++ {
		small := 50
		for _, s := range S {
			small = min(small, countRune(s, r))
		}

		for i := 0; i < small; i++ {
			ans = append(ans, r)
		}
	}

	fmt.Println(string(ans))
}

func countRune(s string, r rune) int {
	var cnt int
	for _, sr := range s {
		if sr == r {
			cnt++
		}
	}

	return cnt
}

// Input. ----------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}

	return i
}

func nextString() string {
	sc.Scan()
	if err := sc.Err(); err != nil {
		panic(err)
	}

	return sc.Text()
}

// ---------- Input.

// Util. ----------

func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

// ---------- Util.


Measured memory_bytes: 640
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<list>
using namespace std;

typedef long long ll;

#define INF 1000000000000000

int main(){
  ll n;
  cin >> n;
  ll a[n];
  for(int i=0;i<n;i++) cin >> a[i];
  ll d[n+1];
  d[0] = -INF;
  for(int i=1;i<n+1;i++){
    a[i-1] *= -1; 
    d[i] = INF;
  }
  for(int i=0;i<n;i++){
    auto itr = upper_bound(d,d+n+1,a[i]);
    ll index = itr - d;
    d[index] = a[i];
  }
  for(int i=n;i>=1;i--){
    if(d[i]!=INF){
      cout << i << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define F first
#define S second
#define int long long
using namespace std;

int n;
pair<int, int> a[200020];
vector<int> ed[200020];
map<int, int> mp;
int sz[200020];
int sum = 0;

void dfs(int now, int dept){
	sum += dept;
	rep(i, ed[now].size()){
		dfs(ed[now][i], dept+1);
	}
}

signed main(){
	cin >> n;
	rep(i, n){
		cin >> a[i].F;
		mp[a[i].F] = i;
		a[i].S = i;
	}
	rep(i, n) sz[i] = 1;
	sort(a, a+n);
	reverse(a, a+n);
	rep(i, n-1){
		int val = a[i].F;
		int to = a[i].F + 2*sz[a[i].S] - n;
		if(!mp.count(to)){
			cout << "-1" << endl;
			return 0;
		}
		int par = mp[to];
		sz[par] += sz[a[i].S];
		ed[par].push_back(a[i].S);
	}
	dfs(a[n-1].S, 0);
	if(sum != a[n-1].F){
		cout << "-1" << endl;
		return 0;
	}
	rep(i, n){
		rep(j, ed[i].size()){
			cout << i+1 << " " << ed[i][j]+1 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 20480
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define maxn 3000006
#define mod 1000000007
#include <bits/stdc++.h>
using namespace std;





int main() {

    ll n, x;
    cin >> n >> x;
    n *= 500;
    if(n >= x) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

int main() {
	int n; cin >> n;
	vector<int> a(n);
	vector<ll> cumu(n);
	for(int i = 0; i < n; i++) {
	    int z; cin >> z;
	    a[i] = z;
	    if(i == 0) cumu[i] = z;
	    else cumu[i] = cumu[i-1] + z;
	}
	ll minv = 1e16;
	ll sumr = 0;
	for(int i = n-1; i >= 1; i--) {
	    sumr += a[i];
	    minv = min(minv, abs(cumu[i-1] - sumr));
	}
	cout << minv;
	return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>

int N;
char S[65536];

int first[10], last[10];

char ok[1000];

int main(void) {
	int i;
	int ayaseharuka = 0;
	if (scanf("%d", &N) != 1) return 1;
	if (scanf("%65534s", S) != 1) return 1;
	for (i = 0; i < 10; i++) {
		first[i] = N;
		last[i] = -1;
	}
	for (i = 0; i < N; i++) {
		int idx = S[i] - '0';
		if (0 <= idx && idx <= 9) {
			if (first[idx] == N) first[idx] = i;
			last[idx] = i;
		}
	}
	for (i = 0; i < N; i++) {
		int idx = S[i] - '0';
		if (0 <= idx && idx <= 9) {
			int j, k;
			for (j = 0; j <= 9; j++) {
				for (k = 0; k <= 9; k++) {
					if (first[j] < i && i < last[k]) {
						ok[j * 100 + idx * 10 + k] = 1;
					}
				}
			}
		}
	}
	for (i = 0; i < 1000; i++) {
		if (ok[i]) ayaseharuka++;
	}
	printf("%d\n", ayaseharuka);
	return 0;
}


Measured memory_bytes: 1764
// StrucuredProgramming.c
// goto 文は、C/C++言語などで使うことのできる文で、実行されると無条件に
// 指定されたラベルに処理が飛びます。
// 例えば goto CHECK_NUM; という文が実行されると、プログラムの中で
// CHECK_NUM: と書かれた行に処理が移ります。
// この機能を使って、繰り返し処理なども実現することができます。
// 一方、goto 文は自由度が高すぎ、プログラムの可読性に影響するため、
// 可能な限り使わないことが推奨されています。
//
// 次のC++言語のプログラムと同じ動作をするプログラムを作成してください。
// ただし、goto 文は使わないで実装してみましょう。
//
// void call(int n){
//   int i = 1;
//  CHECK_NUM:
//   int x = i;
//   if ( x % 3 == 0 ){
//     cout << " " << i;
//     goto END_CHECK_NUM;
//   }
//  INCLUDE3:
//   if ( x % 10 == 3 ){
//     cout << " " << i;
//     goto END_CHECK_NUM;
//   }
//   x /= 10;
//   if ( x ) goto INCLUDE3;
//  END_CHECK_NUM:
//   if ( ++i <= n ) goto CHECK_NUM;
// 
//   cout << endl;
// }
// 【入力】
// １つの整数 nが１行に与えられます。
// 【出力】
// 上記プログラムに入力の整数 nを与えた結果を出力してください。
// 【制約】
// 3≤n≤10000
// 【例】
// 入力：
// 30
// 出力：
//  3 6 9 12 13 15 18 21 23 24 27 30
#include<stdio.h>

void call( int n) {
  int cnt = 0;
  for ( int i = 1; i <= n; i++) {
    int x = i;
    if ( x % 3 == 0) {
      printf(" %d", i);
    } else {
      for ( ; x;  x /= 10) {
	if ( x % 10 == 3) {
	  printf( " %d", i);
	  break;
	}
      }
    }
  }
  printf( "\n");
}

int main( void) {
  int n;

  scanf( "%d", &n);

  call( n);

  return 0;
}



Measured memory_bytes: 2040
#include <iostream>
using namespace std;

int main() {
    int H, W; cin >> H >> W;
    long long ans = 0;
    if (H == 1 || W == 1) ans = 1;
    else if (H % 2 == 1 && W % 2 == 1) ans = ((long long)H * W + 1) / 2;
    else ans = (long long)H * W / 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/*
problem's name:
statue:
writer:Patrick_y
*/
#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>
#include <stack>
#include <set>
#include <deque>
#include <cctype>
#include <sstream>
#include <math.h>
#include <stdio.h>
#include <time.h>
#define mp make_pair
typedef long long ll;
using namespace std;
const int INF=20050208;
/*------------main part------------*/



int a[100005];
int b[100005];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	double mid=1.0*a[n-1]/2;
	double minn=1000000009.0;
	int ans;
	for(int i=0;i<n;i++)
	{
		if(fabs(mid-(1.0*a[n-1]-1.0*a[i]))<minn)
		{
			ans=a[i];
			minn=fabs(mid-(1.0*a[n-1]-1.0*a[i]));
		}
	}
	cout<<a[n-1]<<" "<<ans;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include<sstream>
#include<string>
#include<vector>
#include <cmath>
#include <limits>
#include <queue>
#include<algorithm>
 
using namespace std;
 
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
 
int main(){
    string s,t;
    cin >> s >> t;
    int a,b;
    cin >> a >> b;
    string u;
    cin >> u;
    if (s == u){
        cout << a-1 << " " << b;
    }
    else {
        cout << a << " " << b-1;
    }
    

    return 0;
}

Measured memory_bytes: 256
k = int(input())
a = list(map(int, input().split()))

max_ans = 2
for i in range(k)[::-1]:
    max_ans = (max_ans // a[i]) * a[i] + (a[i] - 1)
    
min_ans = 2
for i in range(k)[::-1]:
    min_ans = -((-min_ans) // a[i]) * a[i]

tmp = max_ans
for i in range(k):
    tmp = (tmp // a[i]) * a[i]
if tmp != 2:
    print(-1)
    exit()
    
tmp = min_ans
for i in range(k):
    tmp = (tmp // a[i]) * a[i]
if tmp != 2:
    print(-1)
    exit()

print(min_ans, max_ans)

Measured memory_bytes: 63856
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
  int H, W, d;
  cin >> H >> W >> d;
  if(d % 2 == 1){
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        if(i % 2 == 0 && j % 2 == 0){
          cout << 'R';
        }
        else if(i % 2 == 1 && j % 2 == 0){
          cout << 'Y';
        }
        else if(i % 2 == 0 && j % 2 == 1){
          cout << 'G';
        }
        else if(i % 2 == 1 && j % 2 == 1){
          cout << 'B';
        }
      }
      cout << endl;
    }
  }
  else{
    for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
        int x = ((i-j+500)/d)%2;
        int y = ((i+j+500)/d)%2;
        if(x == 0 && y == 0){
          cout << 'R';
        }
        else if(x == 0 && y != 0){
          cout << 'Y';
        }
        else if(x != 0 && y == 0){
          cout << 'G';
        }
        else{
          cout << 'B';
        }
      }
      cout << endl;
    }
  }


  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,f,n) for(int i=(f); (i) < (n); i++)
#define repe(i,f,n) for(int i=(f); (i) <= (n); i++)
using namespace std;

typedef long long ll;
ll INF = 1LL << 60;

int 
main() 
{

  int n; cin >> n;
  vector<vector<int>> arr(n - 1);
  rep(i, 0, n - 1){
    rep(j, 0, 3){
      int tmp; cin >> tmp;
      arr[i].push_back(tmp);
    }
  }

  rep(i, 0, n - 1){
  int acum = 0;
    for(int k =  i; k < n - 1; k++){
      if(acum <= arr[k][1]){
        acum += arr[k][0] + (arr[k][1] - acum);
      } else if ((acum - arr[k][1]) % arr[k][2] == 0){
        acum += arr[k][0];
      } else {
        acum += arr[k][0] +  arr[k][2] - (acum - arr[k][1]) % arr[k][2];
      }
    }
    cout << acum << endl;
  }

  cout << 0  << endl;

  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int main(void){
    int N, L;
    string s[101];
    cin >> N >> L;
    rep(i, N) cin >> s[i];

    sort(s, s+N);

    rep(i, N) cout << s[i];
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.size(root_x) < self.size(root_y):
            root_x, root_y = root_y, root_x
        self.parents[root_x] += self.parents[root_y]
        self.parents[root_y] = root_x
        return True

    def find(self, x):
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        return root_x == root_y

def main():
    n, q = LI()
    uf = UnionFind(n)
    ans = []
    for _ in range(q):
        com, x, y = LI()
        if com == 0:
            uf.unite(x, y)
        if com == 1:
            if uf.same(x, y):
                ans.append(1)
            else:
                ans.append(0)
    for a in ans:
        print(a)

main()




Measured memory_bytes: 10184
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}

int main(){
  int K; cin >> K;
  long long ans = 0;
  rep(a, K) rep(b, K) rep(c, K) ans += gcd(gcd(a + 1, b + 1), c + 1);
  cout << ans << endl;
}


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

const int MAXN = 10010;
const int MAXM = MAXN * 10;
typedef long long LL;
int head[MAXN], nxt[MAXM], to[MAXM], val[MAXM], tot = 1;
LL dis[MAXN], cost[MAXM];
void addedge(int b, int e, int v, int c) {
	nxt[++tot] = head[b]; to[head[b] = tot] = e; val[tot] = v, cost[tot] = c;
	nxt[++tot] = head[e]; to[head[e] = tot] = b; val[tot] = 0, cost[tot] = -c;
}
std::queue<int> q;
int S, T, inq[MAXN], pre[MAXN];
bool bellmanford() {
	std::memset(dis, 0xcf, T - S + 1 << 3);
	q.push(S); dis[S] = 0; inq[S] = true;
	while (!q.empty()) {
		int t = q.front(); q.pop(); inq[t] = false;
		for (int i = head[t]; i; i = nxt[i]) {
			if (val[i] && dis[to[i]] < dis[t] + cost[i]) {
				dis[to[i]] = dis[t] + cost[i];
				pre[to[i]] = i ^ 1;
				if (!inq[to[i]]) {
					inq[to[i]] = true;
					q.push(to[i]);
				}
			}
		}
	}
	return dis[T] != (LL) 0xcfcfcfcfcfcfcfcfLL;
}
LL MCMF() {
	int minv = 0x3f3f3f3f, now = pre[T];
	while (now) {
		minv = std::min(minv, val[now ^ 1]);
		now = pre[to[now]];
	}
	now = pre[T];
	while (now) {
		val[now] += minv;
		val[now ^ 1] -= minv;
		now = pre[to[now]];
	}
	return minv * dis[T];
}
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	int n; std::cin >> n;
	S = 0, T = n * 2 + 5;
	for (int i = 1, t1, t2, t3; i <= n; ++i) {
		std::cin >> t1 >> t2 >> t3;
		addedge(S, i, t3, 0);
		addedge(i, n * 2 + 1, 0x3f3f3f3f, t1 + t2);
		addedge(i, n * 2 + 2, 0x3f3f3f3f, t1 - t2);
		addedge(i, n * 2 + 3, 0x3f3f3f3f, -t1 + t2);
		addedge(i, n * 2 + 4, 0x3f3f3f3f, -t1 - t2);
	}
	for (int i = 1, t1, t2, t3; i <= n; ++i) {
		std::cin >> t1 >> t2 >> t3;
		addedge(i + n, T, t3, 0);
		addedge(n * 2 + 1, i + n, 0x3f3f3f3f, - t1 - t2);
		addedge(n * 2 + 2, i + n, 0x3f3f3f3f, -t1 + t2);
		addedge(n * 2 + 3, i + n, 0x3f3f3f3f, t1 - t2);
		addedge(n * 2 + 4, i + n, 0x3f3f3f3f, t1 + t2);
	}
	LL ans = 0;
	while (bellmanford()) ans += MCMF();
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 768
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define INF 1<<31-1
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
#define NUM 100001
void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int cmp(const void* a,const void* b){return *(int*)a-*(int*)b;}

typedef struct{int s,e,c;}Edge;
int par[NUM];
int UF(){for(int i=0;i<NUM;i++)par[i]=-1;}
int Root(int x){if(par[x]<0)return x;else return par[x]=Root(par[x]);}
int Size(int x){return -par[Root(x)];}
bool Same(int x,int y){return Root(x)==Root(y);}
void Unite(int x,int y){x=Root(x);y=Root(y);if(x!=y){if(Size(x)<Size(y))swap(&x,&y);par[x]+=par[y];par[y]=x;}}

int cmpc(const void* a,const void* b){
  return ((Edge*)a)->c-((Edge*)b)->c;
};
int Kruscal(Edge* edge,int n){
  int i,ans=0;
  Edge e;
  qsort(edge,n,sizeof(Edge),cmpc);
  UF();
  FOR(i,0,n){
    e=edge[i];
    if(!Same(e.s,e.e)){
      Unite(e.s,e.e);
      ans+=e.c;
    }
  }
  return ans;
}
Edge e[NUM*2];

typedef struct{int x,y,n;}P;
int cmpx(const void* a,const void* b){
  return ((P*)a)->x-((P*)b)->x;
}
int cmpy(const void *a,const void *b){
	return ((P*)a)->y-((P*)b)->y;
}
P p[NUM];

int main() {
  int N,i;
  scanf("%d",&N);
  FOR(i,0,N)scanf("%d%d",&p[i].x,&p[i].y);
  FOR(i,0,N)p[i].n=i;
  qsort(p,N,sizeof(P),cmpx);
  FOR(i,0,N-1)e[i].s=p[i].n,e[i].e=p[i+1].n,e[i].c=p[i+1].x-p[i].x;
  qsort(p,N,sizeof(P),cmpy);
  FOR(i,0,N-1)e[i+N-1].s=p[i].n,e[i+N-1].e=p[i+1].n,e[i+N-1].c=p[i+1].y-p[i].y;

  printf("%d\n",Kruscal(e,2*N-2));
	return 0;
}


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

using namespace std;


typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m;i>=n;i--)


int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);

 ll n;
  cin >> n;
  vll a(n),s(n+1,0);
  rep(i,0,n){
   cin >> a[i];
   s[i+1]=s[i]+a[i];
  }
  
  ll res=1e+16;
  rep(i,0,n) res=min(res,max(s[n]-2*s[i],2*s[i]-s[n]));
  cout << res << endl;
  
}


Measured memory_bytes: 3456
import collections

N = int(input())
v = list(map(int, input().split()))

odd = [v[2 * i] for i in range(N // 2)]
even = [v[2 * i + 1] for i in range(N // 2)]

# print(odd, even)

odd_dict = sorted(collections.Counter(odd).items(), key=lambda x: x[1])[::-1]
even_dict = sorted(collections.Counter(even).items(), key=lambda x: x[1])[::-1]

# print(odd_dict)
# print(even_dict)

if odd_dict[0][0] != even_dict[0][0]:
    odd_sum = N // 2 - odd_dict[0][1]
    even_sum = N//2 - even_dict[0][1]
    # print(odd_sum)
    # print(even_sum)
    print(odd_sum + even_sum)

else:
    odd_len = len(odd_dict)
    even_len = len(even_dict)

    if (odd_len == 1) and (even_len == 1):
        print(N//2)
    elif (odd_len == 1) and (even_len != 1):
        even_val, even_sec_val = even_dict[0][1], even_dict[1][1]
        print(N//2 - even_sec_val)

    elif (odd_len != 1) and (even_len == 1):
        odd_val, odd_sec_val = odd_dict[0][1], odd_dict[1][1]
        print(N // 2 - odd_sec_val)

    else:
        odd_val, odd_sec_val = odd_dict[0][1], odd_dict[1][1]
        even_val, even_sec_val = even_dict[0][1], even_dict[1][1]
        print(min(N - odd_val - even_sec_val, N - odd_sec_val - even_val))


Measured memory_bytes: 67052
#include "bits/stdc++.h"
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> plint;
typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 1e9 + 7, INF = 1e18;

lint H, W, N, X[100000], Y[100000];
lint cnt[10];
set<plint> poses;
set<plint> blacks;
int main() {
	cin >> H >> W >> N;
	REP(i, N) {
		cin >> Y[i] >> X[i]; Y[i]--; X[i]--;
		blacks.insert({ Y[i], X[i] });
		REP(j, 3) {
			REP(k, 3) {
				if (Y[i] - j < 0 || Y[i] - j >= H - 2) continue;
				if (X[i] - k < 0 || X[i] - k >= W - 2) continue;
				poses.insert({ Y[i] - j, X[i] - k });
			}
		}
	}
	for (auto itr : poses) {
		lint inst_cnt = 0;
		REP(i, 3) {
			REP(j, 3) {
				lint ny = itr.first + i, nx = itr.second + j;
				if (blacks.find({ ny, nx }) != blacks.end()) inst_cnt++;
			}
		}
		cnt[inst_cnt]++;
	}

	lint sum = 0;
	REP(i, 10) {
		sum += cnt[i];
	}
	cnt[0] = (H - 2) * (W - 2) - sum;
	REP(i, 10) {
		cout << cnt[i] << endl;
	}
}


Measured memory_bytes: 67640
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	x := getNextInt64(scanner)
	d := getNextInt64(scanner)

	if d == 0 && x == 0 {
		fmt.Println(1)
		return
	}
	if d == 0 {
		fmt.Println(n + 1)
		return
	}

	n64 := int64(n)
	ysp48 := []Imos{}
	rng58 := map[int64]int{}

	var ans int64
	for i := 0; i <= n; i++ {
		k := int64(i)
		key := (k * x) % d
		inc := (k * x) / d
		mn := k*(k-1)/2 + inc
		mx := k*((n64-1)*2-k+1)/2 + inc
		if _, ok := rng58[key]; ok == false {
			rng58[key] = len(ysp48)
			im := Imos{}
			im.init()
			ysp48 = append(ysp48, im)
		}
		if _, iok := ysp48[rng58[key]].m[mn]; iok == false {
			ysp48[rng58[key]].m[mn] = 0
			ysp48[rng58[key]].a = append(ysp48[rng58[key]].a, mn)
		}
		ysp48[rng58[key]].m[mn]++
		if _, iok := ysp48[rng58[key]].m[mx+1]; iok == false {
			ysp48[rng58[key]].m[mx+1] = 0
			ysp48[rng58[key]].a = append(ysp48[rng58[key]].a, mx+1)
		}
		ysp48[rng58[key]].m[mx+1]--
	}

	var prev int64
	for i := 0; i < len(ysp48); i++ {
		imos := ysp48[i]
		sort.Sort(imos.a)
		prev = 0
		sum := 0
		for j := 0; j < len(imos.a); j++ {
			if sum == 0 {
				prev = imos.a[j]
			}
			sum += imos.m[imos.a[j]]
			if sum == 0 {
				ans += imos.a[j] - prev
			}
		}

	}
	fmt.Fprintln(writer, ans)
	writer.Flush()
}

type Imos struct {
	a S64
	m map[int64]int
}

func (imos *Imos) init() {
	imos.a = S64{}
	imos.m = map[int64]int{}
}

type S64 []int64

func (a S64) Len() int           { return len(a) }
func (a S64) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a S64) Less(i, j int) bool { return a[i] < a[j] }


Measured memory_bytes: 73344
parseInt(x) = parse(Int, x)
parseArray(x::Array{SubString{String}, 1}) = map(parseInt, x)

function main()
  N = readline() |> parseInt
  e = [Tuple{Int, Int}[] for i in 1:N]
  for i in 1:N - 1
    u, v, w = readline() |> split |> parseArray
    push!(e[u], (v, w))
    push!(e[v], (u, w))
  end

  a = zeros(N)
  a[1] = 1

  function dfs(u)
    for (v, w) in e[u]
      if a[v] == 0
        a[v] = -((w%2)*2-1) * a[u]
        dfs(v)
      end
    end
  end

  dfs(1)

  for j in 1:N
    println(a[j] == 1 ? 1 : 0)
  end
end

main()

Measured memory_bytes: 186616
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
    int N;
    string S;
    cin >> N >> S;
    bool ok = true;
    for(int i=0;i<(N/2);i++){
        if(S[i]!=S[i+(N/2)]){
            ok = false;
        }
    }
    if(ok&&N%2==0)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

int read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    int x=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

const int N=3*1e5+5;

int w,h,n,ta,tb,ans;
struct P{int x,y;}p[N],sta[N],stb[N];
bool cmp(P x,P y) {return x.x<y.x;}

int tr[N<<2],tag[N<<2];

void add(int v,int z) {tr[v]+=z;tag[v]+=z;}

void down(int v) {
    if (tag[v]) {
        add(v<<1,tag[v]);
        add(v<<1|1,tag[v]);
        tag[v]=0;
    }
}

void modify(int v,int l,int r,int x,int y,int z) {
    if (l==x&&r==y) {add(v,z);return;}
    int mid=l+r>>1;down(v);
    if (y<=mid) modify(v<<1,l,mid,x,y,z);
    else if (x>mid) modify(v<<1|1,mid+1,r,x,y,z);
    else modify(v<<1,l,mid,x,mid,z),modify(v<<1|1,mid+1,r,mid+1,y,z);
    tr[v]=max(tr[v<<1],tr[v<<1|1]);
}

void solve() {
    sort(p+1,p+n+1,cmp);
    fo(i,1,n<<2) tr[i]=tag[i]=0;
    ta=tb=0;
    fo(i,1,n) {
        if (p[i].y<=h/2) {
            int la=i-1;
            while (ta&&sta[ta].y<p[i].y) {
                modify(1,1,n,sta[ta].x,la,sta[ta].y-p[i].y);
                la=sta[ta--].x-1;
            }
            if (la!=i-1) sta[++ta].x=la+1,sta[ta].y=p[i].y;
        } else {
            int la=i-1;
            while (tb&&stb[tb].y>p[i].y) {
                modify(1,1,n,stb[tb].x,la,p[i].y-stb[tb].y);
                la=stb[tb--].x-1;
            }
            if (la!=i-1) stb[++tb].x=la+1,stb[tb].y=p[i].y;
        }
        sta[++ta].x=i;sta[ta].y=0;
        stb[++tb].x=i;stb[tb].y=h;
        modify(1,1,n,i,i,h-p[i].x);
        ans=max(ans,tr[1]+p[i+1].x);
    }
}

int main() {
    w=read();h=read();n=read();
    fo(i,1,n) {
        p[i].x=read();
        p[i].y=read();
    }
    p[++n].x=0;p[n].y=0;
    p[++n].x=w;p[n].y=h;
    solve();
    fo(i,1,n) swap(p[i].x,p[i].y);
    swap(w,h);
    solve();
    printf("%d\n",ans*2);
    return 0;
}

Measured memory_bytes: 16512
from itertools import groupby
n = list(input())
k = int(input())
if n == 1:
    print(1)
    exit()
li = []
for key,v in groupby(n):
    li.append(list(v))

if li[0][0] == "1":
    if len(li[0])>= k:
        print(1)
        exit()

for i in range(len(n)):
    if n[i] != "1":
        print(n[i])
        break

Measured memory_bytes: 3064
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, t = map(int, readline().split())
ab = sorted([tuple(map(int, readline().split())) for i in range(n)])
dp = np.zeros(t, dtype=int)
ans = 0
for a, b in ab:
    ans = max(ans, max(dp) + b)
    if a < t:
        dp[a:] = np.maximum(dp[a:], dp[:-a] + b)
print(ans)


Measured memory_bytes: 12452
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<long,long>
#define pdd pair<double,double>
#define ff first
#define ss second
#define w(x) int x; cin>>x; while(x--)
using namespace std;
ll mod = 1e9+7;
void ffast(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
double dp[3001][3001];
double solve(vector<double> &ar,int i,int x){
	if(x==0)
		return 1;
	if(i==0)
		return 0;
	if(dp[i][x] > -0.9)
		return dp[i][x];
	return dp[i][x] = ar[i]*solve(ar,i-1,x-1) + (1-ar[i])*solve(ar,i-1,x);
}
int main()
{
    ffast();
    int n;
    cin>>n;
    memset(dp,-1,sizeof dp);
    vector<double> ar(n+1);
    for(int i=1;i<=n;i++)
    	cin>>ar[i];
    cout<<fixed<<setprecision(10)<<solve(ar,n,(n+1)/2);
}

Measured memory_bytes: 74380
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int x, y, z, l, count;
    while(scanf("%d%d%d", &x, &y, &z) != EOF)
	{
		l = 0, count = 0;
		for(int i = 1; ; i++ )
		{
			if(i % 2 != 0)
			{
				l += z;
			}
			else if(i % 2 == 0)
			{
				l += y;
				if((l + z) <= x) count++;
			}
			if(l >= x) break;
		}
		printf("%d\n", count);
	}
	return 0;
}


Measured memory_bytes: 256
while 1:
    m, f, r = [int(i) for i in input().split()]
    if m == -1 and f == -1 and r == -1:
        break
    elif m == -1 or f == -1:
        print("F")
    elif m + f >= 80:
        print("A")
    elif 65 <= m + f < 80:
        print("B")
    elif 50 <= m + f < 65:
        print("C")
    elif 30 <= m + f < 50:
        if r >= 50:
            print("C")
        else:
            print("D")
    elif m + f < 30:
        print("F")

Measured memory_bytes: 7672
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>

int main()

{
    char S[7];
    while(scanf("%s",S)==1){
    if(S[2]==S[3]) {
        if(S[4]==S[5]) {
            printf("Yes\n");
        }else printf("No\n");
    } else {
        printf("No\n");
    }}

    return 0;
}



Measured memory_bytes: 128
import java.util.*;
public class Main {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args){
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		TreeMap<Integer, Integer>rmap = new TreeMap<Integer, Integer>(Collections.reverseOrder());
		while(true){
			String[] record = stdin.nextLine().split(",");
			if(record[0].equals("0") && record[1].equals("0")) break;
			int num = Integer.parseInt(record[1]);
			map.put(record[0], num);
			rmap.put(num, 1);
		}
		Iterator<Integer> itr = rmap.keySet().iterator();
		int rank = 1;
		while(itr.hasNext()) rmap.put(itr.next(), rank++);
		while(stdin.hasNext())
			System.out.println( rmap.get( map.get(stdin.nextLine()) ) );
	}
}

Measured memory_bytes: 26040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    int ma = -1;
    int mai = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (ma < a[i])
        {
            ma = a[i];
            mai = i;
        }
    }
    sort(a.begin(), a.end(), greater<int>());
    for (int i = 0; i < n; i++)
    {
        if (i == mai)
            cout << a[1] << endl;
        else
            cout << a[0] << endl;
    }
}


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

int main() {
    
    int n, k; scanf("%d%d", &n, &k);
    int *p = new int[n];
    int t = 0;
    for (int i = 0; i < k; i++) {
        scanf("%d", &p[i]);
        t += p[i];
    }
    int a = t;
    for (int i = k; i < n; i++) {
        scanf("%d", &p[i]);
        t += p[i] - p[i-k];
        if (a < t) a = t;
    }
    a += k;
    printf("%d.%c\n", a>>1, a&1?'5':'0');

    delete[] p;
    
}

Measured memory_bytes: 1024
N = int(input())
AC, WA, TLE, RE = 0, 0, 0, 0
for i in range(N):
    t = input()
    if t == 'AC':
        AC += 1
    elif t == 'WA':
        WA += 1
    elif t == 'TLE':
        TLE += 1
    else:
        RE += 1
print('AC', 'x', AC)
print('WA', 'x', WA)
print('TLE', 'x', TLE)
print('RE', 'x', RE)


Measured memory_bytes: 9092