akhauriyash/Code-Regression huggingface dataset:
// 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)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll 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,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU
int main(){
	int n;
	cin>>n;
	vi in(n);
	rep(i,n)cin>>in[i];
	rep(i,n)in[i]-=i+1;
	sort(all(in));
	ll out=0;
	rep(i,n)out+=abs(in[i]-in[n/2]);
	cout<<out<<endl;
}








Measured memory_bytes: 1792
import sys
while(True):
 h,w=map(int,raw_input().split())
 if(h==0 and w==0):break
 for i in range(0,h):
  for j in range(0,w):
   if((i==0 or j==0) or (i==h-1 or j==w-1)):
    sys.stdout.write ("#")
   else: sys.stdout.write (".")
  else: print
 else: print

Measured memory_bytes: 4216
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [list(map(int, input().split())) for i in range(M)]

mins = min(a) + min(b)
for i in range(M):
  ai, bi, ci = c[i]
  mins = min(mins, a[ai-1] + b[bi-1] - ci)
print(mins)

Measured memory_bytes: 38496
#include<bits/stdc++.h>
using namespace std;
int n;
int a,b,c;
int dp[100005][4];
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		scanf("%d%d%d",&a,&b,&c);
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a;
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b;
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c;
	}
	printf("%d\n",max(dp[n][0],max(dp[n][1],dp[n][2])));
}

Measured memory_bytes: 1792
def yumiri(L, n):
  for i in range(len(L)):
    if L[i] > n:
      return i - 1

def naobou(d, q):
  newans = ans

  rd = t[d - 1] - 1
  rq = yumiri(ZL[rd], d)
  newans += SUMD[ZL[rd][rq] - ZL[rd][rq - 1] - 1] * c[rd]
  newans += SUMD[ZL[rd][rq + 1] - ZL[rd][rq] - 1] * c[rd]
  newans -= SUMD[ZL[rd][rq + 1] - ZL[rd][rq - 1] - 1] * c[rd] 
  del ZL[rd][rq]

  nd = q - 1
  nq = yumiri(ZL[nd], d)
  newans += SUMD[ZL[nd][nq + 1] - ZL[nd][nq] - 1] * c[nd]
  newans -= SUMD[d - ZL[nd][nq] - 1] * c[nd]
  newans -= SUMD[ZL[nd][nq + 1] - d - 1] * c[nd]
  ZL[nd].insert(nq + 1, d)

  newans -= s[d - 1][rd]
  newans += s[d - 1][nd]

  if newans < ans:
    ZL[rd].insert(rq, d)
    del ZL[nd][nq + 1]
    return ans
  else:
    t[d - 1] = q
    return newans 

def rieshon():
  ans = 0
  for i in range(D):
    ans += s[i][t[i] - 1]
    for j in range(26):
      if t[i] - 1 == j:
        L[j] = 0
        ZL[j].append(i + 1)
      else:
        L[j] += 1
        ans -= L[j] * c[j]
  for i in range(26):
    ZL[i].append(D + 1)
  return ans

import time
import random
startTime = time.time()

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

t = [1] * D

print(" ".join(map(str, list(t))))


Measured memory_bytes: 78028
#include <stdio.h>

