akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  vector<string> result;
  string a, b;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a >> b;
    if (a.size() > 80 || b.size() > 80) {
      result.push_back("overflow");
      continue;
    }

    int carry = 0;
    if (a.size() < b.size())
      a.swap(b);
    string::reverse_iterator ria = a.rbegin();
    string::reverse_iterator rib = b.rbegin();

    while (true) {
      if (*ria - '0' + *rib - '0' + carry >= 10) {
        *ria += *rib + carry - '0' - 10;
        carry = 1;
      } else {
        *ria += *rib + carry - '0';
        carry = 0;
      }
      ria++;
      rib++;
      if (rib == b.rend())
        break;
    }
    /*                                                                                                                                                                                                                                                         
    cout << a << endl;                                                                                                                                                                                                                                         
    cout << carry << endl;                                                                                                                                                                                                                                     
    */
    while (true) {
      if (carry && ria == a.rend())
        a.insert(0, "1");
      else if (carry)
        if (*ria - '0' + 1 >= 10) {
          *ria += carry - 10;
          carry = 1;
        } else {
          *ria += 1;
          carry = 0;
          break;
        }
      else
        break;
      ria++;
    }
    if (a.size() > 80)
      result.push_back("overflow");
    else
      result.push_back(a);
  }

  for (int i = 0; i < result.size(); i++)
    cout << result[i] << endl;
  return 0;
}

Measured memory_bytes: 1228
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        n: usize,
        x: [u64; n],
    }

    let mut x_sorted = x.clone();
    x_sorted.sort();
    for i in 0..n {
        if x[i] >= x_sorted[n / 2] {
            println!("{}", x_sorted[n / 2 - 1]);
        } else {
            println!("{}", x_sorted[n / 2]);
        }
    }
}


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

int main() {
  int N, u, k, v;
  int A[100][100];

  for (int i = 0; i < 100; ++i) {
    for (int j = 0; j < 100; ++j) {
      A[i][j] = 0;
    }
  }

  cin >> N;

  for (int i = 0; i < N; ++i) {
    cin >> u >> k;
    for (int j = 0; j < k; ++j) {
      cin >> v;
      A[u - 1][v - 1] = 1;
    }
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (j > 0) {
        cout << " ";
      }
      cout << A[i][j];
    }
    cout << endl;
  }

  return 0;
}



