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

long long ans(bool black, long long now, long long prev, vector<vector<long long>>& edge, vector<vector<long long>>& memo){
    if(memo[black][now] > 0)return memo[black][now];
    uint_fast64_t ret(1);
    for(auto i : edge[now]){
        if(i != prev){
            if(black)ret *= ans(0, i, now, edge, memo);
            else ret *= ans(0, i, now, edge, memo) + ans(1, i, now, edge, memo);
            ret %= 1000000007;
        }
    }
    return memo[black][now] = ret;
}

int main(){
    long long N;
    scanf("%lld", &N);

    vector<vector<long long>> edge(N + 1);

    for(int i = 0, x = 0, y = 0; i < N - 1; ++i){
        scanf("%d%d", &x, &y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    edge[0].push_back(1);

    vector<vector<long long>> memo(2, vector<long long>(N + 1, 0));

    printf("%lld\n", ans(0, 0, 0, edge, memo));

    return 0;
}

Measured memory_bytes: 17008
#include <stdio.h>

int main(void)
{
	int a, b, c,yaku;
	yaku = 0;

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

	if ((1 <= a, b, c <= 10000) && (a <= b))
	{
		for (int x = a; x <= b; x++)
		{
			if ((c % x) == 0)
			{
				yaku++;
			}
		}

		printf("%d\n", yaku);
	}
	return 0;
}


Measured memory_bytes: 2108
#include<stdio.h>
#include<math.h>


int main()
{
	int debt = 100000;
	int n, i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		debt = debt*1.05;
		if (debt % 1000 !=0)debt = debt / 1000 *1000 + 1000;
	}
	printf("%d\n", debt);
	return 0;
}

Measured memory_bytes: 1020
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int n, m;
LL ans;

int main(){
    read(n, m);
    ans += n * (n - 1) / 2 + m * (m - 1) / 2;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 256
from bisect import bisect_left
A, B, Q = map(int,input().split())
INF = 2 * 10 ** 10
S = [-INF]
T = [-INF]
for _ in range(A):
    S.append(int(input()))
S.append(INF)
for _ in range(B):
    T.append(int(input()))
T.append(INF)
for _ in range(Q):
    x = int(input())
    s = bisect_left(S, x)
    t = bisect_left(T, x)
    ans = min(max(S[s], T[t]) - x, x - min(S[s-1], T[t-1]), 2 * S[s] - T[t-1] - x, 2 * T[t] - S[s-1] - x, T[t] + x - 2 * S[s-1], S[s] + x - 2 * T[t-1])
    print(ans)

Measured memory_bytes: 12092
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	void doIt() {
		while(true){
			try{
				double v = sc.nextDouble();
				double t = v / 9.8;
				double y = 4.9 * t * t;
				int ans = (int) Math.ceil(y / 5)+1;
				System.out.println(ans);
			}catch(Exception g){
				System.exit(0);
			}
		}
	}
    public static void main(String[] args) {
    	new Main().doIt();
    }
}

Measured memory_bytes: 18652
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i <= n; i++) 

int main() {
    int A, B, ans = 0;
    cin >> A >> B;
    if (A >= B) {
        ans += A;
        --A;
    } else {
        ans += B;
        --B;
    }
    if (A >= B) {
        ans += A;
        --A;
    } else {
        ans += B;
        --B;
    }
    cout << ans << endl;
    return 0;
}

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"
*/

int main()
{
    int N;
    cin >> N;
    bool yes = false;
    for(int i=0; i<3; i++){
        if(N % 10 == 7) yes = true;
        else N /= 10;
    }
    if(yes) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
typedef long long int ll;
using namespace std;
using Graph = vector<vector<int>>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    vector<int> l(Q), r(Q);
    rep(i,Q)cin>>l[i]>>r[i];

    vector<int> _S(N+1);
    int cnt = 0;
    _S[0]=0;
    _S[1]=0;
    rep(i,N-1){
        if(S.substr(i,2)=="AC"){
            cnt++;
        }     
        _S[i+2]=cnt;
    }

    vector<int>ans(Q);
    rep(i,Q){
        ans[i]=_S[r[i]]-_S[l[i]];
        cout<<ans[i]<<endl;
    }
 //   system("pause");
    return 0;
}

Measured memory_bytes: 2640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define fbo find_by_order
#define ook order_of_key
#define INF (ll)1e18
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m;cin>>n>>m;
    vector<vi>vec(n+1);
    bool vst[n+1];
    mset(vst);
    ll dist[n+1];
    ll dp[n+1];
    for(int i=0;i<m;i++){
        ll a,b;cin>>a>>b;
        vec[a].pb(b);
        vec[b].pb(a);
    }
    vst[1]=1;
    dist[1]=0;
    queue<int>q;
    q.push(1);
    int j=1;
    while(!q.empty()){
        int s=q.front();q.pop();
        for(auto u:vec[s]){
            if(vst[u])continue;
            vst[u]=true;
            j++;
            dist[u]=dist[s]+1;
            dp[u]=s;
            q.push(u);
        }
    }
    if(j<n){
        cout<<"No\n";return 0;
    }
    cout<<"Yes\n";
    for(int i=2;i<=n;i++){
        cout<<dp[i]<<"\n";
    }
}


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

