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

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

struct Edge{
	int src,dst;
	Edge(){}
	Edge(int s,int d):src(s),dst(d){}
};
typedef vector<vector<Edge>> Graph;

void DFS(const Graph& g,int p,int v,int d,vi& tour,vi& ds)
{
	tour.push_back(v);
	ds.push_back(d);
	for(auto e:g[v]) if(e.dst!=p){
		DFS(g,e.src,e.dst,d+1,tour,ds);
		tour.push_back(v);
		ds.push_back(d);
	}
}

int NextPow2(int x)
{
	x--;
	for(int i=1;i<32;i*=2) x|=x>>i;
	return x+1;
}
const int I=numeric_limits<int>::max();
int F(int a,int b){return min(a,b);}

struct SegmentTree{
	int size;
	vi data,index;
	SegmentTree(int n):size(NextPow2(n)),data(size,I),index(size*2){
		iota(size+all(index),0);
		peri(i,1,size) index[i]=index[i*2];
	}
	SegmentTree(const vi& a):size(NextPow2(a.size())),data(size,I),index(size*2){
		copy(all(a),begin(data));
		iota(size+all(index),0);
		peri(i,1,size){
			int u=index[i*2],v=index[i*2+1];
			index[i]=data[u]==F(data[u],data[v])?u:v;
		}
	}
	void Update(int i,int x){
		data[i]=x;
		for(i+=size;i/=2;){
			int u=index[i*2],v=index[i*2+1];
			index[i]=data[u]==F(data[u],data[v])?u:v;
		}
	}
	int QueryIndex(int a,int b,int i,int l,int r){
		if(b<=l || r<=a) return -1;
		if(a<=l && r<=b) return index[i];
		int u=QueryIndex(a,b,i*2,l,(l+r)/2),v=QueryIndex(a,b,i*2+1,(l+r)/2,r);
		if(u==-1 || v==-1) return u!=-1?u:v;
		return data[u]==F(data[u],data[v])?u:v;
	}
	int QueryIndex(int a,int b){
		return QueryIndex(a,b,1,0,size);
	}
};

int main()
{
	for(int n;cin>>n && n;){
		Graph g(n);
		rep(u,n){
			int k; cin>>k;
			rep(i,k){
				int v; cin>>v;
				g[u].emplace_back(u,v);
				g[v].emplace_back(v,u);
			}
		}
		vi tour,ds;
		DFS(g,-1,0,0,tour,ds);
		vi fs(n,INF);
		rep(i,tour.size()) if(fs[tour[i]]==INF) fs[tour[i]]=i;
		
		SegmentTree st(ds);
		int q; cin>>q;
		rep(_,q){
			int u,v; cin>>u>>v;
			if(fs[u]>fs[v]) swap(u,v);
			cout<<tour[st.QueryIndex(fs[u],fs[v]+1)]<<endl;
		}
	}
}

Measured memory_bytes: 19284
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#define REP(i,N) for(auto i = 0; i<N; i++)
#include <climits>

#include <cmath>
using namespace std;

int in(){
    int temp;
    scanf("%d",&temp);
    return temp;
}


int main() {

   int a = in();
   int b = in();
   int h = in();
  
	cout << (a + b ) * (h/2) << endl;
   return 0;
    
}





Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args)throws Exception{
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		for(int i=0;i<N;i++){
			int A=stdIn.nextInt();
			if(A%2==0)
				if(A%3!=0&&A%5!=0){
					System.out.println("DENIED");
					System.exit(0);
				}
		}
		System.out.println("APPROVED");
	}
}


Measured memory_bytes: 21844
n,m,l=map(int,input().split())
a=list()
for i in range(n):
    a.append(list(map(int,input().split())))
b=list()
for i in range(m):
    b.append(list(map(int,input().split())))

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

for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j]+=a[i][k]*b[k][j]
    print(' '.join(map(str, c[i])))


Measured memory_bytes: 6904
#include<stdio.h>

int main(void){
int r,c,y[1000][1000];
int i,j;
scanf("%d %d",&r,&c);
for(i = 0; i < r; i++){
   int sumt=0;
   for( j = 0; j < c; j++){
    scanf("%d",&y[i][j]);
    sumt += y[i][j];
   }
    y[i][c] = sumt;
   }

for(i = 0; i < c+1; i++){
   int sumy=0;
   for( j = 0; j < r; j++){
    sumy += y[j][i];
   }
    y[r][i] = sumy;
   }

   
for(i = 0; i < r+1; i++){
   for(j = 0; j < c; j++){
    printf("%d ",y[i][j]);
   }
    printf("%d\n",y[i][c]);
}

return 0;
}



Measured memory_bytes: 2100
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main() {
	int n,ans =0,a=0,b=0,c=0;
	string s;
	string ab = "AB";
	cin >> n;
	vector<string>v;
	for (int i =0; i < n; i++) {
		cin >> s;
		v.emplace_back(s);
	}

	for (auto i : v) {
		auto r = i.begin();
		while (r != i.end()) {
			
			r = search(r, i.end(), ab.begin(),ab.end());
			if (r != i.end()) {
				r++; ans++;
			}
			
		}
		if (i.front() == 'B' && i.back() == 'A')c++;
		else if (i.front() == 'B')b++;
		else if (i.back() =='A')a++;
	}
	if (c != 0) {
		ans +=  c - 1;
		if (a != 0) {
			ans++;
			a--;
		}
		if (b != 0) {
			ans++;
			b--;
		}
	}
	ans += min(a, b);
	cout << ans << endl;
}

