akhauriyash/Code-Regression huggingface dataset:
icase=0
if icase==0:
    n=int(input())
    g=[[] for i in range(n)]
    for i in range(n-1):
        ui,vi,wi=map(int,input().split())
        wi=wi%2
        g[ui-1].append((vi-1,wi))
        g[vi-1].append((ui-1,wi))
elif icase==1:
    vv,e,r=4,5,0
    g = [[] for _ in range(vv)]
    g[0]=[(1,1),(2,4)]
    g[1]=[(2,2),(3,5)]
    g[2]=[(3,1)]
    n=3
    g=[[(1, 0)], [(0, 0), (2, 1)], [(1, 1)]]
elif icase==2:
    n=5
    g=[[(2, 0)], [(4, 0), (2, 0)], [(1, 0), (0, 0), (3, 0)], [(2, 0)], [(1, 0)]]

from heapq import heappop,heappush

q=[]
heappush(q,(0,0)) 

inf=float("INF")
dist=[inf]*(n)
dist[0]=0
while len(q)>0:
    dd,state = heappop(q)
#    print("dd:",dd,"state:",state,"q:",q)
    for v,dv in g[state]:
#        print("v:",v,"dv:",dv,"g[state]:",g[state],"parent[v]:",parent[v])
        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(q,(dist[v],v))
#            print(" state:",state,"v:",v,"dist[v]",dist[v])

for i in range(n):
    print(dist[i]%2)



Measured memory_bytes: 94168
#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
int n,m;
vector<int> G[N];
int indeg[N],fa[N];

queue<int> q;
void toposort(int rt) {
	q.push(rt); fa[rt]=0;
	while (!q.empty()) {
		int x=q.front(); q.pop();
		for (int i=0;i<G[x].size();i++) {
			int y=G[x][i];
			if (--indeg[y]==0) {
				fa[y]=x;
				q.push(y);
			}
		}
	} 
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<n+m;i++) {
		int x,y; scanf("%d%d",&x,&y);
		G[x].push_back(y);
		indeg[y]++;
	}
	for (int i=1;i<=n;i++)
		if (indeg[i]==0) {
			toposort(i); break;
		}
	for (int i=1;i<=n;i++) printf("%d\n",fa[i]);	
	return 0;
}

Measured memory_bytes: 7040
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
vector <char> v;
int main()
{
    char str[12];
    scanf("%s",str);
    int len=strlen(str);
    int flag=0;
    for(int i=0;i<len;i++)
    {
        if(str[i]=='0')
            v.push_back('0');
        else if(str[i]=='1')
            v.push_back('1');
        else if(str[i]=='B'&&v.size()>0)
            v.erase(v.end()-1);
    }
    for(int i=0;i<v.size();i++)
        cout<<v[i];
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;
typedef long long ll;
int M = 100000007;

int table[10] = {3,5,5,5,5,5,5,5,3,5};
int dp[10][100001][6];

ll solve(int button, int len) {
  ll res = 0;
//  cout << button << " " << len << endl;
  REP(i, table[button]) {
    res = (res + dp[button][len][i]) % M;
  }
  return res;
}

int main() {
  memset(dp,0,sizeof(dp));
  REP(i, 10) {
    //dp[i][0][0] = 1;
    for (int j=1; j<100001; ++j) {
      if (j%table[i]==1) dp[i][j][0] = 1;
      REP(k, table[i])
        dp[i][j][0] = (dp[i][j][0] + dp[i][j-1][k]) % M;
      for (int k=1; k<table[i]; ++k) {
        dp[i][j][k] = (dp[i][j][k] + dp[i][j-1][k-1]) % M;
      }
    }
  }
  // REP(i,10) {
  //   REP(j,5) {
  //     printf("(%d,%d)=%d ", i,j,dp[1][i][j]);
  //   }
  //   cout <<endl;
  // }
  // cout << endl;
  
  string s;

  while(cin >> s, s!="#") {
    char now = 0;
    int start = 0;
    ll res = 1;
    REP(i, s.size()) {
      if (s[i] != now) {
        if (now!=0) {
          res = (res * solve(now-'0', i-start)) % M;
        }
        now = s[i];
        start = i;
      }
    }
    res = (res * solve(now-'0', s.size()-start)) % M;
    cout << res << endl;
  }
}

Measured memory_bytes: 24000
//https://atcoder.jp/contests/abc121/tasks/abc121_b
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int N, M, C;
vector<int> B;
bool f( vector<int> &A ){
    int res{};
    REP(i, M){
        res += A[i]*B[i];
    }
    return res + (C) > 0 ? 1 : 0;
}
int main()
{
    cin >> N >> M >> C;
    B.resize(M);
    for( auto &x : B ){
        cin >> x;
    }
    int cnt{};
    REP(i, N){
        vector<int> A(M);
        REP(j, M){
            cin >> A[j];
        }
        cnt += f(A);
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

#ifdef  _DEBUG
#define debug(x) cout << "debug" << ": " << x << endl;
#else
    #define debug(x)
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define Rep(i, n) for (long long i = 0; i< (long long)(n); i++)
#define RRep(i,n) for (long long i = ((long long)(n)-1); i>=0; i--)
#define all(v) (v).begin(),(v).end()

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    int weight;
    edge(int f,int t,int w) : from(f), to(t), weight(w){ }
};

using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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

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

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

constexpr ll INF = 1e9+7;

vector<int> dx = {-1,0,1,0};
vector<int> dy = {0,-1,0,1};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x,a,b;
    cin >> x >> a >> b;
    if(b-a<=0){
        cout << "delicious" << endl;  
    }
    else if(b-a<=x){
        cout << "safe" << endl;
    }
    else{
        cout << "dangerous" << endl;
    }
    debug(b-a);
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;


public class Contest
{
	public static void Main()
	{
		int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));

		int[] b = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));