#define endl "\n"
#define int long long
#define vec(x) vector<x>
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define matrix(x) vector<vector<x>>
#define all(v) v.begin(),v.end()
#define mem(a,b) memset(a, b, sizeof a)
#define setBits(n) __builtin_popcountll(n)
#define prec(n) fixed<<setprecision(n)
#define ff first
#define ss second
#define print(x) for(auto it:x) cout<<it<<" ";
#define dbg(x) cerr<<#x<<" :: "<<x<<endl;
#define dbg2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
const int INF = 1e9;
const int MOD = 1e9 + 7; 
const double pi = acos(-1);
int power(int a,int b,int m=MOD)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}
int dir[]={-1, 0, 1, 0, -1};
int dx[]={1,1,0,-1,-1,-1, 0, 1};
int dy[]={0,1,1, 1, 0,-1,-1,-1};

const int N = 1e5+1;
int dp[105][N];
int wt[105],val[105];

int helper(int i,int W)
{
	if(i<0)
	return 0;
	if(dp[i][W]!=-1)
	return dp[i][W];
	int ans=helper(i-1,W);
	if(wt[i]<=W)
	ans=max(ans,val[i]+helper(i-1,W-wt[i]));
	return dp[i][W]=ans;
}

void solve()
{
	int i,n,W;
	cin>>n>>W;
	for(i=0;i<n;i++)
	cin>>wt[i]>>val[i];
	mem(dp,-1);
	cout<<helper(n-1,W)<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--)
		solve();
}

Measured memory_bytes: 82432
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;            //

int main(void)
{
    int A, B;
    char op;
    cin >> A >> op >> B;

    int ans;
    if (op == '+')
    {
        ans = A + B;
    }
    else
    {
        ans = A - B;
    }
    cout << ans << endl;
    return (0);
}

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

if N == 0:
    print(X)
    exit()

P = list(map(int, input().split()))

cnt = 0
while True:
    if X - cnt not in P:
        print(X - cnt)
        exit()
    if X + cnt not in P:
        print(X + cnt)
        exit()
    cnt += 1


Measured memory_bytes: 9172
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

n = ni()
H = lma()
cnt=0
tmp=0
prev=H[0]
for h in H:
    if prev>=h:
        tmp+=1
    else:
        cnt=max(cnt,tmp)
        tmp=1
    prev=h
print(max(cnt,tmp)-1)


Measured memory_bytes: 20720
N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]
c_set = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        c_set[(i+j)%3][c[i][j]-1] += 1
ans = 1e9
for c_1 in range(C):
    for c_2 in range(C):
        for c_3 in range(C):
            if c_1==c_2 or c_1==c_3 or c_2==c_3:
                continue
            c_list = [c_1,c_2,c_3]
            k = 0
            for i in range(C):
                for j in range(3):
                    k += d[i][c_list[j]-1]*c_set[j][i]
            ans = min(ans,k)
print(ans)

Measured memory_bytes: 5620
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <complex>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp make_pair
#define ERASE(v,i) (v).erase(remove(all(v),i),(v).end())
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;
#define LINE cerr<<"LINE: "<<__LINE__<<endl;

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T> void preview(T a,T b){for(T it=a;it!=b;++it)cerr<<*it<<" ";cerr<<endl;}

const int INF = 100000000;
const double PI = acos(-1.0), EPS = 1e-10;

