akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

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

using namespace std;
using ll = long long;
int mod = 1000000007;

void solve();

int main(void){
    int N, M; cin >> N >> M;
    string A[N], B[M];
    bool ok = true;
    rep(i, N) cin >> A[i];
    rep(i, M) cin >> B[i];
    for(int i = 0; i <= N-M; i++){
        for(int j = 0; j <= N-M; j++){
            ok = true;
            for(int i2 = 0; i2 < M; i2++){
                for(int j2 = 0; j2 < M; j2++){
                    if(A[i+i2][j+j2] != B[i2][j2]) ok = false;
                }
            }
            if(ok){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

void solve(){}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	vector<long long>a, b;
	cin >> n;
	a.resize(n);
	b.resize(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
		b[i] = a[i] - (i + 1);
	}
	sort(b.begin(), b.end());
	long long int c = b[n / 2];
	long long int ans = 0;
	for (int i = 0; i < n; i++){
		ans += abs(b[i] - c);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3328
N,K = map(int,input().split())

l = [0 for i in range(N)]
for i in range(K):
    d = int(input())
    A = list(map(int,input().split()))
    for j in A:
        l[j-1] += 1

cnt = 0
for i in l:
    if i == 0:
        cnt += 1

print(cnt)

Measured memory_bytes: 67672
S = input()
N = int(input())

index = -1
r = -1
for i in range(len(S)):
    if index == -1:
        if S[i] == '1':
            index = i
            r = 1
            continue

    if index != -1 and r != 0:
        if S[i] == '1':
            r += 1
        else:
            break
if index == -1:
    print(S[0])
elif index != 0:
    print(S[0])
elif r >= N:
    print(1)
else:
    print(S[r])


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

int main(void) {
  int n;
  string s, t;
  cin >> n >> s >> t;
  string ans = "";
  rep (i, n) {
    ans = ans + s[i];
    ans = ans + t[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
time_arr = []
 
5.times {|_| time_arr << STDIN.gets.to_i }
 
def evaluate(sol, time_arr)
  sol = sol.dup
  t = 0
  while sol.size > 1
    t += time_arr[sol.shift]
    mod = t % 10
    t = ((t / 10 + 1) * 10) if !mod.zero?
  end
  t += time_arr[sol.shift]
  t
end
 
min = 9999999
ARR = [0, 1, 2, 3, 4]
ARR.permutation {|sol|
  d = evaluate(sol, time_arr)
  min = d if min > d 
}
 
STDOUT.puts min

Measured memory_bytes: 1788
#include<stdio.h>
#include<math.h>
int main(){
  long long int n,k;
  scanf("%lld%lld", &n, &k);
  if(k%2==0) printf("%lld\n", (n/k)*(n/k)*(n/k)+((k/2+n)/k)*((k/2+n)/k)*((k/2+n)/k));
  else printf("%lld\n", (n/k)*(n/k)*(n/k));
  return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

const int N = 100, M = 100;
int dx[] = {1, 0}, dy[] = {0, 1};
char map[N + 2][M + 2] = { { 0 } };

int search(int x, int y, int c, int dir){
	if(c == 0) return 1;
	int nx = x + dx[dir], ny = y + dy[dir];
	if(map[ny][nx] == '.'){
		return search(nx, ny, c - 1, dir);
	}
	else return 0;
}

int main(){
	int n, m, d, ans = 0;
	cin >> n >> m >> d;
	for(int i = 0;i < n;++i){
		for(int j = 0;j < m;++j){
			cin >> map[i + 1][j + 1];
		}
	}
	for(int i = 0;i < n;++i){
		for(int j = 0;j < m;++j){
			if(map[i + 1][j + 1] == '.'){
				for(int k = 0;k < 2;++k){
					ans += search(j + 1, i + 1, d - 1, k);
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3096
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007LL;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
int main(){
    int n;
    cin >> n;
    long long x[n],y[n];
    map<pair<long long,long long>,int> mp;
    vector<pair<long long,long long>> vec;
    pair<long long,long long> pr; 
    rep(i,n){
        cin >> x[i] >> y[i];
    }
    for(int i = 0;i<n;i++){
        for(int j = i;j<n;j++){
            if(i!=j){
                if((x[j]-x[i])<0){
                    pr = make_pair(x[i]-x[j],y[i]-y[j]);
                }
                else{
                    pr = make_pair(x[j]-x[i],y[j]-y[i]);
                }
                if(x[j]==x[i]){
                    pr = make_pair(0,abs(y[j]-y[i]));
                }
                vec.push_back(pr);
                if(mp.find(pr)==mp.end()){
                    mp[pr]=1;
                }
                else{
                    mp[pr]++;
                }
            }
        }
    }
    int tmp= 0;
    for(int i = 0;i<vec.size();i++){
        tmp = max(tmp,mp[vec[i]]);
    }
    cout << n - tmp << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int n,h,h2;
string s;
int main(){
	cin>>n;
	cin>>s;
	for(int i=0;i<n;i++){
		if(s[i] == 'I')
			h++;
		else
			h--;
		if(h>h2)
			h2=h;
	}
	cout<<h2;
	cout<<'\n';
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
int a;
  int b;
  int c;
  int d;
  cin >>a>>b>>c>>d;
  
  int x1=c-a;
    int y1=d-b;
  int x2=-y1+c;
  int y2=x1+d;
  int z=x2-c;
  int w=y2-d;
  int x3=-w+x2;
  int y3=z+y2;
  cout<<x2<< " "<< y2<<" "<<x3<<" "<<y3<< endl;
}

 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int main() {
    string s;
    cin >> s;
    string ans = "";
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != 'B') {
            ans += s[i];
        } else {
            if (ans.size() != 0) {
                ans.erase(ans.begin() + ans.size() - 1);
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
W, H, X, Y = gets.split.map(&:to_i)

if W/2.0==X && H/2.0==Y
  puts "#{W.to_f*H.to_f/2.0}" + " " + "1"
else
  puts "#{W.to_f*H.to_f/2.0}" + " " + "0"
end

Measured memory_bytes: 1788
#include<stdio.h>
#define N 100000
 
typedef struct{
  int parent;
  int left;
  int right;
}Node;
 
int depth(int);
int height(int);
 
Node node[N];
 
int main(){
  int i, j, n, id, child;
 
  scanf("%d", &n);
  for(i = 0;i < n;i++){
    node[i].parent = node[i].left = node[i].right = -1;
  }
  for(i = 0;i < n;i++){
    scanf("%d", &id);
    for(j = 0;j < 2;j++){
      scanf("%d", &child);
      if(child != -1){
        node[child].parent = id;
        if(j == 0){
          node[id].left = child;
        }
        else{
          node[id].right = child;
        }
      }
    }
  }
 
  for(i = 0;i < n;i++){
    printf("node %d: parent = %d, sibling = ", i, node[i].parent);
    if(node[i].parent == -1){
      printf("-1, ");
    }
    else{
      if(node[node[i].parent].right == -1){
        if(node[node[i].parent].left != -1 && node[node[i].parent].left != i){
          printf("%d, ", node[node[i].parent].left);
        }
        else{
          printf("-1, ");
        }
      }
      else{
        if(node[node[i].parent].right != i){
          printf("%d, ", node[node[i].parent].right);
        }
        else{
          printf("%d, ", node[node[i].parent].left);
        }
      }
    }
 
    printf("degree = ");
    if(node[i].left == -1){
      if(node[i].right == -1){
        printf("0, ");
      }
      else{
        printf("1, ");
      }
    }
    else{
      if(node[i].right == -1){
        printf("1, ");
      }
      else{
        printf("2, ");
      }
    }
 
    printf("depth = %d, height = %d, ", depth(i), height(i));
 
    if(node[i].parent == -1){
      printf("root\n");
    }
    else{
      if(node[i].left == -1){
        if(node[i].right != -1){
          printf("internal node\n");
        }
        else{
          printf("leaf\n");
        }
      }
      else{
        printf("internal node\n");
      }
    }
  }
  return 0;
}
 
int depth(int id){
  int dep = 0;
  while(1){
    if(node[id].parent == -1){
      return dep;
    }
    else{
      dep++;
      id = node[id].parent;
    }
  }
}
 
int height(int id){
  int hei, l = 0, r = 0;
  if(node[id].left == -1){
    if(node[id].right == -1){
      return 0;
    }
    else{
      r += height(node[id].right) + 1;
    }
  }
  else{
    l += height(node[id].left) + 1;
    if(node[id].right != -1){
      r += height(node[id].right) + 1;
    }
  }
  if(l < r){
    return r;
  }
  else{
    return l;
  }
}

Measured memory_bytes: 1828
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <deque>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vector<vec> v){for(auto e:v){for(auto ee:e)cout<<ee<<" ";cout<<endl;}}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}
const int INF=1e6;
const ll int MOD=998244353;

main(){
    int a=in(),b=in(),h=in();
    cout<<(a+b)*h/2;
}

Measured memory_bytes: 256
/******************************************
*    AUTHOR:         CHIRAG AGARWAL       *
*    INSTITUITION:   BITS PILANI, PILANI  *
******************************************/
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL; 
typedef long double LD;
const int MAX=1e5+5;
vector<int> adj[MAX];


void first()
{
	printf("First\n");
	exit(0);
}

void second()
{
	printf("Second\n");
	exit(0);
}

int dfs(int s,int p)
{
	int val=0;
	for(int i=0;i<adj[s].size();i++)
	{
		int u=adj[s][i];
		if(u!=p)
		{
			val+=dfs(u,s);
		}
	}
	if(val>=2)
	{
		first();
	}
	if(val==0)
	{

		return 1;
	}
	return 0;
}

int main() 
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	if(dfs(1,0))
	{
		first();
	}
	second();
	return 0;
}

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

using namespace std;

int main() {

	string s;
	cin >> s;
	int sum = 0;
	for (int i = 0; i < s.length(); i ++) {
		sum += (s[i] - '0');
	}
	cout << ((sum % 9 == 0) ? "Yes\n" : "No\n");
	return 0;	
}

Measured memory_bytes: 3716
#include<stdio.h>

int main(void){
  int N;
  scanf("%d",&N);
  int i;
  int A[N];
  int v,j,k;
  
  for(i = 0; i<N ;i++)
    {
      scanf("%d",&A[i]);
      printf("%d",A[i]);
      if (i < N-1)printf(" ");
      else printf("\n");
    };
  for(i = 1; i < N;i++)
    {
      v = A[i];
      j = i - 1;
      while(j  > -1 && A[j] > v)
        {
          A[j+1] = A[j];
          j--;
          A[j+1] = v;
        };
      
      for(k = 0; k < N;k++)
        {
          if (k>0)printf(" ");
          printf("%d",A[k]);
        }
      printf("\n");
    }
  return 0;
}

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

#define F first
#define S second
#define int long long
#define inf 1000000000
#define mod 1000000007

using namespace std;

signed main(){
    int a, b, n;
    cin >> a >> b >> n;
    int x;
    if (b-1 <= n){
        x = b-1;
    } else {
        x = n;
    }
    int ans = a*x/b-a*(x/b);
    cout << ans << endl;
    return 0;
}























Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int X, N;
    cin >> X >> N;
    vector<bool> p(102, false);
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        p[x] = true;
    }

    int ans = 0;
    int min_diff = X;
    for (int i = 0; i <= 101; i++)
    {
        if (!p[i] && abs(i - X) < min_diff)
        {
            ans = i;
            min_diff = abs(i - X);
        }
    }

    cout << ans << endl;
}

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

int main() {
	int N, K;
	cin >> N >> K;

	vector<ll> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (int i = 0; i < N - K; i++) {
		if (A[i] < A[i + K]) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 4824
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
  unsigned short *A, *B;
  int C[VMAX+1];
  int n, i, j;

  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  /* your code */
  for(i=0; i<=VMAX;i++)C[i]=0;
  
  for(i=0; i<n; i++){
    scanf("%hu",&A[i+1]);
    C[A[i+1]]++;
  }
  
  for(i=1; i<= VMAX; i++)C[i]=C[i] + C[i-1];

  for(j=1; j<=n;j++){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  
  for(i=1;i<=n;i++){
    if(i >= 2) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
    return 0;
}



Measured memory_bytes: 9620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=525,INF=1<<30;
ll dp[MAX][MAX],mae[MAX][MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N,X;cin>>N>>X;
    dp[0][0]=1;
    
    for(int i=0;i<=X;i++){
        for(int j=0;j<=N;j++){
            for(int k=0;k<512;k++){
                dp[j][k]+=mae[j][k];
                dp[j][k]%=mod;
            }
            
            for(int k=0;k<512;k++){
                if(j) dp[j][k]+=dp[j-1][k^i];
                dp[j][k]%=mod;
            }
        }
        
        for(int j=0;j<=N;j++){
            for(int k=0;k<512;k++){
                mae[j][k]=dp[j][k];
                dp[j][k]=0;
            }
        }
    }
    
    cout<<mae[N][X]<<endl;
}


Measured memory_bytes: 7292
#include<cstdio>
#include<cstring>

int main() {
    char digits[1000];

    while (1) {
        scanf("%s", digits);
        if (strcmp(digits, "0") == 0) break;

        int i = 0, sum = 0;
        while (digits[i]) {
            sum += (digits[i++] - '0');
        }
        printf("%d\n", sum);        
    }

    return 0;
}

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

int main() {
  
  int N,K;
  cin >> N >> K;
  int j;
  int S=1;
  while(j<N){
    int A=S+K;
    int B=S*2;
    
    if (A<B){
    S=A;
    }
    else {
    S=B;
    }
    
    j++;
  
  }
  
  cout << S << endl;
  
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed
#define endl '\n'

const ll MOD = 1e9 + 7;
struct mint {
    ll x;
    mint() : x(0) {}
    mint(ll x) : x((x % MOD + MOD) % MOD) {}
    mint& operator+=(const mint& r) { if ((x += r.x) >= MOD) { x -= MOD; } return *this; }
    mint& operator-=(const mint& r) { if ((x -= r.x) < 0) { x += MOD; } return *this; }
    mint& operator*=(const mint& r) { if ((x *= r.x) > MOD) { x %= MOD; } return *this; }
    mint& operator++() { if ((++x) >= MOD) { x -= MOD; } return *this; }
    mint operator++(int) { mint ret = x; if ((++x) >= MOD) { x-= MOD; } return ret; }
    mint& operator--() { if ((--x) < 0) { x += MOD; } return *this; }
    mint operator--(int) { mint ret = x; if ((--x) < 0) { x += MOD; } return ret; }
    mint operator+(const mint& r) { mint ret; return ret = x + r.x; }
    mint operator-(const mint& r) { mint ret; return ret = x - r.x; }
    mint operator*(const mint& r) { mint ret; return ret = x * r.x; }
    mint operator-() { return mint() - *this; }
    bool operator<(const mint& a) { return x < a.x; }
    bool operator>(const mint& a) { return x > a.x; }
    bool operator<=(const mint& a) { return x <= a.x; }
    bool operator>=(const mint& a) { return x >= a.x; }
    bool operator==(const mint& a) { return x == a.x; }
    bool operator!=(const mint& a) { return x != a.x; }
};
ostream& operator<<(ostream& os, const mint& r) { os << r.x; return os; }
ostream& operator>>(ostream& os, const mint& r) { os >> r.x; return os; }

void solve(istream& cin, ostream& cout) {
  int a, b, x, y;
  cin >> a >> b;
  if (a < b) {
    swap(a, b);
  }
  long tmp;
  x = a;
  y = b;
  while (x % y != 0) {
    tmp = y;
    y = x % y;
    x = tmp;
  }
  cout << (long)a * b / y;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
}
#endif


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

int main()
{
  char N[3];
  char out[3];
  cin >> N;

  for(int i=0; i<3; i++)
  {
    if(N[i] == '1')
    {
      N[i] = '9';
    }
    else if(N[i] == '9')
    {
      N[i] = '1';
    }
  }
  cout << N << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

int N, M;
const int OFFSET = 2000;

LL dp[6001][8001];

LL memo(int total, int dif) {
	if (dif < 0)
		return 0LL;
	if (!total)
		return dif >= OFFSET;
		
	LL &ret = dp[total][dif];
	if (ret != -1)
		return ret;
	
	ret = 0LL;
	
	if (total >= 3)
		ret += (total - 1LL) * (total - 2LL) * memo(total - 3, dif);
	if (total >= 2)
		ret += (total - 1LL) * memo(total - 2, dif - 1);
	ret += memo(total - 1, dif + 1);
	
	ret %= M;
	return ret;
}


int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
	
	cin >> N >> M;
	
	SET(dp, 255);
	
	cout << memo(3 * N, OFFSET) << endl;
	
	return 0;
}

Measured memory_bytes: 375808
#include<stdio.h>
#include<string.h>
int main()
{
    char str[99];
    int n,i,j,k,m,x=0,y=0,z=0;
    gets(str);
    n=strlen(str);
    k=(n-1)/2;
    m=(n+3)/2;
    for(i=0,j=n-1;i<n/2;i++,j--)
    {
        if(str[i]==str[j])
             x++;
    }
    if(x==n/2)
    {
        for(i=0,j=k-1;i<k/2;i++,j--)
        {
            if(str[i]==str[j])
                y++;
        }
        for(i=m-1,j=n-1;i<m-1+(k/2);i++,j--)
        {
            if(str[i]==str[j])
                z++;
        }
        if(y==(k/2) && z==(k/2))
               printf("Yes\n");
        else
            printf("No\n");
    }
    else
        printf("No\n");
    return 0;
}


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

using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;


ll mo=1000000007;
ll comb(ll N_, ll C_) {
    const int NUM_=310000;
    static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
    if (fact[0]==0) {
        inv[1]=fact[0]=factr[0]=1;
        for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
        for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
    }
    if(C_<0 || C_>N_) return 0;
    return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
int32_t main() {
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    
    ini(n);
    ini(n1);
    int tmp = 0;
    while(n1!=n+2){
        int ll = n1*(n1-1)/2;
        int rr = ((n+(n-n1+1))*n1)/2;
        tmp+=rr-ll+1;
        tmp%=mo;
        n1++;
    }
    out(tmp);
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <math.h>
using namespace std;
int E;
int solve (int e) {
	int mi = e;
	for (int z = 0; z*z*z <= e ; z++) {
		for (int y = 0; y*y <= e ; y++) {
			if (e - y*y - z*z*z >= 0) {
				mi = min(mi,e-y*y-z*z*z+y+z);
			}
		}
	}
	return mi;
}
int min(int a,int b) {
	if (a<b) return a;
	else return b;
}
int main() {
	while (cin >> E && E > 0 ) {
		cout << solve(E) << endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 998244353;
const ld PI = acosl(-1);

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

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

    bool isok = true;
    if (s.back() == '1' || s[0] == '0')
        isok = false;

    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = n - i - 1;
        if (i < n - 1 && s[i] != s[n - i - 2])
            isok = false;
    }

    if (!isok)
        cout << -1 << '\n';
    else {
        vector<bool> finished(n);
        int pos = 1;
        for (int i = 0; i < n; ++i) {
            if (finished[i] || s[i] == '0')
                continue;
            while (pos < i + 1) {
                cout << pos << " " << i + 1 << '\n';
                pos++;
            }
            finished[i] = finished[n - i - 2] = true;
        }
        cout << pos << " " << pos + 1 << endl;
        pos++;
        for (int i = pos + 1; i <= n; ++i)
            cout << pos << " " << i << '\n';
    }

    return 0;
}


Measured memory_bytes: 2000
N = int(input())
cnt = [0] * 4
for n in range(N):
    s = input()
    if s == 'AC':
        cnt[0] += 1
    elif s == 'WA':
        cnt[1] += 1
    elif s == 'TLE':
        cnt[2] += 1
    elif s == 'RE':
        cnt[3] += 1

print('AC x ',cnt[0])
print('WA x ',cnt[1])
print('TLE x ',cnt[2])
print('RE x ',cnt[3])



Measured memory_bytes: 9196
import java.lang.Math.abs

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    var lastX = 0
    var lastY = 0
    var lastV = 0
    var ret = true
    for(_i in 0 until n){
        val (_v,x,y) = readLine()!!.split(' ').map(String::toInt)
        val v = _v - lastV
        val dist = (abs(x - lastX) + abs(y - lastY))
        if(dist <= v && (dist - v) % 2 == 0){
            lastX = x
            lastY = y
            lastV = _v
        }else{
            ret = false
            break
        }
    }
    print(if (ret) "Yes" else "No")
}

Measured memory_bytes: 51848
from sys import stdin

def solve(nums):
    a, b = nums
    p = 0
    for i in range(2):
        if a < b:
            p = p + b
            b = b - 1
        else:
            p = p + a
            a = a - 1
    return p


def main():
    nums = [int(n) for n in stdin.readlines()[0].split(' ')]
    p = solve(nums)
    print(p)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 9999999999999999;
using ll = long long;
int main(){
  string s;
  cin>>s;
  if(s.at(3) == s.at(2) && s.at(5) == s.at(4)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}

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


int main() {
  string N;
  cin>>N;
int k=N.size();
  vector<int>vec(k);
  for(int i=0;i<k;i++){
  for(int j=0;j<10;j++){
    if(N.at(i)=='0'){vec.at(i)=0;}
    else if(N.at(i)=='1'){vec.at(i)=1;}
    else if(N.at(i)=='2'){vec.at(i)=2;}
    else if(N.at(i)=='3'){vec.at(i)=3;}
    else if(N.at(i)=='4'){vec.at(i)=4;}
    else if(N.at(i)=='5'){vec.at(i)=5;}
    else if(N.at(i)=='6'){vec.at(i)=6;}
    else if(N.at(i)=='7'){vec.at(i)=7;}
    else if(N.at(i)=='8'){vec.at(i)=8;}
    else if(N.at(i)=='9'){vec.at(i)=9;}
                       
  } }
int s;
  for(int l=0;l<k;l++){s+=vec.at(l);}
  if(s%9==0){
  cout<<"Yes"<<endl;}
  else{cout<<"No"<<endl;}
}

Measured memory_bytes: 4436
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    cin>>a>>b;
    int n=a.length(),m=b.length();
    for(int i=0;i<2*m;i++)
    {
        if(i%2==0)  cout<<a[i/2];
        else  cout<<b[i/2];
    }
    if(m!=n)  cout<<a[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int x;
    int ans;
    cin >> x;
    if(x <= 599){
        ans = 8;
    }else if(600 <= x && x <= 799){
        ans = 7;
    }else if(800 <= x && x <= 999){
        ans = 6;
    }else if(1000 <= x && x <= 1199){
        ans = 5;
    }else if(1200 <= x && x <= 1399){
        ans = 4;
    }else if(1400 <= x && x <= 1599){
        ans = 3;
    }else if(1600 <= x && x <= 1799){
        ans = 2;
    }else if(1800 <= x){
        ans = 1;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3588
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(k,v) emplace_back(k,v)
#define ct(res) cout << res << "\n";
#define vi vector<int>
#define vl vector<ll>
using namespace std;
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; }
const int INF = 1e9;
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int func(ll a, ll k) {
    ll a1 = a;
    ll a2 = k;
    ll diff = abs(a-k);
    swap(a,diff);
    a = diff - k;
    if (a1 == a && a2 == diff) {
        return min(a,diff);
    }
    func(a, k);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,k; cin >> n >> k;
    ll ans = min(n%k, k-n%k);
    ct(ans);
}



Measured memory_bytes: 256
h, w, m = map(int, input().split())
h_cnt = [0 for i in range(h)]
w_cnt = [0 for i in range(w)]
bomb = set()

for i in range(m):
  _h, _w = map(int, input().split())
  h_cnt[_h - 1] += 1
  w_cnt[_w - 1] += 1
  bomb.add(((_h - 1),(_w - 1)))

h_max = max(h_cnt)
w_max = max(w_cnt)

max_h = []
max_w = []

for i in range(h):
  if h_cnt[i] == h_max:
    max_h.append(i)

for j in range(w):
  if w_cnt[j] == w_max:
    max_w.append(j)

flag = True

for i in max_h:
  for j in max_w:
    if (i, j) not in bomb:
      flag = False
      break

print(h_max + w_max - 1 if flag else h_max + w_max)

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

using namespace std;

int main() {
   int n, m;
   cin >> n >> m;
   vector<int> v(m);
   for (int &val : v) {
      cin >> val;
      n -= val;
   }
   cout << (n < 0 ? -1 : n) << endl;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

struct edge {
	int cost;
	int to;
};

int n;
ll INF = (ll)(1e15);
ll d[100010];
vector<edge> G[100010];

void dijkstra(int s) {
	priority_queue<pl, vector<pl>, greater<pl>> q;
	fill(d, d + n, INF);
	d[s] = 0;
	q.push(pl(0, s));

	while (!q.empty()) {
		pl p = q.top(); q.pop();
		int v = p.second;
		if (d[v] < p.first)continue;
		for (int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				q.push(pl(d[e.to], e.to));
			}
		}
	}
}

int main()
{
	cin >> n;

	for (int i = 0; i < n-1; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		x--, y--;
		G[x].push_back({c,y});
		G[y].push_back({c,x});
	}

	int q, k;
	cin >> q >> k;
	k--;
	dijkstra(k);
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		cout << d[y] + d[x] << endl;
	}
	return 0;
}

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

namespace AtCoder.Abc
{
    class QuestionD
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var s = Console.ReadLine();

            s = s.Replace("2017", "2018");


            Console.WriteLine(s);

            Console.Out.Flush();
        }
    }
}


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

int main(void) {
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int abc[3];
  for (int i = 0; i < 3; ++i) abc[i] = 0;
  for (auto c : S) abc[c - 'a']++;

  int diff = 0;
  diff = max(diff, abs(abc[0] - abc[1]));
  diff = max(diff, abs(abc[0] - abc[2]));
  diff = max(diff, abs(abc[1] - abc[2]));
  if (diff <= 1)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}


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

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n , k ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	return cout<<n-k+1<<"\n" , 0 ;
}		

Measured memory_bytes: 3648
package main

import (
        "fmt"
        "math"
)

func main() {
        var n int
        fmt.Scan(&n)
        min := math.MaxInt32
        for i := 1; i <= n/2; i++ {
                tmp := sumValues(i, n-i)
                if tmp < min {
                        min = tmp
                }
        }
        fmt.Printf("%d\n", min)
}

func sumValues(x, y int) int {
        return sum(x) + sum(y)
}
func sum(i int) (r int) {
        tmp := i
        for tmp != 0 {
                r += tmp % 10
                tmp /= 10
        }
        return r
}

Measured memory_bytes: 512
N=int(input())
for h in range(3500,0,-1):
    for n in range(3500,0,-1):
        X=(4/N)-(1/h)-(1/n)
        if X>0 and X<=1:
            w=int(1/X)
            if 4/N==(1/h+1/n+1/w):
                print(h,n,w)
                exit()

Measured memory_bytes: 42956
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
ll n,m;
ll a[200010],b[200010];
ll sp,sn;
bool is0=0;
ll md=1e9+7;
ll ai[200010],bi[200010];
int main()
{
	cin >>n>>m;
	for (int i=0;i<n;i++)
	{
		int x;
		cin >>x;
		if (!x) is0=1;
		else if (x<0) b[sn++]=x;
		else a[sp++]=x;
	}
	sort(a,a+sp),reverse(a,a+sp);
	int ok=-1;
	for (int i=0;i<=min(m,sn);i++)
	{
		if (i+sp<m) continue;
		if (i%2==0)
		{
			ok=i;
			break;
		}
	}
	if (ok==-1 || sp+sn<m)
	{
		if (is0)
		{
			cout <<"0";
			return 0;
		}
		vector<ll> v;
		for (int i=0;i<sp;i++) v.push_back(a[i]);
		for (int i=0;i<sn;i++) v.push_back(-b[i]);
		sort(v.begin(),v.end());
		ll res=1;
		for (int i=0;i<m;i++) res=(res*v[i])%md;
		cout <<(md-res)%md;
		return 0;
	}
	for (int i=0;i<sn;i++) b[i]=-b[i];
	sort(b,b+sn);
	reverse(b,b+sn);
	ai[0]=bi[0]=1;
	for (int i=0;i<sp;i++) ai[i+1]=(a[i]*ai[i])%md;
	for (int i=0;i<sn;i++) bi[i+1]=(b[i]*bi[i])%md;
	ll res=-1e18;
	bool fl=0;
	for (int i=ok;i<=min(m,sn);i+=2)
	{
		//cout <<i<<" "<<b[i-1]*b[i-2]<<" "<<a[sp-i]*a[sp-i+1]<<" ##\n";
		if (i==ok || b[i-1]*b[i-2]>a[m-i]*a[m-i+1])
			res=(bi[i]*ai[m-i])%md;
		else break;
	}
	cout <<res;
	return 0;
}

Measured memory_bytes: 6836
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

xs, ys, xt, yt = map(int, input().split())
n = int(input())

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[-1]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)

#ここから
G = csgraph_from_dense(edge,null_value=-1)
print(dijkstra(G,indices=0)[1])

Measured memory_bytes: 63872
def result(w)
  r = ""
  if w <= 48.0 then r = "light fly"
  elsif w <= 51.0 then r = "fly"
  elsif w <= 54.0 then r = "bantam"
  elsif w <= 57.0 then r = "feather"
  elsif w <= 60.0 then r = "light"
  elsif w <= 64.0 then r = "light welter"
  elsif w <= 69.0 then r = "welter"
  elsif w <= 75.0 then r = "light middle"
  elsif w <= 81.0 then r = "middle"
  elsif w <= 91.0 then r = "light heavy"
  else r = "heavy"
  end
  r
end

while line = gets do
  w = line.chop.to_f
  puts result(w)
end


Measured memory_bytes: 6848
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define INF 999999999
#define rep(i,m,n) for(int i = m;i < n;i++)
#define pb(n) push_back(n)
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl;
#define Vecpr vector<pair<lli,lli>>
#define mod 1000000007;
int main() {
  lli A,B,C,D=0,E=0,F=INF,N,M;
    cin >> N;
    vector<int>P(N);
    rep(i,0,N){
      cin >> P[i];
      D+=P[i];
    }
    cin >> M;
    vector<int>Q(M),R(M);
    rep(i,0,M)cin >> Q[i] >> R[i];
    rep(i,0,M){
      E=D;
      E=E-P[Q[i]-1]+R[i];
      Out(E);
    }
}

Measured memory_bytes: 256
n=gets.to_i
a=gets.split(" ")
a.unshift("0")
a.push("0")

sum=0
for i in 0..n do
  sum+=(a[i].to_i-a[i+1].to_i).abs
end

for i in 1..n do
  puts sum-(a[i-1].to_i-a[i].to_i).abs-(a[i].to_i-a[i+1].to_i).abs+(a[i-1].to_i-a[i+1].to_i).abs
end
  

Measured memory_bytes: 11012
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

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

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};



void solve(){
    ll a,b,c,x,ans=0;
    cin>>a>>b>>c>>x;
    rep(i,a+1){
        rep(j,b+1){
            rep(k,c+1){
                if(500*i+100*j+50*k==x) ans++;
            }
        }
    }
    cout<<ans<<endl;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
    
    solve();

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;
namespace CP
{
    class Atria
    {
        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());
            int[] s = ReadLine().Split(' ').Select(int.Parse).ToArray();
            long ans = long.MaxValue;
            for (int select = -100; select <= 100; select++)
            {
                ans = Min(ans, s.Sum(x => (x - select)* (x - select)));
            }
            WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll n,w;
  cin >> n >> w;
  vector<pair<ll,ll>> a(n);
  for(int i = 0;i < n;i++){
    ll noww,nowv;
    cin >> noww >> nowv;
    a[i] = make_pair(noww,nowv);
  }
  vector<vector<ll>> dp(n,vector<ll>(100001));
  for(int i = 0;i < n;i++)for(int j = 0;j < 100001;j++)dp[i][j] = pow(10,18);
  for(int i = 0;i < 100001;i++){
    if(a[0].second >= i)dp[0][i] = a[0].first;
    //cout << dp[0][i] << " " << a[0].first << endl;
  }
  for(int i = 1;i < n;i++){
    for(int j = 0;j < 100001;j++){
      if(a[i].second >= j)dp[i][j] = min(dp[i][j],a[i].first);
      if(j - a[i].second >= 0)dp[i][j] = min(dp[i][j],dp[i - 1][j - a[i].second] + a[i].first);
      dp[i][j] = min(dp[i][j],dp[i - 1][j]);
    }
  }
  ll res = 0;
  for(int i = 0;i < n;i++){
    for(int j = 0;j < 100001;j++){
      if(dp[i][j] <= w)res = max(res,(ll)j);
    }
  }
  /*for(int i = 0;i < n;i++){
    for(int j = 0;j < 29;j++){
      if(dp[i][j] <= 10000000)cout << dp[i][j] << " ";
      else cout << "!" << " ";
    }
    cout << endl;
  }*/
  cout << res << endl;
  /*for(int i = 0;i < n;i++){
    for(int j = 0;j < w + 1;j++){
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }*/
}

Measured memory_bytes: 79488
n = int(input())
while n != 0:
    A = 0
    B = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a > b:
            A += a + b
        elif a < b:
            B += a + b
        else:
            A += a
            B += b
    print('{} {}'.format(A, B))
    n = int(input())

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<string> input(H);
  vector<string> output(H);
  for(int i=0; i<H; i++){
    cin >> input.at(i);
    output.at(i)="#"+input.at(i)+"#";
  }
  string t;
  for(int i=0; i<W+2; i++){
    t+="#";
  }
  cout << t <<endl;
  for(int j=0; j<H; j++){
    cout << output.at(j) << endl;
  }
  cout << t <<endl;
}


Measured memory_bytes: 256
n = int(input())
s = list(input() for _ in range(n))
m,a,r,c,h = 0,0,0,0,0

for ch in s:
  if ch[0] == 'M':
    m += 1
  elif ch[0] == 'A':
    a += 1
  elif ch[0] == 'R':
    r += 1
  elif ch[0] == 'C':
    c += 1
  elif ch[0] == 'H':
    h += 1

ans = 0
cnt = 0
if m != 0:
  cnt += 1
if a != 0:
  cnt += 1
if r != 0:
  cnt += 1
if c != 0:
  cnt += 1
if h != 0:
  cnt += 1
if cnt < 3:
  print(0)
else:
  ans += m * a * r
  ans += m * a * c
  ans += m * a * h
  ans += m * r * c
  ans += m * r * h
  ans += m * c * h
  ans += a * r * c
  ans += a * r * h
  ans += a * c * h
  ans += r * c * h
  print(ans)

Measured memory_bytes: 9784
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class GFG
{
    static public void Main()
    {
        try
        {
            var n = int.Parse(Console.ReadLine());
            //var input1 = Console.ReadLine().Split(' ');
            //var n = int.Parse(input1[0]);
            //var L = int.Parse(input1[1]);

            //var aar = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();

            Candies(n);
        }
        catch (Exception ex)
        {
            Console.Write(ex);
        }
    }

    static void Candies(int n)
    {

        var ans = n * (n + 1) / 2;

        Console.Write(ans);

    }

}

Measured memory_bytes: 13140
import java.io.*;

class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str;
while(!(str=br.readLine()).equals("0")){
int n=Integer.parseInt(str);
long max=-1000000;
int[] s=new int[n+1];
s[0]=0;
for(int i=0;i<n;i++){
int m=Integer.parseInt(br.readLine());
s[i+1]=s[i]+m;
}
for(int a=0;a<n;a++){
for(int b=a+1;b<=n;b++){
max=Math.max(max,s[b]-s[a]);
}
}
System.out.println(max);
}
}
}

Measured memory_bytes: 21932
import Control.Monad(join)

type Coord = (Int, Int)

flipZigzag :: [[a]] -> [[a]]
flipZigzag l =
    let
        f :: Bool -> [[a]] -> [[a]]
        f _ [] = []
        f False (x:xs) = x:(f True xs)
        f True (x:xs) = (reverse x):(f False xs)
    in f False l

zipWithIndex :: [a] -> [(Int, a)]
zipWithIndex = zip [1..]

zipAdj :: [a] -> [(a, a)]
zipAdj x = zip x $ tail x

third :: (a, b, c) -> c
third (a, b, c) = c

collectParity :: [(Coord, Int)] -> [(Coord, Coord)]
collectParity array =
    let 
        foldFunction :: (Int, Coord, [(Coord, Coord)]) -> (Coord, Int) -> (Int, Coord, [(Coord, Coord)])
        foldFunction (parity, prevCoord, cum) (coord, elem) =
            let
                newCum = if parity /= 0 then (prevCoord, coord):cum else cum
            in
                (mod (parity + elem) 2, coord, newCum)
        firstCoord = fst $ head array
        firstElem = snd $ head array
    in
        third $ foldl foldFunction (mod firstElem 2, firstCoord, []) (drop 1 array)

main = do
    [h, w] <- map read . words <$> getLine
    a <- sequence (replicate h $ (map read . words <$> getLine))
    let indexZipped = fmap (\(rowIndex, row) -> fmap (\(columnIndex, elem) -> ((rowIndex, columnIndex), elem)) (zipWithIndex row)) (zipWithIndex a)
    let array = join $ flipZigzag $ indexZipped
    let operations = collectParity array
    let flattendOperations = fmap (\((y1, x1), (y2, x2)) -> unwords $ fmap show [y1, x1, y2, x2]) operations
    putStrLn $ show $ length flattendOperations
    sequence $ fmap putStrLn flattendOperations


Measured memory_bytes: 107516
#include<bits/stdc++.h>
using namespace std;
 
 
int main() {
    string str;
    cin >> str;
 
    int len = str.size();
    for( int n = 0 ; n < len ; ++n ){
        if( n %2 == 0 ){
            cout<<str[n];
        }
 
    }
    return 0;
}

Measured memory_bytes: 512
import sys
readline = sys.stdin.readline

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

P1 = [0, 2, 3, 1, 1, 3, 2, 0]
P2 = [0, 2, 3, 1, 1, 0, 2, 3]
Q = [0, 1, 1, 0]
def grey(N, K):
    if K%2 == 0:
        return False
    if N == 1:
        return [0, 1]
    if N == 2:
        return [0, 2, 3, 1]
    
    if N == K:
        L = grey(N-2, K-2)
        P = P1*((1<<(N-3))-1) + P2
        return [(1<<(N-2))*P[i]|L[i//4] for i in range(1<<N)]
    
    L = grey(N-1, K)
    return [(1<<(N-1))*Q[i%4]|L[i//2] for i in range(1<<N)]

def calc(N, y):
    k = popcount(y)
    pu = [0]*N
    cnt0 = k
    cnt1 = 0
    for i in range(N):
        if (1<<i)&y:
            pu[cnt1] = i
            cnt1 += 1
        else:
            pu[cnt0] = i
            cnt0 += 1
    return pu

def restore(N, x, pu):
    res = 0
    for i in range(N):
        if (1<<i)&x:
            res |= 1<<pu[i]
    return res
    
    
N, A, B = map(int, readline().split())

K = popcount(A^B)
Ans = grey(N, K)

if Ans:
    pu = calc(N, A^B)
    Ans = [A^(restore(N, a, pu)) for a in Ans]
    print('YES')
    print(*Ans)
else:
    print('NO')

Measured memory_bytes: 56384
//大文字->小文字 tolower(),逆はtoupper()
//int a = stoi(c); 文字列をintへ
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//等価なものに変換する思考
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//配列はvector<>を使う：意味わからないエラーがなくなる。
//背反な事象にちゃんとわける
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

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

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

//円周率
const double PI = 3.14159265358979323846;

int main() {
	int H, W; cin >> H >> W;
	char a[H + 2][W + 2];
	for (int i = 0; i < H + 2; i++) {
		for (int j = 0; j < W + 2; j++) {
			if (i == 0 || i == H + 1)a[i][j] = '#';
			else if (j == 0 || j == W + 1)a[i][j] = '#';
			else cin >> a[i][j];
		}
	}

	rep(i, H + 2) {
		rep(j, W + 2) {
			cout << a[i][j];
		}
		cout << endl;
	}
}

Measured memory_bytes: 256
import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();
        int X = sc.nextInt();
        int n;
        int O;
        int T;
        int G;
        int z;
        int y;

        T = X / 500;
        n = X / 1000;
        if (X % 1000 == 0) {
            O = A * n;
        } else {
            O = A * (n + 1);
        }
        if (X % 500 == 0) {
            G = B * T;

        } else {
            G = B * (T + 1);
        }
        int mini = 99999999;
        int nedan;

        for (int i = 0; i < 1000; i++) {
            if (X >= i * 1000) {
                z = X - (i * 1000);

                y = z / 500;
                if (z % 500 == 0) {
                    nedan = i * A + y * B;

                } else {
                    nedan = i * A + (y + 1) * B;
                }
                if (mini >= nedan) {
                    mini = nedan;
                }
            }
        }

        if (O < G && O < mini) {

            System.out.println(O);

        } else if (G < O && G < mini) {

            System.out.println(G);

        } else if (mini <= O && mini <= G) {
            System.out.println(mini);
        }
    }

}



Measured memory_bytes: 26364