//		int[] c = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));
//		int[] d = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));

		int s1 = 0;
		int s2 = 0;

		for(int i=0; i<b.Length; i++) {
			s2+=b[i];
		}
		int df = s2;
		for(int i=0; i<b.Length; i++) {
			s1+=b[i];
			s2-=b[i];
			if(Math.Abs(s1-s2)<df) df = Math.Abs(s1-s2);
		}

		Console.WriteLine(df);
	}
	
	private static int calc_main(int[] a,int[] b,int[] c,int[] d) {



		return 0;
	}




}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    string S;
    cin >> S;
    int cnt = 0;
    int N = S.length();
    for (int i = 1; i < N; i++) {
        if(S[i] != S[i-1]){
            cnt++;
        }
    }
    printf("%d\n", cnt);
}

Measured memory_bytes: 3848
#include<iostream>
#include<string>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef long long ll;
const long long MOD=1e9+7;

int main(){
	int n;
	cin>>n;
	string s[2];
	rep(i,2)cin>>s[i];
	ll ans=1;
	bool pre;
	rep(j,n){
		if(j==0){
			if(s[0][j]==s[1][j]){
				ans*=3;
				pre=false;
			}else{
				ans*=6;
				j++;
				pre=true;
			}
		}else{
			if(s[0][j]==s[1][j]){
				if(pre)ans*=1;
				else ans*=2;
				pre=false;
			}else{
				if(pre)ans*=3;
				else ans*=2;
				pre=true;
				j++;
			}
		}
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3628
#include <iostream>
using namespace std;
int main(void){
    int x,y;
    while(true){
        cin>>x;
        cin>>y;
        if(x==0 && y==0 ){  
            break;
        }
        
        if(x<y){
            cout<<x<<" "<<y<<endl;
        }
        else {
            cout<<y<<" "<<x<<endl;
        }
    }
}       


Measured memory_bytes: 2996
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9

vector<vector<int> > wl;
vector<int> wn;
int n;
int cnt;
void dfs(int x,int y){
 //   cout<<x<<' '<<y<<endl;
    if( x== n-1 && y == n ){
	if( wn[x] == 0 ) cnt++;
	 return;
    }
    if( x== y ){
	dfs(x,y+1);
	return;
    }
    
    if( wl[x][y] == 0 ){
	for(int w=1;w>=-1;w-=2){
	    wl[x][y] == w;
	    wl[y][x] == -w;
	    wn[x] += w;
	    wn[y] -= w;
	  //  if( -n+y < wn[x] < n-y)
	    if( y == n-1 ){
		if(wn[x]==0)dfs(x+1,x+2);
	    }else{
		dfs(x,y+1);
	    }
	    wl[x][y] = 0;
	    wl[y][x] = 0;
	    wn[x] -=w;
	    wn[y] +=w;
	}
    }else{
	//if(-n+y  <wn[x]<n-y) 
	if( y == n-1 ){
	    if(wn[x]==0)dfs(x+1,x+2);
	}else{
	    dfs(x,y+1);
	}
    }
}


int main(){
    while(1){
	cin>>n;
	if(n==0)break;
	cnt = 0;
	wl = vector<vector<int> >(n,vector<int>(n,0) );
	wn = vector<int>(n,0);
	int m;
	cin>>m;
	for(int i=0;i<m;i++){
	    int x,y;
	    cin>>x>>y;
	    x--,y--;
	    wl[x][y] =  1;
	    wl[y][x] = -1;
	    wn[x]++;
	    wn[y]--;
	}
	dfs(0,1);
	//dfs(0,0,-1);
	cout<<cnt<<endl;
    }
    return 0;
}



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

int main() {
  int n,k;
  cin >>n>>k;
  map<int,int>mp;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    mp[a]++;
  }
  int kazu=mp.size();
  vector<int>p;
  auto begin=mp.begin(),end=mp.end();
  for(auto iter=begin;iter!=end;iter++){
    int b=iter->second;
    p.push_back(b);
  }
  sort(p.begin(),p.end());
  long long kotae=0;
  for(int i=0;i<kazu-k;i++){
    kotae+=p[i];
  }
  cout<<kotae<<endl;
  return 0;
}
  

Measured memory_bytes: 13508
#include <stdio.h>

unsigned xor128() {
	static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

typedef struct node_t {
	int val;
	struct node_t *lch, *rch;
	int size;
	unsigned int pri;
} node;

node* new_node(int val) {
	static int it = 0;
	static node pool[200000];
	pool[it] = (node) { val, 0, 0, 1, xor128() };
	return &pool[it++];
}

int count(node *t) {
	return !t ? 0 : t->size;
}

node *update(node *t) {
	t->size = count(t->lch) + count(t->rch) + 1;
	return t;
}

node *merge(node *l, node *r) {
	if (!l || !r) return !l ? r : l;
	if (l->pri > r->pri) {
		l->rch = merge(l->rch, r);
		return update(l);
	}
	r->lch = merge(l, r->lch);
	return update(r);
}

typedef struct{ node *a, *b; } pnode;

pnode split(node *t, int k) {
	if (!t) return (pnode) { 0, 0 };
	if (k <= count(t->lch)) {
		pnode s = split(t->lch, k);
		t->lch = s.b;
		return (pnode) { s.a, update(t) };
	}
	pnode s = split(t->rch, k - count(t->lch) - 1);
	t->rch = s.a;
	return (pnode) { update(t), s.b };
}

int count_lower(node *t, int v) {
	int res = 0;
	while (t) {
		if (t->val < v) {
			res += count(t->lch) + 1;
			t = t->rch;
		}
		else {
			t = t->lch;
		}
	}
	return res;
}

node *insert(node *t, int val) {
	int k = count_lower(t, val);
	pnode s = split(t, k);
	return merge(merge(s.a, new_node(val)), s.b);
}

node *erase(node *t, int l, int r) {
	pnode s1 = split(t, l), s2 = split(s1.b, r - l);
	return merge(s1.a, s2.b);
}

void print(node *t) {
	if (!t) return;
	print(t->lch);
	printf("%d\n", t->val);
	print(t->rch);
}

int main(void)
{
	int q, com, x, l, r, cnt = 0;
	node *root = 0;
	pnode p1, p2;
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &com, &x);
		if (com == 0) {
			root = insert(root, x);
			printf("%d\n", ++cnt);
		}
		else if (com == 1) {
			printf("%d\n", count_lower(root, x + 1) - count_lower(root, x));
		}
		else if (com == 2) {
			l = count_lower(root, x);
			r = count_lower(root, x + 1);
			cnt -= r - l;
			root = erase(root, l, r);
		}
		else {
			scanf("%d", &r);
			l = count_lower(root, x);
			r = count_lower(root, r + 1);
			p1 = split(root, l), p2 = split(p1.b, r - l);
			print(p2.a);
			root = merge(merge(p1.a, p2.a), p2.b);
		}
	}
	return 0;
}