Measured memory_bytes: 3128
int main(void){
    int n;
    char s1[100],s2[100],s[200];
    scanf("%d",&n);
    scanf("%s",s1);
    scanf("%s",s2);
    int i,j=0;
    for(i=0;i<n;i++){
        s[j]=s1[i];
        s[j+1]=s2[i];
        j+=2;
    }
    s[j]='\0';
    printf("%s\n",s);
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

class Main {
  public static void main(String... args) {
    Scanner sc = new Scanner(System.in);
    int size = sc.nextInt();
    int[][] graph = new int[size+1][size+1];

    for (int i = 1; i <= size; i++) {
      for (int j = 1; j <= size; j++) {
        graph[i][j] = 0;
      }
    }

    int addr;
    int time;
    for (int i = 0; i < size; i++) {
      addr = sc.nextInt();
      time = sc.nextInt();
      for (int j = 0; j < time; j++) {
        graph[addr][sc.nextInt()] = 1;
      }
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= size; i++) {
      for (int j = 1; j <= size; j++) {
        sb.append(graph[i][j]).append(' ');
      }
      System.out.println(sb.deleteCharAt(sb.length() - 1));
      sb.setLength(0);
    }
  }
}



Measured memory_bytes: 30536
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <climits>
#include <sstream>

using namespace std;

int main(){
    int a, b, c, ans=0;

    cin >> a >> b >> c;

    if(a == b && b == c) ans = 1;
    else if(a == b && a != c) ans = 2;
    else if(a == c && a != b) ans = 2;
    else if(b == c && b != a) ans = 2;
    else ans = 3;

    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, m, c;
  cin >> n >> m >> c;
  vl b(m);
  rep(i, m) cin >> b[i];
  ll ans = 0;
  rep(i, n) {
    ll now = c;
    rep(j, m) {
      ll a;
      cin >> a;
      now += a * b[j];
    }
    if(now > 0) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3584
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line[] = scanner.nextLine().split(" ", -1);
        int A = Integer.parseInt(line[0]);
        int B = Integer.parseInt(line[1]);
        int K = Integer.parseInt(line[2]);

        for (int i = 0; i < K; i++) {
            if (i % 2 == 0) {
                // turn A
                if (A % 2 != 0) {
                    A--;
                }
                int giveA = A / 2;
                A -= giveA;
                B += giveA;
            } else {
                // turn B
                if (B % 2 != 0) {
                    B--;
                }
                int giveB = B / 2;
                A += giveB;
                B -= giveB;
            }
        }

        System.out.print(A);
        System.out.print(" ");
        System.out.println(B);
    }
}


Measured memory_bytes: 21716
l=map(str,raw_input().split())
ans=[]
for i in l:
    if 'peach' in i:
        ans.append(i.replace('peach','apple'))
    elif 'apple' in i:
        ans.append(i.replace('apple','peach'))
    else:
        ans.append(i)
print ' '.join(ans)

Measured memory_bytes: 6236
import java.util.*;
import java.lang.*;

public class Main {
    static final int INF = (1 << 31) - 1;             
    static final int MAXN = 111111; 
    
    public static void main(String[] args) throws Exception {                
        Scanner input = new Scanner(System.in);
        int n, q;
        n = input.nextInt();
        q = input.nextInt();        
        int[] it = new int[n * 5];
        for (int i = 0; i < n * 5; ++i) it[i] = (1 << 31) - 1;
        for (int i = 0; i < q; ++i) {
            int op = input.nextInt();
            if (op == 0) {
                int u, x;
                u = input.nextInt();
                x = input.nextInt();
                update(1, 0, n - 1, u, x, it);
            } else {
                int u, v;
                u = input.nextInt();
                v = input.nextInt();
                System.out.println(get(1, 0, n - 1, u, v, it));                
            }
        }
    }                  
    
    static void update(int seg, int lo, int hi, int x, int g, int[] it) {
        if (x < lo || x > hi) return;
        if (x == lo && hi == x) {            
            it[seg] = g;
            return;
        }
        int mid = (lo + hi) / 2;
        update(seg * 2, lo, mid, x, g, it);
        update(seg * 2 + 1, mid + 1, hi, x, g, it);
        it[seg] = Math.min(it[seg * 2], it[seg * 2 + 1]);
    }
    
    static int get(int seg, int lo, int hi, int u, int v, int[] it) {
        //System.out.println(lo + " " + hi + " " + u + " " + v);
        if (v < lo || hi < u) return INF;
        if (u <= lo && hi <= v) return it[seg];
        int mid = (lo + hi) / 2;
        int min1 = get(seg * 2, lo, mid, u, Math.min(v, mid), it);
        int min2 = get(seg * 2 + 1, mid + 1, hi, Math.max(u, mid + 1), v, it);
        return Math.min(min1, min2);
    }
}

Measured memory_bytes: 101268
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<iomanip>
#include<stack>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define sz(a) (int)a.size()
using namespace std;

int main() {
	double a, b, h, m;
	double pi = acos(-1);
	cin >> a >> b >> h >> m;
	double dif = abs((double)6 * m - (double)30 * h - 0.5 * m);
	cout << fixed << setprecision(12) << sqrt((b-a*cos(pi*dif/(double)180))*(b-a*cos(pi*dif/(double)180))+a*a*sin(pi*dif/(double)180)*sin(pi*dif/(double)180)) << endl;
}

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

#define DEBUG 0

#if DEBUG
  #define DLOG(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DLOG(...)
#endif

void debug(auto f) {
#if DEBUG
  f();
#endif
}

ll K;
vector<ll> ans;

ll colS(ll x) {
  ll s = 0;
  while (x > 0) {
    s += x % 10;
    x = x / 10;
  }
  return s;
}

ll seq9(ll k, ll n) {
  ll t = 1;
  for (ll i = 0; i < n; i++) {
    t *= 10;
  }
  return (k+1) * t - 1;
}

int main() {
#if !DEBUG
  ios_base::sync_with_stdio(false);
#endif

  cin >> K;
  for (ll i = 1; i <= 9; i++)  ans.push_back(i);
  ll z = 9;
  ll n = 1;
  ll k = 1;
  while (z < K) {
    while (k - colS(k) <= 9 * n - 1) {
      ans.push_back(seq9(k, n));
      k++;
      z++;
    }
    n += 1;
    k /= 10;
  }
  for (ll w = 0; w < K; w++) {
    cout << ans.at(w) << "\n";
  }

  return 0;
}



Measured memory_bytes: 256
// Problem Code: abc172_d

#include <iostream>

using namespace std;

long long sum_of_divisors(int N) {
	long long res = 0;
	for (int i = 1; i <= N; i++) {
		long long f = N / i;
		res += i * f * (f + 1) / 2;
	}
	return res;
}

int main() {
	int N;
	cin >> N;
	cout << sum_of_divisors(N);
	return 0;
}

Measured memory_bytes: 3564
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TEMPAtCoder2
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = System.Console.ReadLine();

            int cnt = chk(S);
            System.Console.WriteLine(cnt);               
                            

        }

        static int chk(string s)
        {

            int cnt = 0;

            int cnt01 = 0;
            int cnt10 = 0;

            int N = s.Length;

            char carrentval01 = '0';
            char carrentval10 = '1';

            for(int i = 0; i < N; ++i)
            {
                if(s[i] != carrentval01)
                {
                    cnt01++;
                }
                carrentval01 = carrentval01 == '0' ? '1' : '0';
                if (s[i] != carrentval10)
                {
                    cnt10++;
                }
                carrentval10 = carrentval10 == '0' ? '1' : '0';

            }

            cnt = cnt10 < cnt01 ? cnt10 : cnt01;

            return cnt;
        }
    }
}


Measured memory_bytes: 13116
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <iomanip>
using namespace std;

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

int main() {
    int a;
    string s;
    cin >> a;
    cin >> s;
    if(a >= 3200) {
        cout << s << endl;
    }else {
        cout << "red" << endl;
    }

    return 0;
}

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

void main_()
{
    string s, t;
    cin >> s >> t;
    sort(begin(s), end(s));
    sort(begin(t), end(t), greater<char>());
    cout << (s < t ? "Yes" : "No") << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 256
s=input()

a=True
for i in range(0,len(s),2):
    if s[i] == 'L':
        a=False
        
b=True
for i in range(1,len(s),2):
    if s[i] == 'R':
        b=False        
        
if a and b:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


ll N,C;

bool is_ok(ll num){

	stack<ll> S;

	while(num > 0){
		S.push(num%10);
		num /= 10;
	}

	int index = 0;
	ll array[22];

	while(!S.empty()){
		array[index++] = S.top();
		S.pop();
	}

	if(array[N] != C){
		return false;
	}

	for(int i = 0; i < index/2; i++){
		if(array[i] != array[index-1-i]){
			return false;
		}
	}
	return true;
}


int main(){

	scanf("%lld %lld",&N,&C);

	if(C < 0){
		if(N == 1){
			printf("11\n");
		}else{
			for(ll i = 0; i < 2*N; i++){
				printf("9");
			}
			printf("\n");
		}
		return 0;
	}

	ll num = 0;
	for(ll i = 0; i < N; i++){
		num = 10*num+9;
	}
	num = 10*num+C;
	for(ll i = 0; i < N; i++){
		num = 10*num+9;
	}

	bool FLG;

	while(true){
		if(is_ok(num)){
			if(num%2 != 0){
				FLG = true;
				for(int i = 3; i*i <= num; i += 2){
					if(num%i == 0){
						FLG = false;
						break;
					}
				}
				if(FLG){
					printf("%lld\n",num);
					return 0;
				}
			}
		}
		num--;
	}
	return 0;
}



Measured memory_bytes: 3184
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
	int y,m,d;
} koiwaikotori;