Measured memory_bytes: 768
N, M = map(int, input().split())
_input = []
for i in range(M):
    _input.append(list(map(int,input().split())))

_input.sort(key=lambda x: x[1])

removed = []

for a,b in _input:
    flag = False
    for i in removed:
        if a <= i < b:
            flag = True
            break
    if not flag:
        removed.append(b-1)

print(len(removed))

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

int v[100];
int w[100];
int dp[101][10001];
int main(int argc, char* argv){
	int N, W;
	int i, j;
	scanf("%d %d", &N, &W);
	for(i = 0; i < N; i++){
		scanf("%d %d", &v[i], &w[i]);
	}

	for(i = 0; i < W; i++){
		dp[0][i] = 0;
	}

	for(i = 0; i < N; i++){
		for(j = 0; j <= W; j++){
			if(j - w[i] >= 0 && dp[i][j - w[i]] + v[i] > dp[i][j]){
				dp[i + 1][j] = dp[i][j - w[i]] + v[i];
			}else{
				dp[i + 1][j] = dp[i][j];
			}
		}
	}
/*
	for(i = 0; i <= N; i++){
		for(j = 0; j <= W; j++){
			printf("%3d", dp[i][j]);
		}
		printf("\n");
	}
*/

	printf("%d\n", dp[N][W]);
}

Measured memory_bytes: 4968
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int MOD = 1000000007;
int INF = numeric_limits<int>::max() / 2;
typedef pair<int, int> P;


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

  int N, W;
  cin >> N >> W;
  P p[N];
  rep(i,N){
    cin >> p[i].first >> p[i].second;
  }
  int dp[N+1][100010]{};
  rep(i,N+1){
    rep(j, 100010){
      dp[i][j] = INF;
    }
  }
  rep(i,N+1) dp[i][0] = 0;
  for(int i=1;i<=N;i++){
    for(int j=0;j<=100010;j++){
      if(j >= p[i-1].second) dp[i][j] = min(dp[i-1][j], dp[i-1][j-p[i-1].second] + p[i-1].first);
      else dp[i][j] = min(dp[i-1][j], dp[i-1][0] + p[i-1].first);
    }
  }
  int ans = 0;
  rep(i,100010){
    if(dp[N][i] <= W) ans = max(i, ans);
  }

  cout << ans << endl;

}

Measured memory_bytes: 79232
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
long long read() {
  long long x = 0, w = 1;
  char ch = getchar();
  while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar();
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * w;
}
const int Max_n = 5e5 + 5, mod = 998244353;
int n, m, ans;
int fac[Max_n], ifac[Max_n];
int f[Max_n];
int ksm(int a, int b) {
  int res = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) res = 1ll * res * a % mod;
  return res;
}
int C(int n, int m) { return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod; }
int main() {
  n = read(), m = read();
  if (n > m) swap(n, m);
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= m; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  ifac[m] = ksm(fac[m], mod - 2);
  for (int i = m - 1; i; i--) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
  for (int i = 0; i <= n; i++) {
    f[i] = 1ll * C(n, i) * C(m, i) % mod * fac[i] % mod;
    f[i] = 1ll * f[i] * ksm(m + 1, n - i) % mod * ksm(n + 1, m - i) % mod;
  }
  for (int i = 0; i <= n; i++)
    ans = ((ans + ksm(-1, i & 1) * f[i]) % mod + mod) % mod;
  cout << ans;
}


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

#define int long long int
#define vi vector<int>
#define pii pair<int,int>
#define pq priority_queue<int>
#define pb push_back
#define INF 1000000000000000000
#define modu 1000000007
#define out(a) cout<<a
#define out2(a,b) cout<<a<<" "<<b
#define out3(a,b,c) cout<<a<<" "<<b<<" "<<c
#define in(a) cin>>a
#define in2(a,b) cin>>a>>b
#define in3(a,b,c) cin>>a>>b>>c
#define spc <<" "
#define nl <<"\n"
#define khubTesh(ti) cout<<"Case "<<ti<<": "

void testCase(int ti,int ans){
    khubTesh(ti);
    out(ans) nl;
}

void debug(string pr,vector<int> var)
{
    cout<<pr;
    for(int i=0;i<var.size();i++) cout<<" "<<var[i];
    cout<<endl;
}

void faster(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
}

int n,k;
int ans[100010];
int  h[100010];

int dp(int at){
    if(at==n) return 0;
    if(ans[at]!=INF) return ans[at];
    int mn=INF;
    for(int i=1;i<=k;i++){
        if(at+i>n) break;
        mn=min(mn,dp(at+i)+abs(h[at+i]-h[at]));
    }
    return ans[at]=mn;
}

int32_t main(){
    faster();
    //Now I will start writing codes and start preparation to get errors
    cin>>n>>k;
    for(int i=1;i<=n;i++) ans[i]=INF,cin>>h[i];

    cout<<dp(1);
    
    
    return 0;
}


Measured memory_bytes: 6528
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------