Measured memory_bytes: 7952
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
  int n,a[100],ans=10000000,cnt;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> a[i];
  }
  for(int i=-100; i<=100; i++) {
    cnt=0;
    for(int j=0; j<n; j++) {
      cnt+=(a[j]-i)*(a[j]-i);
    }
    ans=min(ans,cnt);
  }
  cout << ans << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FALSE 0
#define TRUE 1

int main(){
    // int A, B, C;
    // int N;
    string S;
    vector<int>     vD(100010);
    vector<int>     vRen(100010);
    vector<int>     vRes(100010, 0);
    // map<int64_t, int>   mP;
    // string res;

    cin >> S;
    int N = S.length();
    vRen.at(0) = 1;
    for (int i=0; i<N-1; i++){
        vD.at(i) = (int)(S[i] - S[i+1]);
        vRen.at(i+1) = (S[i] == S[i+1])?
                       vRen.at(i) + 1: 1;
    }

    const int dRL = (int)('R' - 'L');
    const int dLR = (int)('L' - 'R');
    
    int nowRpos = 0;
    for (int i=0; i<N; i++){
        if (vD.at(i) == dRL){
            nowRpos = i;
            int RNum = vRen.at(i) / 2;
            vRes.at(i) += RNum + (vRen.at(i)%2);
            vRes.at(i+1) += RNum;
        }
        if (vD.at(i) == dLR){
            int LNum = vRen.at(i) / 2;
            vRes.at(nowRpos) += LNum;
            vRes.at(nowRpos+1) += LNum + (vRen.at(i)%2);
        }
    }
    
    // 最後のLの連続を処理
    int LNum = vRen.at(N-1) / 2;
    vRes.at(nowRpos) += LNum;
    vRes.at(nowRpos+1) += LNum + (vRen.at(N-1)%2);

    for (int i=0; i<N; i++){
        cout << vRes.at(i) << " ";
    }
    cout << endl;
    
    // cout << res << endl;
    return 0;
}


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

int main() {

  long x;
  cin >> x;

  long count = 2 * (x / 11);

  long mod = x % 11;

  if (0 < mod && mod < 7){
    count += 1;
  } else if (6 < mod) {
    count += 2;
  }

  cout << count << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <functional>
#include <utility>
#include <unordered_map>
#include <map>
#include <set>
#include <array>
#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int gcd(int a, int b) {
	return b != 0 ? gcd(b, a % b) : a;
}

int gcd_m(vector<int> x) {
	int a = x[0], b = x[1];
	int tmp = gcd(a, b);
	x.erase(x.begin(), x.begin() + 1);
	while (x.size()) {
		int c = x[0];
		tmp = gcd(tmp, c);
		x.erase(x.begin());
	}
	return tmp;
}

int main() {
	int N, X;
	cin >> N >> X;
	set<int> num;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		num.insert(abs(a-X));
	}
	vector<int> dist;
	for (auto x : num) {
		dist.push_back(x);
	}
	if (dist.size() != 1) {
		cout << gcd_m(dist) << endl;
	}
	else {
		cout << dist[0] << endl;
	}
	return 0;
}

Measured memory_bytes: 5752
#include <bits/stdc++.h>
#define r(i,n) for(int i = 0; i<n; i++)
using namespace std;
 
int main() {
  int n,k,mini=1000000000;
  cin >> n >> k;
  vector<int> v(n);
  r(i,n) cin>>v.at(i);
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  r(i,n-k+1){
   if(mini>v.at(i)-v.at(k-1+i)) mini = v.at(i) -v.at(k-1+i);
  }
  cout << mini<< endl;
}



Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
typedef pair<int,int> P;
typedef vector<int> vi;