typedef struct {
	char asumikana[64];
	char murakawarie[64];
	koiwaikotori sakuraayane;
} nadukakaori;

typedef struct {
	char asumikana[64];
	char murakawarie[64];
	koiwaikotori sintaniryouko;
	koiwaikotori fukuennmisato;
} horieyui;

void kitamuraeri(nadukakaori* sintasu) {
	if(scanf("%s%s%d/%d/%d",sintasu->asumikana,sintasu->murakawarie,
			 &sintasu->sakuraayane.y,&sintasu->sakuraayane.m,&sintasu->sakuraayane.d)!=5)exit(1);
}

void kugimiyarie(horieyui* asumisu) {
	char mizuhasikaori[64];
	if(scanf("%s%s",asumisu->asumikana,asumisu->murakawarie)!=2)exit(1);
	if(scanf("%s",mizuhasikaori)!=1)exit(1);
	if(mizuhasikaori[0]=='*') {
		asumisu->sintaniryouko.y=asumisu->sintaniryouko.m=asumisu->sintaniryouko.d=-1;
	} else {
		if(sscanf(mizuhasikaori,"%d/%d/%d",
				  &asumisu->sintaniryouko.y,&asumisu->sintaniryouko.m,&asumisu->sintaniryouko.d)!=3)exit(1);
	}
	if(scanf("%s",mizuhasikaori)!=1)exit(1);
	if(mizuhasikaori[0]=='*') {
		asumisu->fukuennmisato.y=asumisu->fukuennmisato.m=asumisu->fukuennmisato.d=-1;
	} else {
		if(sscanf(mizuhasikaori,"%d/%d/%d",
				  &asumisu->fukuennmisato.y,&asumisu->fukuennmisato.m,&asumisu->fukuennmisato.d)!=3)exit(1);
	}
}

int tomatuharuka(const koiwaikotori* miyanomamoru,const koiwaikotori* hanazawakana) {
	if(miyanomamoru->y > hanazawakana->y) return 1;
	if(miyanomamoru->y < hanazawakana->y) return -1;
	if(miyanomamoru->m > hanazawakana->m) return 1;
	if(miyanomamoru->m < hanazawakana->m) return -1;
	if(miyanomamoru->d > hanazawakana->d) return 1;
	if(miyanomamoru->d < hanazawakana->d) return -1;
	return 0;
}

int maenotomoaki(const nadukakaori* yukana, const horieyui* satourina) {
	if(satourina->asumikana[0]!='*' && strstr(yukana->asumikana,satourina->asumikana)==NULL)return 0;
	if(satourina->murakawarie[0]!='*' && strstr(yukana->murakawarie,satourina->murakawarie)==NULL)return 0;
	if(satourina->sintaniryouko.y>=0) {
		if(tomatuharuka(&yukana->sakuraayane,&satourina->sintaniryouko)<0)return 0;
	}
	if(satourina->fukuennmisato.y>=0) {
		if(tomatuharuka(&satourina->fukuennmisato,&yukana->sakuraayane)<0)return 0;
	}
	return 1;
}

