akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ll long long
#define db double

using namespace std;

const int MAXN = 300010;
const ll INF = 10000000000000000ll;

int n, m;
int stk[MAXN], top = 0;
ll a[MAXN], sum[MAXN], dp[MAXN], h[MAXN], tmp[MAXN];
ll fo[MAXN], ba[MAXN], chose_ans[MAXN];//fo forward; ba backward

db getK(int a, int b)
{
	return 1.0 * (dp[a] + sum[a] + 1ll * a * (a - 1) / 2 - dp[b] - sum[b] - 1ll * b * (b - 1) / 2) / (a - b);
}

void getsum()
{
	sum[0] = 0;
	for (int i = 1; i <= n; i++)
		sum[i] = a[i] + sum[i - 1];
}

void getdp()
{
	getsum();
	stk[top = 1] = 0;
	for (int i = 1; i <= n; i++)
	{
		while (top > 1 && getK(stk[top], stk[top - 1]) <= i) top--;
		int now = stk[top];
		dp[i] = max(dp[i - 1], dp[now] + 1ll * (i - now) * (i - now + 1) / 2 + sum[now] - sum[i]);
		while (top > 1 && getK(stk[top], stk[top - 1]) < getK(i, stk[top])) top--;
		stk[++top] = i;
	}
}

void rev()
{
	for (int i = 1; i <= n / 2; i++)
		swap(a[i], a[n - i + 1]);
}