int main(void){

    ll a, b, k;
 
    cin >> a >> b >> k;
 
    if(a >= k){
        cout << a - k << " " << b << endl;
    } else {
        cout << 0 << " " << max(0LL, b - (k - a)) << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> cnt(N);
  rep(i, N-1) {
    cin >> A[i];
    A[i]--;
    cnt[A[i]]++;
  }
  rep(i, N) cout << cnt[i] << endl;
  return 0;
}


Measured memory_bytes: 4844
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<functional>
using namespace std;

int n,m,h,k;
typedef pair<int,int> P;
vector<P> ber;
long long int x[1001],ax[1001];
long long int sc[1001],scn[1001];
long long int yk[100001][2],ys[100001][2];
int resn;
long long int res;
long long int ans;

int main(void){
	while(1){
		scanf("%d%d%d%d",&n,&m,&h,&k);
		if(n==0 && m==0 && h==0 && k==0)break;
		memset(x,0,sizeof(x));
		memset(ax,0,sizeof(ax));
		memset(sc,0,sizeof(sc));
		memset(scn,0,sizeof(scn));
		memset(yk,0,sizeof(yk));
		memset(ys,0,sizeof(ys));
		ber.clear();
		res=0;
		ans=0;
		for(int i=1;i<=n;i++){
			scanf("%lld",&sc[i]);
			scn[i]=sc[i];
			x[i]=i;
			ax[i]=i;
		}
		for(int i=0;i<m;i++){
			int a,b;
			scanf("%d%d",&a,&b);
			ber.push_back(P(b,a));
		}
		sort(ber.begin(),ber.end());
		for(int i=0;i<m;i++){
			swap(x[ber[i].second],x[ber[i].second+1]);
		}
		resn=-1;
		for(int i=m-1;i>=0;i--){
			ys[i][0]=scn[ber[i].second],ys[i][1]=scn[ber[i].second+1];
			swap(x[ber[i].second],x[ber[i].second+1]);
			swap(scn[ber[i].second],scn[ber[i].second+1]);
			yk[i][0]=x[ber[i].second],yk[i][1]=x[ber[i].second+1];
			if(yk[i][0]<=k && yk[i][1]>k){
				long long int sa=ys[i][1]-ys[i][0];
				if(sa>=res)resn=i,res=sa;
			}
			if(yk[i][1]<=k && yk[i][0]>k){
				long long int sa=ys[i][0]-ys[i][1];
				if(sa>=res)resn=i,res=sa;
			}
		}
		for(int i=0;i<m;i++){
			if(i!=resn)swap(ax[ber[i].second],ax[ber[i].second+1]);
		}
		for(int i=1;i<=n;i++){
			if(ax[i]<=k)ans+=sc[i];
		}
		printf("%lld\n",ans);
	}
    return 0;
}

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

int main() {
 string s;
  cin>>s;
  if(s.at(2) == s.at(3) && s.at(4) == s.at(5)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
/*
======================
[     ___T_          ]
[    | 6=6 | =>HI :-)] 
[    |__o__|         ]
[ >===]__o[===<      ]
[     [o__]          ]
[      .".           ]
[      |_|           ]
[                    ]
======================
 */

#include<bits/stdc++.h>
using namespace std;
using lli = int64_t;
int main(){
	 ios::sync_with_stdio(false);
	 cin.tie(nullptr);
	 cout.tie(nullptr);
	 int T = 1;
	 for(int t = 1; t <= T; t++){
		 int n;
		 cin >> n;
		 map<string,int> count;
		 int max_count = 0;
		 for(int i = 1; i <= n; i++){
			 string in;
			 cin >> in;
			 count[in] += 1;
			 max_count = max(max_count,count[in]);
		 }
		 vector<string> items;
		 for(auto item : count){
			 if(item.second == max_count){
				 items.push_back(item.first);
			 }
		 }
		 sort(items.begin(),items.end());
		 for(auto item : items){
			 cout << item << "\n";
		 }
	 }
}



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

 
int main() {

    int n,d;
    int x[20][20];
    cin>>n>>d;
    rep(i,n) {
        rep(j,d) {
            cin>>x[i][j];
        }
    }
    double dis=0;
    int count=0;
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            for(int k=0;k<d;k++) {
                dis+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
                if(k==d-1) {
                    dis=sqrt(dis);
                    if(double(dis-int(dis))==0)    count++;
                    dis=0;
                }
            }
        }
    }
    cout<<count<<endl;
    
 return 0;
}

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

const int inf=1<<30;
int memo[1<<16][16], t[17][17], n;

#define min(x, y) ((x)<(y)?(x):(y))

int func(int S, int k)
{
    int i, j, res=memo[S][k];
    if (S==(1<<n)-1) return 0;
    if (res) return res;

    res=inf;
    for(i=0;i<n;++i) if (!(S&(1<<i))) {
        int minT=t[i+1][0];
        for(j=0;j<n;++j) if (j!=i && (S&(1<<j))) minT=min(minT, t[i+1][j+1]);
        res=min(res, func(S|(1<<i), i)+minT);
    }
    return memo[S][k]=res;
}

int main(void)
{
    while (scanf("%d", &n), n) {
        int i, j, res;
        for(i=1;i<=n;++i) for(j=0;j<=n;++j) scanf("%d", &t[i][j]);
        res=inf;
        memset(memo, 0, sizeof(memo));
        res=min(res, func(0, 0));
        printf("%d\n", res);
    }
    return 0;
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(1e5 + 5);

int n;

ll a[MAX_N];

ll ans;

int main(void) {
  // Here your code !
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%lld", &(a[i]));
  }

  int cnt = 0;

  for (int i = 0; i < n; ++i) {
    if (a[i] < 0) cnt += 1;
  }

  ll whole = 0LL;
  ll min_a = INF;

  for (int i = 0; i < n; ++i) {
    whole += abs(a[i]);
    min_a = min(min_a, abs(a[i]));
  }

  if (cnt % 2 == 0) {
    ans = whole;
  } else {
    ans = whole - 2 * min_a;
  }

  printf("%lld\n", ans);

  return 0;
}


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

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int h,w,n,sr,sc;
    string s, t;
    cin>>h>>w>>n>>sr>>sc>>s>>t;
    sr--; sc--;

    bool isok = true;
    int left = 0, right = w;
    if (s.back() == 'L') left++;
    if (s.back() == 'R') right--;
    for (int i = n - 2; i >= 0; i--) {
        if (t[i] == 'L') right = min(right+1, w);
        if (t[i] == 'R') left  = max(left-1, 0);
        if (s[i] == 'L') left++;
        if (s[i] == 'R') right--;
        if (left >= right)  isok = false;
    }

    if (!isok or sc < left or right <= sc) {
        cout << "NO" << endl;
        return 0;
    }

    left = 0, right = h;
    if (s.back() == 'U') left++;
    if (s.back() == 'D') right--;
    for (int i = n - 2; i >= 0; i--) {
        if (t[i] == 'U') right = min(right+1, h);
        if (t[i] == 'D') left  = max(left-1, 0);
        if (s[i] == 'U') left++;
        if (s[i] == 'D') right--;
        if (left >= right) isok = false;
    }

    if (!isok or sr < left or right <= sr) {
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 920
import numpy as np
N,D=map(int,input().split())
X=[np.array(input().split(),dtype=np.int64) for _ in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        d=((X[i]-X[j])*(X[i]-X[j])).sum()
        dd=int(round(d**.5))
        if d==dd*dd:
            ans +=1
print(ans)


Measured memory_bytes: 26912
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int out[200100];
vector<int> gr[200100];
queue<int> s;
int main()
{
	int n,m,a,b;
	cin>>n>>m;
	rep(i,m){
		cin>>a>>b;gr[a].pb(b);gr[b].pb(a);
	}
	memset(out,-1,sizeof(out));out[1]=0;
	s.push(1);
	while(!s.empty()){
		int v=s.front();s.pop();
		rep(i,gr[v].size()){
			int w=gr[v][i];
			if(out[w]>=0) continue;
			s.push(w);out[w]=v;
		}
	}
	cout<<"Yes"<<endl;
	REP(i,2,n+1) cout<<out[i]<<endl;
}


Measured memory_bytes: 13256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M = map(int, input().split())
    bridge = []
    uni = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        bridge.append([A,B])
    cnt = N * (N - 1) // 2
    ans = [cnt]
    for i in range(M-1,-1,-1):
        A, B = bridge[i]
        if uni.same(A,B):
            ans.append(cnt)
        else:
            cnt -= uni.size(A) * uni.size(B)
            ans.append(cnt)
            uni.union(A,B)
    for i in range(M-1,-1,-1):
        print(ans[i])



if __name__ == "__main__":
    main()

Measured memory_bytes: 97372
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >>n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        string s = to_string(i);
        if(s.size()%2 == 1)
            ans++;
    }
    cout <<ans;
    return 0;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn gcd(min: usize, max: usize) -> usize {
    if min == 0 {}
    let r = max % min;
    if r == 0 {
        return min;
    }
    gcd(r, min)
}

fn main() {
    let n: usize = read();
    if n == 2 {
        println!("{}", std::cmp::max(read::<usize>(), read::<usize>()));
        return;
    }
    let mut vec: Vec<usize> = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    let mut gcd_l = vec![0; n];
    let mut now_l_gcd = vec[0];
    let mut gcd_r = vec![0; n];
    let mut now_r_gcd = vec[n - 1];
    for i in 0..n {
        gcd_l[i] = gcd(now_l_gcd, vec[i]);
        now_l_gcd = gcd_l[i];
        gcd_r[n - i - 1] = gcd(now_r_gcd, vec[n - i - 1]);
        now_r_gcd = gcd_r[n - i - 1];
    }
    let mut max = 1;
    for i in 0..n {
        let gcd = if i == 0 {
            gcd_r[i + 1]
        } else if i == n - 1 {
            gcd_l[i - 1]
        } else {
            gcd(gcd_l[i - 1], gcd_r[i + 1])
        };
        max = std::cmp::max(gcd, max);
    }
    println!("{}", max);
}


Measured memory_bytes: 6396
#include <stdio.h>
int main()
{
    int n;
    int a=0;
    int b=0;
    scanf("%d",&n);
    if(n%100<=12&&n%100>=1)
    {
        a++;
    }
    if((n/100)<=12&&n/100>=1)
    {
        b++;
    }
    if((a+b)==2)
    {
        printf("AMBIGUOUS");
    }
    else if(a==1)
    {
        printf("YYMM");
    }
    else if(b==1)
    {
        printf("MMYY");
    }
    else{
        printf("NA");
    }
    return 0;
}

Measured memory_bytes: 128
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	if(d%2==0)cout<<a-b<<endl;
	else cout<<b+c-a-c<<endl;
}







Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;
#define _GLIBCXX_DEBUG

// bit表現まではいいと思うが，答えがかすりもしない．原因も分からないし人のコードも理解できない．．．
// 2^12までの全パターンを考慮してしまっているので答えが合わない


int main() {
  ll H, W, K;
  cin >> H >> W >> K;
  //vector<ll> a(N);
  vector<vector<char>> data(H + 1, vector<char>(W + 1));
  ll ans = 0;

  for(ll i=1; i <=H; i++){  
    for(ll j=1; j<=W; j++){
      char tmp;
      cin >> tmp;
      data[i][j] = tmp;
    }
  }
  
  for (int tmp = 0; tmp < (1 << H+W); tmp++) {
    bitset<12> s(tmp);
    auto copy_data = data;

    for(ll i=0; i < 12; i++){//赤にするパターン
      
      if(s.test(i)){
        
        if(i<H){
          //行に対応
          for (ll j=1; j <= W; j++){
            copy_data[i+1][j] = 'R';
          }
        }

        if(H<= i){
          for (ll j=1; j <= H; j++){
            copy_data[j][i+1-H] = 'R';
          }
        }

      }     
    
    }
    
    // countする    
    ll count_sum = 0 ;
    for(ll i=1; i <=H; i++){  
      for(ll j=1; j<=W; j++){
        if (copy_data[i][j] =='#') count_sum++;
      }
    }
    if(count_sum == K){
      ans ++;
    }
       
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define NMAX 110000
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
typedef long long int ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int main()
{	
    ll n;
    cin >> n;
    vector<ll> w(n);
    for(int i=0; i<n; i++) cin >> w[i];
    vector<ll> sum;
    sum.assign(n+1,0);
    for(int i=0; i<n; i++) sum[i+1] = sum[i] + w[i];

    ll ans(1000000);
    ll s1, s2;
    for(int i=0; i<n; i++){
        s1 = sum[i];
        s2 = sum[n]-sum[i];
        if((ll)fabs(s1-s2)<ans) ans = (ll)fabs(s1-s2);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))


import math
a,b,h,m=l_in()

t1 = 2*math.pi*(h*60+m)/(12*60)
t2 = 2*math.pi*m/60

print(math.sqrt(a*a + b*b - 2*a*b*math.cos(t1-t2)))



Measured memory_bytes: 62420
#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	int a,b;
	scanf("%d %d",&a,&b);
	if(a<=0&&b>=0)printf("Zero\n");
	if(a>0&&b>0)printf("Positive\n");
	if(a<0&&b<0) {
		if((b-a+1)%2)printf("Negative\n");
		else printf("Positive\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    string s;
    cin >> n >> s;

    int res = 0;
    REP(i, 1, n) {
        int cnt = 0;

        for (char c = 'a'; c <= 'z'; c++) {
            bool left = false, right = false;
            
            for (int j = 0; j < i; j++) {
                if (s[j] == c) left = true;
            }

            for (int j = i; j < n; j++) {
                if (s[j] == c) right = true;
            }

            if (left && right) cnt++;
        }
        chmax(res, cnt);
    }

    cout << res << endl;
    return 0;
}

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

const double EPS = 1e-3;

double dist(double x1, double y1, double x2, double y2) {
  return sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
}

int main() {
  int n, p, q;
  double x[3], y[3], ta, tb, tc, sta, cta, r;
  double z[2], a, b, c, d, e, f;
  bool zf;
  cin >> n;
  for (int k=0;k<n;k++) {
    for (int i=0;i<3;i++) {
      cin >> x[i] >> y[i];
    }
    ta = dist(x[1], y[1], x[2], y[2]);
    tb = dist(x[0], y[0], x[1], y[1]);
    tc = dist(x[0], y[0], x[2], y[2]);
    cta = (ta*ta - tb*tb - tc*tc) / (2*tb*tc);
    sta = sqrt(1 - cta*cta);
    r = ta / sta / 2;

    double m[2][3] = { { 2*(x[0]-x[1]), 2*(y[0]-y[1]), x[0]*x[0]+y[0]*y[0]-x[1]*x[1]-y[1]*y[1] }, 
                       { 2*(x[0]-x[2]), 2*(y[0]-y[2]), x[0]*x[0]+y[0]*y[0]-x[2]*x[2]-y[2]*y[2] } };
    zf = false;
    for (int i=0;i<2;i++) {
      for (int j=0;j<2;j++) {
        if (m[i][j] == 0) {
          p = i; q = j;
          zf = true;
        }
      }
    }
    if (zf) {
      z[1-q] = m[p][2] / m[p][1-q];
      z[q] = (m[1-p][2] - m[1-p][1-q] * z[1-q]) / m[1-p][q];
    } else {
      a = m[0][0]; b = m[0][1]; c = m[0][2];
      d = m[1][0]; e = m[1][1]; f = m[1][2];
      z[1] = (f - d*c/a) / (e - d*b/a);
      z[0] = (c - b*z[1]) / a;
    }
    printf("%.3f %.3f %.3f\n", z[0], z[1], r);
  }
  return 0;
}

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

int main() {
  int a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;
  if(a == 0){
	cout << 1 << endl;
  }else if(b == 0){
	cout << 2 << endl;
  }else if(c == 0){
	cout << 3 << endl;
  }else if(d == 0){
	cout << 4 << endl;
  }else{
    cout << 5 << endl;
  }
}

Measured memory_bytes: 3556
//This is getting accepted!
// I HATE BUG
// God Of The Bugs
// 12/11/2016
#include<bits/stdc++.h>
 
using namespace std;
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define FI first
#define SE second
#define pb push_back
#define mp make_pair
#define ll long long
#define sz(a) ((int)(a).size())
#define __builtin_popcount __builtin_popcounll
#define ld long double
 
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> ppi;
 
const double PI = acos(0) * 2;
const double EPS = 1e-8;
const ll MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int oo = 1e9;
const double foo = 1e30;
 
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcounll(s);}
template<class T> T sqr(T x) { return x * x; }
 
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
 
int K, dp[2][MAXN];
 
ll cal(ll x) {
    ll res = 0;
    while (x) {
        res += x % 10;
        x /= 10;
    }
    return res;
}
 
int main() {
//#ifndef ONLINE_JUDGE
//    freopen("inp.txt", "r", stdin);
////    freopen("out.txt", "w", stdout);
//#endif
 
    cin >> K;
    
    FOR(i, 0, 2) {
        FOR(j, 0, K) {
            dp[i][j] = oo;
        }
    }
    
    int lv = 0;
    
    FOR(i, 1, 10) {
        dp[0][i % K] = min(dp[0][i % K], i);
    }
        
    int cur = 1;
    int ans = oo;
    FOR(i, 1, 1700) {
        cur = cur * 10 % K;
        FOR(j, 0, min(K, 1700 * 9 + 1)) dp[lv ^ 1][j] = oo;
        FOR(j, 0, min(K, 1700 * 9 + 1)) {
            FOR(t, 0, 10) {
                int rem = cur * t % K;
//                if (i == 1 && (j + rem) % K == 92) cout << j << endl;
                dp[lv ^ 1][(j + rem) % K] = min(dp[lv ^ 1][(j + rem) % K], dp[lv][j] + t);
            }
        }
        FOR(t, 1, 10) {
            int rem = cur * t % K;
            dp[lv ^ 1][rem] = min(dp[lv ^ 1][rem], t);
        }
        ans = min(ans, dp[lv ^ 1][0]);
        lv ^= 1;
    }
//    cout << dp[0][2] << endl;
    cur = 1;
    
    FOR(i, 0, 100000) {
        cur = cur * 10 % K;
        int rem = (K - cur) % K;
        ans = min(ans, dp[lv][rem] + 1);
    }
    
    cout << ans;
 
    return 0;
}

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

int main() {
	int a,b;
	cin>>a>>b;
	if(a>b){
		cout<<"a > b"<<endl;
	}
	if(a<b){
		cout<<"a < b"<<endl;
	}
	if(a==b){
		cout<<"a == b"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3076
moveList = raw_input()

rockCounter = 0
score = 0

for i in moveList:
    if i == 'g' and rockCounter > 0:
        score += 1
        rockCounter -= 1
    elif i == 'g':
        rockCounter += 1
    elif i == 'p' and rockCounter > 0:
        rockCounter -= 1
    else:
        rockCounter += 1
        score -= 1
        
print(score)

Measured memory_bytes: 2692
n, q = list(map(int, input().split()))

e = [[] for _ in range(n)]
v = [0]*n

for _ in range(n-1):
  x = list(map(int, input().split()))
  e[x[0]-1].append(x[1]-1)  

for _ in range(q):
  x = list(map(int, input().split()))
  v[x[0]-1] += x[1]

for i, x in enumerate(e):
    for j in x:
        v[j] += v[i]
        
for x in v:
  print(x, end=" ")

Measured memory_bytes: 57280
N=int(input())
A=list(map(int, input().split()))
ans=[0]*N

for i in range(N, 0, -1):
  if i>N//2:
    ans[i-1]=A[i-1]
  else:
    X=i+i
    now=0
    while X<=N:
      now+=ans[X-1]
      X+=i
    if now%2==A[i-1]:
      ans[i-1]=0
    else:
      ans[i-1]=1
      
      
print(sum(ans))
for i,a in enumerate(ans):
  if a==1:
    print(i+1, end=" ")
    

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

typedef pair<int,int> pi;
#define MAX 1000005 
#define mp make_pair
//#define pb push_back

int N, M, a, b, c, pt, mx=-1, q[MAX], ptr[MAX], step[MAX];
vector<pi> lian[MAX];
vector<int> all[MAX], newlian[MAX];
int vis[MAX];

int main()
{
	scanf("%d %d", &N, &M);
	pt=N;
	while(M--)
	{
		scanf("%d %d %d", &a, &b, &c);
		a--, b--;
		all[c].push_back(a);
		all[c].push_back(b);
		lian[a].push_back(mp(c, b));
		lian[b].push_back(mp(c, a));
		mx=max(mx, c);
	}
	for(int i=0; i<N; i++)
	{
		sort(lian[i].begin(), lian[i].end());
		ptr[i]=0;
		vis[i]=-1;
	}
	for(int clr=0; clr<=mx; clr++)
	{
		if(!all[clr].size())
			continue;
		for(int it=0; it<all[clr].size(); it++)
		{
			int v=all[clr][it];
			if(vis[v]==clr)
				continue;
			int l=0, r=1;
			q[0]=v;
			while(l<r)
			{
				int t=q[l];
				while(ptr[t]<lian[t].size())
				{
					c=lian[t][ptr[t]].first;
					if(c!=clr)
						break;
					int u=lian[t][ptr[t]].second;
					if(vis[u]!=clr)
					{
						vis[u]=clr;
						q[r++]=u;
					}
					ptr[t]++;
				}
				l++;
			}
			for(int i=0; i<r; i++)
			{
				newlian[pt].push_back(q[i]);
				newlian[q[i]].push_back(pt);
			}
			pt++;
		}	
	}
	for(int i=0; i<pt; i++)
		step[i]=-2;
	int l=0, r=1;
	q[0]=0;
	step[0]=0;
	while(l<r)
	{
		for(int j=0; j<newlian[q[l]].size(); j++)
		{
			int u=newlian[q[l]][j];
			if(step[u]==-2)
			{
				step[u]=step[q[l]]+1;
				q[r++]=u;
			}
		}
		l++;
	}
	printf("%d", step[N-1]/2);
	return 0;
}
/*
8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5
*/

Measured memory_bytes: 100736
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>

using namespace std;

int main() {
  long H, W;
  cin >> H >> W;


  // 縦または横に３つ
  if (H % 3 == 0 || W % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }



  long avh = H / 3,
      avw = W / 3;

  long res1 = ((avh+1) * W) - (avh * W);
  long res2 = ((avw+1) * H) - (avw * H);


  long res = min(res1, res2);
  long maxv, minv;

  long a, b, c;
  for (long i=1; i<=H/2; i++) {
    a = i*W;
    b = (H-i)*(W/2);
    c = (H-i)*(W/2 + W%2);

    maxv = max(a, max(b, c));
    minv = min(a, min(b, c));

    res = min(res, maxv - minv);
  }
  

  for (long i=1; i<=W/2; i++) {
    a = H*i;
    b = (W-i)*(H/2);
    c = (W-i)*(H/2 + H%2);

    maxv = max(a, max(b, c));
    minv = min(a, min(b, c));

    res = min(res, maxv - minv);
  }

  cout << res << endl;
}



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

using namespace std;

#define N 2000
#define pb push_back

int n, k, d[N + 5], f[N + 5], ans = 0x3f3f3f3f;
vector<int> G[N + 5];

void dp(int u, int fa) {
    f[u] = 0;
    for (auto v : G[u]) {
        if (v == fa) continue;
        d[v] = d[u] + 1;
        dp(v, u);
        f[u] += f[v];
    }
    f[u] += d[u] > k / 2;
}

int main() {
    cin >> n >> k;
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        G[x].pb(y), G[y].pb(x);
    }
    if (k & 1) {
        for (int i = 1; i <= n; ++i)
            for (auto v : G[i]) {
                d[i] = 0, d[v] = 0;
                dp(i, v), dp(v, i);
                ans = min(ans, f[i] + f[v]);
            }
    }
    else {
        for (int i = 1; i <= n; ++i) {
            d[i] = 0;
            dp(i, 0);
            ans = min(ans, f[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

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

int h, w;
char t[110][110];

int main(){
  while(cin >> h >> w, h || w){
    for(int i = 0; i < h; i++){
      cin >> t[i];
    }

    int x = 0, y = 0;

    while(true){
      //ツ止ツづ慊づ?つスツづィ, ツδ?ツプツつオツつスツづィツつオツつスツづァツ終ツ猟ケ
      if(t[y][x] == '.' || t[y][x] == 'L'){
        break;
      }

      //ツパツネツδ仰づ個津環づィツづ可暗堋督ョツつキツづゥ
      int nx = x;
      int ny = y;

      switch(t[y][x]){
        case '^': ny--; break;
        case '>': nx++; break;
        case 'v': ny++; break;
        case '<': nx--; break;
      }

      //ツ辿ツづ?つスツづ?つアツづォツづ可づ? ツ暗ウツづーツづつつッツづ?つィツつ「ツづ? ツδ?ツプツつオツつスツつアツづ?つェツづュツつゥツづゥツづヲツつ、ツづ可つキツづゥ
      t[y][x] = 'L';
      x = nx;
      y = ny;
    }

    //ツ暗ェツ度ツ辿ツづ?つスツつアツづ?つ?づゥツ渉ーツづ?終ツ猟ケツつオツづ?つ「ツつスツづァツδ?ツプ
    if(t[y][x] == 'L'){
      cout << "LOOP\n";
    }
    //'.'ツづ?終ツづュツづ?づ?つ「ツつスツづァツ止ツづ慊づ?つス
    else{
      cout << x << " " << y << endl;
    }
  }
}

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

using namespace std;

int main()
{
    int n;
    cin >> n;
    int x = n % 10;
    if(x == 1 || x == 6 || x == 0 ||x == 8)
        cout << "pon";

    else
        if(x == 3)
        cout << "bon";

    else
        cout << "hon";
    return 0;
}


Measured memory_bytes: 3620
import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) {
	
		MyScanner sc = new MyScanner();
		int n=sc.nextInt();
		int max_w=sc.nextInt();
		int w[]=new int[n];
		int v[]=new int[n];
		for(int i=0;i<n;i++) {
			w[i]=sc.nextInt();
			v[i]=sc.nextInt();
		}
		
		long dp[][]=new long[n][max_w+1];
		for(int k=w[0];k<max_w+1;k++) {
			dp[0][k]=v[0];
		}
		for(int i=1;i<n;i++) {
			for(int j=1;j<max_w+1;j++) {
				dp[i][j]=j>=w[i]?Math.max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]):dp[i-1][j];
			}
		}
				
		System.out.println(dp[n-1][max_w]);
	}
	
	public static PrintWriter out;

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}
	

}





Measured memory_bytes: 124756
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<algorithm> 
using namespace std;
#define REP(i,x,y) for(int i=x;i<=y;i++)
#define rep(i,n) REP(i,1,n)
#define rep0(i,n) REP(i,0,n-1)
#define repG(i,x) for(int i=pos[x];~i;i=e[i].next)
const int N=7;
const int INF=1e9+7;
int a,b;

int main(){
	scanf("%d%d",&a,&b);
	if(a+b==15)printf("+\n");
	else if(a*b==15)printf("*\n");
	else printf("x\n");
	return 0;
}

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

int X;

int main() {
    cin >> X;
    for (long long int i = 0; i * i * i * i <= X; i++) {
        for(long long int j = 0; j <= i; j++) {
            long long int i5 = i * i * i * i * i;
            long long int j5 = j * j * j * j * j;
            if (i5 - j5 == X) {
                cout << i << " " << j << endl;
                return 0;
            }
            else if (i5 + j5 == X) {
                cout << i << " " << -j << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3564
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1111111111;
constexpr lint LINF = 1LL << 60;

////////////////// Debug

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" :" ");
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
	for (const auto &e : mp) os << e << " ";
	return os;
}

template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n" ;};
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n" ;
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)

///////////////// Debug end

#define all(vec) vec.begin(), vec.end()
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; i++ )
#define rep(i,n) REP(i,0,n)

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

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

template<class T>
vector<T> make_vec(size_t s, T val){ return vector<T>(s, val); }
template<class... Size>
auto make_vec(size_t s, Size... tail) {
	return vector<decltype(make_vec(tail...))>(s, make_vec(tail...));
}

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	
	int n;
	cin>>n;
	
	vector<int>a(n),lcs(n,INF);
	rep(i,n){
		int p;
		cin>>p;
		a[--p]=i;
	}	
	
	a.emplace_back(-1); //番兵
	int ans=0, cnt=1;
	rep(i,n){
		if(a[i]<a[i+1])cnt++;
		else ans=max(ans,cnt),cnt=1;
	}
	
	cout<<n-ans<<endl;
	
	
	return 0;
}


Measured memory_bytes: 2560
s = input()
t = 0
u = 0
if 0 < int(s[:2]) < 13:
    t = 1
if 0 < int(s[2:]) < 13:
    u = 1

if u == 1 and t == 1:
    print('AMBIGUOUS')
elif u == 1 and t == 0:
    print('YYMM')
elif u == 0 and t == 1:
    print('MMYY')
else:
    print('NA')

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

using namespace std;
typedef long long ll;

char A[10][10];
queue<pair<pair<int, int>, int> > Q;

int main(void) {
    int h, w, visited = 0;
    cin >> h >> w;
    for(int i=0; i<h; i++) cin >> A[i];
    for(int i=0; i<h; i++) for(int j=0; j<w; j++) {
        if(A[i][j] == '#') visited++;
    }
    Q.push(make_pair(make_pair(0, 0), 1));
    while(!Q.empty()) {
        int y = Q.front().first.first, x = Q.front().first.second;
        int v = Q.front().second;
        Q.pop();
        if(y == h-1 &&  x == w-1 && v == visited) return !printf("Possible\n");

        if(A[y][x] == '.') continue;
        if(y < h-1) Q.push(make_pair(make_pair(y+1, x), v+1));
        if(x < w-1) Q.push(make_pair(make_pair(y, x+1), v+1));
    }

    return !printf("Impossible\n");
}

Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;


void CountingSort(vector<int> &A, vector<int> &B, int k){
    vector<int> C(k + 1, 0);
    rep(i, A.size()) C[A[i]]++;
    rep(i, k) C[i + 1] += C[i];
    for(int i = A.size() - 1; i >= 0; i--){
        C[A[i]]--;
        B[C[A[i]]] = A[i];
    }
}

int main(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    rep(i, N) cin >> A[i];
    CountingSort(A, B, 10010);
    rep(i, N){
        if(i) cout << ' ';
        cout << B[i];
    }
    cout << endl;
}


Measured memory_bytes: 18340
#include <stdio.h>
int main(){
  int n;
  int m;
  int a[10000];
  int total = 0;
  
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; i++){
    scanf("%d", &a[i]);
    total += a[i];
  }
  
  if(total > n){
    printf("-1\n");
  }else{
    printf("%d\n", (n - total));
  }
  return 0;
}


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

int main() {
  int n;
  while (cin >> n, n) {
    vector<string> s(n);
    for (auto& e : s) {
      cin >> e;
    }
    for (int i = n - 1; i >= 0; i--) {
      for (int j = 0; s[i][j] == '.'; j++) {
        if (j + 1 < s[i].size() && s[i][j + 1] != '.') {
          s[i][j] = '+';
        } else if (i + 1 < n && j < s[i + 1].size() && (s[i + 1][j] == '+' || s[i + 1][j] == '|')) {
          s[i][j] = '|';
        } else {
          s[i][j] = ' ';
        }
      }
    }
    for (auto e : s) {
      cout << e << endl;
    }
  }
}



Measured memory_bytes: 3848
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main(int argc, char* argv[])
{
	int H,W,M;
	cin>>H>>W>>M;
	int x,y,i,j;
	set<pair<int,int>> mySet;
	set<pair<int,int>>::iterator sit;
	vector<int> LineBom(H+1,0);
	vector<int> ColBom(W+1,0);
	int MaxLineBom=0;
	int MaxColBom=0;
	for (i=0;i<M;i++){
		cin>>x>>y;
		LineBom[x]++;
		if (MaxLineBom<LineBom[x]){
			MaxLineBom = LineBom[x];
		}
		ColBom[y]++;
		if (MaxColBom<ColBom[y]){
			MaxColBom = ColBom[y];
		}
		mySet.insert(pair<int,int>(x,y));
	}
	vector<int> MaxLine;
	for (i=1;i<=H;i++){
		if (MaxLineBom==LineBom[i]){
			MaxLine.push_back(i);
		}
	}
	vector<int> MaxCol;
	for (j=1;j<=W;j++){
		if (MaxColBom==ColBom[j]){
			MaxCol.push_back(j);
		}
	}
	int MaxBom=MaxLineBom+MaxColBom;
	for (i=0;i<MaxLine.size();i++){
		for (j=0;j<MaxCol.size();j++){
			sit=mySet.find(pair<int,int>(MaxLine[i],MaxCol[j]));
			if (sit==mySet.end()){
				cout<<MaxBom<<endl;
				return 0;
			}
		}
	}
	cout<<MaxBom-1<<endl;
	return 0;
}

Measured memory_bytes: 23292