int main() {
	for(double a; cin >> a;) {
		double ans = a;
		for(int i = 2; i <= 10; i++) {
			a = (i % 2 == 0) ? (a * 2) : (a / 3);
			ans += a;
		}
		printf("%.8f\n", ans);
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <numeric>
typedef long long int ll;
using namespace std;
int main(){
	int C;
	char s; 
	cin >> C;
	for(int k=0;k<C;k++){
		cin>>s;
		if(s=='Y'){
			cout<<"Four"<<endl;
			return 0;
		}
	}
	cout<<"Three"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;
void f(){
 int n, k;

 cin >> n >> k;
 int ans = 0, one = 0, left, right, temp, rem = 0;

 //vector<int> seq(n);
 forn(i,n){
     cin >> temp;
     if(temp == 1)
        one = i;
 }
 /*
 left = one;
 right = (n - 1) - one;
 if((k - 1) > left && left > 0){
     right -= (k - 1) - left;
     left = 0;
     ans++;
 }
if((k - 1) > right && right > 0){
     left -= (k - 1) - right;
     right = 0;
     ans++;
 }

 if(left > 0){
    ans += left / (k - 1);
    if(left  % (k-1) != 0){
        ans++;
        if(left / (k - 1) != 0)
            rem += (k-1) - left % (k-1);
    }
 }
 if(right > 0){
    ans += right /(k - 1);
    if(right % (k-1) != 0){
        ans++;
        if(right /(k - 1) != 0)
        rem += (k-1) - right % (k-1);
    }
 }
 if(rem > (k-1))
    ans--;
*/
ans = 1;
while(k + (ans-1)*(k-1) < n){
    ans++;
}
 cout << ans << endl;
}
   
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    
  f();
 return 0;
}

Measured memory_bytes: 3656
N = int(input())
A = [0] + [int(i) for i in input().split()]

from itertools import accumulate
from collections import Counter
from math import factorial

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

Acum_cnt = Counter(list(accumulate(A)))

ans = 0
for _, cnt in Acum_cnt.items():
    if cnt < 2:
        continue

    ans += combinations_count(cnt, 2)

print(ans)

Measured memory_bytes: 41740
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <string>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
  long long int n,x;
  long long int a[100100];
  cin>>n>>x;
  REP(i,n)cin>>a[i];
  long long int ans=0;
  for(int i=1;i<n;i++){
    if(a[i]+a[i-1]>x){
      ans+=(a[i]+a[i-1]-x);
      a[i]=max(0LL,x-a[i-1]);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<i_i, int> p_i;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef vector<char> vc;
typedef vector<vector<char> > vvc;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
template<class T> using vv=vector<vector< T > >;
typedef deque<int> di;
typedef deque<deque<int> > ddi;

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len - 1) s << "\t";
    }
    return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
    int len = vv.size();
    for (int i = 0; i < len; ++i) {
        s << vv[i] << endl;
    }
    return s;
}

int main() {
    int n;
    cin >> n;
    vi l(2*n);
    rep (i, 2*n) { cin >> l[i]; }
    sort(all(l));
    int ans = 0;
    rep (i, n) {
        ans += l[2*i];
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 888
#include <stdio.h>
#include <stdlib.h>
#define N 8

int main(void)
{
	int i,j,k;
	char sq[N][N];
	char change[N][N];

	for(i=0; i<N; i++)
		scanf("%s",&sq[i]);
	for(k=1; k<=3; k++){
		printf("%d\n",90*k);
		for(i=0; i<N; i++)
			for(j=0; j<N; j++)
				change[i][j]=sq[i][j];	
		for(i=0; i<N; i++){
			for(j=0; j<N; j++){
				sq[i][j]=change[N-1-j][i];
				printf("%c",sq[i][j]);
			}
			puts("");
		}
	}

	return 0;
}

Measured memory_bytes: 552
# dpに最大桁数を持たせる
N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
f = [-1, 2,5,5,4,5,6,3,7,6] # 1-indexed

# dp[i]: マッチi本数で作れる最大の桁数(int)
dp = [-float('inf')]*(N+1)
dp[0] = 0
for i in range(N+1):
    nxt = dp[i]
    for aj in A:
        if i-f[aj]<0: continue
        nxt = max(nxt, 
                  dp[i-f[aj]] + 1)
    dp[i] = nxt
    #print(dp)
#print(dp[N])
keta = dp[N]
ans = ""
matchs = N
# 上位の桁から貪欲に
while keta>0:
    for aj in A:
        if matchs-f[aj] < 0: continue
        if dp[matchs-f[aj]] == keta-1:
            ans += str(aj)
            matchs -= f[aj]
            keta -= 1
            break
print(ans)

Measured memory_bytes: 42220
<?php
fscanf(STDIN, '%s', $s);
if ($s != strrev($s)) {
  echo "No";
  exit;
}
$counted_s = strlen($s);
$half_s = (int)floor($counted_s/2);
$flont_s = substr($s, 0, $half_s);
$end_s = substr($s, -$half_s);
if ($flont_s == $end_s && $flont_s == strrev($flont_s)) {
  echo "Yes";
} else {
  echo "No";
}

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

int main() {

  string S, T;
  cin >> S >> T;

  string answer = "No";

  for (int i = 0; i < S.size(); i++) {
    string s_ = S.substr(i, S.size() - i);
    s_ += S.substr(0, i);
    if (s_ == T) {
      answer = "Yes";
      break;
    }
  }
  
  cout << answer << endl;

}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int a, b;
    cin >> a >> b;

    if (a >= 13)
    {
        cout << b << endl;
    }
    else if (a >= 6)
    {
        cout << b / 2 << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}

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

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

int main()
{
    int N;
    cin >> N;
    int sum = 0;
    repwi(i, 1, N+1){
        if(to_string(i).length() % 2 == 1){
            sum++;
        }
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
class table{
  char tab[128];
public:
  table(){for(unsigned char i=0;i<128;++i)tab[i]=i;}
  char& operator[](char p){return tab[p];}
  const char& operator[](char p)const{return tab[p];}
};
int main(){
  int n;
  while(1){
    std::cin>>n;
	if(!n)return 0;
	table tab;
	while(n--){char a,b;std::cin>>a>>b;tab[a]=b;}
    std::cin>>n;
    while(n--){char a;std::cin>>a;std::cout<<tab[a];}
    std::cout<<std::endl;
  }
}

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


void init(){
    cin.tie(0);
    cin.sync_with_stdio(0);
}

#define ll long long
#define ld long double
#define ull unsigned long long
#define ull unsigned long long
#define mod 1000000007
#define pi (3.1415926)

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

#define scd(a)  scanf("%lld",&a)
#define scdd(a,b)	scanf("%lld%lld",&a,&b)
#define scddd(a,b,c)	scanf("%lld%lld%lld",&a,&b,&c)
#define ptab(a)	printf("%lld ",a)
#define pdn(a)	printf("%lld\n",a)
#define pddn(a,b)	printf("%lld %lld\n",a,b)
#define pdddn(a,b,c)	printf("%lld %lld %lld\n",a,b,c)

#define Filein(N) freopen("N.txt", "r", stdin);
#define Fileout(N) freopen("N.txt", "w", stdout);

#define forr(n) for(ll i=0;i<n;i++)
#define rev(n) for(ll i=n-1;i>=0;i--)
#define forp(x, y) for(ll i=x;i<y;i++)
#define loop( j, k, in) for (ll i=j ; i<k ; i+=in)

#define en "\n"
#define sp " "
#define eps 1.0E-14
#define l length()
#define preci(x) cout << fixed<<setprecision(x)
#define inf LONG_LONG_MAX
#define ninf LONG_LONG_MIN

ull fastpow(ull a,ull b)
{
  ull wynik=1;
  while (b)
  {
    if (b&1)wynik=(wynik*a)%mod;
    a=(a*a)%mod;
    b>>=1;
  }
  return wynik;
}

bool odd(int n)
    {
        int x = sqrt(n);
    for (int i=2 ; i<=x ; ++i)

    {
        if(n%i == 0)return false;
    }

    return true;
    }
ll fact(int n ){

long long fact =1;

for (int i =2 ;i<=n;++i)

{
    fact*=i;
}
return fact;
}

bool prim(long long a){

long long s = sqrt(a);

for (int i=2 ; i<= s ;++i){

    if (a % i == 0)return false;
}
return true;
}

ll sum (int n ){return ((n*(n+1)) / 2) ;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

bool myfunction (string i,string j) /* this function to check who is grater in
sorting strings as numbers ////////
int n;
    cin>>n;
    vector <string> arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];


    sort(arr.begin(),arr.end(),myfunction);

    for(int i=0;i<n;i++)1
        cout<<arr[i]<<endl;
*/
{
    int n=i.length();
    int m=j.length();
    if(n==m)
        return (i<j);

    return n<m;
}
long long solve (int a, int b)
{
    return min(a,min(b , (a+b) / 3));
}

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

    char c; cin>>c;

    if (c>='A'&&c<='Z')cout << "A";
    else cout << "a";
}




Measured memory_bytes: 3616
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

int main(){

    ll N;
    cin >> N;
    vector<ll>v(N);
    ll sum = 0;
    rep(i, N){
        cin >> v[i];
        sum += v[i];
    }
    ll ans = sum;
    for(ll tmp = 0, i = 0; i < N - 1; i++){
        tmp += v[i];
        ll a = tmp;
        ll b = sum - tmp;
        chmin(ans, abs(a - b));
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 1792
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、要素の個数を負の値で保持している
            return x  # 自身が親であるということ
        else:
            self.parents[x] = self.find(self.parents[x])  # 再帰的に親を探しにいく
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)  # この変数xに格納されているものは必ず根のノード
        y = self.find(y)  # この変数yに格納されているものは必ず根のノード
        if x == y:
            return  # もし同じ親ならば何も起こらない

        if self.parents[x] > self.parents[y]:  # それぞれ、要素の個数が負で格納されている
            # yのグループの方が要素が多いの場合（yの方が値が小さいということは、負の世界では値が大きいため）
            x, y = y, x  # 必ずxの方が要素が多い状態にする

        self.parents[x] += self.parents[y]  # 負の値だが、これでいい
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    def size(self, x):
        return -self.parents[self.find(x)]  # 親まで辿ればグループの大きさが負で格納されているため、それにマイナスをつけてreturnする

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 親が同じならTrueが返却される

    def members(self, x):  # この実装変じゃね？
        root = self.find(x)  # 親の値を取得する
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # 親であるノードの番号を全部取得する
        return [i for i in range(self.n) if self.find(i) < 0]

    def group_counts(self):
        return len(self.roots())  # グループの数を返す

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}  # 親のノード番号をキーにして、子のノードを対応させた辞書を返す

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


N, M = map(int, input().split())
graph = [[] for _ in range(N)]  # 隣接行列
brige_info = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, map(int, input().split()))
    brige_info.append((a, b))
    # graph[a].append(b)
    # graph[b].append(a)
ans = [int(N*(N-1))//2]*M
uf = UnionFind(N)

for i in reversed(range(1, M)):
    if uf.same(brige_info[i][0], brige_info[i][1]):
        ans[i-1] = ans[i]  # その橋を繋いでも不便さは改善されなかった、何も変わらない
        continue

    ans[i-1] = ans[i] - uf.size(brige_info[i][0]) * uf.size(brige_info[i][1])
    uf.union(brige_info[i][0], brige_info[i][1])

for i in range(M):
    print(ans[i])


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

typedef long long ll;

vector<ll> pf (long long x) {
	vector<ll> result;
	for (ll i = 2; i <= x/i; ++i) {
			while (x % i == 0) {
			result.push_back(i);
			x /= i;
		}
	}
	if (x > 1) result.push_back(x);
	return result;
}

int main() {
	long long N;
	scanf("%lld", &N);
	vector<ll> v = pf(N);
	ll sz = (ll)v.size();
	ll ans = 10000000;
	for (ll i = 0; i < (1 << sz); i++) {
		ll prod = 1;
		for (ll j = 0; j < sz; j++) {
			if (i & (1 << j)) prod *= v[j];
		}
		ll vprod = N / prod;
		prod = max(prod, vprod);
		prod = log10(prod) + 1;
		ans = min(ans, prod);
	}
	printf("%lld", ans);
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int a,b;
	char op = '+';

	while(op != '?'){
	/*	scanf("%d",&a);
		scanf(" %c",&op);
		scanf("%d",&b);
	*/

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

	//	printf("input =\n \t%d\n \t%c\n \t%d\n",a,op,b);

		switch(op){
			case '+':
			printf("%d\n",a + b);
			break;

			case '-':
			printf("%d\n",a - b);
			break;

			case '*':
			printf("%d\n",a * b);
			break;

			case '/':
			printf("%d\n",a / b);
			break;

			case '?':
			break;

			default:
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 1792
object Main{
 def main(args:Array[String]):Unit={
  val sc = new java.util.Scanner(System.in)
  println(sc.nextInt match {
   case 25 => "Christmas"
   case 24 => "Christmas Eve"
   case 23 => "Christmas Eve Eve"
   case 22 => "Christmas Eve Eve Eve"
  })
 }
}

Measured memory_bytes: 25884
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define endl "\n"
#define ar array
#define pb push_back
#define sz(X) ((int)(X).size())
#define pcnt __builtin_popcount
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define get_pos(c, x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define all(X) (X).begin(), (X).end()
#define ms(c,x)  memset(c,x,sizeof c)
#define  No cout<<"NO"<<endl;
#define  Yes cout<<"YES"<<endl;
#define  nl cout<<endl;
template<typename T>
using orderedSet=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
ostream &operator+(ostream &out, const vector<T> &vec) {
    for (const auto &x : vec) {
        out << x << " ";
    }
    out << "\n";
    return out;
}

template<typename T>
ostream &operator*(ostream &out, const vector<T> &vec) {
    for (const auto &x : vec) {
        out + x;
    }
    return out;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &vec) {
    for (auto &x : vec) {
        in >> x;
    }
    return in;
}

template<class T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }


const int mod = 1e9 + 7;
const int mod2 = 998244353;
const ll INF = 1e9 + 6;

ll add(ll a, ll b) {
    a += b;
    return a % mod;
}

ll mul(ll a, ll b) {
    a *= b;
    return a % mod;
}

inline ll power(ll x, ll y, ll p) {
    ll res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

inline ll modInverse(ll x, ll p) {
    return power(x, p - 2, p);
}
const int MXN=302;
double cache[MXN][MXN][MXN];
ll cnt[4];

double dp(ll one,ll two,ll three,ll n){
    if(one==0&&two==0&three==0){
        return 0;
    }
    if(one<0||two<0||three<0){
        return 0;
    }
    double &ans=cache[one][two][three];
    if(ans!=-1){
        return ans;
    }
    double sum=one+two+three;
    return  ans=one*dp(one-1,two,three,n)/(sum)+two*dp(one+1,two-1,three,n)/sum+three*dp(one,two+1,three-1,n)/sum+n*1.0/sum;
}
void solve() {
    int n;
    cin >>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        cnt[x]++;
    }
    for(int i=0;i<MXN;i++)for (int j = 0; j <MXN ; ++j)for (int k = 0; k < MXN; ++k)cache[i][j][k]=-1;

    cout.precision(10);
    cout<<fixed<<dp(cnt[1],cnt[2],cnt[3],n)<<endl;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    //cin >> t;
    while (t--)solve();
#ifndef ONLINE_JUDGE
    cerr << endl << "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
#endif
    return 0;
}
//look if it requires ll

Measured memory_bytes: 219036
n,m,c = map(int, input().split())
B = list(map(int, input().split()))

cnt = 0
for i in range(n):
    judge = 0
    A = list(map(int, input().split()))
    for j in range(m):
        judge += A[j]*B[j]
    if judge + c > 0:
        cnt += 1
print(cnt)

Measured memory_bytes: 9124
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long L = sc.nextLong();
		long R = sc.nextLong();
		sc.close();
		long anser = 0;
		long min = 2 * (long) Math.pow(10, 9);
		//大きすぎる値は制約を越えるので０を出す
		if(R-L>=2018) System.out.println(0);
		else {
			for(long i = L ; i<=R;i++) {
				for(long j = i+1; j <= R; j++) {
					anser = (i*j)%2019;
					min = Math.min(anser, min);
				}
			}
		System.out.println(min);
		}
	}
}

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


typedef long long ll;

const int INF = 1e6;
const int MAX_N = 1005;

const int dx[4] = { -1,0,0,1 };
const int dy[4] = { 0,-1,1,0 };

int M[MAX_N][MAX_N];

struct P
{
	int x;
	int y;
	int st;
	P() {}
	P(const int& x, const int& y, const int& st)
		:x(x), y(y), st(st) {}
};


int main()
{
	int H, W;
	char ch;

	scanf("%d%d", &H, &W);

	queue<P> q;
	for (int i = 1; i <= H; ++i)
	{
		for (int j = 1; j <= W; ++j)
		{
			scanf(" \n%c", &ch);
			if (ch == '#')
			{
				M[i][j] = 0;
				q.push(P(i, j, 0));
			}
			else
			{
				M[i][j] = INF;
			}
		}
	}

	while (!q.empty())
	{
		P cur = q.front();
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			P nxt(cur.x + dx[i], cur.y + dy[i], cur.st + 1);
			if (M[nxt.x][nxt.y] > nxt.st)
			{
				M[nxt.x][nxt.y] = nxt.st;
				q.push(nxt);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= H; ++i)
	{
		for (int j = 1; j <= W; ++j)
		{
			if (M[i][j] > ans)
			{
				ans = M[i][j];
			}
		}
	}
	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 16000
def main():
    n,m=map(int,input().split())
    A=[]
    B=[]
    A=[list(map(int,input().split())) for _ in range(n)]
    B=[int(input()) for _ in range(m)]

    for a in A:
        ans=0
        for a_value,b_value in zip(a,B):
            ans+=a_value*b_value
        print(ans)

if __name__=="__main__":
    main()


Measured memory_bytes: 6004
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <math.h>
#include <cmath>

#define INF 100000000
#define ll long long

using namespace std;

int main() {
	string s;
	ll ans = 0;
	cin >> s;

	for (int i = 0; i < s.size() - 1; i++)
	{
		if (s[i] != s[i + 1]) {
			ans++;
			continue;
		}
		else {
			continue;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 512
def divisors(N):
    U = int(N ** 0.5)
    L, R = [], []
    all((L.append(i), R.append(N // i)) for i in range(1, U) if N % i == 0)
    if N % U == 0:
        L.append(U)
    R.reverse()
    L += R
    return L

N, M = map(int, input().split())
print(max(d for d in divisors(M) if d * N <= M))


Measured memory_bytes: 3060
M=10**9+7
H=Hash.new{_1[_2]=0,0}
$<.drop(s=o=1).map{a,b=_1.split.map &:to_r
a==0&&b==0 ? o-=1 :(r,f=b==0 ? [0r,1] : a/b<0 ? [-b/a,1] : [a/b,0]
H[r][f]+=1)}
H.map{|k,v|t=-1
v.map{t+=2.pow _1,M}
s=s*t%M}
p (s-o)%M

Measured memory_bytes: 74416
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
int mod=163577857;
inline int gcd(int a,int b){if(a==0) return b;return gcd(b%a,a);}
inline int power(int a,int n,int m){if(n==0)return 1;int p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
vector<int>adj[100009];
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x;
    cin>>x;
    for(int i=-1000;i<=1000;i++)
    {
        int flag=0;
        for(int j=-1000;j<=1000;j++)
        {
           int d=pow(i,5);
           int e=pow(j,5);
           if(d-e==x)
           {
               cout<<i<<" "<<j;flag=1;break;
           }
        }
        if(flag==1)
            break;
    }

    return 0;
}


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

int main(){
	int i;
	char S[20];
	char T[] = "YAKI";
	scanf("%s", S);
	for(i = 0; i < 4; i++){
		if(S[i] != T[i]){
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 128
from collections import deque
n = int(input())
task = deque()
now = 0
for i in range(n):
  task.append(tuple(map(int, input().split())))
task = deque(sorted(task, key = lambda x: x[1]))
while True:
  work = task.popleft()
  now+=work[0]
  if now>work[1]:
    print('No')
    break
  if len(task) == 0:
    print('Yes')
    break

Measured memory_bytes: 96308
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define int long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second

using namespace std;
int pallindr(string s, int i, int j)
{
	while (i <= j)
	{
		if (s[i] != s[j])
			return 0;
		i++;
		j--;
	}
	return 1;
}
int dp[1001][1001];
int pallindrome_partitioning(string s, int i, int j)
{
	if (i >= j)
		return 0;
	if (pallindr(s, i, j))
	{
		return dp[i][j] = 0;

	}

	if (dp[i][j] != -1)
		return dp[i][j];

	int ans = INT_MAX;
	for (int k = i; k < j; k++)
	{
		int left, right;
		if (dp[i][k] != -1)
			left = dp[i][k];
		else
		{
			left = pallindrome_partitioning(s, i, k);
			dp[i][k] = left;
		}

		if (dp[k + 1][j] != -1)
			right = dp[k + 1][j];
		else
		{
			right = pallindrome_partitioning(s, k + 1, j);
			dp[k + 1][j] = right;
		}

		int xx = left + right + 1;
		ans = min(ans, xx);
	}
	return dp[i][j] = ans;


}

int32_t main()
{
	std::ios::sync_with_stdio(false);


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

	int res = 0;
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum = (sum + a[i] + mod) % mod;

	for (int i = n - 1; i >= 0; i--)
	{
		sum = (sum - a[i]) % mod;
		res = (res + (a[i] * sum) % mod + mod) % mod;

	}
	cout << (res + mod) % mod << endl;
	return 0;
}


Measured memory_bytes: 5204
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pairSS
#define int long long
#define MOD 1000000007
int gcd(int a,int b){
  if(a==0){
    return b;
  }
  return gcd(b%a,a);
}
int lcm(int a,int b){
  return a*b/gcd(a,b);
}
int keta(int a){
  int count = 0;
  while(a!=0){
    a = a/10;
    count++;
  }
  return count;
}
signed main(){
  int n;
  cin >> n;
  int count = 0;
  for(int i=1;i<n+1;i++){
    if(keta(i)%2==1){
      count++;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 256
N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

def farthest_node_and_dist(s):
    dist = [N]*N
    dist[s] = 0
    stack = [s]
    ret_node = -1
    ret_dist = 0
    while stack:
        v = stack.pop()
        d = dist[v]
        for to in es[v]:
            if d+1 < dist[to]:
                dist[to] = d+1
                stack.append(to)
                if ret_dist < d+1:
                    ret_dist = d+1
                    ret_node = to
    return (ret_node, ret_dist)

n,d = farthest_node_and_dist(0)
n,d = farthest_node_and_dist(n)
print('Second' if d%3==1 else 'First')

Measured memory_bytes: 61448
int main(void)
{
  int n,p,hako,sum=0;
  int i;
  scanf("%d",&n);
  while(i<n)
  {
    scanf("%d",&p);
    if(p>hako)
    {
      sum+=hako;
      hako=p;
    }
    else {
        sum+=p;
    }
    i++;
  }
  sum+=hako/2;
  printf("%d",sum);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int main()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    int st[30];
    int ed[30];
    int x = 0;
    for (int m=0;m<26;m++)
    {
        char t = m + 'a';
        for (int i = 0;i<n;i++)
        {
            bool found = false;
            if (s[i] == t)
            {
                for (int j = n-1;j>i;j--)
                {
                    if (s[j] == t)
                    {
                        st[x] = i;
                        ed[x] = j;
                        x++;
                        found = true;
                        break;
                    }
                }
            }
            if (found) break;
        }
    }
    int ans = 0;
    for (int i=0;i<n;i++)
    {
        int ad = 0;
        for (int j=0;j<x;j++)
        {
            if (st[j] <= i && ed[j] > i) ad++;
        }
        ans = (ad > ans ? ad : ans);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
from bisect import bisect_left as bisect

n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

BtoA=[]
for b in B:
    BtoA.append(bisect(A,b))

#累積和
sum_BtoA=[BtoA[0]]
for i in range(n-1):
    sum_BtoA.append(sum_BtoA[i]+BtoA[i+1])


#CtoB=[]
#for callable in range(n):
#    CtoB.append(bisect(B,C[i]))
#
##累積和
#sum_CtoB=[CtoB[0]]
#for i in range(n-1):
#    sum_CtoB.append(sum_CtoB[i]+CtoB[i+1])

ans=0
for c in C:
    index=bisect(B,c)
    if index>0:
        ans+=sum_BtoA[index-1]

print(ans)







Measured memory_bytes: 31304
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 5010
#define maxint 0x7fffffff/2
using namespace std;
double pi=3.1415926;
int main() {
	int n;
	cin>>n;
	double r=double(1.0*n);
	printf("%.4lf",1.0*r*2.0*1.0*pi);
	return 0;
}


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

#define int long long

using namespace std;

int a[100001];

 main () {
	int n, k;
	cin >> n >> k;
	int gcd = 0;
	for (int i = 1;i <= n;i ++) {
		cin >> a[i];
  		gcd = __gcd (a[i], gcd);
  	}
  	for (int i = 1;i <= n;i ++) {
  		if (a[i] >= k && (a[i] - k) % gcd == 0) {
  			cout << "POSSIBLE";
  			return 0;
  		}
  	}        
  	cout << "IMPOSSIBLE";
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define alll(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}cout<<endl;}

class UF    {
public:
    int *id, cnt, *sz;
    // Create an empty union find data structure with N isolated sets.
    UF(int N)   {
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++)    {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF()    {
        delete [] id;
        delete [] sz;
    }
    // Return the id of component corresponding to object p.
    int find(int p)    {
        int root = p;
        while (root != id[root])
            root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    // Replace sets containing x and y with their union.
    void merge(int x, int y)    {
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        
        // make smaller root point to larger one
        if   (sz[i] < sz[j])    {
            id[i] = j;
            sz[j] += sz[i];
        } else    {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }
    // Are objects x and y in the same set?
    bool connected(int x, int y)    {
        return find(x) == find(y);
    }
    // Return the number of disjoint sets.
    int count() {
        return cnt;
    }
};

int main() {
    ll n,m;
    cin>>n>>m;
    vector<ll> va,vb;
    rep(i, m){
        ll a,b;
        cin>>a>>b;
        va.push_back(a-1);
        vb.push_back(b-1);
    }
    reverse(alll(va));
    reverse(alll(vb));
    ll sum = n*(n-1)/2;
    auto uf = new UF(n);
    
    vector<ll> yu;
    rep(i, m){
        yu.push_back(sum);
        ll a = va[i];
        ll b = vb[i];
        if(!uf->connected(a, b)){
            auto prod = uf->sz[uf->find(a)] * uf->sz[uf->find(b)];
            sum-=prod;
        }
        uf->merge(a, b);
    }
    reverse(alll(yu));
    prr(yu);
    
}



Measured memory_bytes: 5356
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<assert.h>
#include<string>
#include<cstdlib>
#include<cctype>
#include<unordered_map>
#include<sstream>
#include<numeric>
#include<stack>
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 9e18;
constexpr int inf = 1e9;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
};
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
};

// intやllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ----------------------------------------------------------------------------

int main(){
  int H,W;
  cin >> H >> W;
  vector<vector<int>> G(10, vector<int> (10));
  for(int i=0; i<10; i++){
    for(int j=0; j<10; j++){
      cin >> G[i][j];
    }
  }
  vector<int> cnt(10,0);
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      int a;
      cin >> a;
      if(a == -1) continue;
      cnt[a]++;
    }
  }
  for(int k=0; k<10; k++){
    for(int i=0; i<10; i++){
      for(int j=0; j<10; j++){
        chmin(G[i][j],G[i][k]+G[k][j]);
      }
    }
  }
  int ans = 0;
  for(int i=0; i<10; i++){
    ans += cnt[i]*G[i][1];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
learn = []
verify = []
for i in range(N):
    a = tuple(map(int, input().split()))
    if a[2] > 0 and learn == []:
        learn.append(a)
    else:
        verify.append(a)

for Cx in range(101):
    for Cy in range(101):
        H = learn[0][2] + abs(learn[0][0] - Cx) + abs(learn[0][1] - Cy)
        right = True
        for v in verify:
            if max(H - abs(v[0] - Cx) - abs(v[1] - Cy), 0) != v[2]:
                right = False
                break
        else:
            break
        continue
    else:
        continue
    break

print(Cx, Cy, H)


Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		// map(HashMap)に全データ、list(ArrayList)に商品名を格納
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		ArrayList<String> list = new ArrayList<String>();
		for (int i = 0; i < n; i++){
			String a = sc.next();
			int b = sc.nextInt();
			if (map.containsKey(a)){
				map.put(a, map.get(a) + b);
			} else {
				map.put(a, b);
				list.add(a);
			}
		}
		sc.close();
		// listのソート
		Collections.sort(list, new CompArray());

		// 出力していく
		for(String a: list){
			System.out.println(a+" "+map.get(a));
		}
	}

	static class CompArray implements Comparator<String>{
		@Override
		public int compare(String s1, String s2){
			// 長さの比較。短い方を持ってくる。
			int l1 = s1.length();
			int l2 = s2.length();
			if (l1 != l2){
				return l1 - l2;
			} else {
			// 長さが同じ場合は文字を比較。若い文字を優先
				for (int i = 0; i < l1; i++){
					char c1 = s1.charAt(i);
					char c2 = s2.charAt(i);
					if (c1 != c2){
						return c1 - c2;
					}
				}
			}
			return 0;
		}
	}
}


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

int main(){
  int x,y;
    
  while(1){
      cin >> x >> y ;
    if ( x == 0 && y == 0 ) break;
        if ( x < y ){
      cout << x << " " << y << endl;
    }
    else {
      cout << y << " " << x << endl;
    }
  }
}


Measured memory_bytes: 3036
#include <bits/stdc++.h>
#define ___                      \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(0);
#define endl '\n'
#define pii pair<int, int>
#define MAX INT_MAX
#pragma GCC optimize("Ofast")
#define int long long
const int MOD = (1e9 + 7);
using namespace std;
#define vvi vector<vector<int>>
signed main()
{
	___ 
	int n,m;
	cin>>n>>m;
	int arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
	pii gate[m];
	for(int i=0;i<m;i++){
		cin>>gate[i].second>>gate[i].first;
	}
	sort(arr,arr+n);
	sort(gate,gate+m);
	//for(int i=0;i<m;i++) cout<<gate[i].first<<" ";
	//cout<<endl;
	int ind=m-1;
	for(int i=0;i<n;i++){
		if(ind<0) break;
		if(arr[i]<gate[ind].first){
			arr[i]=gate[ind].first;
			gate[ind].second--;
			if(gate[ind].second==0) ind--;
			//cout<<arr[i]<<endl;
		}
	}
	int sum=0;
	for(int i=0;i<n;i++) sum+=arr[i]; 
	cout<<sum<<endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  int n;
  cin >> n;
  map<string, int> mp;
  REP(i, n){
    string s;
    cin >> s;
    mp[s]++;
  }
  int m;
  cin >> m;
  REP(i, m){
    string t;
    cin >> t;
    mp[t]--;
  }
  int ans = 0;
  for(auto p : mp) chmax(ans, p.second);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
N,K = map(int, input().split())
A = [*map(lambda x:int(x)-1, input().split())]

index = [-1]*N
pre, path_cnt = 0, 0
for i in range(N):
    if index[pre] >= 0: break
    else:
        index[pre] = i
        path_cnt += 1
    pre = A[pre]

loops = path_cnt - index[pre]
one = index[pre]
k = max(0, K-one) % loops + min(K, one)

pre = 0
for _ in range(k): pre = A[pre]
print(pre + 1)


Measured memory_bytes: 32372
#include <stdio.h>
typedef long long LL;

int main()
{	 
	LL x, k, d, y, z;
	
	scanf("%lld%lld%lld", &x, &k, &d);	
	if(x < 0) x = -x;
	y = x / d;
	if(y >= k) z = x - d * k;
	else{
		z = x % d;
		if((k - y) & 1) z = d - z;
	}
	printf("%lld\n", z);
		
	return 0;
}

Measured memory_bytes: 1736
while True :
    m, r, f = map(int, input().split())
    if m == -1 and r == -1 and f == -1 :
        break
    if m == -1 or r == -1 :
        print("F")
    elif m + r >= 80 :
        print("A")
    elif m + r >= 65 :
        print("B")
    elif m + r >= 50 :
        print("C")
    elif m + r >= 30 :
        if f >= 50 :
            print("C")
        else :
            print("D")
    else :
        print("F")




Measured memory_bytes: 5592