int main(void) {
	int haradahitomi,tamurayukari;
	nadukakaori simonohiro[100];
	horieyui tangesakura;
	int mimorisuzuko,tokuisora;
	if(scanf("%d",&haradahitomi)!=1)return 1;
	for(mimorisuzuko=0;mimorisuzuko<haradahitomi;mimorisuzuko++) {
		kitamuraeri(&simonohiro[mimorisuzuko]);
	}
	if(scanf("%d",&tamurayukari)!=1)return 1;
	for(mimorisuzuko=0;mimorisuzuko<tamurayukari;mimorisuzuko++) {
		if(mimorisuzuko>0)putchar('\n');
		kugimiyarie(&tangesakura);
		for(tokuisora=0;tokuisora<haradahitomi;tokuisora++) {
			if(maenotomoaki(&simonohiro[tokuisora],&tangesakura)) {
				puts(simonohiro[tokuisora].asumikana);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 632
#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);
#define ADD +
#define SUBTRACT -
#define MULTIPLY *
#define DIVIDE /
#define MOD %
#define INCREMENT(x) ++x
#define DECREMENT(x) --x
#define in(a,b) cin>>a>>b;
#define out(a,b) cout<<a<<endl<<b<<endl;
#define scan(a) scanf("%d",&a);
#define print(a) printf("%d\n",a);
#define scanii(a,b) scanf("%d %d",&a,&b);
#define printii(a,b) printf("%d\n%d\n",a,b);
#define scaniii(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define ll long long
#define ull unsigned long long
#define sll signed long long
#define pi acos(-1)
#define mod 1000000007
#define TRUE 1
#define FALSE 0
#define ZERO 0
#define MP make_pair
#define F first
#define S second
#define f1(i,a) for(int i=0;i<a;++i)
#define f2(i,a) for(int i=a-1;i>=0;--i)
#define en puts("");
#define elif else if
typedef ll int lli;
typedef sll int slli;
typedef ull int ulli;
const int sz=10000;
using namespace std;

int clue();
int result();
void show();
bool check(int n) {
    for(int i=2;i*i<=n;++i) {
        if(n%i==0)
        return false;
    }
    return true;
}


// bool cmp(pair<int,int>p,pair<int,int>q) {
//     // return p.first>q.first;//descending by first
//     // return p.first<q.first;//ascending by first
//     // return p.second>q.second;//descending by second
//     return p.second<q.second;//ascending by second
// }

bool cmp(int p,int q) {
    return p>q;//descending
    // return p<q;//ascending
}


int main() {

    int t;
    // cin>>t;
    t=1;
    while(t-->0) {
        clue();
    }

    return 0;
}
int clue() {

    string s;
    cin>>s;
    int n=s.size();
    int det=0;

    f1(i,n) {
        int x=i+1;
        if(x%2==0) {
            if(s[i]=='R')++det;
        }
        else
        {
            if(s[i]=='L')++det;
        }
    }
    (!det)?cout<<"Yes"<<endl:cout<<"No"<<endl;
    
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

namespace INPUT{
	const int L=1<<15;
	char _buf[L],*S,*T,c;
	char _gc(){
		if(S==T){
			T=(S=_buf)+fread(_buf,1,L,stdin);
			if(S==T) return EOF;
		}
		return *S++;
	}
	void readi(int &X){
		for(c=_gc();c<'0'||c>'9';c=_gc());X=c&15;
		for(c=_gc();c>='0'&&c<='9';X=X*10+(c&15),c=_gc());
	}
}
using INPUT::readi;

const int LI=2E5;
const int Maxn=4E5+5;

int N,Q;
int a[Maxn];
int p[Maxn];
int d[Maxn];
int Ans;

int main(){
	readi(N),readi(Q);
	for(int i=1;i<=N;++i)
		readi(a[i]),a[i]+=LI,++p[a[i]];
	for(int i=LI+1;i<=LI+N;++i)
		for(int j=i;j>i-p[i];--j) ++d[j];
	for(int i=LI+1;i<=LI+N;++i)
		Ans+=(d[i]==0);
	while(Q--){
		int x,y;
		readi(x),readi(y),y+=LI;
		int pos=a[x]-p[a[x]]+1;
		--p[a[x]],--d[pos];
		Ans+=(d[pos]==0&&pos>LI);
		pos=y-p[y];
		++p[y],++d[pos];
		Ans-=(d[pos]==1&&pos>LI);
		a[x]=y;
		//Ans+=(d[pos1]==0&&tmp1>0&&pos1>LI);
		//Ans-=(d[pos2]>0&&tmp2==0&&pos2>LI);
		//for(int i=1;i<=N;++i) cerr<<a[i]-LI<<' ';cerr<<endl;
		//for(int i=LI+1;i<=LI+N;++i) cerr<<d[i]<<' ';cerr<<endl;
		//Ans=0;
		//for(int i=LI+1;i<=LI+N;++i)
		//	Ans+=(d[i]==0);
		printf("%d\n",Ans);
	}
	return 0;
}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
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; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

ll dp(ll l,ll r,vector<vector<ll>>&dpv,ll &n,vector<ll>&a){
  if(dpv[l][r]!=-INF)return dpv[l][r];
  if(l==r)return dpv[l][r]=0;

  if((r-l)%2==n%2){
    return dpv[l][r]=max(dp(l+1,r,dpv,n,a)+a[l],dp(l,r-1,dpv,n,a)+a[r-1]);
  }else{
    return dpv[l][r]=min(dp(l+1,r,dpv,n,a)-a[l],dp(l,r-1,dpv,n,a)-a[r-1]);
  }
}

bool solve(){
  ll n;cin>>n;
  vector<ll>a(n);
  rep(i,n)cin>>a[i];

  vector<vector<ll>>dpv(n+1,vector<ll>(n+1,-INF));

  function<ll(int,int)> dp=[&](int l,int r){
    if(dpv[l][r]!=-INF)return dpv[l][r];
    if(l==r)return dpv[l][r]=0;

    if((r-l)%2==n%2){
      return dpv[l][r]=max(dp(l+1,r)+a[l],dp(l,r-1)+a[r-1]);
    }else{
      return dpv[l][r]=min(dp(l+1,r)-a[l],dp(l,r-1)-a[r-1]);
    }
  };
  cout<<dp(0,n)<<endl;

  return false;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(30);
  solve();
}


Measured memory_bytes: 71040
import java.util.*;

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

    String check = "";
    int todot = 0;
    int current;
    int min;

    for (int i=0; i<n; i++) {
      check = s.substring(i,i+1);
      if (check.equals(".")) {
        todot++;
      }
    }
    
    current = todot;
    min = todot;
    
	for (int i=0; i<n; i++) {
      check = s.substring(i,i+1);
      if (check.equals(".")) {
        current--;
      } else {
        current++;
      }
      if (current < min) {
        min = current;
      }
    }
    
    System.out.println(min);
  }
}


Measured memory_bytes: 42504
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int N,X,T;
    cin >> N >> X >> T;

    if(N % X == 0){
      cout << N / X * T << endl;
      return 0;
    } else {
      cout << ((N / X) + 1 ) * T << endl;
    }
}

Measured memory_bytes: 3628
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int x = in();
    cout << 3 * x * x << endl;
    return 0;
}


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

using namespace std;

int main()
{
    string S;
    cin >> S;
    vector<bool> ch(26, false);
    for (int i = 0; i < S.size(); ++i){
        ch[S[i]-'a'] = true;
    }
    for (int i = 0; i < ch.size(); ++i){
        if(ch[i]==false){
            cout << (char)('a' + i) << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll mod=1e9;

int main(){
  int a,b;
  cin>>a>>b;
  if (a<10&& b<10){
    cout << a*b << endl;
  }else{
    cout << "-1" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <cctype>
#include <map>
#include <stdio.h>
#include <string.h>


#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long
#define FOR(i,l,r) for(size_t i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

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

    int n;
    string tmp;
    map<string,int> mp;
    mp["AC"] = 0;
    mp["WA"] = 0;
    mp["TLE"] = 0;
    mp["RE"] = 0;

    cin >> n;
    REP(i,n){
        cin >> tmp;
        mp[tmp] ++;
    }

    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] ;

    return 0;
}









Measured memory_bytes: 3664
#include<bits/stdc++.h>
#define int long long
const int inf=1145141919ll;
const int mod=1000000007ll;
const int dd[]={0,-1,0,1,0};
using namespace std;
int a,b,c,d;
int p[114514],q[114514];
signed main(){
	int i,j;
	cin>>a>>b;
	for(i=0;i<a;i++)
		cin>>p[i];
	q[0]=1;
	for(i=0;i<a;i++){
		for(j=99999;j>=0;j--)
			if(j+p[i]<100000)
				q[j+p[i]]+=q[j];
	}
	int r[2]={};
	for(i=0;i<100000;i++)
		r[i%2]+=q[i];
	cout<<r[b]<<endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"

using namespace std;

#define COUNTOF(array) (sizeof(array) / sizeof(array[0]))
#define OUT(P) cout << (P) << endl
#define OUT2(P1, P2) cout << (P1) << " " << (P2) << endl
#define PRINT_ARRAY(P) for(int i=0; i<P.size(); i++) cout << P[i] << endl;
#define PRINT_ARRAY_INLINE(P) do { for(int i=0; i<P.size(); i++) cout << P[i] << " "; cout << endl; } while(0)
#define PRINT_ARRAY_WITH_LABEL(L, P) do { cout << L << ": "; PRINT_ARRAY_INLINE(P); cout << endl; } while(0)
typedef long long ll;

int sum_digits(int num);
template <class T>
vector<T> copy_vector(vector<T> vec);
int gcd(int a, int b);

#define RED '0'
#define BLUE '1'

int main() {
    string s;
    cin >> s;
    
    int n = s.size();
    int count = 0;
    int stacked_red = 0;
    int stacked_blue = 0;
    for(int i=0; i<n; i++) {
        if(s[i] == RED) {
            if(stacked_blue > 0) {
                stacked_blue--;
                count+=2;
            } else {
                stacked_red++;
            } 
        } else { // BLUEのとき
            if(stacked_red > 0) {
                stacked_red--;
                count+=2;
            } else {
                stacked_blue++;
            } 
        }
    }
    cout << count << endl;

    return 0;
}

/******************************/
/***** DECRARED FUNCTIONS *****/
/******************************/

int sum_digits(int num) {
    int rtn = 0;
    while(num != 0) {
        int tmp = num % 10; 
        rtn += tmp;
        num /= 10; 
    }   
    return rtn;
}
//int sum_digits(int num) {
//    int rtn = 0;
//    string num_str = to_string(num);
//    for(int i=0; i<num_str.size(); i++) {
//        rtn += num_str[i] - '0';
//    }   
//    return rtn;
//}

// vectorのコピー
template <class T>
vector<T> copy_vector(vector<T> vec) {
    vector<T> rtn;
    rtn.reserve(vec.size());
    copy(vec.begin(), vec.end(), back_inserter(rtn));
    return rtn;
}

// ユークリウッドの互除法
int gcd(int a, int b) {
    if(b==0) return a;
    else return gcd(b, a % b);
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;

int main(){
  ll h, w; cin >> h >> w;
  
  // 幅1マスだと駒は動かせない
  if(h == 1 || w == 1){
    cout << 1 << endl;
    return 0;
  }
  
  // チェック柄を一行ずつ見たとき、移動可能マスが多く含まれているのはH行
  // そのときのマス数はW
  ll H = h/2, W = w/2;
  if(h%2 != 0) ++H;
  if(w%2 != 0) ++W;
  
  cout << H*W + (h-H)*(w-W) << endl;
  return 0;
}


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

int main(){
  int mod = 1000000007;
  int nmax = 100000;
  vector<int>fib(nmax+2);
  fib.at(0) = 0; fib.at(1) = 1;
  for(int i = 2; i < nmax+2; i++)
    fib.at(i) = (fib.at(i-1)+fib.at(i-2))%mod;
  int n,m;
  cin >> n >> m;
  if(m == 0)  cout << fib.at(n+1) << endl;
  else{
    vector<int> a(m);
    rep(i,m)  cin >> a.at(i);
    vector<int> b(m+1);
    b.at(0) = a.at(0);
    b.at(m) = n-a.at(m-1);
    for(int i = 1; i < m; i++)  b.at(i) = a.at(i)-a.at(i-1)-1;
    int64_t ans = 1;
    for(int k : b){
      ans *= fib.at(k);
      ans %= mod;
    }
  cout << ans << endl;
  }
}

Measured memory_bytes: 1408
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <deque>
#include <map>
using namespace std;

typedef long long ll;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl "\n"
#define forn(i,n) for(int i=0; i<int(n); i++)
#define for1(i,n) for(int i=1; i<=int(n); i++)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

void no(int ex = -1) {
	cout << ex << endl;
	//cout << "NO" << endl;
	//exit(0);
}
void bl(bool win) {
	if (win) cout << "YES"; else cout << "NO";
	cout << endl;
}

const int N = 1000000;
const ll INF = LLONG_MAX;
const int mod = 998244353;

/*vector<bool> pr;
void prime() {
	int EDGE = 1000;
	pr.assign(EDGE, true);
	pr[0] = false; pr[1] = false;
	for (int i = 2; i < EDGE; i++) {
		if (pr[i])
			if (1LL * i * i < EDGE)
				for (int j = i * i; j < EDGE; j += i)
					pr[j] = false;
	}
}*/
//prime


ll T;

int main() {
	IOS;
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	string str;
	cin >> str;
	if (str == "ABC") cout << "ARC"; else cout << "ABC";

}

Measured memory_bytes: 3036
#include <iostream>

using namespace std;

bool test(const char c, char _c[3][3]){
        bool flag = false;
        for(int i = 0; i < 3; i++){
                bool _flag1, _flag2;
                _flag1 = _flag2 = true;
                for(int j = 0; j < 3; j++){
                        _flag1 &= _c[i][j] == c;
                        _flag2 &= _c[j][i] == c;
                }   
                flag |= _flag1 || _flag2;
        }   
        bool _flag1, _flag2;
        _flag1 = _flag2 = true;
        for(int i = 0 ; i < 3; i++){
                _flag1 &= *(*(_c+i)+i) == c;
                _flag2 &= *(*(_c+2-i)+i) == c;
        }   
        return flag || _flag1 || _flag2;
}
int main(){
        char c[10];
        while(cin >> c){ 
                char _c[3][3];
                for(int i = 0; i < 3; i++){
                        for(int j = 0; j < 3; j++){
                                _c[i][j] = c[i*3+j];
                        }   
                }   
                if(test('o', _c)) cout << 'o';
                else if(test('x', _c)) cout << 'x';
                else cout << 'd';
                cout << endl;
        }   
}

Measured memory_bytes: 0
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
X = LI2()
X.reverse()

if N == 1 and len(X) == 1 and X[0] == 0:
    print(1)
    exit()


def popcount(n):
    res = 0
    m = n.bit_length()
    for i in range(m):
        res += (n >> i) & 1
    return res


F = [0]*(2*10**5)
for i in range(1,2*10**5):
    F[i] = 1 + F[i % popcount(i)]

a = sum(X)
b = a-1
c = a+1
if a == 1:
    A, C = [1], [1]  # 2冪をa,b,cで割った余り
    xa, xc = 0, 0  # Xをa,b,cで割った余り
    for i in range(N):
        if X[i] == 1:
            xa += A[-1]
            xc += C[-1]
            xa %= a
            xc %= c
        A.append((2 * A[-1]) % a)
        C.append((2 * C[-1]) % c)

    ANS = []
    for i in range(N):
        if X[i] == 1:
            ANS.append(0)
        else:
            ANS.append(1 + F[(xc + C[i]) % c])

    ANS.reverse()
    print(*ANS, sep='\n')
    exit()

A,B,C = [1],[1],[1]  # 2冪をa,b,cで割った余り
xa,xb,xc = 0,0,0  # Xをa,b,cで割った余り
for i in range(N):
    if X[i] == 1:
        xa += A[-1]
        xb += B[-1]
        xc += C[-1]
        xa %= a
        xb %= b
        xc %= c
    A.append((2*A[-1])%a)
    B.append((2*B[-1])%b)
    C.append((2*C[-1])%c)

ANS = []
for i in range(N):
    if X[i] == 1:
        ANS.append(1 + F[(xb-B[i]) % b])
    else:
        ANS.append(1 + F[(xc+C[i]) % c])

ANS.reverse()
print(*ANS,sep='\n')


Measured memory_bytes: 134748
#include<iostream>
#include<vector>
#define MAX_N 100001
using namespace std;
typedef long long ll;
bool used[MAX_N]={};
ll dp[MAX_N]={};
vector<ll> G[MAX_N];
ll f(ll x){
  if(used[x]) return dp[x];
  used[x]=true;
  ll tmp=0;
  for(ll i=0;i<G[x].size();i++){
    tmp = max(tmp,f(G[x][i])+1);
  }
  return dp[x]=tmp;
}
signed main(){
  ll n,m,ans=0;
  cin >> n >> m;
  ll x[m],y[m];
  for(int i=0;i<m;i++){
    cin >> x[i]>>y[i];
    x[i]--;
    y[i]--;
    G[x[i]].push_back(y[i]);
  }
  for(int i=0;i<n;i++){
    ans = max(ans,f(i));
  }
  cout << ans << endl;
}


Measured memory_bytes: 10240
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#": ans = "#"
        else:
            ans = 0
            for k in [-1, 0, 1]:
                for l in [-1, 0, 1]:
                    if k == l == 0: continue
                    if 0 <= i+k < h and 0 <= j+l < w and s[i+k][j+l] == "#":
                        ans += 1
        print(ans, sep="", end="")
    print("")
            



Measured memory_bytes: 3444
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
use proconio::input;
use proconio::marker::Usize1;
//use proconio::marker::Chars;
//use std::collections::HashSet;
use std::cmp::*;

const INF: usize = 1000_000_000_000;
fn main() {
    input! {
        N: usize,
        M: usize,
        S: usize,
        mut UVAB: [(Usize1,Usize1,usize,u64);M],
        CD:[(usize,u64);N]
    }
    // g[i] = (j, a,b)なら、iからjへ、a円 b時間
    let mut g = vec![vec![]; N];
    for &(u, v, a, b) in UVAB.iter() {
        g[u].push((v, a, b));
        g[v].push((u, a, b));
    }
    // 銀貨最大値
    let w = 50 * 49;
    let mut dp = vec![vec![std::u64::MAX; w + 1]; N];
    // 都市0で銀貨S枚持つまでに0分かかる。
    dp[0][min(w, S)] = 0;
    let mut h = std::collections::BinaryHeap::new();
    // 謎。Heapに、逆順を指定したうえでタプルを加えている模様。
    h.push(Reverse((0, 0, min(w, S))));
    // hからpop出来る限り繰り返す。
    while let Some(Reverse((d, v, k))) = h.pop() {
        // heap は既に訪れた場所？
        // 既に訪れたHeapについて、dp[v][k]のより小さいものが見つかったとしたら、無視。
        // 最初は0,0,Sであり、dp[0][S]=0だから、if式はfalse。
        if d > dp[v][k] {
            continue;
        }
        for &(u, a, b) in g[v].iter() {
            // 移動可能な場所uへの運賃aが、所持金より多い場合、移動不可。
            if a > k {
                continue;
            }
            // そうでなければ移動。移動時間を加えたものをdとすると、
            // 所持金をa減らしてuに到着した場合の時刻dとなるので、
            // dが過去に計算されたdp[u][k-a]を更新できるなら、更新し、
            // hに、検査対象の (d,u,k-a)を追加する。
            let next_d = d + b;
            let next_k = k - a;
            if next_d < dp[u][next_k] {
                dp[u][next_k] = next_d;
                //let mut tmp_k = next_k;
                for tmp_k in (0..next_k).rev() {
                    if dp[u][tmp_k] > dp[u][next_k] {
                        dp[u][tmp_k] = dp[u][next_k];
                    } else {
                        break;
                    }
                }
                h.push(Reverse((next_d, u, next_k)));
            }
            // 以上を、vから移動可能な路線(u,a,b)のすべてについてチェックする。。
        }
        // 次に換金時間を足す。dは時刻、kは所持金
        let next_d = d + CD[v].1;
        let next_k = min(k + CD[v].0, w);
        if dp[v][next_k] > next_d {
            dp[v][next_k] = next_d;
            for tmp_k in (0..next_k).rev() {
                if dp[v][tmp_k] > dp[v][next_k] {
                    dp[v][tmp_k] = dp[v][next_k];
                } else {
                    break;
                }
            }
            h.push(Reverse((next_d, v, next_k)));
        }
    }

    //println!("dp[0]={:?}", &dp[0][0..10]);
    //println!("dp[1]={:?}", &dp[1][0..10]);
    for v in 1..N {
        println!("{}", dp[v].iter().min().unwrap());
    }
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin >> s;
  int n = s.length();
  string w = "";
  for (int i = 0; i < (int) s.length(); i++) {
    if (s[i] != 'x') {
      w += s[i];
    }
  }
  string ww = w;
  reverse(ww.begin(), ww.end());
  if (w != ww) {
    printf("%d\n", -1);
    return 0;
  }
  int ans = 0;
  int i = 0, j = n - 1;
  while (i < j) {
    if (s[i] == s[j]) {
      i++;
      j--;
      continue;
    }
    ans++;
    if (s[i] == 'x') {
      i++;
    } else {
      j--;
    }
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 10;
int a[maxn];
int cnt[1010101];
int Min1[maxn] , Max1[maxn];
int rk[maxn] , sum = 0;
int n;
bool cmp(int x , int y){
	return Min1[x] < Min1[y];
}
int main(){
	ios::sync_with_stdio(0);
	cin >> n;
	for(int i = 1 ; i <= n ; ++ i)
		cin >> a[i];
	for(int i = 1 ; i <= n ; ++ i)
		if(a[i] >= i){
			cout << -1 << endl;
			return 0;
		}
	for(int i = 1 ; i <= n ; ++ i)
		Min1[i] = 202020 , Max1[i] = 0;
	for(int i = 1 ; i <= n ; ++ i){
		Min1[i - a[i]] = min(Min1[i - a[i]] , i);
		Max1[i - a[i]] = max(Max1[i - a[i]] , i);
	}
	for(int i = 1 ; i <= n ; ++ i)
		if(Max1[i]) rk[++ sum] = i;
	sort(rk + 1 , rk + sum + 1 , cmp);
	for(int i = 2 ; i <= sum ; ++ i)
		if(Min1[rk[i]] != Max1[rk[i - 1]] + 1){
			cout << -1 << endl;
			return 0;
		}
	long long ans = 0;
	for(int i = 1 ; i <= n ; ++ i)
		cnt[i - a[i]] = max(cnt[i - a[i]] , a[i]);
	for(int i = 0 ; i <= n ; ++ i)
		ans += cnt[i];
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	int road[50][50] = {};
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		road[a - 1][b - 1]++;
		road[b - 1][a - 1]++;
	}
	for (int i = 0; i < n; i++)
	{
		int ans = 0;
		for (int j = 0; j < n; j++)
			ans += road[i][j];
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) begin(x), end(x)
#define x first
#define y second
typedef long long ll;
typedef long double ld;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;

const int MAX_N = 2e5 + 10;

char str[MAX_N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> str;
	int n = strlen(str);
	ll ans = 0;
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (str[i] == 'W')
			ans += i - cnt, ++cnt;
	}
	cout << ans << "\n";
	return 0;
}

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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define intMAX 1000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod = 1e9+7;

int n;
ll dp[101][4][4][4];	//globalで宣言することで0で初期化される
int main(){
  cin >> n;

  dp[0][3][3][3]  = 1;
  for(int i = 0; i < n; i++){

    //最後から3文字目
    for(int c1 = 0; c1 < 4; c1++){

      //最後から２文字目
      for(int c2 = 0; c2 < 4; c2++){

        //最後から1文字目
        for(int c3 = 0; c3 < 4; c3++){

          //３文字目の段階で0だったら何加えても0になる．
          if (dp[i][c1][c2][c3] == 0)continue;

          //付け加える文字
          for(int a = 0; a < 4; a++){
            if(a == 2 && c3 == 1 && c2 == 0)continue;
            if(a == 2 && c3 == 0 && c2 == 1)continue;
            if(a == 1 && c3 == 2 && c2 == 0)continue;
            if(a == 2 && c3 == 1 && c1 == 0)continue;
            if(a == 2 && c2 == 1 && c1 == 0)continue;

            dp[i+1][c2][c3][a] += dp[i][c1][c2][c3];
            dp[i+1][c2][c3][a] %= mod;
          }
        }
      }
    }
  }
  int ans = 0;
  for(int c1 = 0; c1 < 4; c1++){
    for(int c2 = 0; c2 < 4; c2++){
      for(int c3 = 0; c3 < 4; c3++){
        ans += dp[n][c1][c2][c3];
        ans %= mod;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
def main(X, Y):
    M = len(Y)
    dp = [0]*(M+1)
    for i, x in enumerate(X):
        dp_pre = dp[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = dp_pre[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
    return print(dp[M])


for _ in range(int(input())):
    X = input()
    Y = input()
    main(X, Y)



Measured memory_bytes: 5624
#include <bits/stdc++.h>
using namespace std;
#define optimizar_io ios_base::sync_with_stdio(false);cin.tie(0);

int main() {
	optimizar_io
	
	string s; 

	cin >> s;
	for (int i = 0; i < s.size(); i++)
		cout << "x";
	cout << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>
#include <sstream>
#include <istream>
#include <iomanip>
#include <typeinfo>
#include <stack>

using namespace std;
typedef long long ll;

int main(){

    ll N;
    cin >> N;
    if(N == 1){
        cout << 0 << endl;
        return 0;
    }
    N--;
    ll ans =  N * (N + 1);
    ans /= 2;
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(void){
  int i, j, c, num, data, n, state_n;
  long int staff[4000], value;
  long int state[4000];
  char buf[8];

  while(1){
    num = j = 0;
    while((c = getchar()) != '\n'){
      buf[j++] = c;
      if(j == 1 && c == '0') break;
    }
    buf[j] = '\0';
    num = atoi(buf);
    if(num == 0) break;

    for(i = 0; i < 4000; i++){
      staff[i] = 0;
      state[i] = 0;
    }
    state_n = 0;

    for(i = 0; i < num; i++){
      data = j = 0;
      while((c = getchar()) != '\n'){
        buf[j] = c;
        if(c == ' ' && data == 0){
          buf[j] = '\0';
          n = atoi(buf);
          j = 0;
          data++;
          continue;
        }
        if(c == ' ' && data == 1){
          buf[j] = '\0';
          value = atol(buf);
          j = 0;
          data++;
          continue;
        }
        j++;
      }
      buf[j] = '\0';
      staff[n-1] += atol(buf) * value;
      if(staff[n-1] >= 1000000 && state[n-1] == 0){
        state[n-1] = ++state_n;
      }
    }

    if(state_n == 0){
      printf("NA\n");
    }
    for(j = 1; j <= state_n; j++){
      for(i = 0; i < 4000; i++){
        if(state[i] == j) printf("%d\n", i+1);
      }
    }
  }
  return 0;
}

Measured memory_bytes: 588
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e5)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
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; }
typedef pair <ll,ll> P;

int main()
{
    ll N;
    cin >> N;
    vector<ll> p(N);
    rep(i, N) { 
        cin >> p[i];
    }
    vector<ll> a(N);
    iota(all(a),1);
    ll cnt = 0;
    rep(i, N) {
        if (p[i] != a[i]) cnt++;
    }
    if(cnt <= 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define r0 return 0;
#define f(k,i,n,j) for(ll k=i;k<=n;k=k+j)
#define cin(a) cin>>a;
#define loop while(t--)
#define vi vector<int>
#define vii vector<long long int>
#define SORT(v) sort(v.begin(),v.end());
#define mod (1e9+7)
#define crap ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
signed main()
{
    crap;
    int n,sum=0;
    cin>>n;
    int c=n;
    while(c>0)
    {
        sum+=c%10;
        c/=10;
    }
    if(n%sum==0)
    cout<<"Yes";
    else
    cout<<"No";
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<string> A(N), B(M);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    for(int i = 0; i < M; i++){
        cin >> B[i];
    }
    
    for(int i = 0; i <= N - M; i++){
        for(int j = 0; j <= N - M; j++){
            bool flag = true;
            
            for(int k = 0; k < M; k++){
                for(int l = 0; l < M; l++){
                    if(A[i + k][j + l] != B[k][l]){
                        flag = false;
                        break;
                    }
                }
                if(!flag)   break;
            }
            
            if(flag){
                cout << "Yes\n";
                return 0;
            }
        }
    }
    
    cout << "No\n";
}

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

int main(){
	int N;
	cin>>N;
	cout<<std::fixed;
	if(N&1){
		cout<<setprecision(10)<<(N+1)/(2.0*N);
	}
	else{
		cout<<setprecision(10)<<0.5;
	}
	return 0;
}

Measured memory_bytes: 256
import collections

n = int(input())
A = list(map(int,input().split()))
Q = int(input())

count = dict(collections.Counter(A))

ans = sum(A)

for _ in range(Q):
    b,c = map(int, input().split())
    if b in count:
        ans -= count[b]*b
        ans += count[b]*c
        if c not in count:
            count[c] = count[b]
        else:
            count[c] += count[b]

        count[b] = 0
    
    print(ans)
    

Measured memory_bytes: 21284
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int main(void)
{
	int a, b,ans = 0;
	cin >> a >> b;
	ans = a * b;
	if (a + b > ans) { ans = a + b; }
	if (a - b > ans) { ans = a - b; }
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256