int main(){
	int i, j, H, W;
	
	while(1){
	    scanf("%d %d",&H,&W);
	    if(H == 0 && W == 0){
		   break;
	    }
		
		for(i = 0; i < H; i++){
			for(j = 0;j < W; j++){
				if((i + j) % 2 == 0){
					printf("#");
				}else{
			    	printf(".");
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}

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

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


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void){
  int N;
  cin >> N;
  int M = -1;
  int ans = 0;
  for(int i = 0; i < N; i++){
    int H;
    cin >> H;
    if(M <= H){
      M = H;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import math
N = int(input())
num = 0
i = 1
while i <= math.sqrt(N):
    if N % i == 0:
        a = i - 1
        b = (N // i) - 1
        if a == b:
            if a > 0 and N // a == N % a:
                num += a
        else:
            if a > 0 and N // a == N % a:
                num += a
            if b > 0 and N // b == N % b:
                num += b
    i += 1

print(num)

Measured memory_bytes: 3060
#include <iostream>
#include <string>

int main(){
  int n;
  std::cin >> n;
  std::string s;
  std::cin >> s;
  for(auto &i : s)
    for(int j=0; j<n; ++j)
      if(i != 'Z')
        i += 1;
  	  else
        i = 'A';
  std::cout << s << std::endl;
  return 0;
}


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

using namespace std;

int n;
int H, W;
const char frame = '#';
const char inner = '.';

int main(){
    int flag =0;
    while(1){
        cin >> H >> W;
        if(!(H|W)){ break;}
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if((i+j)%2){
                    cout << inner;
                }else{
                    cout << frame;
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3056
#include<iostream>

using namespace std;

int main() {
   int n,m,add,A[100][100],b[100];
   cin >> n >> m;
   for (int i = 0; i < n; i++) {
       for (int j = 0; j < m; j++) {
           cin >> A[i][j];
       }
   }
   for (int j = 0; j < m; j++) {
       cin >> b[j];
   }
   for(int i = 0; i < n; i++) {
       add = 0;
       for (int j = 0; j < m; j++) {
           add += A[i][j] * b[j];
       }
       cout << add << endl;
   }
   return 0;
}

Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
int n,ans,k,t,b[100005],c[16],d[1<<16];
void gao(int i){
	for(int j=0;j<16;j++)
		if(i>>j&1)k^=j;
	if(!k){
		d[i]=1;
		for(int j=(i-1)&i;j;j=(j-1)&i)
			d[i]=max(d[i],d[j]+d[j^i]);
	}
}
void gg(int i){
	for(int j=0;j<16;j++)
		for(int p=0;p<16;p++)
			if(j&p>=i)k^=j&p;
}
int main(){
	n=read();
	for(int i=0;i<n-1;i++){
		int x=read(),y=read(),a=read();
		b[x]^=a,b[y]^=a;
	}
	for(int i=0;i<n;i++)
		c[b[i]]++;
	for(int i=1;i<1<<16;i++){
		k=0;
		gao(i);
	}
	for(int i=1;i<16;i++){
		ans+=c[i]/2;
		if(c[i]&1)t^=1<<i;
	}
	printf("%d",ans+__builtin_popcount(t)-d[t]);
	return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int main() {
    int N; cin>>N;
    vector<int> d(N);
    int ans;ans=1;
    for(int i=0;i<N;i++){//入力
        cin>>d[i];
    }
    sort(d.begin(),d.end());//昇順
    reverse(d.begin(),d.end());//反転
    for(int i=0;i<N-1;i++){//次の数字より小さいときans++
        if(d[i]-d[i+1]!=0){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
<?php

//input
fscanf(STDIN,"%s",$str);

$num = str_split($str);
$cnt = count($num)-2;

$result = [];

for($i=0;$i<$cnt;$i++){
    $result[] = abs(753-intval($num[$i].$num[$i+1].$num[$i+2]));
}

echo min($result);

exit;
?>

Measured memory_bytes: 4856
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
   int n,d;cin>>n>>d;
   d=2*d+1;
   cout<<(n-1)/d+1;
}

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

int main() {
	int n; cin>>n; 
	vector<int>b(n);
	int a[n];
	for(int i=0;i<n;i++) {
		cin>>a[i]; b[i]=0;
	}
	for(int i=n-2;i>=0;i--) {
		if(a[i+1]<=a[i]) b[i]=b[i+1]+1;
	}
	sort(b.begin(),b.end());
	cout<<b[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n))
#define Vec(a,n) vector<string> (a)((n))
using namespace std;
signed main(){
	int n,ans=0;
	cin >> n;
	n *= 2;
	vec(a,n);
	REP(i,n){
		cin >> a[i];
	}
	sort(a.begin(),a.end());
	REP(i,n){
		if(i%2 == 0){
			ans += a[i];
		}
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
data = []
for i in 1..(n)
  data = gets.chomp.split(" ")
  data[0] = data[0].to_i
  data[1] = data[1].to_i
  data[2] = data[2].to_i
  data = data.sort
  if data[0] * data[0] + data[1] * data[1] == data[2] * data[2]
    puts("YES")
  else
    puts("NO")
  end
end


Measured memory_bytes: 6868
n,m=map(int,input().split())
mod=10**9+7
import math
if 2<=abs(n-m):
    print(0)
elif n==m:
    print((math.factorial(n)*math.factorial(m)*2)%mod)
else:
    print((math.factorial(n)*math.factorial(m))%mod)
    

Measured memory_bytes: 5184
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	char sa[20],sb[20];
	for(int i=0;i<b;i++)
	 sa[i]=a+'0';
	sa[b]='\0';
	for(int i=0;i<a;i++)
	 sb[i]=b+'0';
	sb[a]='\0';
	if(strcmp(sa,sb)>=0)
	cout<<sb<<endl;
	else
	cout<<sa<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1e18;

int main(){
    int h, w, k;
    cin >> h >> w >> k;

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int s = (x1 - 1) * w + (y1 - 1);
    int t = (x2 - 1) * w + (y2 - 1);

    vector<vector<char>> c(h, vector<char>(w));
    for(int x=0; x<h; x++){
        for(int y=0; y<w; y++){
            cin >> c[x][y];
        }
    }

    vector<long long int> d(h*w, INF);
    queue<long long int> q;
    d[s] = 0;
    q.push(s);

    vector<int> dx = {1, 0, -1, 0};
    vector<int> dy = {0, 1, 0, -1};

    while(q.empty() == false){
        long long int current = q.front(); q.pop();
        int cx = current / w;
        int cy = current % w;

        for(int i=0; i<4; i++){
            int x = cx;
            int y = cy;

            for(int j=0; j<k; j++){
                x += dx[i];
                y += dy[i];
                int v = x * w + y;

                if(x < 0 || h <= x
                || y < 0 || w <= y
                || c[x][y] == '@') break;

                if(d[v] != INF && d[v] != d[current] + 1) break;
                
                if(d[v] == INF){
                    d[v] = d[current] + 1;
                    q.push(v);
                }
            }
        }
    }

    /*
    for(int x=0; x<h; x++){
        for(int y=0; y<w; y++){
            if(d[x * w + y] == INF) cout << "   @";
            else cout << setw(4) << d[x * w + y];
        }
        cout << endl;
    }
    */

    if(d[t] != INF) cout << d[t] << endl;
    if(d[t] == INF) cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 12992
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define pi acos(-1)
ll mod=998244353 ;
 
ll po(ll a,ll p)
{
    if(p==0)
        return 1ll;
    else if(p==1)
        return a%mod;
    else if(p%2)
    {
        ll temp=po(a,p/2);
        return ((((temp%mod)*(temp%mod))%mod*(a%mod)))%mod;
    }
    else
    {
        ll temp=po(a,p/2);
        return ((temp%mod)*(temp%mod))%mod;
    }
}

//int distance[100005];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll t, n, m;
    cin >> n;
    int arr[n+5] = {0}, distance[n+5] = {0};
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    
    for(int i = 1; i < n; i++)
    {
        if(i==1)
        {
            distance[i] = distance[i-1]+abs(arr[i]-arr[i-1]);
        }
        else
        {
            int temp1 = distance[i-1]+abs(arr[i]-arr[i-1]);
            int temp2 = distance[i-2]+abs(arr[i]-arr[i-2]);
            distance[i] = min(temp1, temp2);
        }
    }
    cout << distance[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define bitsz(x) int(__builtin_popcount(x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb(x) push_back(x)
#define INF 1e9
#define LINF 1e18
#define mod 1000000007
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
const int di[4] = {1,0,-1,0};
const int dj[4] = {0,1,0,-1};


int main() {
    int h,w,k; cin >> h >> w >> k;
    vector<string> c(h);
    rep(i,h) cin >> c[i];
    int ans = 0;
    rep(i,1<<(h+w)) {
        int cnt = 0;
        set<int> st; //赤く塗る列を入れる
        rep(j,w) {
            if (i>>(h+j) & 1) st.insert(j);
        }
        rep(j,h) {
            if (i>>j & 1) { //i行目赤く塗るならば
                continue;
            }
            rep(k,w) {
                if (st.find(k)!=st.end()) continue;
                if (c[j][k]=='#') cnt++;
            }
        }
        if (cnt==k) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3556
from math import log,ceil
n=int(input())
l=ceil((log(25*n+26)/log(26)))-1
d=n-26*(pow(26,l)-1)//25-1
s=''
for i in range(int(l)):
    s=chr(97+int(d)%26)+s
    d//=26
print(s)
    


Measured memory_bytes: 62220
import java.util.*;

public class  Main {

	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int m=input.nextInt();
		int s=0;
		Integer a[]=new Integer[n];
		for(int i=0;i<n;i++)
			a[i]=input.nextInt();
		Arrays.sort(a,new Comparator<Integer>() {
			public int compare(Integer o1,Integer o2) {
				return o2-o1;
			}
		});
		for(int i=0;i<m;i++)
			s=s+a[i];
		System.out.println(s);
}
}

Measured memory_bytes: 23764
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
using namespace std;

int main() {
	int N; cin >> N;
	vi c(N - 1), s(N - 1), f(N - 1);
	rep(i, N - 1) {
		cin >> c[i] >> s[i] >> f[i];
	}

	vector<ll> ans(N); // ans[0] means minimum time required to reach the station N-1
	//binary search
	ans[N - 1] = 0;
	for (int i = N - 2; i >= 0; i--) {
		int cur = i;
		ll now = 0;
		now = s[i];
		now += c[i];
		cur++;
		while (cur < N - 1) {
			if (now <= s[cur]) {
				now = ans[cur];
				break;
			}
			else {
				//find T s.t. T%f[cur] and T >= S[cur]
				now = ((now + f[cur] - 1) / f[cur]) * f[cur];
				now += c[cur];
				cur++;
			}
		}
		ans[i] = now;
	}

	for (auto a : ans) {
		cout << a << endl;
	}
}


Measured memory_bytes: 3640
// Problem01.cpp : アプリケーションのエントリ ポイントを定義します。
//

//#include <bits/stdc++.h>
//#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{
	//cin.tie(0);
	string s;
	cin >> s;
	if (s == "AAA" || s == "BBB")
		cout << "No" << endl;
	else
		cout << "Yes" << endl;

}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
int n,a[maxn],head[maxn],cnt,dp[maxn],ans[maxn];
struct node{
	int to,next;
}e[maxn<<1]; 
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int son,int fa){
	int pos=lower_bound(dp+1,dp+1+n,a[son])-dp;
	int temp=dp[pos];
	dp[pos]=a[son];
	ans[son]=max(ans[fa],pos);
	for(int i=head[son];i;i=e[i].next){
		if(e[i].to!=fa){
			dfs(e[i].to,son);
		}
	}
	dp[pos]=temp;
}
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++){
   	  scanf("%d",&a[i]);
   }
   for(int i=1,u,v;i<=n-1;i++)
   {
   	  scanf("%d %d",&u,&v);
   	  add(u,v);add(v,u);
   }
   memset(dp,0x3f,sizeof(dp));
   dfs(1,0);
   for(int i=1;i<=n;i++)
      printf("%d\n",ans[i]);

return 0;
}



Measured memory_bytes: 24284
#include <iostream>
#include <math.h>
using namespace std;
int e;
int main(){
  for(;;){
    cin >> e ;;
    int m = e;
    if(e == 0) break;
    for(int y=0; y*y <= e; y++){
      for(int z=0; y*y + z*z*z <= e; z++){
        int x = e - z*z*z - y*y;
        if( x + y + z < m){
          m = x+y+z;
        }
      }
    }
    cout << m << endl;
  }
}

Measured memory_bytes: 3048
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std;

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

static const int MAXN = 1001;
static const int MAXM = 1001;
static const int INF = 1e5;

int main() {

	string S;
	int w;
	cin >> S >> w;
	
	int index;
	index = 0;
	while (true) {
		cout << S[index];
		index += w;
		if (index >= S.length()) {
			break;
		}
	}
	cout << endl;



	//cout << "out" << endl;

	//int end;
	//cin >> end;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>                                             
#include<string>
#include<cstdlib>
using namespace std;
int main(){
    string s;
    while(cin>>s&&s!="0"){
        int num=0;
        for(int i=0;i<s.size();i++)
            num+=s[i]-'0';
        cout<<num<<"\n";    
    }   
    return 0;
        
}



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

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;

int main(){

    ll N = 0;
    cin >> N;
    ll l1 = 2;
    ll l2 = 1;

    ll ans = 0;

    for(ll i = 2; i <= N; i++){
        ll t_l = l1 + l2;
        l1 = l2;
        l2 = t_l;
    }

    cout << l2 << endl;


}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  ll ans = 0;
  rep(i, n){
    if (i == 0) continue;
    if (a[i] < a[i-1]){
      int d = a[i-1] - a[i];
      a[i] += d;
      ans += d;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int top, S[1000];

void push(int x) {
    S[++top] = x;
}

int pop() {
    top--;
    return S[top+1];
}

int main() {
    int a, b;
    top = 0;
    char s[100];
    
    while( scanf("%s", s) != EOF ) {
        if( s[0] == '+' ) {
            a = pop();
            b = pop();
            push(a + b);
        } else if (s[0] == '-') {
            b = pop();
            a = pop();
            push(a-b);
    } else if ( s[0] =='*' ) {
        a = pop();
        b = pop();
        push(a * b);
} else {
    push(atoi(s));
}
}

printf("%d\n", pop());

return 0;
}


Measured memory_bytes: 2036
#include <iostream>


using namespace std;


int main(void){
    int H=0,W=0;
  
        
    while( cin>>H>>W&&(H&&W)){
        for(int i=0;i<H;++i){
            if(i%2==0){
                for(int j=0;j<W;++j){
                    if(j%2==0){
                        cout<<'#';
                    }else{
                        cout<<'.';
                    }
                }
                cout<<'\n';
            }else{
                for(int j=0;j<W;++j){
                    if(j%2==0){
                        cout<<'.';
                    }else{
                        cout<<'#';
                    }
                }
                 cout<<'\n';
            }
        }
        cout<<'\n';
       }
    
    
    return 0;
}


Measured memory_bytes: 3016
n = int(input())
s = list(input())
maxC=0
index=0
while index<n:
    list1=[]
    list2=[]
    listForChar=[]
    index2=0
    sum=0
    while index2<index+1:
        list1.append(s[index2])
        index2+=1
    index3=index+1
    while index3<n:
        list2.append(s[index3])
        index3+=1
    for char in list1:
        if char in list2 and char not in listForChar:
            sum +=1
            listForChar.append(char)
    if sum>maxC:
        maxC=sum
    index+=1
print(maxC)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<char>> A(H, vector<char>(W));
    for (int h = 0; h < H; ++h){
        for (int w = 0; w < W; ++w){
            cin >> A[h][w];
        }
    }

    vector<bool> row(H, false);
    vector<bool> col(W, false);
    for (int i = 0; i < H; ++i){
        for (int j = 0; j < W; ++j){
            if(A[i][j] == '#'){
                row[i] = true;
                col[j] = true;
            }
        }
    }

    for (int i = 0; i < H; ++i){
        if(row[i]){
            for (int j = 0; j < W; ++j){
                if(col[j]){
                    cout << A[i][j];
                }
            }
            cout << endl;
        }
    }

    return 0;
}

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

struct TNode
{
	int Index;
	TNode* Parent;
	TNode* Left;
	TNode* Right;
	
	TNode();
};

TNode::TNode()
{
	Index  = -1;
	Parent = NULL;
	Left   = NULL;
	Right  = NULL;
}

typedef std::vector<TNode> TBinaryTree;
void Initialize(TBinaryTree& BinaryTree)
{
	for(unsigned int i = 0; i < BinaryTree.size(); ++i){
		BinaryTree[i].Index = i + 1;
	}
}

typedef std::vector<TNode*> TOrder;

void InputNodes(TBinaryTree& Tree, TOrder& PreOrder, TOrder& InOrder)
{
	for(unsigned int i = 0; i < Tree.size(); ++i){
		int Index;
		std::cin >> Index;
		PreOrder[i] = &(Tree[Index - 1]);
	}
	for(unsigned int i = 0; i < Tree.size(); ++i){
		int Index;
		std::cin >> Index;
		InOrder[i] = &(Tree[Index - 1]);
	}
}

void ReconstructTree(TOrder::iterator PreOrderPos,
	                 TOrder::iterator PreOrderLast,
	                 TOrder::iterator InOrderBegin,
	                 TOrder::iterator InOrderLast)
{
	if(PreOrderPos == PreOrderLast) return;
	TOrder::iterator Position = std::find(InOrderBegin, InOrderLast + 1, *PreOrderPos);
	TOrder::iterator Left  = PreOrderPos + 1;
	TOrder::iterator Right = PreOrderPos + 1 + distance(InOrderBegin, Position);
	if(Position != InOrderBegin){
		(*PreOrderPos)->Left = *Left;
		(*Left)->Parent = *PreOrderPos;
		ReconstructTree(Left, Right - 1, InOrderBegin, Position - 1);
	}
	if(Position != InOrderLast){
		(*PreOrderPos)->Right = *Right;
		(*Right)->Parent = *PreOrderPos;
		ReconstructTree(Right, PreOrderLast, Position + 1, InOrderLast);
	}
}

void OutputPostOrder(const TNode* Root)
{
	if(Root == NULL) return;
	OutputPostOrder(Root->Left);
	OutputPostOrder(Root->Right);
	std::cout << Root->Index;
	if(Root->Parent != NULL){
		std::cout << " ";
	}else{
		std::cout << std::endl;
	}
}

int main()
{
	int Count;
	std::cin >> Count;
	TBinaryTree BinaryTree(Count);
	Initialize(BinaryTree);
	TOrder PreOrder(Count);
	TOrder InOrder(Count);
	
	InputNodes(BinaryTree, PreOrder, InOrder);
	
	ReconstructTree(PreOrder.begin(), PreOrder.end() - 1, InOrder.begin(), InOrder.end() - 1);
	
	TNode* Root = *(PreOrder.begin());
	OutputPostOrder(Root);
	
	return 0;
}

Measured memory_bytes: 3056
<?php
function gcd($x, $y){
    if($x < $y) list($x, $y) = array($y, $x);

    while(true){
        if($y == 0){
            return $x;
        }
        $pre_y = $y;
        $y = $x % $y;
        $x = $pre_y;
    }
}

while(fscanf(STDIN, "%d%d", $a, $b)){
    $g = gcd($a, $b);
    $l = $a * $b / $g;
    echo $g . " " . $l . "\n";
}

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

int main(){
  int n;
  long int r[200000];
  long int maxv=-1000000000000;
  long int minv=1000000000000;

  cin >> n;
  for(int i=0; i<n; i++){
    cin >> r[i];
  }

  for(int i=0; i<n; i++){
    maxv = (maxv<(r[i]-minv))?(r[i]-minv):maxv;
    minv = (minv>r[i])?r[i]:minv;
  }
  cout << maxv << endl;
}



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

int main()
{
  int roads[50][50];
  for (int i = 0; i < 50; i++)
  {
    for (int j = 0; j < 50; j++)
    {
      roads[i][j] = 0;
    }
  }

  int n, m;
  cin >> n >> m;

  int a, b;
  for (int i = 0; i < m; i++)
  {
    cin >> a >> b;
    a--;
    b--;
    roads[a][b] = roads[b][a] += 1;
  }

  for (int i = 0; i < n; i++)
  {
    int res = 0;
    for (int j = 0; j < n; j++)
    {
      res += roads[i][j];
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void){
	double n,k;
	double x[10000],y[10000],z[10000];
	double ans=0,ans2=0,ans3=0;
	double a[100000];

	scanf("%lf%lf",&n,&k);

	for(int i=1;i<=n;i++){
		ans=i;
		ans2=1/n;
		while(ans < k){
			ans*=2;
			ans2/=2;
		}
		//printf("%lf\n",x[i]);
		ans3+=ans2;
	}

	
	printf("%.12lf\n",ans3);
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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; }

const ll INF = 1e15;
const ll MOD = 1e9+7;
const ll LINF = 1e18;


signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  string s; cin>>s;
  ll n=s.size();
  vll ans(n);
  vll a(2);
  rep(i,n){
    if(s[i]=='R'){
      a[i%2]++;
    }else{
      if(i%2) swap(a[0],a[1]);
      ans[i-1]+=a[1];
      ans[i]+=a[0];
      a=vll(2,0);
    }
  }
  
  a=vll(2,0);
  rrep(i,n){
    if(s[i]=='L'){
      a[i%2]++;
    }else{
      if(i%2) swap(a[0],a[1]);
      ans[i]+=a[0];
      ans[i+1]+=a[1];
      a=vll(2,0);
    }
  }
  rep(i,n) cout<<ans[i]<<' ';
  cout<<endl;
}

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

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        double a = sc.nextDouble();
        double b = sc.nextDouble();
        double x = sc.nextDouble();

        if(a*a*b >= 2*x){
            double ans = Math.toDegrees(Math.PI/2.d - Math.atan(x/(b*b*a/2)));
            System.out.println(ans);
        }else{
            double ans = Math.toDegrees(Math.atan((a*a*b-x)/(a*a*a*0.5d)));
            System.out.println(ans);
        }
    }


    private static 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: 22484
#include <bits/stdc++.h>
using namespace std;

int main()
{
   int K;
   cin >> K;
   string S;
   cin >> S;
   if(S.size()>K){
      for(int i=0;i<K;i++){
         cout << S.at(i);
      }
      cout << "..." << endl;
   }
   else{
      cout << S << endl;
   }
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define PI 3.14159265358979323846
using namespace std;
using ll = long long;

int gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }
    else {
        return gcd(b, a % b);
    }
}
int main() {
    int k;
    cin >> k;
    int ans = 0;

    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= k; l++) {
                int d = gcd(i, j);
                ans += gcd(d, l);
            }
        }
    }

    cout << ans << endl;
}

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

typedef long long ll ; 
typedef unsigned long long ull ; 
typedef vector<int> vi ; 
typedef vector<vi> vii ;
typedef vector<ll> vl ;
typedef vector<vl> vll ;
typedef set<int> si ; 
typedef map<int,int> mii ; 
typedef map<ll,ll>  mll ; 
typedef map<string,int> msi ;
typedef set<ll> sl ; 
typedef set<char> sc ; 
typedef pair<int,int> pii ;


#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
const int INF = 1 << 29 ; 
#define MOD (ll)(1e9+7)
#define eps 1e-6
#define pb push_back 
#define mp make_pair 
#define DEBUG(x)		cout << '>' << #x << ':' << x << endl;
#define F first 
#define S second 
#define all(s) s.begin,s.end() 

int main() 
{
	ios::sync_with_stdio(0) ;
	cin.tie(NULL) ; 
	int n ,k;
	cin >> n >> k;
	long long h[n];
	REP(i,n) cin >> h[i];
	long long dp[n];
	REP(i,n) dp[i] = 1e10 + 15;
	dp[0] = 0;
	for(int i = 0; i < n; ++i) {
		//DEBUG(i);
		for(int j = i+1; j <= i + k && j < n; ++j) {
			dp[j] = min(dp[j] , dp[i] + abs(h[j] - h[i]));
		}
		
	}
	cout << dp[n-1] << endl;
	return 0 ; 
}



Measured memory_bytes: 1792
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        String s = sc.next();
        if(n%2 == 0 && s.substring(0,n/2).equals(s.substring(n/2,n))){
            System.out.print("Yes");
        }else{
            System.out.println("No");
        }

    }
}

Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
 
const int MOD = 1e9+7;
 
int main()
{
	int a,b,c,k;
	cin >> a >> b >> c >> k;
	if(a < b) swap(a,b);
	if(a < c) swap(a,c);
	cout << (a<<k) + b + c << endl;
}

Measured memory_bytes: 256
from math import gcd
from functools import reduce
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))

g=reduce(gcd,a)
if g!=1:
  print("not coprime")
  exit()

def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
d=defaultdict(int)
s=set()
for q in a:
  p=primeFactor(q)
  for j in p:
    if d[j]==1:
      print("setwise coprime")
      exit()
    d[j]+=1
print("pairwise coprime")

Measured memory_bytes: 186860
#include <iostream>
using namespace std;
int gcd(int a, int b) {
   if (b == 0)
      return a;
   return gcd(b, a % b);
}
int main() {
   long long a,b,c;
   cin >>a >> b;
   cout  << gcd(a,b) <<endl;
   return 0;
}



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

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

  int max = 1;

  for(int i = 1;i <= X;i++){//底
    for(int j = 2;j <= 10;j++){//肩の数
      if(max < pow(i,j) and pow(i,j) <= X)max = pow(i,j);
    }
  }

  cout << max << endl;


}


Measured memory_bytes: 512
h, w = map(int, input().split())

# =パターン
x, y = divmod(h, 3)
if y == 0:
    x1, x2, x3 = x, x, x
elif y == 1:
    x1, x2, x3 = x+1, x, x
else:
    x1, x2, x3 = x+1, x+1, x

s1, s2, s3 = map(lambda x: x*w, (x1, x2, x3))
ans = s1-s3

# llパターン
x, y = divmod(w, 3)
if y == 0:
    x1, x2, x3 = x, x, x
elif y == 1:
    x1, x2, x3 = x+1, x, x
else:
    x1, x2, x3 = x+1, x+1, x

s1, s2, s3 = map(lambda x: x*h, (x1, x2, x3))
ans = min(ans, s1-s3)

# トパターン
x = -(-w//3)
s1 = x*h
y = w-x
x1, x2 = h//2, (h+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))

# トパターン
x = w//3
s1 = x*h
y = w-x
x1, x2 = h//2, (h+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))

# Tパターン
x = -(-h//3)
s1 = x*w
y = h-x
x1, x2 = w//2, (w+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))

# Tパターン
x = h//3
s1 = x*w
y = h-x
x1, x2 = w//2, (w+1)//2
s2, s3 = x1*y, x2*y
Ss = (s1, s2, s3)
ans = min(ans, max(Ss)-min(Ss))
print(ans)


Measured memory_bytes: 9196
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield set(x for x, _ in group)

N,M,K = m()

po = [0 for i in range(N)]

uni = UnionFind(N-1)

pon = [set() for i in range(N)]

for i in range(M):
    x,y = m()
    po[x-1] -= 1
    po[y-1] -= 1
    uni.unite(x-1,y-1)

for i in range(K):
    x,y = m()
    pon[x-1].add(y-1)
    pon[y-1].add(x-1)

a = list(uni.grouper())


for i in range(len(a)):
    for popo in a[i]:
        po[popo] += len(a[i]) - len(a[i] & pon[popo]) - 1
print(jo(po))



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

int main(void){
    int x, y;
    cin >> x >> y;

    while((x >= 1) && (y >= 1)){
        if(x >= y) x = x % y;
        else y = y % x;
    }
    cout << ((x >= y)? x : y) << endl;
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  int a[n-1];
  rep(i,n-1)cin >> a[i];

  int leader[n];
  memset(leader,0,sizeof(leader));
  rep(i,n-1)leader[a[i]-1]++;

  rep(i,n)cout << leader[i] << endl;
}

Measured memory_bytes: 5200
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <stack>
#include <queue>
#include <vector>

static const int IINF = 1 << 29;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  int H, W;
  std::cin >> H >> W;
  std::vector<std::vector<char>> S(H, std::vector<char>(W));
  for (int i = 0; i < H; ++i)
    for (int j = 0; j < W; ++j)
      std::cin >> S[i][j];

  const int dx[4] = {1, 0, -1, 0};
  const int dy[4] = {0, 1, 0, -1};
  auto idx = [&](int i, int j) { return W * i + j; };

  int N = H * W;
  std::vector<std::vector<int>> dp(N);
  for (int x = 0; x < N; ++x) {
    dp[x].resize(N);
    for (int y = 0; y < N; ++y) {
      dp[x][y] = IINF;
    }
  }

  // 初期値の設定
  for (int x = 0; x < N; ++x)
    dp[x][x] = 0;
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (S[i][j] == '#')
        continue;
      for (int dir = 0; dir < 4; ++dir) {
        int ni = i + dx[dir];
        int nj = j + dy[dir];
        if (ni < 0 or H <= ni or nj < 0 or W <= nj or S[ni][nj] == '#')
          continue;
        dp[idx(i, j)][idx(ni, nj)] = 1;
      }
    }
  }

  // std::cout << dp << std::endl;
  // exit(1);

  // Warshall-Floyd
  for (int z = 0; z < N; ++z)
    for (int x = 0; x < N; ++x)
      for (int y = 0; y < N; ++y)
        chmin(dp[x][y], dp[x][z] + dp[z][y]);


  int res = 0;
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (S[i][j] == '#')
        continue;
      for (int h = 0; h < H; ++h) {
        for (int k = 0; k < W; ++k) {
          if (S[h][k] == '#')
            continue;
          chmax(res, dp[idx(i, j)][idx(h, k)]);
        }
      }
    }
  }
  std::cout << res << std::endl;

  return 0;
}


Measured memory_bytes: 896
N,M = map(int,input().split())

E = [[False]*N for _ in range(N)]

for n in range(N):
  E[n][n] = True

for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  E[a][b] = True
  E[b][a] = True


unvisited = set(range(N))
color = [None]*N
components = []

while unvisited:
  v0 = next(iter(unvisited))
  count = [0,0]

  stack = [(v0,False)]
  while stack:
    v,c = stack.pop()
    if color[v] is None:
      color[v] = c
      unvisited.discard(v)
      count[c] += 1
      for u,f in enumerate(E[v]):
        if not f:
          stack.append((u, not c))

    elif color[v] != c:
      print(-1)
      exit()

  components.append(count)

# DP
L = N//2+1
dp = [False]*L


dp[0] = True

for a,b in components:
  ndp = [False]*L
  for i,f in enumerate(dp):
    if f:
      if i+a < L:
        ndp[i+a] = True
      if i+b < L:
        ndp[i+b] = True
  dp = ndp

for i,f in zip(reversed(range(L)), reversed(dp)):
  if f:
    break
j = N - i

print(i*(i-1)//2 + j*(j-1)//2)

Measured memory_bytes: 11392
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
const int mod=1e9+7;
int a[maxn];
int l[maxn];//记录左边比i要小的数 的个数 
int r[maxn];//记录右边比i要小的数 的个数
int main()
{
	int n,k;
	ll ans;
	ll sam;
	int a[maxn];
	int l[maxn];//记录左边比i要小的数 的个数 
	int r[maxn];//记录右边比i要小的数 的个数
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	scanf("%d%d",&n,&k); 
	sam=(ll)(k+1)*k/2;//总和时要算右边比i小的次数 
	sam-=k; //总和时要算左边比i小的次数 
	sam=(sam+mod)%mod;
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
			if(a[j]<a[i])
				l[i]++;
		for(int j=i+1;j<n;j++)
			if(a[j]<a[i])
				r[i]++;		 
	}
	ans=0; 
	for(int i=0;i<n;i++)
	{
		ans+=(l[i]*sam);
		ans%=mod;
		ans+=(r[i]*(sam+k));
		ans%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2432
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;

int N;
vector<int> d;

int main() {
	cin >> N;
	d.assign(N, 0);
	for (int i = 0; i < N; i++)
		cin >> d[i];
	sort(d.begin(), d.end());

	int l = d[N / 2 - 1];
	int r = d[N / 2];

	cout << r - l << endl;
	return 0;
}


Measured memory_bytes: 640
#from fractions import gcd
"""
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
"""
def gcd(a,b):
    if b==0:
        return a
    r=a%b
    while r!=0:
        a=b
        b=r
        r=a%b
    return b
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)#basementで初期化
 
        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]
 
        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])
 
    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])
 
    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
 

n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,gcd,0)
ans=1
for i in range(n):
    ans=max(ans,gcd(seg.query(0,i),seg.query(i+1,n)))
print(ans)


Measured memory_bytes: 14440