ll gcd(ll a,ll b){
    ll v0=a,v1=b,v2=a%b;
    while(v2!=0){
        v0=v1;
        v1=v2;
        v2=v0%v1;
    }
    return v1;
}

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

int main(){
    ios::sync_with_stdio(false);
    int n; cin >> n;
    double d1=0.0,d2=0.0,d3=0.0,di=0.0,d[n],x[n],y[n];
    rep(i,n) cin >> x[i];
    rep(i,n) cin >> y[i];
    rep(i,n){
        d1+=abs(x[i]-y[i]);
        d2+=pow(abs(x[i]-y[i]),2);
        d3+=pow(abs(x[i]-y[i]),3);
        d[i]=abs(x[i]-y[i]);
    }
    rep(i,n){
        di=max(di,abs(x[i]-y[i]));
    }
    printf("%.6f\n" "%.6f\n" "%.6f\n" "%.6f", d1, pow(d2,0.5), pow(d3,0.3333333333), di);
    return 0;
}


Measured memory_bytes: 3416
//In The Name of ALLAH//

/*      ______     _    _______
       |  ___ \   | |  |  ____/   /\
       | |   \ \  | |  | |       /  \
       | |___/ /  | |  | |___   / /\ \
       |     _/   | |  |  __/  / /__\ \
       | |\ \     | |  | |    / ______ \
       | | \ \    | |  | |   / /      \ \
       |_|  \_\   |_|  |_|  /_/        \_\
*/

#include<bits/stdc++.h>

//#define FILEIO
#define ll long long

using namespace std;

const int SZ = 100005;
const int LIM = 1000000000;
const double EPS = 1e-9;
const int MOD = 100000008;
const int INF = ( 1 << 30 ) - 1;
const double PI = 2 * acos( 0.0 );

template <class T> T MIN(T a, T b) { return (a < b) ? a : b; }
template <class T> T MAX(T a, T b) { return (a > b) ? a : b; }
template <class T> void SWAP(T &a, T &b) { T c; c = a; a = b; b = c; }
template <class T> T GCD(T a, T b) { T c; while(b > 0) { c = a % b; a = b; b = c; } return a; }

bool CMP(int a, int b)
{
    return (a > b);
}

void solve()
{
    ll n, a[SZ], dp[SZ];
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    dp[1] = 0;
    if(n > 1) dp[2] = abs(a[1] - a[2]);
    //if(n > 2) dp[3] = abs(a[2] - a[3]);
    for(int i = 3; i <= n; i++)
    {
        dp[i] = min(dp[i - 1] + abs(a[i] - a[i - 1]), dp[i - 2] + abs(a[i] - a[i - 2]));
    }
    cout << dp[n] << endl;
}

int main()
{
    #ifdef FILEIO
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int tc;

    //cin >> tc;
    //while(tc--)
    {
        solve();
    }

    return 0;
}




Measured memory_bytes: 5152
n=int(input())
a=list(map(int,input().split()))

dp=[[0]*(n) for i in range(n)]

if n%2!=0:
    for i in range(n):
        dp[i][i]=a[i]
else:
    for i in range(n):
        dp[i][i]=-a[i]
    

for i in range(n-1)[::-1]:
    for g in range(i,n):
        if (i+g)%2!=n%2:
            dp[i][g]=max(dp[i][g-1]+a[g],dp[i+1][g]+a[i])
        else:
            dp[i][g]=min(dp[i][g-1]-a[g],dp[i+1][g]-a[i])

print(dp[0][n-1])

Measured memory_bytes: 112732
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++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 UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const ll INF = 1000000000;