void solve(int l, int r)
{
	if (l == r)
	{
		h[l] = max(h[l], fo[l - 1] + 1 + ba[l + 1] - a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	stk[top = 1] = l - 1;
	for (int i = l; i <= mid - 1; i++)
	{
		while (top > 1 && getK(stk[top], stk[top - 1]) < getK(i, stk[top])) top--;
		stk[++top] = i;
	}
	for (int i = mid; i <= r; i++)
	{
		while (top > 1 && getK(stk[top], stk[top - 1]) <= i) top--;
		int now = stk[top];
		tmp[i] = dp[now] + (i - now) * (i - now + 1) / 2 + sum[now] - sum[i] + ba[i + 1];
	}
	for (int i = r - 1; i >= mid; i--) tmp[i] = max(tmp[i], tmp[i + 1]);
	for (int i = mid; i <= r; i++) h[i] = max(h[i], tmp[i]);
	solve(l, mid); solve(mid + 1, r);
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	getdp();
	for (int i = 1; i <= n; i++) fo[i] = dp[i];
	rev();
	getdp();
	for (int i = 1; i <= n; i++) ba[n - i + 1] = dp[i];
	rev();
	
	for (int i = 1; i <= n; i++) chose_ans[i] = -INF;
	
	for (int i = 1; i <= n; i++) dp[i] = fo[i];
	getsum();
	for (int i = 1; i <= n; i++) h[i] = -INF;
	solve(1, n);
	for (int i = 1; i <= n; i++)
		chose_ans[i] = max(chose_ans[i], h[i]);
	
/*	for (int i = 1; i <= n; i++)
		cout << h[i] << ' ';
	cout << endl;*/
	
	rev();
	for (int i = 1; i <= n; i++) swap(fo[i], ba[i]);
	for (int i = 1; i <= n / 2; i++)
	{
		swap(fo[i], fo[n - i + 1]);
		swap(ba[i], ba[n - i + 1]);
	}
	for (int i = 1; i <= n; i++) dp[i] = fo[i];
	getsum();
	for (int i = 1; i <= n; i++) h[i] = -INF;
	solve(1, n);
	for (int i = 1; i <= n; i++)
		chose_ans[i] = max(chose_ans[i], h[n - i + 1]);
	
	rev();
	for (int i = 1; i <= n; i++) swap(fo[i], ba[i]);
	for (int i = 1; i <= n / 2; i++)
	{
		swap(fo[i], fo[n - i + 1]);
		swap(ba[i], ba[n - i + 1]);
	}
	
/*	for (int i = 1; i <= n; i++)
		cout << chose_ans[i] << ' ';
	cout << endl;
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ' << fo[i] << ' ' << ba[i] << endl;*/	
	
	cin >> m;
	while (m--)
	{
		int p, x;
		cin >> p >> x;
		cout << max(fo[p - 1] + ba[p + 1], chose_ans[p] + a[p] - x) << endl;
	}
	return 0;
}


Measured memory_bytes: 21376
n,w = map(int,input().split())
wait = [""]*n
value = [""]*n
for i in range(n):
    wait[i],value[i] = map(int,input().split())
# print(wait,value)

# dp[i][j]=(i番目までの品物を、重さがj以下になるように選んだときの価値の最大値)を考える
# dp[i][j]は、
# i番目の品物を使うとき      i−1番目までで重さが(j − w[i])以下の価値の最大値 + v[i]
#              使わないとき  i−1番目までの重さがj以下の価値の最大値

knapsak = [0]*(n+1)
for i in range(n+1):
    knapsak[i] = [0]*(w+1)

for i in range(1,n+1):
    for j in range(0,w+1):
        # print(j-wait[i-1])
        if(j-wait[i-1]>= 0):
            knapsak[i][j] = max(knapsak[i-1][j],knapsak[i-1][j-wait[i-1]]+value[i-1])
            # print(knapsak)
        else:
            knapsak[i][j] = knapsak[i-1][j]
print(knapsak[n][w])

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

int main(void){
    // Your code here!
    string S;cin>>S;
    if(S[S.size()-1]!='s'){
        S+='s';
    }
    else{
        S+="es";
    }
    cout<<S<<endl;
    return 0;
}


Measured memory_bytes: 3628
// by newbiechd
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

// DELETE the debugging information!
#define debug(x) std::cerr << #x << " = " << (x) << std::endl

const int N_MAX = 100003;
int a[N_MAX];
long long dp[N_MAX][2];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", a + i);
  dp[0][1] = -1;
  for (int i = 1; i <= n; ++i) {
    dp[i][0] = std::max(dp[i - 1][0] + a[i] / 2, dp[i - 1][1] + (a[i] + 1) / 2);
    dp[i][1] = std::max(dp[i - 1][0] + (a[i] - 1) / 2, dp[i - 1][1] + a[i] / 2);
    if (a[i] == 0)
      dp[i][1] = -1;
  }
  printf("%lld\n", std::max(dp[n][0], dp[n][1]));
  return 0;
}


Measured memory_bytes: 2176
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

int N;
vector<string> S;


int main()
{
	
	cin >> N;
	
	S = vector<string>(N);


	unordered_map<string, int> map;
	for (int i = 0; i < N; i++) {
		cin >> S[i];

		string hs = S[i];
		sort(hs.begin(),hs.end());
		map[hs]++;

	}

	long long ans = 0;

	for (pair<string, int> i : map) {
		long long c = i.second;
		ans += c * (c - 1) / 2;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 17700
r,g,b,n=map(int, input().split())

sum=0

for i in range(n//r+1):
    for j in range((n-i*r)//g+1):
        if (n-i*r-j*g)%b==0:
            sum=sum+1
        #    print(i*r,j*g,(n-(i*r)-(j*g))%b)

print(sum)


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

#define ll long long
#define ul 100000
// #define ul 10
#define fo(i,a,b) for(int i=a;i<b;++i)
#define mod 1000000007
#define sff fflush(stdout)
string str;
int f(int x)
{
	cout<<x<<'\n';
	sff;
	cin>>str;
	if(str=="Vacant") return -1;
	else if(str=="Male") return 0;
	else return 1;
}

int main()
{
	int n;
	cin>>n;
	int low=0,hi=n-1;
	int lo,h,xx;
	lo = f(low);
	if(lo==-1) return 0;
	h = f(hi);
	if(h==-1) return 0;
	while(str!="Vacant")
	{
		int mid = (low+hi)/2;
		xx = f(mid);
		if(xx==-1) return 0;
		int l = mid - low - 1;
		int r = hi - mid - 1;
		if((xx==lo)&&(l%2==0)) {hi = mid; h =xx;}
		else if((xx!=lo)&&(l%2==1)) {hi = mid; h =xx;}
		else if((xx==h)&&(r%2==0)) {low = mid; lo=xx;}
		else if((xx!=h)&&(r%2==1)) {low = mid; lo=xx;}
	}
}

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define cinv(n,vec) V vec(n);for(auto&v:vec)cin>>v;
#define int long long
#define itn int
#define pb push_back
#define m_p make_pair
#define m_t meke_tuple
#define p_p(a,b) pb(m_p(a,b))
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(all(a));reverse(all(a))
#define UNIQUE(a) a.erase(unique(all(a)),a.end())
#define SZ(a) (ll)(a.size())
#define ENDL cout<<endl
#define debg(a) cout<<#a<<" "<<a<<endl;
#define debgp(a) cout<<#a<<" "<<a.fi<<" : "<<a.se<<endl
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define out(a) cout<<(a)<<endl
#define cont const auto
#define fi first
#define se second
#define Vec vector
#define P pair
#define VV(type,name,y,x,a) vector<vector<type>> name = vector<vector<type>>(y,vector<type>(x,a))
typedef long long ll;
typedef double D;
typedef long double LD;
typedef string str;
typedef vector<ll> V;
typedef pair<ll,ll> Pi;
typedef vector<Pi> VP;
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
typedef priority_queue<ll,vector<ll>,greater<>> PQ;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n,k;
  cin>>n>>k;
  V a(n);
  rep(i,n)cin>>a[i];
  
  int ans=-INF,mx=min(n,k);
  rep(i,mx+1){ //左からとる
    rep(j,mx-i+1){ //右からとる
      if(i==0&&j==0)continue;
      int res=k-i-j; //残りの操作回数
      PQ tmp; //優先度キューで持ている宝石の価値を管理
      rep(x,i)tmp.push(a[x]); //要素の追加はO(logN)
      rep(x,j)tmp.push(a[n-1-x]);
      while(res--){
        if(tmp.top()<0)tmp.pop(); //価値が0未満ならpop
        else break;
        if(tmp.empty())break;
      }
      int sum=0;
      while(!tmp.empty()){ //価値の計算
        sum+=tmp.top();
        tmp.pop();
      }
      chmax(ans,sum); //更新
    }
  }
  out(ans);

  
  
  
  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

#define MAX 25

typedef struct {
  int P;
  int L;
  int R;
}tree;

tree T[MAX];
int N;

int height(int);

int max(int,int);

int main()
{
  int n,i,j,id,k,kodomo,irekae,depth,degree,hei;

  scanf("%d",&n);



  /*入力編*/

  for(i=0;i<n;i++)/*一旦全部の親を-1にする。*/
    {
      T[i].P=-1;
      T[i].R=-1;
      T[i].L=-1;
    }
  
  for(i=0;i<n;i++)
    {
      scanf("%d",&id);/*idとkの入力*/
      scanf("%d",&T[id].L);
      kodomo=T[id].L;
      if(kodomo!=-1)T[kodomo].P=id;
      scanf("%d",&T[id].R);
      kodomo=T[id].R;
      if(kodomo!=-1)T[kodomo].P=id;
    }

  /*出力編*/

  for(i=0;i<n;i++)
    {

      printf("node %d: ",i);/*ノード番号出力*/
 
      printf("parent = %d, ",T[i].P);/*親出力*/
      
      if(T[i].P==-1) printf("sibling = -1, ");
      else if(i==T[ T[i].P ].L)printf("sibling = %d, ",T[ T[i].P ].R);
      else if(i==T[ T[i].P ].R)printf("sibling = %d, ",T[ T[i].P ].L);

      
      degree=0;
      if(T[i].L!=-1)degree++;
      if(T[i].R!=-1)degree++;
      printf("degree = %d, ",degree);
      
      depth=0;
      id=i;
      
      while(1)
	{
	  if(T[id].P==-1)break;
	  
	  depth++;
	  
	  irekae=id;
	  id=T[irekae].P;
	}

      printf("depth = %d, ",depth);/*深さ出力*/  

      N=n;
      
      hei=height(i);

      printf("height = %d, ",hei);
      
      if(T[i].P==-1)
	{
	  printf("root\n");
	}
      else if(T[i].L==-1&&T[i].R==-1)
	{
	  printf("leaf\n");
	}
      else
	{
	  printf("internal node\n");
	}
    }
      
  return 0;
}
  
int height(int i)
{
  if(T[i].L==-1&&T[i].R==-1)return 0;
  else if(T[i].L==-1)return 1+height(T[i].R);
  else if(T[i].R==-1)return 1+height(T[i].L);
  return 1+max( height(T[i].L), height(T[i].R) );
}

int max(int l,int r)
{
  if(l>r)return l;
  else return r;
}
  

  


Measured memory_bytes: 2056
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,a,s=0;
	cin>>n>>m;
	while(m){
		cin>>a;
		s+=a;
		m--;
	}
	if(s>(n+m)) cout<<"-1";
	else cout<<n+m-s<<endl;
	return 0;
} 

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
long n,f[100005],k,a[100005];
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for (long i=1;i<=n;i++) cin>>a[i];
    for (long i=1;i<=k;i++)
    {
        for (long j=1;j<=n;j++)
        {
            if (i-a[j] >=0 && f[i-a[j]]==0) f[i]=1;
        }
    }
    if (f[k]==1) cout<<"First";
    else cout<<"Second";
}


Measured memory_bytes: 1024
n=input()

if n[len(n)-1] == "3":
    print("bon")

elif n[len(n)-1] == "0" or n[len(n)-1] == "1" or n[len(n)-1] == "6" or n[len(n)-1] =="8":
    print("pon")

else:
    print("hon")

Measured memory_bytes: 9052
# 参考URL https://note.nkmk.me/python-union-find/
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, q = map(int, input().split())

    uf = UnionFind(n)

    ans = []
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            uf.union(u, v)
        else:
            if uf.same(u, v):
                ans.append(1)
            else:
                ans.append(0)
    
    for i in ans:
        print(i)

main()

Measured memory_bytes: 80052
n=int(input())
b_list=[int(i) for i in input().split()]

if n==2:
    print(b_list[0]*2)
    exit()

ans=b_list[0]+b_list[-1]

for i in range(n-2):
    ans+=min(b_list[i],b_list[i+1])

print(ans)

Measured memory_bytes: 3060
N=int(input())
# アルファベットをずらす数
S=input()
# 復号した文字列の結果を格納
result = ""
for c in S:
    # 復号する処理
    if ord('a') <= ord(c) <= ord('z') :
        result = result + chr(abs(((ord(c) + N + ord('a')) % 26)) + ord('a'))
    else :
        result = result + chr(abs(((ord(c) + N + ord('A')) % 26)) + ord('A'))

print (result)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin>>S;
  int count=0;
  int N=S.size();
  while(N>0){
    
    if(N==1){
      count++;
      break;
    }
    if(N==2){
      if(S.at(0)==S.at(1)){
        count+=1;
        break;
      }
      if(S.at(0)!=S.at(1)){
        count+=2;
        break;
      }
    }
    if(S.at(N-1)!=S.at(N-2)){
      S.pop_back();
    }
    else{
      S.pop_back();
      S.pop_back();
      S.pop_back();
      count++;
    }
    
    count++;
    N=S.size();
  }
  cout<<count<<endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

const int mod = 2011;
int pow(int n, int m){
	int res = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
int inv(int n){
	return pow(n, mod - 2);
}

int n;
string in[20];
int expr(int&, int&, int&, int&);


int f(int y, int x, int Y, int X){
	int res = -1;
	for(int i = y; i < Y; i++) if(in[i][x] != '.'){
		res = res == -1 ? i : -2;
	}
	return res;
}
int powexpr(int &y, int &x, int &Y, int &X){
	int p, res;
	while(x < X && (p = f(y, x, Y, X)) < 0) x++;
	if(in[p][x] == '('){
		x++;
		res = expr(y, x, Y, X);
		x++;
	}
	else{
		res = 0;
		while(x < X && isdigit(in[p][x])) res *= 10, res += in[p][x++] - '0';
	}
	if(x < X){
		p = f(y, x, Y, X);
		if(p >= 0){
			int e = 0;
			while(x < X && isdigit(in[p][x])) e *= 10, e += in[p][x++] - '0';
			res = pow(res, e);
		}
	}
	return res;
}
int factor(int &y, int &x, int &Y, int &X){
	int p;
	bool sign = 0;
	while(1){
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		if(x + 1 < X && in[p][x] == '-' && in[p][x + 1] == '.') sign ^= 1, x += 2;
		else break;
	}
	if(x + 1 < X && in[p][x] == '-' && in[p][x + 1] == '-'){
		int q = x;
		while(q < X && in[p][q] == '-') q++;
		
		int a = y, b = x + 1, c = p, d = q - 1;
		int num = expr(a, b, c, d);
		
		a = p + 1, b = x + 1, c = Y, d = q - 1;
		int den = expr(a, b, c, d);
		
		num = num * inv(den) % mod;
		x = q + 1;
		return sign ? (mod - num) % mod : num;
	}
	return ((sign ? -1 : 1) * powexpr(y, x, Y, X) % mod + mod) % mod;
}
int term(int &y, int &x, int &Y, int &X){
	int res = inf, p;
	while(1){
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		int a = factor(y, x, Y, X);
		res = res == inf ? a : (a * res) % mod;
		p = 0;
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		if(p < 0 || x >= X || in[p][x] != '*') break;
		x++;
	}
	return res;
}
int expr(int &y, int &x, int &Y, int &X){
	int res = 0, p, op = 0;
	while(1){
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		int a = term(y, x, Y, X);
		(res += op ? mod - a : a) %= mod;
		p = 0;
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		if(p < 0 || x >= X || in[p][x] != '+' && in[p][x] != '-') break;
		op = in[p][x] == '-';
		x++;
	}
	return res;
}

int main(){
	while(cin >> n, n){
		rep(i, n) cin >> in[i];
		int y = 0, x = 0, Y = n, X = in[0].size();
		cout << expr(y, x, Y, X) << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
#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 N;
  int K;
  int X;
  int Y;
  cin >>N>>K>>X>>Y;
  if(N<=K) {
cout <<N*X << endl;
  }
else {
cout <<K*X+(N-K)*Y << endl;
}
}

Measured memory_bytes: 256
#include <stdio.h>

#define MAX_N 100

int bubbleSort(int A[], int N);

int main() {
  int N;
  int A[MAX_N];
  int cnt;
  int i;

  scanf("%d", &N);
  for(i = 0; i < N; ++i) scanf("%d", A+i);

  cnt = bubbleSort(A, N);
  for(i = 0; i < N; ++i) printf("%d%c", A[i], " \n"[i==N-1]);
  printf("%d\n", cnt);

  return 0;
}

int bubbleSort(int A[], int N) {
  int cnt = 0;
  int tmp;
  int flag = 1;
  int j;

  while(flag) {
    flag = 0;
    for(j = N-1; j > 0; --j) {
      if(A[j] < A[j-1]) {
        tmp = A[j];
        A[j] = A[j-1];
        A[j-1] = tmp;
        flag = 1;
        ++cnt;
      }
    }
  }
  return cnt;
}




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

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  while (m--) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<int> r(n, -1);
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    auto i = q.front();
    q.pop();
    for (auto j : g[i]) {
      if (r[j] == -1) {
        r[j] = i;
        q.push(j);
      }
    }
  }

  cout << "Yes" << endl;
  for (int i = 1; i < n; i++) cout << r[i] + 1 << endl;
}


Measured memory_bytes: 10060
import java.util.*;

public class Main {
	//static boolean f;
	static long min;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		/* 入力の受け取り
		 * String s = sc.next();
		 * int a = sc.nextInt();
		 * long a = sc.nextLong();
		 */
		
		// 文字列(String)を文字(char)に分解
		// char[] s_char = s.toCharArray();
		
		long n = sc.nextLong();
		long k = sc.nextLong();
		
		min = n%k;
		min = Math.min(min, Math.abs(min-k));
		
		System.out.println(min);
		
		/*
		 * if(f)
		 *	System.out.println("Yes");
		 * else
		 * 	System.out.println("No");
		 */
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,n1) for(int i=0;i<n1;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<'YES'<<endl;}else{cout<<'NO'<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
#define PI 3.141592653589793
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<int,ll> Pil;
typedef pair<ll,ll> Pll;
typedef pair<string,int> Psi;
typedef pair<Psi,int> Psii;

const ll inf=1000000007;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

vector<Pii> v[100001];
ll dp2[300000][60]={};
int main() {
	int h,w;
	cin>>h>>w;
	int d[20][20]={};
	queue<Piii>  que;
	int r=0;
	rep(i,h){
		rep(j,w){
			char s;
			cin>>s;
			if(s=='#')d[i][j]=1;
		}
	}
	rep(i,h){
		rep(j,w){
			que.push(Piii(Pii(i,j),1));
			int dp[20][20]={};
			int r2=0;
			while(!que.empty()){
				Piii p=que.front();que.pop();
				int x=p.first.first;
				int y=p.first.second;
				int cost=p.second;
				if(cost>=dp[x][y]&&dp[x][y]>0)continue;
				if(d[x][y]>0)continue;
				dp[x][y]=cost;
				if(x>0)que.push(Piii(Pii(x-1,y),cost+1));
				if(x<h-1)que.push(Piii(Pii(x+1,y),cost+1));
				if(y>0)que.push(Piii(Pii(x,y-1),cost+1));
				if(y<w-1)que.push(Piii(Pii(x,y+1),cost+1));
				r2=max(r2,cost);
//				printf("%d %d\n",x,y);
			}
//			cout<<r2<<endl;
			r=max(r,r2);
		}
	}
	cout<<(r-1)<<endl;
	return 0;
}


Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pu push  //  adds the value to the last of the queue 
#define lld long long int
#define ins insert /// used in set to insert the values 
#define adv advance  /// used to increment the iterator
#define mp make_pair
#define fi first
#define se second
#define all(c) c.begin(),c.end()
#define PI 3.1415926
//a power n mod p
long long int modp(lld a,lld p,lld n)
{
    int d[100];
    int i,j,k,l;
    if(n==0) return 1;
    for(i=0;n>=1;i++)
    {
        d[i]=n%2;
        n/=2;
    }
    l=i;
    long long int e=1;
    if(d[0]==1) e*=(a%p);
    for(i=1;i<l;i++)
    {
        a*=a;
        a=a%p;
        if(d[i]==1) 
        {
            e*=a;
            e=e%p;
        }
    }
    return e%p;
}
lld modInverse(lld n, lld p) 
{ 
    return modp(n, p, p-2); 
}

long long int nCrModPFermat(lld n, lld r,lld p) 
{ 
   // Base case 
   if (r==0) 
      return 1; 
    
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
    lld fac[n+1]; 
    fac[0] = 1; 
    for (lld i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
  
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
}


long long int gcd(lld b,lld a)
{
    if(a<b) return gcd(a,b);
    if(a%b==0) return b;
    return gcd(a%b , b);
}
int main()
{
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
    lld n,ans,i,j,k,l;
    cin>>n;
    ans=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            for(k=1;k<=j;k++)
            {
                l=gcd(gcd(j,k),i);
                if(i!=j)
                {
                    if(j!=k) ans+=6*l;
                    else ans+=3*l;
                }
                else
                {
                    if(j!=k) ans+=3*l;
                    else ans+=(l);
                }

            }
        }
    }
    cout<<ans;
    return 0;
}

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

int main(){
    int K;
    cin >> K;
    int A[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout << A[K-1] << endl;
    return 0;
}


Measured memory_bytes: 768
using System;
    using System.Linq;
    using System.Collections.Generic;
    using static System.Math;

    public class Program
    {
        public static void Main(string[] args)
        {
            string input = Console.ReadLine();
            foreach (char n in input.Select(m => m).Select((x, y) => new { word = x, idx = y }).Where(o => o.idx % 2 == 0 || o.idx == 0).Select(p => p.word).ToList()) Console.Write("{0}",n);
        }
    }

Measured memory_bytes: 15968
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define sf scanf
#define pf printf
#define pb push_back
#define llu unsigned long long
#define U unsigned int
#define SIZE 100005
#define pie 3.14159265358979323
#define minuss 1e-6
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define BIG 100000000
#define N 10000
int main()
{



   char str[100];
   cin>>str;
   if(str[2]==str[3] && str[4]==str[5])
     cout<<"Yes"<<endl;
    else
         cout<<"No"<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>& p) { os << p.first << " " << p.second; return os; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) { for(int i = 0; i < (int) v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : ""); return os; }

void solve()
{
    int x, y, z; cin >> x >> y >> z;
    swap(x, y);
    swap(x, z);
    cout << x << " " << y << " " << z << endl;
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

n = int(input())
T = list(map(int, input().split()))
m = int(input())
A = [list(map(int, input().split())) for _ in range(m)]
_sum = sum(T)

for a in A:
    print(_sum - T[a[0]-1] + a[1])


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

int gcd(int x, int y) {
	if (x < y) {
		swap(x, y);
	}
	int r = x % y;
	while (r!=0) {
		x = y;
		y = r;
		r = x % y;
	}
	return y;
}

int main() {
	int a, b, k; cin >> a >> b>> k;
	int c = 0;
	int g = gcd(a, b);
	int ans;
	for (int i = 1; i <= g; i++) {
		if (g % i == 0) {
			c++;
			if (c == k) {
				ans = g / i;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 764
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int main(void){
    char *l,*m,t[33];
    char s[500][33];
    int c[500]={0},n=0,cnt=0,max=0,lm=0;
    while(scanf("%s",s[n++])!=EOF)if(s[n-1][0]=='0')break;
    for(int i=n;i>0;i--){
        for(int j=0;j<i;j++){
            if(i!=j && strcmp(s[i],s[j])<0){
                strcpy(t,s[i]);
                strcpy(s[i],s[j]);
                strcpy(s[j],t);
            }
        }
    }
    for(int i=0;i<n;i++){
        int ln = strlen(s[i]);
        if(ln>lm){
            m=s[i];
            lm = ln;
        }
        if(i==0)continue;
        if(strcmp(s[i],s[i-1])==0){
            cnt++;
            if(cnt>max){
                max=cnt;
                l = s[i];
            }
        }else cnt = 0;
    }
    printf("%s %s\n",l,m);
    return 0;
}

Measured memory_bytes: 1004
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<math.h>
#define REP(i,a) for (int i = 0;i < (a);++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(obj) (obj).begin,(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
    ll a,b;
    cin >> a >> b;
    ll answer = 0;
    ll g = gcd(a,b);

    map<ll,ll>m;
    for(ll i=2;i*i <= a;i++){
        while(g%i==0){
            g/=i;
            m[i]++; 
        }
    }
    if(g!=1)m[g]=1;
    cout << m.size()+1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fori(j,n) for(ll i=j;i<n;i++)
#define forb(n,j) for(ll i=n-1;i>=0;i--)
#define endl "\n"
#define pb push_back
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define vec vector<ll>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int32_t main()
{
    IOS;
    ll a,b;
    cin>>a>>b;
    cout<<a*b;
    return 0;
}




Measured memory_bytes: 3644
<?php
list($n) = ints();
echo isHarshad($n) ? 'Yes' : 'No';

function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}

function isHarshad($n)
{
    return $n % array_sum(array_map('intval', str_split((string) $n))) === 0;
}


Measured memory_bytes: 4728
#include<stdio.h>

int main(void)
{
  int a = 0;
  int b = 0;
  int data[3] = {0};
  int buffer = 0;
  int i = 0, j = 0;

  scanf("%d %d", &a, &b);

  data[0] = a + b;
  data[1] = a - b;
  data[2] = a * b;

  for(i = 0; i< 2; i++){
    for(j = 1; j< 3; j++){
      if(data[i] < data[j]){
        buffer = data[i];
        data[i] = data[j];
        data[j] = buffer;
      }
    }
  }

  printf("%d\n", data[0]);

  return 0;

}


Measured memory_bytes: 128
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
#素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n,p = inpl()
soin = prime_factorize(p)
cnt = Counter(soin)
res = 1
for key in cnt.keys():
    if cnt[key] >= n:
        res *= key ** (cnt[key]//n)
print(res)


Measured memory_bytes: 3948
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i=init;i<(n);i++)

int main() {
    string s;
    cin >> s;
    int ans = INF;
    repi(i, s.size() - 2, 0) {
        int num = 0;
        repi(j, i + 3, i) {
            num += pow(10,i - j + 2) * (s[j] - '0');
        }
        ans = min(ans,abs(753 - num));
    }
    cout << ans << endl;
    return 0;
}

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

int main () {
  int N,K;
  cin >> N >> K;
  
  int sum = 1;
  
  rep(i, N) {
    if(sum > K )
      sum += K;
    else 
      sum *= 2;
    
  }
  
  cout << sum << endl;
    
}

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

ans=[]
tmp=N%K

for i in range(10**18):
    tmp=abs(tmp-K)
    #print(tmp)
    #print(i)
    if i == 0:
        ans.append(tmp)
    elif tmp>ans[i-1]:
        ans.append(tmp)
        break
    else:
        ans.append(tmp)

print(min(ans))


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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
int main( void ){
	// initialize();
	string str; cin >> str;
	rep(i,0,3){
		if (str.c_str()[i] == '7'){
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#include <numeric>
#include <math.h>
using namespace std;
typedef pair<int, int>P;

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	if (n % 2 != 0) {
		cout << "No";
		return 0;
	}
	int m = n / 2;
	
	for (int i = 0; i < m; i++) {
		if (s[i] != s[i + m]) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
}

Measured memory_bytes: 256
#include <stdio.h>          // printf(), scanf()
#include <stdbool.h>

#define MAX_N 50000
#define MAX_SQRT_N 224
#define MAX_P 5140

bool f[MAX_N + 1];
int count[MAX_N + 1];
int primes[MAX_P];
int np;

int
main(int argc, char **argv)
{
	int i, j;

	for (i = 0; i <= MAX_N; ++i)
		f[i] = true;

	for (i = 2; i <= MAX_SQRT_N; ++i)
	{
		if (f[i])
		{
			for (j = i + i; j <= MAX_N; j += i)
				f[j] = false;
		}
	}

	np = 0;
	for (i = 2; i <= MAX_N; ++i)
	{
		if (f[i])
			primes[np++] = i;
	}

	for (i = 0; primes[i] <= MAX_N / 2; ++i)
	{
		for (j = i; primes[i] + primes[j] <= MAX_N; ++j)
			count[primes[i] + primes[j]]++;
	}

	while (true)
	{
		int n;
		scanf("%d", &n);
		if (n == 0)
			break;

		printf("%d\n", count[n]);
	}

	return 0;
}

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

#define MAXN 100010
#define ll long long
#define mod 1000000007

using namespace std;

int n;

int a[MAXN];

int main() {
	for (int i = 1; i <= 3; i++) scanf("%d", &a[i]);
	sort(a + 1, a + 4);
	if (a[1] == a[2] && a[1] != a[3] && a[2] != a[3]) cout << "Yes" << endl;
	else if (a[1] == a[3] && a[1] != a[2] && a[2] != a[3]) cout << "Yes" << endl;
	else if (a[2] == a[3] && a[1] != a[2] && a[1] != a[3]) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
} 

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

#if !__has_include(<optional>)
#include <experimental/optional>
namespace std {
  template <typename T> using optional = std::experimental::optional<T>;
  constexpr auto nullopt = std::experimental::nullopt;
}
#endif

template <typename Cost = int> class Edge{
public:
  int from,to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost): to(to), cost(cost){}
  Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}

  Edge rev() const {return Edge(to,from,cost);}
  
  friend std::ostream& operator<<(std::ostream &os, const Edge &e){
    os << "(FROM: " << e.from << "," << "TO: " << e.to << "," << "COST: " << e.cost << ")";
    return os;
  }
};

template <typename T> using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T> using Tree = std::vector<std::vector<Edge<T>>>;

template <typename C, typename T> void add_edge(C &g, int from, int to, T w){
  g[from].push_back(Edge<T>(from, to, w));  
}

template <typename C, typename T> void add_undirected(C &g, int a, int b, T w){
  g[a].push_back(Edge<T>(a, b, w));
  g[b].push_back(Edge<T>(b, a, w));
}


template <typename T>
struct DirectShortestCycle{
  const int N;
  std::optional<std::vector<int>> cycle;

  void bfs(int i, const Graph<T> &g, int &min_len){
    std::queue<int> q;
    q.push(i);

    std::vector<int> dist(N), pre(N);
    std::vector<bool> visited(N);

    while(not q.empty()){
      int cur = q.front(); q.pop();

      if(visited[cur]) continue;
      visited[cur] = true;

      for(auto &e : g[cur]){
        if(e.to == i){
          if(dist[cur] < min_len){
            min_len = dist[cur];
            cycle = std::vector<int>();

            int j = cur;
            while(1){
              (*cycle).push_back(j);
              if(j == i) break;
                
              j = pre[j];
            }

            std::reverse((*cycle).begin(), (*cycle).end());
          }

          return;
        }
        
        if(not visited[e.to]){
          dist[e.to] = dist[cur] + 1;
          pre[e.to] = cur;
          q.push(e.to);
        }
      }
    }
  }
  
  DirectShortestCycle(const Graph<T> &g): N(g.size()){
    int min_len = INT_MAX;
    
    for(int i = 0; i < N; ++i){
      bfs(i, g, min_len);
    }
  }
};


int main(){
  int N,M;
  while(std::cin >> N >> M){

    Graph<int> g(N);
    for(int i = 0; i < M; ++i){
      int a,b; std::cin >> a >> b;
      --a, --b;
      add_edge(g, a, b, 1);
    }

    auto res = DirectShortestCycle<int>(g).cycle;

    if(!res){
      std::cout << -1 << std::endl;
    }else{
      std::cout << (*res).size() << std::endl;
      for(auto x : *res){
        std::cout << x+1 << std::endl;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 384
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	var s string
	fmt.Scan(&s, &n)
	m := map[string]int{}
	for i := 0; i < len(s); i++ {
		for j := 1; j <= n; j++ {
			if i+j > len(s) {
				break
			}
			m[s[i:i+j]]++
		}
	}
	a := []string{}
	for k, _ := range m {
		a = append(a, k)
	}
	sort.Strings(a)
	fmt.Println(a[n-1])
}
func min(a, b int) int {
	if b < a {
		return b
	}
	return a
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  const Int MAX = 2e5;
  vector<Int> ok(MAX,0);
  for(Int i=2;i<MAX;i++){
    Int res=1;
    for(Int j=2;j*j<=i;j++){
      if(i%j) continue;
      res*=j;
      if(j*j!=i) res*=i/j;
      if(res>=i*2) break;
    }
    ok[i]=res>=i*2;
  }

  vector<Int> ans(MAX,0);
  for(Int i=1;i<MAX;i++) ans[i]=ans[i-1]+ok[i];

  Int q;
  cin>>q;
  for(Int i=0;i<q;i++){
    Int x;
    cin>>x;
    cout<<ans[x]<<"\n";
  }
  cout<<flush;
  return 0;
}



Measured memory_bytes: 5872
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int dp[101][101];
int grid[101][101];
int B = 1, W = 0;

int main() {
  int h, w;
  cin >> h >> w;
  for (int y = 0; y < h; ++y) {
    string s; cin >> s;
    for (int x = 0; x < w; ++x) {
      if (s[x] == '#') grid[y][x] = B;
      else grid[y][x] = W;
    }
  }
  int c = grid[0][0];
  dp[0][0] = c;
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (i == 0 && j == 0) continue;
      int c = grid[i][j];
      dp[i][j] = 1000;
      if (i > 0) {
        int bc = grid[i-1][j];
        if (c == bc) dp[i][j] = dp[i-1][j];
        else dp[i][j] = dp[i-1][j]+1;
      }
      if (j > 0) {
        int bc = grid[i][j-1];
        if (c == bc) dp[i][j] = min(dp[i][j], dp[i][j-1]);
        else dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
      }
    }
  }
  cout << (dp[h-1][w-1]+1)/2 << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
  int x; cin >> x;
  vector<int> kyu {1800, 1600, 1400, 1200, 1000, 800, 600, 400};
  for (int i = 0; i < kyu.size(); i++) {
    if (x >= kyu[i]) {
      cout << (i + 1) << endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<string>
using namespace std;
int main()
{
	//int n;
	//cin >> n;
	//if (n % 10 == 3)
	//	cout << "bon";
	//else if (n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8)
	//	cout << "pon";
	//else
	//	cout << "hon";

	int n = 0;
	cin >> n;
	string duck;
	cin.ignore();
	getline(cin, duck);
	if (n > duck.size())
		n = duck.size();
	for (int i = 0; i < n; i++) {
		cout << duck[i];
	}
	if(n<duck.size())
	cout << "...";
    return 0;
}



Measured memory_bytes: 3628
import java.util.Scanner;

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

		int n;
		while(!((n = scan.nextInt()) == 0)) {
			int a = 0;
			int b = 0;

			int tb;
			int ta;
			for(int i = 0 ; i < n ; i++) {
				if((ta = scan.nextInt()) == (tb = scan.nextInt())) {

					a += ta;
					b += tb;

				}else if(ta > tb) {
					a += (ta +tb);
				}else {
					b += (ta + tb);
				}
			}
			System.out.println(a +" "+ b);
		}


	}
}



Measured memory_bytes: 56424
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
 
  string s;
  cin>>s;

  if(s.at(0)=='R' && s.at(1)=='R' && s.at(2)=='R')
    cout<<3<<endl;
  else if(s.at(0)=='R' && s.at(1)=='R')
    cout<<2<<endl;
  else if(s.at(1)=='R' && s.at(2)=='R')
    cout<<2<<endl;
  else if(s.at(1)=='R' || s.at(0)=='R' || s.at(2)=='R')
    cout<<1<<endl;
  else
    cout<<0<<endl;

	return 0;
}



Measured memory_bytes: 3624
#include <stdio.h>
#define MAX 10001
#define NIL -1

struct Node{
  int p;
  int l;
  int r;
};

struct Node T[MAX];
int n;
int D[MAX];
int H[MAX];

int max(int h1, int h2){

  if( h1 < h2 )
    return h2;

  return h1;

}

int Height(int u){

  int h1 = 0;
  int h2 = 0;

  if( T[u].r != NIL ){
    h1 = Height(T[u].r ) + 1;
  }

  if( T[u].l != NIL ){
    h2 = Height(T[u].l) + 1;
  }

  return H[u] = max(h1,h2);

}

void Depth(int i, int d){
  if( i == NIL ) return;
  D[i] = d;
  Depth(T[i].l,d+1);
  Depth(T[i].r,d+1);

}

int Sibling(int i){

  if( T[i].p == NIL ){
    return NIL;
  }

  if( T[T[i].p].l != i && T[T[i].p].l != NIL ){
    return T[T[i].p].l;
  }

  if( T[T[i].p].r != i && T[T[i].p].r != NIL ){
    return T[T[i].p].r;
  }

  return NIL;

}

void print(int i){

  int deg = 0;

  printf("node %d: ",i);
  printf("parent = %d, ",T[i].p);
  printf("sibling = %d, ",Sibling(i));

  if( T[i].l != NIL ){
    deg++;
  }

  if( T[i].r != NIL ){
    deg++;
  }

  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[i]);
  printf("height = %d, ",H[i]);

  if( T[i].p == NIL ){
    printf("root\n");
  }else if( T[i].l == NIL && T[i].r == NIL ){
    printf("leaf\n");
  }else{
    printf("internal node\n");
  }

}

int main(int argc, char const *argv[]) {

  int v,l,r;
  int root = 0;
  int i,j;

  scanf("%d",&n);

  for( i = 0 ; i < n ; i++ ){
    T[i].p = T[i].l = T[i].r = NIL;
  }

  for( i = 0 ; i < n ; i++ ){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l = l;
    T[v].r = r;

    if( l != NIL ){
      T[l].p = v;
    }
    if( r != NIL ){
      T[r].p = v;
    }

  }

  for( i = 0 ; i < n ; i++ ){

    if( T[i].p == NIL ){
      root = i;
    }

  }


  Depth(root,0);
  Height(root);

  for( i = 0 ; i < n ; i++ ){
    print(i);
  }

  return 0;
}

Measured memory_bytes: 624
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

//N??\???????´???°?????????O(N log log N)
int N = 300000;
vector<int> primes;
vector<bool> is_prime(N + 1, true);
void init() {
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i <= N; i ++) {
                if (is_prime[i]) {
                        primes.push_back(i);
                        for (int j = i + i; j <= N; j += i) is_prime[j] = false;
                }
        }
}

int main() {
        int n;
        init();
        while (scanf("%d", &n), n) {
                int ans = upper_bound(primes.begin(), primes.end(), 2 * n) - upper_bound(primes.begin(), primes.end(), n);
                printf("%d\n", ans);
        }
        return 0;
}

Measured memory_bytes: 3304
import collections
A,B = map(int,input().split())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c1 = collections.Counter(prime_factorize(A))
c2 = collections.Counter(prime_factorize(B))
c1_list = list(c1.keys())
c2_list = list(c2.keys())
c1_c2 = set(c1_list) & set(c2_list)
print(len(c1_c2)+1)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main(){
    int n;
    cin >>n;
    vector<ll> a(n);
    rep(i,n) cin >>a[i];
    sort(all(a));

    ll ans = 0;

    // pat.1
    int idx = (n-1)/2;
    vector<ll> v;
    v.pb(a[idx]);

    int l = 0, r = n-1;
    rep(i,n/2){
        if(r==idx) break;
        v.pb(a[r]);
        --r;

        if(l==idx) break;
        v.pb(a[l]);
        ++l;
    }

    ll t = 0;
    rep(i,n-1) t+=abs(v[i]-v[i+1]);
    ans = max(ans, t);

    // pat.2
    idx = n/2;
    v.clear();
    v.pb(a[idx]);

    l = 0;
    r = n-1;
    rep(i,n/2){
        if(l==idx) break;
        v.pb(a[l]);
        ++l;

        if(r==idx) break;
        v.pb(a[r]);
        --r;
    }

    t = 0;
    rep(i,n-1) t+=abs(v[i]-v[i+1]);
    ans = max(ans, t);

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2168
n = int(input())
weight_lists = list(map(int, input().split()))

tmp = 1000000
for i in range(1, n, 1):
    s_1 = weight_lists[:i]
    s_2 = weight_lists[i:]

    s_1_sum = 0
    for j in s_1:
        s_1_sum += j

    s_2_sum = 0
    for k in s_2:
        s_2_sum += k

    diff = abs(s_1_sum - s_2_sum)
    if diff < tmp:
        tmp = diff
        ans = tmp

print(ans)

Measured memory_bytes: 9204
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N,M;
    cin >> N >> M;
    vector<ll> a(M),b(M);
    vector<vector<ll>> c(M);
    ll t;
    rep(i,M){
        cin >> a[i] >> b[i];
        rep(j,b[i]){
            cin >> t;
            c[i].push_back(--t);
        }
    }
    vector<ll> dp(5000,1e18);
    dp[0] = 0;
    rep(i,M){
        ll now = 0;
        rep(j,b[i]){
            now |= (1LL << c[i][j]);
        }
        for(ll j=0;j<(1LL<<N);j++){
            cmin(dp[now | j], dp[j] + a[i]);
        }
    }
    if(dp[(1LL << N) - 1] == 1e18){
        cout << -1 << endl;
    }else{
        cout << dp[(1LL << N) - 1] << endl;
    }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
 

 int main(){
  int n ; cin>> n ;
  int all = 196470 ;
  while(n--){
    int a ,b,c ; cin>> a>>b>> c ;
   int ans=0 ;
   rep(i,a-1){
     if(i%3==2) ans +=200 ;
     else ans += 195;
   }
   rep(i,b-1){
     if(a%3==0){
       ans += 20 ;
     }
     else{
       if(i%2==0) ans+= 20 ;
       else ans += 19 ;
     }
   }

   ans += c;
   ans-- ;
   cout<< all -ans<<endl ;
  }
   return 0 ;
 }




Measured memory_bytes: 3068
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::string s;
    std::cin >> s;
    int n = s.size() + 1;
    std::vector<std::pair<char, int>> v { { '<', 0 } };
    for (auto c : s) {
        if (v.empty() || v.back().first != c) v.emplace_back(c, 1);
        else v.back().second++;
    }

    if (v.back().first == '<') v.emplace_back('>', 0);

    i64 ret = 0;
    for (int i = 0; i < v.size(); i += 2) {
        i64 p = v[i].second, q = v[i + 1].second;
        ret += p * (p - 1) / 2 + q * (q - 1) / 2;
        ret += std::max(p, q);
    }

    std::cout << ret << std::endl;

    return 0;
}


Measured memory_bytes: 3068