akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define  vi vector<long long int>
#define  set1 set<long long int>
#define  pb push_back
#define  map1 map<long long int,long long int>
#define  ll  long long int
#define  inf INT_MAX
#define  minf INT_MIN
#define setbits(x) __builtin_popcountll(x)
#define pres(x,y) fixed<<setprecision(y)<<x
#define pair1 pair<long long int,long long int>
#define mk(arr,n,type) type *arr=new type[n];
#define mod 1000000007
#define w(t) long long int t;t=1; while(t--)


struct p
{

	ll a, b, c;

};

ll fun(vector<p> v, ll n) {

	ll dp[n][3];

	dp[0][0] = v[0].a;
	dp[0][1] = v[0].b;
	dp[0][2] = v[0].c;

	for (ll i = 1; i < n; i++) {
		dp[i][0] = v[i].a + max(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = v[i].b + max(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = v[i].c + max(dp[i - 1][1], dp[i - 1][0]);
	}


	return max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));

}


void solve() {

	ll n;
	cin >> n;
	vector<p> v(n);
	for (ll i = 0; i < n; i++) {
		cin >> v[i].a >> v[i].b >> v[i].c;
	}

	cout << fun(v, n);


}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	w(t) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 10300
#include <iostream>

using namespace std;


bool check( int a, int b, int c )
{
	if( ( a * a ) == ( b * b ) + ( c * c ) )
	{
		return true;
	}else{
		return false;
	}
}
int main()
{
	int a, b, c, cnt;

	cin >> cnt;


	for( int i = 0; i < cnt; i++ )	
	{
		cin >> a >> b >> c;
		if( check( a, b, c ) || check( b, a, c ) || check( c, a, b ) )
		{
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
#define f first
#define s second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int n, r[4005], g[4005], b[4005];
ll ans;
string s;

int main() {
	fastio; cin >> n >> s;
	s = " " + s;
	FOR(i, 1, n) {
		r[i] = r[i-1];
		g[i] = g[i-1];
		b[i] = b[i-1];
		if (s[i] == 'R') r[i]++;
		else if (s[i] == 'G') g[i]++;
		else b[i]++;
	}
	FOR(i, 1, n-2) FOR(j, i+1, n-1) {
		set<char> se; se.insert(s[i]); se.insert(s[j]);
		if (se.size() == 1) continue;
		else if (se.find('R') == se.end()) {
			ans += r[n] - r[j-1];
			if (2*j-i <= n and se.find(s[2*j-i]) == se.end()) ans--;
		} else if (se.find('G') == se.end()) {
			ans += g[n] - g[j-1];
			if (2*j-i <= n and se.find(s[2*j-i]) == se.end()) ans--;
		} else if (se.find('B') == se.end()) {
			ans += b[n] - b[j-1];
			if (2*j-i <= n and se.find(s[2*j-i]) == se.end()) ans--;
		}
	}
	cout << ans;
}


Measured memory_bytes: 3640
use proconio::input;

fn main() {
  input! {
    n: i32,
    h: [i32; n],
  }
  
  let mut max: i32 = 0;
  let mut cnt: i32 = 0;
  
  for _h in h {
    if _h >= max {
      max = _h;
      cnt += 1;
    }
  }
  
  println!("{}", cnt);
}

Measured memory_bytes: 2068
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5;
int height[N];
int dp[N];

int solve(int n) {
    //base
    if (n<=1) return 0;
    //lookup
    if (dp[n] != -1) return dp[n];
    int op1 = abs(height[n] - height[n - 1]) + solve(n - 1);
    int op2 = INT_MAX;
    if(n>2)
     op2 = abs(height[n] - height[n - 2]) + solve(n - 2);
    dp[n] = min(op1, op2);    
    return dp[n];
}
    
    
signed main()
{
    int n;
    cin>>n;
    memset(dp, -1, sizeof dp);
    for(int i=1;i<=n;i++) cin>>height[i];
    cout << solve(n);
}



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


int main(){
int a,b,c,d;
cin >> a >> b >> c >> d;
if(a+b>c+d){
  cout << "Left" <<  endl;
}else if(a+b==c+d){
  cout << "Balanced" << endl;
}else{
  cout << "Right" << endl;
}
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<utility>
#include<cstdio>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include <bitset>
using namespace std;
const int mod=1e9+7;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define rep2(i,x,n) for (int i= x;i<n;i++)
#define all(v) v.begin(), v.end()
#define nepe(v) next_permutation(all(v))
#define F first 
#define S second
#define PB push_back 
#define MP make_pair
using ll = long long;
using vi = vector<int>; 
using vvi = vector<vi>;
using vl=vector<long long>;
using vvl = vector<vl>;
using vp =vector<pair<int,int>>;

typedef pair<int,int> P;
string s;
int k;
ll INF = 1000000000000;

int main(){
    string S;
    cin >>S;
    int N =S.size();
    int nw=0;
    ll ans=0;
    rep(i,N){
        if(S[i]=='W'){
            nw++;
            ans += i-nw+1;
        }
    }
    cout <<ans <<endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<iterator>
using namespace std;

int main() {
	int i, n, a, b;
	char com[10];
	string str, p;
	string::iterator j;
	cin >> str >> n;
	for (i = 0; i < n; i++) {
		cin >> com >> a >> b;
		if (com[2] == 'p') {
			cin >> p;
			str.replace(a, b - a + 1, p);
		} else if (com[2] == 'v') {
			string tmp;
			for (j = begin(str) + b; ; j--) {
				tmp += *j;
				if (j == begin(str) + a)break;
			}
			str.replace(a, b - a + 1, tmp);
		} else {
			string tmp;
			tmp.assign(str, a, b - a + 1);
			cout << tmp << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3224
<?php
list($a, $b) = ints();
$cnt = 0;
for ($i = $a; $i <= $b; $i++) {
    $s = strval($i);
    if ($s[0] === $s[4] && $s[1] === $s[3]) $cnt++;
}
echo $cnt;

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

Measured memory_bytes: 4728
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)//rep(i,回数){処理}
using namespace std;
using ll = long long int;
using P = pair<int, int>;

int main() {
    ll k,d,x;
    cin >> x >> k >> d;
    ll s, a;

    if (abs(x)/d >= k) {
        cout << abs(x) - d*k << endl;
    } else {
        s = abs(x)/d;
        a = abs(x)%d;
        
        if ((k-s)%2==0) {
            cout << a << endl;
        } else {
             cout << min(abs(a-d), abs(a+d)) << endl;
        }
        
    } 

    return 0;
}



Measured memory_bytes: 3644
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define x real()
#define y imag()
#define fi first
#define se second
#define pii pair<int, int>

map<pii, int> idx;
vector<vector<int>> g;
vector<int> ans;
int k;
vector<bool> visited;
vector<int> bad;
void dfs(int v) {
	visited[v] = true;
	int c = 1;
	for (auto &u : g[v]) {
		if (!visited[u]) {
			if (c == bad[v]) {
				ans[idx[{u, v}]] = c + 1;
				bad[u] = c + 1;
				c += 2;
			} else {
				ans[idx[{u, v}]] = c;
				bad[u] = c;
				c++;
			}
			dfs(u);
		}
	}
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
	int n;
	cin >> n;
	g.resize(n + 1);
	visited.assign(n + 1, false);
	bad.assign(n + 1, -1);
	vector<pii> edges(n - 1);
	ans.resize(n - 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		edges.push_back({u, v});
		idx[{u, v}] = i;
		idx[{v, u}] = i;
	}
	vector<pii> fs;
	for (int i = 1; i <= n; i++) {
		fs.push_back({sz(g[i]), i});
	}
	sort(fs.rbegin(), fs.rend());
	k = fs[0].fi;
	int v = fs[0].se;
	dfs(v);
	cout << k << "\n";
	for (int i = 0; i < sz(ans); i++) {
		cout << ans[i] << "\n";
	}
}



Measured memory_bytes: 27364
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n, k;
  cin >> n >> k;
  vector<i64> h(n);
  for (i64 i = 0; i < n; i++)
    cin >> h[i];
  i64 ans = 0;
  for (i64 i = 0; i < n; i++)
    if (k <= h[i])
      ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;


int n, x[200005], y[200005];
int arr[4005][4005];
lint fact[10005], invf[10005];

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}


lint bino(int x, int y){
	return fact[x] * (invf[y] * invf[x-y] % mod) % mod;
}

int main(){
	cin >> n;
	fact[0] = invf[0] = 1;
	for(int i=1; i<=10000; i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod-2);
	}
	for(int i=0; i<n; i++){
		cin >> x[i] >> y[i];
		arr[2000-x[i]][2000-y[i]]++;
	}
	for(int i=0; i<=4000; i++){
		for(int j=0; j<=4000; j++){
			if(j) arr[i][j] += arr[i][j-1];
			if(i) arr[i][j] += arr[i-1][j];
			arr[i][j] %= mod;
		}
	}
	int ans = 0;
	for(int i=0; i<n; i++){
		ans += arr[2000+x[i]][2000+y[i]];
		ans %= mod;
	}
	for(int i=0; i<n; i++){
		ans += mod - bino(2 * x[i] + 2 * y[i], 2 * y[i]);
		ans %= mod;
	}
	ans = (ans * ipow(2, mod - 2)) % mod;
	cout << ans;
}


Measured memory_bytes: 64768
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
ll dp[10][20];//dp[i][j]代表以i开头的j位数有多少个lunlun 
ll sum[20], pos;
ll k;
void dfs(ll num, ll lst) {
    if (num > pos) return;
    if (num == 1) {
        for (ll i = 1; i < 10; i++) {
            if (k > dp[i][pos - num + 1]) {
                k -= dp[i][pos - num + 1];
            } else {
                cout << i;
                dfs(num + 1, i);
                break;
            }
        }
    } else {
        for (ll i = lst - 1; i <= lst + 1; i++) {
            if (i < 0 || i > 9) continue;//记住特判 
            if (k > dp[i][pos - num + 1]) {
                k -= dp[i][pos - num + 1];
            } else {
                cout << i;
                dfs(num + 1, i);
                break;
            }
        }
    }
}
int main() {
    cin >> k;
    for (ll i = 0; i < 10; i++) {
        dp[i][1] = 1;
    }
    sum[1] = 9;
    for (ll j = 2; j <= 10; j++) {
        for (ll i = 0; i < 10; i++) {
            if (i != 0 && i != 9) dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + dp[i + 1][j - 1];
            else if (i != 0) dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            else if (i != 9) dp[i][j] = dp[i][j - 1] + dp[i + 1][j - 1];
            if (i != 0) sum[j] += dp[i][j];
        }
    }
    for (ll i = 1; i <= 20; i++) {
        if (k > sum[i]) {
            k -= sum[i];
        } else {
            pos = i;
            break;
        }
    }
    dfs(1, 0);
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
    char s[6];
    scanf("%s",s);

    if(s[0]==s[1] && s[1] !=s[2] && s[2]==s[3])
        printf("Yes\n");
    else if(s[0]==s[2] && s[2]!=s[1] && s[1] ==s[3])
        printf("Yes\n");
    else if(s[0] ==s[3] && s[3] !=s[1] && s[1]==s[2])
        printf("Yes\n");
    else printf("No\n");
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7,INF=1e17;
const int iINF=1e9;
int main(){
    ll n;
    cin>>n;
    vector<ll>dp(n+1,iINF);
    dp[0]=0;
    for(int i=1;i<=n;i++){
        ll six=6,nine=9;
        while(six<=i){
            dp[i]=min(dp[i-six]+1,dp[i]);
            six*=6;
        }
        while(nine<=i){
            dp[i]=min(dp[i-nine]+1,dp[i]);
            nine*=9;
        }
        dp[i]=min(dp[i-1]+1,dp[i]);
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 1024
import sys
nq = int(input())
lines = sys.stdin.readlines()
vector = []
for i in range(nq):
    query, *arg = lines[i].split()
    if query == '0':    # pushback
        vector.append(arg[0])
    elif query == '1':  # randaccess
        print(vector[int(arg[0])])
    elif query == '2':    # pop
        vector.pop()
    else:
        raise AssertionError


Measured memory_bytes: 33968
a,b,c,d,e,f = map(int,raw_input().split())
lim = f
f /= 100
wl = [False for _ in range(f+1)]
sl = [False for _ in range(f*e+1)]
if a <= f:
    wl[a] = True
if b <= f:
    wl[b] = True
if c <= f*e:
    sl[c] = True
if d <= f*e:
    sl[d] = True

for i in range(f):
    if wl[i] and i+a <= f:
        wl[i+a] = True
    if wl[i] and i+b <= f:
        wl[i+b] = True

for i in range(f*e):
    if sl[i] and i+c <= f*e:
        sl[i+c] = True
    if sl[i] and i+d <= f*e:
        sl[i+d] = True

maxd = 0.0
maxw = a*100
maxs = 0
for i,w in enumerate(wl):
    for j,s in enumerate(sl):
        if w and s and i*100+j <= lim:
            if i*e >= j and float(j) / float(100*i+j) > maxd:
                maxd = float(j) / float(100*i + j)
                maxw = i*100
                maxs = j
print maxw+maxs,maxs


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

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//grobal variable
//------------------------------------------
int N,M;
VI Vec;

//動的計画法で役に立つ関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//最大公約数と最小公倍数
ll gcd(ll a, ll b) {
    if(b==0)return a;
    return gcd(b, a%b);
}

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

    
const int vmax=50;
bool graph[vmax][vmax];
bool visited[vmax];

void bfs(int v)
{
    visited[v]=true;
    REP(i, N)
    {
        if (!graph[v][i]) continue;
        if (visited[i]) continue;
        bfs(i);
    }
}



int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int M; cin>>N>>M;
    VI A(M), B(M);

    REP(i, M)
    {
        cin >> A.at(i) >> B.at(i);
        graph[A.at(i)-1][B.at(i)-1] = graph[B.at(i)-1][A.at(i)-1] = true;
    }
    
    int ans=0;
    REP(i, M)
    {
        //i番目の辺を消去
        graph[A.at(i)-1][B.at(i)-1] = graph[B.at(i)-1][A.at(i)-1] = false;
        
        visited[0] =true;
        bfs(0);

        bool is_separated=false;
        REP(i, N)
        {
            if (!visited[i]) 
            {
                is_separated=true;
                break;
            }
        }
        if (is_separated) ans++;
        
        REP(i, N)
        {
            visited[i] = false; 
        }

        //i番目の辺を復活
        graph[A.at(i)-1][B.at(i)-1] = graph[B.at(i)-1][A.at(i)-1] = true;
    }

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



Measured memory_bytes: 256
/*
 *  Author : Jun_SH
 *  Solution for ABC 146 D
 */
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
const int maxn=1e5+10;
struct node{
    int to,id;
    node(int to,int id):to(to),id(id){};
};
int ans[maxn];
vector<node>v[maxn];
queue<node>q;
int mx=0;
bool vis[maxn];
void bfs(){
    q.push(node(1,-1));
    vis[1]=true;
    while(!q.empty()){
        node now=q.front();
        q.pop();
        int tmp=0;
//        cout<<now.to<<endl;
        for(auto i:v[now.to]){
            if(vis[i.to])continue;
            vis[i.to]=true;
            if(now.id==tmp)tmp++;
            tmp%=mx;
            ans[i.id]=tmp+1;
            q.push(node(i.to,tmp));
            tmp++;
            tmp%=mx;
        }
    }
}

main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(vis,false,sizeof(vis));
    int n;
    cin>>n;
    for(int i=1;i<n;++i){
        int x,y;
        cin>>x>>y;
        v[x].emplace_back(node(y,i));
        v[y].emplace_back(node(x,i));
        int vx=v[x].size();
        int vy=v[y].size();
        mx=max({vx,mx,vy});
    }
    cout<<mx<<endl;
    bfs();
    for(int i=1;i<n;++i)cout<<ans[i]<<endl;
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
#define forr(i,a,n)	for(long long int i=a; i<n; i++)
#define loop(i,a,n)	for(long long int i=a; i>=n; i--)

int main() 
{	
	ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(0);

	long long int a,b,ct=0,ans=0;
	cin>>a>>b;
	int c[a];
	forr(i,0,a)
		cin>>c[i],ans+=c[i];
	
	sort(c,c+a);
	forr(i,0,a)
	{
		if(c[i]>=double(ans/double(4*b)))	ct++;
	}
	if(ct>=b)	cout<<"Yes";
	else cout<<"No";
		
	
	return 0;	
}

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

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define foreach(it, v) for(typeof(v.begin()) it=v.begin(); it!=v.end(); ++it)
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second

typedef unsigned int uint;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef set<int> si;

//MOD//
const ll MOD = 1000000007;
struct big;
big ex(big a, ll tms);
typedef struct big{
  ll val;
  big():val(0){}
  big(ll val):val((val%MOD+MOD)%MOD){}
  big& operator += (const big& obj){ (val+=obj.val)%=MOD; return *this;}
  big& operator -= (const big& obj){ (val+=MOD-obj.val)%=MOD; return *this;}
  big& operator *= (const big& obj){ (val*=obj.val)%=MOD; return *this;}
  big& operator /= (const big& obj){ (val*=ex(obj,MOD-2).val)%=MOD; return *this;}
  big operator + (const big& obj)const{ return big(*this) += obj;}
  big operator - (const big& obj)const{ return big(*this) -= obj;}
  big operator * (const big& obj)const{ return big(*this) *= obj;}
  big operator / (const big& obj)const{ return big(*this) /= obj;}
  bool operator < (const big& obj)const{ return val < obj.val;}
  bool operator == (const big& obj)const{ return val == obj.val;}
} big;
istream& operator >> (istream& i, big& obj){ i>>obj.val; return i;}
ostream& operator << (ostream& o, const big& obj){ o<<obj.val; return o;}
big ex(big obj, ll tms){
  if(!tms) return 1;
  big ret = ex(obj, tms/2);
  ret *= ret;
  return (tms&1) ? ret*obj : ret;
}
//MOD//

big bpow(big n, int m){
  if(!m) return 1;
  big ret = bpow(n, m/2);
  ret *= ret;
  return (m&1) ? ret*n : ret;
}

template <class F, class T>
void convert(const F &f, T &t){
  stringstream ss;
  ss << f;
  ss >> t;
}

int  B, W;
int x[200005];
big ans;

int main(){
  scanf("%d%d",&B,&W);

  /*
  x[0] = 1;
  rep (i, B+W) {
    ans = 0;
    int bef = 0;
    if (i-W>0) bef = x[i-1-W];
    for (int j=max(0,i-W); j<=min(i,B); ++j) {
      int bef2 = x[j];
      x[j] += bef;
      if (j==i-W) x[j] += bef;
      if (j==B) x[j] += bef2;
      bef = bef2;
      //cout << i << " " << j << " " << x[j] << endl;
      ans += x[j];
      if (j==i-W) ans += x[j];
      if (j==B) ans -= x[j];
    }
    ans /= pow(2,i+1);
    //cout << ans << endl;
  }
  */

  vector<big> CBi(W+1);
  vector<big> CWi(B+1);
  CBi[0] = 1;
  CWi[0] = 1;
  rep(i,W) CBi[i+1] = CBi[i] * big(B+i) / big(i+1);
  rep(i,B) CWi[i+1] = CWi[i] * big(W+i) / big(i+1);

  big noB = 0;
  big noW = 0;
  rep(i, B+W) {
    if (i>=B) noB = noB * 2 + CBi[i-B];
    if (i>=W) noW = noW * 2 + CWi[i-W];
    ans = bpow(2,i);
    ans += noW;
    ans -= noB;
    ans /= bpow(2,i+1);
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 3712
/*            AUTHOR - SHIVAM GUPTA
                       Jalpaiguri Govt. Engg College             */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
vector<ll> ve[100005];
ll vis[100005],z;
ll dp[3005][3005];

void solve()
{
    vector<ll> v;        vector<pair <ll,ll>> vp;
    // map<ll,ll> mp;       set<ll> st;        multiset<ll> mst;
    ll n=0,m=0,i=0,j=0,k=0,c=0,l=0,r=0,p=0,q=0,x=0,y=0,z=0,flag=0,sum=0;
    // ll a[300005]={0},b[300005]={0},ans[300005];
    string s=" ",t=" ",st,tt,ans="";
    cin>>st;
    cin>>tt;
    s+=st;
    t+=tt;
    n=st.size();
    m=tt.size();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(s[i]==t[j])
            dp[i][j]=dp[i-1][j-1]+1;
            else
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    c=dp[n][m];
    while(c)
    {
        if(dp[n][m]==dp[n][m-1])
        m--;
        else if(dp[n][m]==dp[n-1][m])
        n--;
        else
        {
            ans=s[n]+ans;
            n--;m--;c--;
        }
    }
    cout<<ans<<endl;
}
bool imp=false;int main()
{
    fio;
    int t=1;
    if(imp)
	cin>>t;
	ll j=t;
    while(t--){
    // cout<<"Case #"<<j-t<<": ";
    solve();}
    return 0;
}

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

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

  map<string, int> MA;
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    MA[s]++;
  }

  int M;
  cin >> M;

  for (int i = 0; i < M; i++) {
    string t;
    cin >> t;
    MA[t]--;
  }

  int ans = 0;

  for (auto x : MA) ans = max(ans, x.second);

  cout << max(ans, 0) << "\n";
}

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

signed main() {
  int a,v,b,w,t;
  cin >> a >> v >> b >> w >> t;

  int dist = abs(a - b);
  int v_diff = v - w;
  if(v_diff <= 0) {
    cout << "NO" << '\n';
    return 0;
  }

  if(dist <= t * v_diff) {
    cout << "YES" << '\n';
  } else {
    cout << "NO" << '\n';
  }
}


Measured memory_bytes: 3640
#include<stdio.h>
#include<math.h>
int main(void){
  int N,K,i;
  double ans,x,l,w;
  ans=0;
  scanf("%d %d",&N,&K);
  for(i=1;i<=N;i++){
    if(i<K){
      x=(double)K/i;
      w=ceil(log2(x));
      l=pow(2,w);
      ans=ans+1/l;
    }
    if(i>=K){
      ans=ans+1;
    }
  }
  ans=ans/N;
  printf("%13.12lf",ans);
  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void){
  int a,b;
  scanf("%d %d",&a,&b);
  int ans;
  if(a>b){
    ans=a+(a-1);
  }else if(b>a){
    ans=b+(b-1);
  }else{
    ans=a+b;
  }
  printf("%d",ans);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

long long f(int n) {
  long long ret = 0;
  for (int x = 1; x * x < n; x++) {
    for (int y = 1; x * x + y * y + x * y < n; y++) {
      int m = n - (x * x + y * y + x * y);
      int D = (x + y) * (x + y) + 4 * m;
      int d = sqrt(D) + 0.5;
      if (d * d != D) continue;
      if (((x + y + d) & 1)) continue;
      int z = (d - (x + y)) / 2;
      if (z < 1) continue;
      ret++;
    }
  }
  return ret;
}

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

  for (int i = 1; i <= N; i++) {
    cout << f(i) << endl;
  }

  return 0;
}


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


int main() {
	int K, X;
	cin >> K >> X;
	for(int i = X - K + 1; i < X + K; i++){
		if(i != X + K - 1){
			cout << i << " ";
		}
		else{
			cout << i << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{   
    int N,K; cin>>N>>K;
    vint cnt(N);
    REP(i,N){
        int a; cin>>a;
        cnt[a-1]++;
    }
    sort(ALL(cnt));
    
    int ans=0;
    REP(i,N-K){
        ans+=cnt[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
def p_d():
    N = int(input())
    A = list(map(int, input().split()))

    top = (N + 1) // 2
    a1 = 0
    for i in range(top):
        if i == top - 1:
            a1 += A[i] * ((-1) ** i)
        else:
            a1 += (A[i] + A[~i]) * ((-1) ** i)

    ans = []
    ans.append(a1)
    for i in range(N - 1):
        x = A[i] - ans[i] // 2
        ans.append(x * 2)

    print(*ans)


if __name__ == '__main__':
    p_d()


Measured memory_bytes: 69348
#include <stdio.h>

main(){
  char data[1005];
  int i, n, j, temp;

  scanf("%d", &n);
  getchar();

  for(i=0;i<n;i++){
    for(j=0;;j++){
      scanf("%c", &data[j]);
      if(data[j]=='\n'){
	data[j]='\0';
	temp=j;
	break;
      }
    }
    for(j=0;;j++){
      if(temp<7) break;
      if(data[j+6]=='\0') break;
      if(data[j]=='H'){
	if(data[j+1]=='o'){
	  if(data[j+2]=='s'){
	    if(data[j+3]=='h'){
	      if(data[j+4]=='i'){
		if(data[j+5]=='n'){
		  if(data[j+6]=='o'){
		    data[j+6]='a';
		  }
		}
	      }
	    }
	  }
	}
      }		   
    }

    printf("%s\n", data);
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
ld a,b,c;
int main(void){
    cin>>a>>b>>c;
    //cout<<(c-a-b)*(c-a-b)/4.0<<endl;
    if(c-a-b>0&&b*a<(c-a-b)*(c-a-b)/4.0){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
}


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

int main(){
 int a,b,c;
  cin>>a>>b;
  vector<int> p(b),y(b);
  vector<vector<int>> d(a+1);
  for(int i=0;i<b;i++){
    cin>>p[i]>>y[i];
d[p[i]].push_back(y[i]);
    }
  

  for(int i=0;i<a+1;i++){
 sort(d[i].begin(),d[i].end());

  }
  for(int i=0;i<b;i++){
    c=lower_bound(d[p[i]].begin(), d[p[i]].end(), y[i])- d[p[i]].begin() + 1;
 printf("%06d", p[i]);
printf("%06d\n",c);
  }
}


Measured memory_bytes: 7808
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;

void print_a_b(char *, int , int);
void reverse_a_b(char *, int, int);
void replace_a_b(char *, int , int , char*);

int main()
{
	int q, a, b;
	char str[1024], order[16], p[1024];
	scanf("%s", str);
	scanf("%d", &q);

	for(int i = 0; i < q; i++)
	{
		cin >> order >> a >> b;
		if(!(strcmp(order, "replace")))
		{
			cin >> p;
			replace_a_b(str, a, b, p);
		}
		else if(!(strcmp(order, "print")))
		{
			print_a_b(str, a, b);
		}
		else
		{
			reverse_a_b(str, a, b);
		}
		
	}

	return 0;
}

void print_a_b(char str[], int a, int b)
{
	for(int i = a; i <= b; i++)
	{
		cout << str[i];
	}
	cout << endl;
}

void reverse_a_b(char str[], int a, int b)
{
	for(int i = 0; (a + i) < (b - i); i++)
	{
		swap(str[a+i], str[b-i]);
	}
}

void replace_a_b(char str[], int a, int b, char p[])
{
	for(int i = 0; i <= (b-a); i++)
	{
		str[a+i] = p[i];
	}
}


Measured memory_bytes: 3216
fun main(args: Array<String>) {
    val (l, k) = readLine()!!.split(" ").map(String::toInt)
    val dp = Array(l + 1, {0L})
    dp[1] = 1
    if (k <= l) {
        dp[k] = 1
    }
    for (x in 2..l) {
        if (x - 2 >= 0) {
            dp[x] += dp[x - 2]
        }
        if (x - k - 1 >= 0) {
            dp[x] += dp[x - k - 1]
        }
    }
    println(dp.sum())
}


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

int main() {
  int n;
  cin >> n;
  
  int x=1;
  while(true){
    if(x<=n){
      x*=2;
      
    }
    else{
      break;
    }
  }

  cout << x/2 << endl;
}

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

using namespace std;
typedef long long ll;

#define INF (long long)(10e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)

int main(void)
{
    int cnt[30];
    REP(i, 30) cnt[i] = 0;
    string s;
    cin >> s;
    REP(i, s.size()) cnt[s[i]-'a']++;
    REP(i, 26) {
        if(cnt[i]==0) {
            cout << (char)('a'+i) << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}


Measured memory_bytes: 512
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
A=[int(input()) for i in range(N)]
if A[0]>0:
    print(-1)
    exit()
for i in range(N-1):
    if A[i]+1<A[i+1]:
        print(-1)
        exit()



count=A[-1]
for i in range(1,N)[::-1]:

    if A[i-1]==A[i]-1:
        pass
    else:
        count+=A[i-1]
print(count)


Measured memory_bytes: 76632
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int aCount = 0; //0 ~ 50
        int bCount = 0 ; //0 ~ 50
        int cCount = 0; //0 ~ 50
        int x = 0; //50 <= x <= 20,000 && x % 50 == 0
        int answer = 0;

        try {
            aCount = Integer.parseInt(bufferedReader.readLine());
            bCount = Integer.parseInt(bufferedReader.readLine());
            cCount = Integer.parseInt(bufferedReader.readLine());
            x = Integer.parseInt(bufferedReader.readLine());
        } catch (IOException e) {
            e.printStackTrace();
        }

        for (int i = 0; i < aCount + 1; i++) {
            for (int j = 0; j < bCount + 1; j++) {
                for (int k = 0; k < cCount + 1; k++) {
                    int total = 500 * i + 100 * j + 50 * k;
                    if (total == x) {
                        answer++;
                    }
                }
            }
        }

        System.out.println(answer);
    }
}

Measured memory_bytes: 21460
n = int(input())
l = list(map(int, input().split()))
cnt = 0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if l[i] == l[j] or l[j] == l[k] or l[k] == l[i]:
        continue
      a,b,c = l[i],l[j],l[k]
      if a+b > c and b+c > a and a+c>b:
        cnt += 1
print (cnt)

Measured memory_bytes: 68036
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

INF = 10**10 + 1
dp = [[INF]*(N+1) for i in range(1000*N+2)]

for i in range(N+1):
        dp[0][i]=0

i = 1

#while(True):
for i in range(1, 1000*N+2):
        for j in range(1, N+1):
                if i-WV[j-1][1]>=0:
                        dp[i][j] = min(dp[i-WV[j-1][1]][j-1]+WV[j-1][0], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(i, dp[i][N])
        if dp[i-1][N] <= W and dp[i][N] > W:
                break
        #i += 1

print(i-1)

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

ll sa,sb,tc,td,ans=1e18;;

int main(){
    int a,b,q;
    cin>>a>>b>>q;
    vector<ll> s(a+2),t(b+2),x(q);
    for(int i=1;i<=a;i++){
        cin>>s[i];
    }
    s[0]=-1e18; s[a+1]=1e18;
    for(int i=1;i<=b;i++){
        cin>>t[i];
    }
    t[0]=-1e18; t[b+1]=1e18;
    for(int i=0;i<q;i++){
        cin>>x[i];
        auto itr =upper_bound(s.begin(),s.end(),x[i]);
        sb = *itr;
        sa = *(itr-1);
        itr =upper_bound(t.begin(),t.end(),x[i]);
        td = *itr;
        tc = *(itr-1);
        
        ans=min(ans,abs(x[i]-sa)+abs(sa-tc));
        ans=min(ans,abs(x[i]-sa)+abs(sa-td));
        ans=min(ans,abs(x[i]-sb)+abs(sb-tc));
        ans=min(ans,abs(x[i]-sb)+abs(sb-td));
        ans=min(ans,abs(x[i]-tc)+abs(sa-tc));
        ans=min(ans,abs(x[i]-tc)+abs(sb-tc));
        ans=min(ans,abs(x[i]-td)+abs(sa-td));
        ans=min(ans,abs(x[i]-td)+abs(sb-td));
        cout << ans<<endl;
        ans=1e18;


    }
}


Measured memory_bytes: 3712
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		FastScanner fs = new FastScanner();
		int n = fs.nextInt();
		long k = fs.nextLong();
		int a[] = new int[n + 1];
		int b[] = new int[n + 1];
		for (int i = 1; i < n + 1; i++) {
			a[i] = fs.nextInt();
		}
		b[1] = 1;
		long roopstart = 0;
		long roopend = k;
		int next = 1;
		int i;
		for (i = 1; i < n + 1 && i < k; i++) {
			next = a[next];
			if (b[next] == 0) {
				b[next] = i + 1;
			} else {
				roopstart = b[next] - 1;
				roopend = i;
				break;
			}
		}
		int end = (int) (((k - roopstart) % (roopend - roopstart)) + roopstart);
		if (i == k && roopstart == 0 && roopend == k) {
			end = (int) k;
		}
		int ans = 1;
		for (i = 0; i < end; i++) {
			ans = a[ans];
		}
		System.out.println(ans);
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

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

Measured memory_bytes: 36940
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
#define pb                emplace_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (ll)((x).size())
#define ff                first
#define ss                second
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
#define isBitset(S,i)     ((S>>i)&1)
#define print(x) 		  for(auto it:x) cout<<it<<" "; cout<<"\n"; 
#define MOD 1000000007
ll gcd(ll a, ll b){
    while(true){
        if(a>b)
            swap(a,b);
        if (a == 0) 
            return b; 
        ll p = b % a  , q = a;
        a = p;
        b = q;
    }
}
 
ll powerMod(ll x,ll y){
    ll res = 1;
    x %= MOD;
    while(y > 0){
        if(y & 1)res = (res*x)%MOD;
        y = y >> 1;
        x = (x * x)%MOD;
    }
    return res%MOD;
}
 
string binary(ll s) {
    string res = "";
    while(s != 0) {
        res += (char)('0' + s % 2);
        s /= 2;
    }
    reverse(res.begin() , res.end());
    return res;
}
void solve()
{
	string s;
	cin>>s;
	ll ans=0;
	for(ll i=0;i<sz(s);++i)
		ans+=(s[i]-'0');
		if(ans%9==0)
			cout<<"Yes";
		else
			cout<<"No";
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);  
        solve();
    return 0;
}


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

  string S,T,U;

  cin >> S >> T ;

  U=T+S;

  cout << U << endl;

  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  long long kekka = 0;
  int I,O,T,J,L,S,Z;cin>>I>>O>>T>>J>>L>>S>>Z;//IOJL;
  //できる形
  kekka += O;//O=1;

  if(I > 0 && J > 0 && L > 0){
    long long a1 = J/2*2;
    long long a2 = L/2*2;
    long long a3 = I/2*2;
    //cout << a1 << " " << a2 << " " << a3 << endl;
    long long b1 = (J-1)/2*2;
    long long b2 = (L-1)/2*2;
    long long b3 = (I-1)/2*2;
    //cout << b1 << " " << b2 << " " << b3 << endl;
    kekka += max(a1+a2+a3,b1+b2+b3+3);
  }
  else {
    kekka += (J)/2*2;//J=2;
    kekka += (L)/2*2;//L=2;
    kekka += (I)/2*2;//I=2;
  }
  cout << kekka << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define vi vector <int>
#define si set <int>
#define mii map <int,int>
#define pii pair <int,int>
#define endl "\n"
#define ZERO 0ll
#define FOR(P,Q) for(int P=0;P<(Q);P++)
#define FORR(P,Q) for(int P=1;P<=(Q);P++)
#define rep(P,R,Q) for(int P=(R);P<=(Q);P++)
#define repb(P,R,Q) for(int P=(R);P>=(Q);P--)
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef long double ld;
using namespace std;


    
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("error.txt","w",stderr);
	#endif
	//change ll to int before using string builtin operations
	int tces=1;
	//cin>>tces;
	while(tces--){
		int n,m;
		int ans=0;
		cin>>n>>m;
		if(n>1){
			int t=n*(n-1);
			ans+=t/2;
		}
		if(m>1){
			int t=m*(m-1);
			ans+=t/2;
		}
		cout<<ans;
	}
	
return 0;
}

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

typedef long long int ll;

const double PI=3.14159265358979323846;

int main () {
    ll n; cin >> n;
    vector<ll> as(n, 0);
    for (int i = 1; i < n; i++) {
        cin >> as[i];
        as[i]--;
    }
    vector<int> ans(n, 0);
    for (int i = 1; i < n; i++) {
        ans[as[i]]++;
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 5148
#import sys
#sys.setrecursionlimit(500000)　マージテクをちゃんとしていればこんなものはいらないはず……

class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
            a_par,b_par = b_par,a_par
        if self.rnks[a_par] == self.rnks[b_par]:
            self.rnks[a_par] += 1
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def length(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.length(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


    print(" ".join(map(str,answer)))






if __name__ == '__main__':
    main()


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

map<string, int> mp;

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s; cin >> s;
		mp[s]++;
	}

	int m; cin >> m;
	for (int i = 0; i < m; i++)
	{
		string s; cin >> s;
		mp[s]--;
	}

	int maxv = 0;
	for (auto p : mp)
	{
		maxv = max(maxv, p.second);
	}

	cout << maxv << endl;

	return 0;
}


Measured memory_bytes: 3636
//compiledef
#include <bits/stdc++.h>
#define rep(i, n) for(i=0;i<(n);i++)
#define per(i, n) for(i=(n);i>0;i--)
#define repx(i, n, x) for(i=(x);i<(n);i++)
#define xper(i, n, x) for(i=(n);i>(x);i--)
#define pback push_back

//c++def
using namespace std;
typedef long long int ll;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;

int main(){
	ll a, b, c;
	ll ans;
	cin >> a >> b >> c;

	ans = c - a - b;
	if(ans*ans > 4*a*b && ans > 0)cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
S = [input() for _ in range(H)]

Left  = [[0] * 2100 for _ in range(2100)]
Right = [[0] * 2100 for _ in range(2100)]
Up    = [[0] * 2100 for _ in range(2100)]
Down  = [[0] * 2100 for _ in range(2100)]

for i in range(H):
	cur = 0
	for j in range(W):
		if S[i][j] == '#':
			cur = 0
		else:
			cur += 1
		Left[i][j] = cur

for i in range(H):
	cur = 0
	for j in range(W-1, -1, -1):
		if S[i][j] == '#':
			cur = 0
		else:
			cur += 1
		Right[i][j] = cur

for j in range(W):
	cur = 0
	for i in range(H):
		if S[i][j] == '#':
			cur = 0
		else:
			cur += 1
		Up[i][j] = cur

for j in range(W):
	cur = 0
	for i in range(H-1, -1, -1):
		if S[i][j] == '#':
			cur = 0
		else:
			cur += 1
		Down[i][j] = cur

cnt = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			continue
		cnt = max(cnt, Left[i][j] + Right[i][j] + Up[i][j] + Down[i][j] - 3)

print(cnt)

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

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

	int n, k;
	cin >> n >> k;
	
	int mod = 1e9 + 7;
	auto update = [&](int &val)
	{
		if(val > mod) val -= mod;
		if(val < 0) val += mod;
	};

	vector<int> dp(k + 1);
	dp[0] = 1;

	for(int i = 0; i < n; i++)
	{
		int a;
		cin >> a;

		vector<int> next(k + 1);
		for(int j = 0; j <= k; j++)
		{
			if(j != 0) next[j] += next[j - 1];
			next[j] += dp[j];
			update(next[j]);
			if(j > a) next[j] -= dp[j - a - 1];
			update(next[j]);
		}

		dp = next;
	}

	cout << dp[k] << "\n";
}


Measured memory_bytes: 1024
S=input()

ans = 0
count = 0
for i in S:
    if i == 'A' or i == 'T' or i == 'C' or i == 'G':
        count += 1
    else:
        if ans < count:
            ans = count
        count = 0
if ans < count:
    ans = count
print(ans)


Measured memory_bytes: 8988
#include<stdio.h>
#include<string.h>
#include<math.h>

int main() {
    int n,t,m,sum=0;
    scanf("%d%d",&n,&t);
    while(t--){
            scanf("%d",&m);
            sum+=m;
    }
    if(sum>=n)
        printf("Yes\n");
    else
        printf("No\n");
}


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

int abs(int x) {
    if(x<0) return -x;
    else return x;
}

int main() {
    int n;
    cin >> n;
    int a[n+2], b[n];
    a[0]=0; a[n+1]=0;
    for(int i=1; i<n+1; i++) cin >> a[i];

    int sum=0;
    for(int i=0; i<n+1; i++) sum += abs(a[i]-a[i+1]);

    for(int i=1; i<n+1; i++) {
        cout << sum - abs(a[i-1]-a[i]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1]) << endl;
    }
    return 0;
}



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


int GCD(int m,int n){
    int big,small;
    int p=-1;
    big=max(m,n);
    small=min(m,n);

    while(1){
        p=big%small;
        if(p==0)break;
        big=small;
        small=p;
    }
    
    return small;
}

int main(){
    int MIN=1e9+1;
    int ans=0;
    int n,x,xi;

    cin >> n>>x;
    cin >>xi;
    ans=abs(x-xi);
    for (int i = 1; i < n; i++){
        cin >> xi;
        ans = GCD(ans,abs(x-xi));
    }
    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
$stdin.gets.strip
A = $stdin.gets.strip.split(' ').map(&:to_i)
$stdin.gets.strip
ms = $stdin.gets.strip.split(' ').map(&:to_i)

def solve(i, m)
  if m == 0
    return true
  end

  if i >= A.length
    return false
  end

  return solve(i+1, m) || solve(i+1, m - A[i])
end

ms.each do |m|
  if solve(0, m)
    puts 'yes'
  else
    puts 'no'
  end
end


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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int X,Y; cin >> X >> Y;
	forn(a,0,X+1){
		forn(b,0,Y+1){
			if(a+b == X && 2*a+4*b == Y){
				cout << "Yes\n";
				return 0;
			}
		}
	}
	cout << "No\n";
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


Measured memory_bytes: 3660
# code-festival-2016-qualbB - Qualification simulator
def main():
    N, A, B = tuple(map(int, input().split()))
    S = input()
    ans, x, y = [], 0, 0
    for i in S:
        if (i == "a" and x < A + B) or (i == "b" and x < A + B and y < B):
            ans += ["Yes"]
            x += 1
            y += 1 if i == "b" else 0
        else:
            ans += ["No"]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Measured memory_bytes: 6344
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define PI 3.1415926535897932384626433832795
int MOD=1e9+7;
int powmod(int a,int l, int md){int res=1;while(l){if(l&1)res=res*a%md;l/=2;a=a*a%md;}return res;}
typedef long long ll; typedef vector<ll> vi; typedef pair<ll, ll> ii; typedef vector<ii> vii;
#define pb push_back
int __set(int b, int i) {return b|(1<<i);} //set ith bit
int __unset(int b, int i) {return b&!(1<<i);}
int __check(int b, int i) {return b&(1<<i);} //returns 0 if ith bit is 0
int mul(int a, int b) {return ((a%MOD)*(b%MOD))%MOD;}
int add(int a, int b) {return (a+b)%MOD;}
int sub(int a, int b) {return (((a-b)%MOD)+MOD)%MOD;}
int __div(int a, int b) {return mul(a, powmod(b, MOD-2, MOD));} //if MOD is prime;
const int inf = 0xFFFFFFFFFFFFFFFL; //very large number
priority_queue<int, vector<int>, greater<int> > pq; //for min priority_queue
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t time_p=clock();
void time()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

int32_t main(void)
{
	IOS;
	int n; cin>>n;
	vi a(n);
	for(int i = 0; i < n; i++)
		cin>>a[i];
	int dp[n][n];
	for(int i = 0; i < n; i++) {
		dp[i][i]=a[i];
	}
	for(int i = 2; i <= n; i++) {
		for(int j = 0; j <= n-i; j++) {
			int lo=j, hi=j+i-1;
			dp[lo][hi] = max(a[lo]-dp[lo+1][hi], a[hi]-dp[lo][hi-1]);
		}
	}
	cout<<dp[0][n-1]<<endl;
	time();	
	return 0;
}

Measured memory_bytes: 70272