int main() {
    string s; cin >> s;
    s = s.substr(0,4);
    cout << (s=="YAKI" ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ

long long p[310000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%lld",p+i);
	long long ret=0;
	for(int i=0;i<60;i++){
		int A=0;
		for(int j=0;j<a;j++){
			if(p[j]&(1LL<<i))A++;
		}
		long long B=(long long)A*(a-A)%mod;
		ret=(ret+(1LL<<i)%mod*B)%mod;
	}
	ret%=mod;
	printf("%lld\n",ret);
}

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

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

    long long r, d, x;
    cin >> r >> d >> x;
    for(int i = 0; i < 10; i++){
        long long a = r * x - d;
        cout << a << endl;
        x = a; 
    }

    return 0;
}

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

ll gcd(ll a, ll b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return b ? gcd(b, a % b) : a;
}

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

int main(){
    ll a, b;
    cin >> a >> b;
    ll ans = lcm(a, b);
    cout << ans;
}

Measured memory_bytes: 256
s = input()
k = int(input())

if len(s) == 1:
    print(s)
elif len(set(s)) == 1:
    print(s[0])
else:
    t = s.replace('1','')
    if k < len(s) - len(t):
        print(1)
    else:
        print(t[0])

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

typedef long long lint;
#define REP(i, x, n) for(lint i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(lint i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const lint inv = MOD - 2;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

int solve(void){
    int n, m;
    cin >> n >> m;
    vector<int> di;
    for(int i = 1 ; i * i <= m ; i++){
        if(m % i == 0){
            di.push_back(i);
            di.push_back(m / i);
        }
    }
    SORT(di);
    int k = upper_bound(di.begin(), di.end(), m/n) - di.begin();
    k--;
    return di[k];
}

int main(){
    int ans = solve();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,a1,a2;
cin>>n>>m;
  vector<int> numk(m);
  int sum=0;
for(int i=0;i<m;i++){
  cin>>numk.at(i);
  sum+=numk.at(i);
}
  
if(sum<=n){
  sum=n-sum;
}else{
  sum = -1;
}
cout<<sum<<endl;
}

Measured memory_bytes: 3672
#解説放送見てからの書き直し
import sys
import os
INF = 10**12
ans = INF
N, M = map(int,input().split())
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
C = []
for i in range(M):
    a, b = map(int,input().split())
    A[i] = a  #鍵の金額
    B[i] = b  #開けられる宝箱の種類数
    tmp = list((map(int,input().split())))
    s = 0
    for j in range(b):
        t = tmp.pop(0)-1
        s |= 1 << t
    C.append(s)
    
dp = [INF]*(1<<N) #2^N
dp[0] = 0 #0 = 0b0000の時、スコアは0（まだ1つも鍵を購入してないので）

for s in range(1<<N): #1<<Nは2^N。つまりどの宝箱が開くかの全ての状態
    for j in range(M): # 全ての鍵について見ていく
        t = s | C[j] # 論理和。sには現在どの宝箱が開けられるかの状態、
                     # C[j]にはその新たな鍵が開ける宝箱。
                     # その論理和はこれまでの鍵と新たな鍵でどの宝箱が開けられるか
        cost = dp[s] + A[j] # その鍵を買った時のコスト
        dp[t] = min(dp[t],cost) #新たな宝箱の状態について、コストがより低くなるようなら保存する。
ans = dp[-1] #dp[-1]、つまり0b1111。宝箱が全て開けられる状態。
if ans == INF: #もし0b1111がINFのまま（最初から変わってない）ということはそこにたどり着けなかったということ。
               #つまり、全ての鍵を使っても宝箱を開けられなかった。
    ans = -1
print(ans)


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

int main() {
  long long N;
  vector<long long> d(5);
  cin >> N;
  for (int i = 0; i < 5; i++)
    cin >> d.at(i);

  long long min = LLONG_MAX;
  for (int i = 0; i < 5; i++) {
    if (d.at(i) < min) {
      min = d.at(i);
    }
  }

  if (min == 1) {
    cout << N / min + 4LL << endl;
  }
  else {
    cout << N / min + 5LL << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}
long long gcd(long long x,long long y){
	return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
	return x/gcd(x,y)*y;
}

int main(void){
	int n=in(),a[100],i,A=0,B=0;
	rep(i,n)a[i]=in();
	sort_r(a,n);
	for(i=0;i<n;i+=2)A+=a[i];
	for(i=1;i<n;i+=2)B+=a[i];
	print(A-B);
	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)


using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	cout << (b - a)*(b - a + 1) / 2 - b << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin >> s;
    if(s=="Sunny"){
        cout << "Cloudy" << endl;
    }else if(s=="Cloudy"){
        cout << "Rainy" << endl;
    } else {
        cout << "Sunny" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
    ll n, m; cin >> n >> m;
    vector<pair<ll,ll>> data(n);
    rep(i,n) cin >> data[i].first >> data[i].second;
    sort(all(data));
    vector<ll> a(n); rep(i,n) a[i] = data[i].first;
    
    ll ans = 0;
    ll save = 0;
    priority_queue<ll> pq;
    for(int i = 1; i <= m; i++){
        int k = upper_bound(all(a),i) - a.begin();
        for(int j = save; j < k; j++) pq.push(data[j].second);
        // 候補の追加
        if(!pq.empty()){
            ans += pq.top(); pq.pop();
        }
        // 最大のものを取り出す
        save = k;
    }
    cout << ans << endl;
}

Measured memory_bytes: 6604
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>

typedef long long int64;

int main(void) {
  const double PI = 3.14159265358979323846;
  int r;
  std::cin >> r;
  std::cout << 2 * PI * r << std::endl;
  return 0;
}


Measured memory_bytes: 3788
use std::io::prelude::*;

fn main() {
    let mut input_str = String::new();
    std::io::stdin().read_to_string(&mut input_str).unwrap();

    let input_parts = input_str.split_whitespace().collect::<Vec<_>>();
    let mut input_parts_it = input_parts.iter().cloned();

    let a: i64 = input_parts_it.next().unwrap().parse().unwrap();
    let b: i64 = input_parts_it.next().unwrap().parse().unwrap();

    let diff = b - a;

    if diff % 2 == 0 {
        println!("{}", a + diff / 2);
    } else {
        println!("IMPOSSIBLE");
    }
}


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

using namespace std;

typedef long long int ll;

#define FOR(i,l,r) for(i=l;i<r;i++)

#define REP(i,n) FOR(i,0,n)

#define ALL(x) x.begin(),x.end()

#define P pair<ll,ll>

#define F first

#define S second

signed main(){

  ll N,K,d,A,i,j,ans;cin>>N>>K;
  vector<bool>X(N,true);ans=N;
  REP(i,K){
    cin>>d;
    REP(j,d){
      cin>>A;
      if(X.at(A-1)){
        X.at(A-1)=false;ans--;
      }
    }
  }
  cout<<ans<<endl;

  return 0;

}

Measured memory_bytes: 3624
#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
        cout << "a > b" << endl;
    else if (a < b)
        cout << "a < b" << endl;
    else
        cout << "a == b" << endl;

   return 0;
}

Measured memory_bytes: 1156
#include<cstdio>
#include<algorithm>
using namespace std;
int T,k,n,a,b,c,d;
int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d%d%d",&a,&b,&c,&d);
		n=a+b;
		int l=0,r=n+1,mid,A,B;
		k=(max(a,b)-1)/(min(a,b)+1)+1;;
		while(l<r) {
			mid=(l+r)>>1;
			A=a-mid/(k+1)*k-mid%(k+1);
			B=b-mid/(k+1);
			if(B<=1ll*A*k)l=mid+1;
			else r=mid;
		}
		A=a-l/(k+1)*k-l%(k+1);
		B=b-l/(k+1);
		r=l+B-A*k+1;
		for(int i=c; i<=min(d,l); i++)putchar(i%(k+1)?'A':'B');
		for(int i=max(c,l+1); i<=d; i++)putchar((i-r)%(k+1)?'B':'A');
		puts("");
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string ans;
  string s;
  cin >> s;
  for(int i = 0;i<s.size();i++){//空文字列＝サイズが０の文字列
    if(s[i] == 'B'){
      if(ans.size() > 0) ans.pop_back();
    }
    else if(s[i] == '1'){
      ans.push_back('1');
    }
    else if(s[i] == '0'){
      ans.push_back('0');
    }
  }
  cout << ans << endl;
 }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,i,j,k,m;
int main(){
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;i++)
	for(j=0;j<=n;j++)
	if (i+j<=n){
		k=n-i-j;
		if (i*10000+j*5000+k*1000==m){
			printf("%d %d %d\n",i,j,k);
			return 0;
		}
	}
	puts("-1 -1 -1");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char** argv) {
  int h, n;
  int sum = 0;
  
  cin >> h >> n;
  for (int i=0; i < n; ++i) {
    int a_i;
    cin >> a_i;
    sum += a_i;
  }
  if (h <= sum)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3624
#include<iostream>
using namespace std;
int main(){
    char b;
    cin >> b;
    switch(b){
        case 'A':
            cout << 'T' << endl;
            break;
        case 'T':
            cout << 'A' << endl;
            break;
        case 'C':
            cout << 'G' << endl;
            break;
        case 'G':
            cout << 'C' << endl;
            break;
    }
    return 0;
}

Measured memory_bytes: 256
package main

import(
    "fmt"
)

func main() {
    var w, m, x, y int
    fmt.Scan(&w, &m, &x, &y)
    
    fmt.Print(float64(w)*float64(m)/2)
    fmt.Print(" ")
    if (w % 2 == 0 && x == w/2) && (m % 2 == 0 && y == m/2) {
        fmt.Println(1)
    }else {
        fmt.Println(0)
    }
}

Measured memory_bytes: 512
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 適当に根を決める
# 根から偶数回でも奇数回でも行ける点があれば，結局全部繋げる
# なければ，偶奇が異なるものだけ繋げる

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = LI()
A,B = LIR(M,2)

pt = edges_to_pt(A,B,N)

odd = [False]*N
even = [False]*N
even[0] = True

q = [0]
c = 1
flag = False
while q:
    q1 = []
    for v in q:
        for u in pt[v]:
            if c%2:
                if even[u]:
                    flag = True
                    break
                if not odd[u]:
                    odd[u] = True
                    q1.append(u)
            else:
                if odd[u]:
                    flag = True
                    break
                if not even[u]:
                    even[u] = True
                    q1.append(u)                
        if flag:
            break
    if flag:
        break
    q = q1
    c += 1

if flag:
    print(N*(N-1)//2 - M)
else:
    odds = 0
    evens = 0
    for i in range(N):
        if odd[i]:
            odds += 1
        else:
            evens += 1
    print(odds*evens - M)

Measured memory_bytes: 73308
#include <iostream>
#include <math.h>
using namespace std;

int main(){
	double d,e,res,a;
	while(1){
		cin >> d >> e;
		if(d == 0)break;
		res = 1e9;
		for(int i = 0;i <= d/2 + 1;i++){
			a = sqrt(i * i + (d - i) * (d - i));
			if(a < e){
				res = min(res, e - a);
			}	
			else{
				res = min(res, a - e);
			}
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 1284
#include<iostream>
#include<vector>
#include<math.h>
#include<string>
#include<queue>
#include<map>
#include <stdio.h>
#include<algorithm>
using namespace std;



  long long tmp[100010]={};

int main() {
  long long  n,l;
  cin >> n >> l;
  for(int i=0;i<n;i++){
    cin >>tmp[i];
  }
  int index=-1;
  for(int i=0;i<n-1;i++){
    if(tmp[i]+tmp[i+1]>=l){
      index =i;
      break;
    }
  }

  if(index>=0){
    cout << "Possible"<<endl;
    for(int i=0;i<index;i++){
      cout << i+1 << endl;
    }
    for(int i=n-2;i>index;i--){
      cout << i+1<<endl;
    }
    cout << index+1<<endl;
  }else{
    cout << "Impossible"<<endl;
  }
  return 0;
}



Measured memory_bytes: 1536
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

int main() {
  while(1){
    int t,n;
    cin>>t>>n;
    if(!t)break;
    vector<vector<int>> m(121,vector<int>(121));
    vector<vector<int>::iterator> vitr(121);
    REP(i,121) vitr[i] = begin(m[i]) + 60;
    auto grid = begin(vitr) + 60;
    REP(i,n){
      int x,y;
      cin>>x>>y;
      grid[x][y] = 1;
    }
    int sx,sy;
    cin>>sx>>sy;
    set<tuple<int,int>> vis;
    vis.insert(make_tuple(sx,sy));
    queue<tuple<int,int,int>> q;
    q.push(make_tuple(0,sx,sy));
    while(!q.empty()){
      int i,j,d;
      tie(d,i,j) = q.front();q.pop();
      if(d==t)continue;
      int di[] = {1,1,0,-1,-1,0};
      int dj[] = {1,0,-1,-1,0,1};
      REP(k,6){
        int ni=i+di[k];
        int nj=j+dj[k];
        if(grid[ni][nj] == 1) continue;
        if(vis.find(make_tuple(ni,nj)) != end(vis))continue;
        vis.insert(make_tuple(ni,nj));
        q.push(make_tuple(d+1,ni,nj));
      }
    }
    cout << vis.size() << endl;
  }
  return 0;
}

Measured memory_bytes: 1408
#include <iostream>
typedef long long ll;
using namespace std;

ll s[100010], mod=1000000007, dp[100010][2];
int ngdist[100010][2];

int main() {
	int N;
	ll A[2];
	cin >> N >> A[0] >> A[1];
	s[0]=(-1e18)-100;
	for(int i=1; i<=N; ++i) cin >> s[i];
	for(int t=0; t<2; ++t){
		ngdist[0][t]=0;
		for(int i=1; i<=N; ++i){
			ngdist[i][t]=ngdist[i-1][t];
			if(s[i]-s[i-1]<A[t]) ++ngdist[i][t];
		}
	}
	dp[0][0]=1;
	dp[0][1]=0;
	int now[2]={0, 0};
	for(int i=1; i<=N; ++i){
		for(int t=0; t<2; ++t){
			while(s[i]-s[now[t]]>=A[t] && now[t]<i) ++now[t];
			if(now[t]==i) dp[i][t]=(dp[i-1][t]+dp[i-1][1-t])%mod;
			else if(ngdist[i-1][1-t]==ngdist[now[t]][1-t]) dp[i][t]=dp[now[t]][1-t];
			else dp[i][t]=0;
		}
	}
	cout << (dp[N][0]+dp[N][1])%mod << endl;
	return 0;
}

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


int main(void){
  int n,d; cin >> n >> d;
  if(n%(2*d + 1) == 0) cout << n/(2*d+1) << endl;
  else cout << n/(2*d + 1) + 1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
//vector<vector<ll>> data(3, vector<ll>(4));
//vector<ll> data(N);
//str s = to_string(i);
//int i = c - '0'
//sort(data.begin(), data.end());
//reverse(data.begin(), data.end());
//data.erase(unique(data.begin(), data.end()), data.end());
//str.substr(n)//n番以降スライス
//str.substr(n,m)//n番以降m文字スライス
//str.erase(n)//n番以降削除
//str.erase(n,m)//n番以降m文字削除
typedef long long ll;
#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=ll(a);i<ll(b);i++)
#define FORD(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define PB push_back
#define MOD 1000000007
using namespace std;

int main() {
	ll N;
	cin >> N;

	vector<ll> data(N+1);
	data.at(0) = 1;
	data.at(1) = 0;
	if (N >= 2) data.at(2) = 0;
	if (N >= 3) {
		FOR(i, 3, N + 1) {
			data.at(i) = data.at(i - 1) + data.at(i - 3);
			data.at(i) %= MOD;
		}
	}
	if (data.at(N) % MOD >= 0) data.at(N) = data.at(N) % MOD;
	else data.at(N) = data.at(N) % MOD + MOD;
	cout << data.at(N) << endl;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  vector<int> V(N);
  for(int i=0;i<N;i++)
    cin>>V.at(i);
  vector<int> C(N);
  for(int i=0;i<N;i++)
    cin>>C.at(i);
  int sum=0;
  for(int i=0;i<N;i++)
    if(C.at(i)<V.at(i))
      sum+=V.at(i)-C.at(i);
  
  cout<<sum<<endl;
   return 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(unused_mut)]
use crate::rust::library::data_structure::{union_find};
use crate::rust::library::math::{mod_int};
use crate::rust::library::util::io::*;
use itertools::*;

fn main() {
    input!{
        s:bytes,
        t:bytes,
    }
    
    println!("{}",s.windows(t.len()).map(|s|zip(s,&t).filter(|&(s,t)|s!=t).count()).min().unwrap());
}




pub mod rust {

pub mod library {

pub mod data_structure {

pub mod union_find {

pub struct UF{
    par:Vec<usize>,
    rank:Vec<usize>,
}
impl UF{
    pub fn new(n:usize)->UF{
        let mut v=vec![0;n];
        for i in 0..n{
            v[i]=i;
        }
        UF{
            par:v,
            rank:vec![1;n],
        }
    }
    pub fn root(&mut self,x:usize)->usize{
        if x==self.par[x]{
            x
        }else{
            let par=self.par[x];
            let res=self.root(par);
            self.par[x]=res;
            res
        }
    }
    pub fn same(&mut self,a:usize,b:usize)->bool{
        self.root(a)==self.root(b)
    }
    pub fn unite(&mut self,a:usize,b:usize)->bool{
        let ap=self.root(a);
        let bp=self.root(b);
        if ap==bp{
            return false;
        }
        if self.rank[ap]<self.rank[bp]{
            self.par[bp]=ap;
            self.rank[ap]+=self.rank[bp];
        }else{
            self.par[ap]=bp;
            self.rank[bp]+=self.rank[ap];
        }
        return true;
    }
    pub fn size(&mut self,a:usize)->usize{
        let ap=self.root(a);
        self.rank[ap]
    }
}

}  // mod union_find

}  // mod data_structure

pub mod math {

pub mod mod_int {

pub fn hello(){
    println!("hello");
}

}  // mod mod_int

}  // mod math

pub mod util {

pub mod io {

#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export] 
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export] 
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    
    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

}  // mod io

}  // mod util

}  // mod library

}  // mod rust



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

int main(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	
	for(int i=0; i<s.size(); i++){
		s[i] = s[i]+n;
		if(s[i]-0>90) s[i]=s[i]-26;
	}
	cout << s << endl;
}

Measured memory_bytes: 256
N = int(input())
p = list(map(int, input().split()))
P = list(range(1,N+1))
if p == P:
    print('YES')
    exit()

tmp = [i for i in range(N) if P[i] - p[i] != 0]
#print(tmp)

if len(tmp) != 2:
    print('NO')
else:
    p[tmp[0]], p[tmp[1]] = p[tmp[1]], p[tmp[0]]
    if p == P:
        print('YES')
    else:
        print('NO')


Measured memory_bytes: 3064
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int a,b,c; cin>>a>>b>>c;
    if(b>=a*c) cout<<c;
    else cout<<b/a;
    return 0;
}

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

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=1e6+7;
const int mod=1e9+7;

int a,b,c,d;
LL ans;
int main()
{
    cin>>a>>b>>c>>d;
    ans=min(b,d)-max(a,c);
    if(ans<0) ans=0;
    cout<<ans<<'\n';
    return 0;
}
/*
3 5
5
1 2 3 4 5
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=1000005;
const int mo=1000000007;
int fac[N],inv[N];
int f[N][3],Inv[N];
int n,ans;
void init(){
	fac[0]=inv[0]=inv[1]=Inv[0]=1;
	For(i,2,N-1) inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;
	For(i,1,N-1) Inv[i]=1ll*Inv[i-1]*inv[i]%mo;
	For(i,1,N-1) fac[i]=1ll*fac[i-1]*i%mo;
}
int C(int x,int y){
	if (x<0||y<0||y>x) return 0;
	return 1ll*fac[x]*Inv[y]%mo*Inv[x-y]%mo;
}
int main(){
	init();
	scanf("%d",&n);
	f[0][0]=1;
	For(i,1,n) For(j,0,2) For(k,0,2)
		if (j!=k) f[i][k]=(f[i][k]+f[i-1][j])%mo;
	For(i,1,n){
		int val=1ll*inv[n]*inv[i]%mo;
		ans=(ans+1ll*f[i][1]*C(n,i)%mo*val)%mo;
	}
	For(i,1,n) ans=1ll*(mo+1)/3*ans%mo;
	printf("%d",ans);
}

Measured memory_bytes: 23680
#include <stdio.h>
#define MAX 100

int A[MAX][MAX],i,j;

void MST(int n){
    int a=1,size,min,B[MAX],C[MAX],sum=0;
    C[0]=0;
    B[0]=1;
    for(i=1;i<n;i++) B[i]=0;
    
    while(3){
        size=2001;
        for(i=0;i<a;i++){
            for(j=0;j<n;j++){
                if(A[C[i]][j]<size && A[C[i]][j]!=-1 && B[j]!=1){
                    size=A[C[i]][j];
                    min=j;
                }
            }
        }      
        if(a!=n){
            C[a]=min;
            B[min]=1;
            sum+=size;
            a++;
        }
        else break;
    }
    printf("%d\n",sum);
}

int main(){
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++) scanf("%d",&A[i][j]);
    }
    MST(n);

    return 0;
}


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

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define fio ios_base::sync_with_stdio(false)
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  int  arr[n];
  for(int i=0;i<n;i++)
  cin>>arr[i];
  sort(arr,arr+n);
  int i=0;
ll res=0;
  while(i<k){
    res+=arr[i++];
  }
  cout<<res;
  }


Measured memory_bytes: 3640
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		int n=in.nextInt();
		long [] arr=new long[n];
		long x=0;
		for(int i=0;i<n;i++){
			arr[i]=in.nextInt();
			x=(x^arr[i]);
		}
		for(int i=0;i<n;i++){
			System.out.print((x^arr[i])+" ");
		}
	}
}

Measured memory_bytes: 63076
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
 
#define barsik ios::sync_with_stdio(false)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
typedef long long ll;
typedef std::vector<int> vi;
typedef std::pair <int, int> pii;
typedef std::unordered_set <int> u_si;
const double PI = acos(-1);
const long double EPS = 1e-9;
using namespace std;


void solve(){
    int n;
    cin >> n;
    
    // l <= j < r
    int l = 0;
    int r = n + 1;
    while(r - l > 1){
        int mid = l + (r - l) / 2;
        if(mid * 1ll * mid <= 1ll * n) l = mid;
        else r = mid;
    }
    cout << l * l;
    
}
int main(){
    int q = 1;
    //cin >> q;}
    while(q--) solve();
}


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

int main() {
  int n;cin>>n;
  set<string> st;
  rep(i,n){
    string s;cin>>s;
    st.insert(s);
  }
  int ans=st.size();
  cout<<ans<<endl;
}

Measured memory_bytes: 19204