akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using i64 = int64_t;
using f80 = __float80;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  i64 X;
  cin >> X;
  i64 ans = 0;
  i64 m = 100;
  while(m<X){
    m *= 1.01;
    ans++;
  }
  cout << ans << "\n";


}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 3612
using System;
class Program
{
	static void Main()
	{
  int answer = 0;
  string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
  int h = int.Parse(input[0]);//行の長さ
  int w = int.Parse(input[1]);//列の長さ
  int[,] moveMatrix = new int [10,10];//行列
  
    for(int i = 0; i < 10; i++)//それぞれの行
    {
	     int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
	     for(int j = 0; j < 10; j++) moveMatrix[i,j] = nums[j];//行の全ての成分
    }

    int[] walls = new int[10];//各壁の個数
    
      for(int i = 0; i < h; i++)//それぞれの行
      {
  	     int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
  	     for(int j = 0; j < w; j++) 
         {
          if(nums[j] != -1)  walls[nums[j]]++;//行の全ての成分
         }
      }

    for(int k = 0; k < 10; k++)
    {
      for(int i = 0; i < 10; i++)
      {
        for(int j = 0; j < 10; j++)
        {
          if(moveMatrix[i,j] > moveMatrix[i,k] + moveMatrix[k,j])
            moveMatrix[i,j] = moveMatrix[i,k] + moveMatrix[k,j];//距離の更新
        }
      }
    }

    for(int i = 0; i < 10; i++)
    {
    answer += moveMatrix[i,1] * walls[i];
    }

	Console.WriteLine(answer);//WriteLineをWriteとすると、改行なしで出力。
	}
}

Measured memory_bytes: 13140
def main():
    n, m = map(int, input().split())
    ps_lst = [list(map(str, input().split())) for _ in range(m)]
    judge_lst = [0] * n
    penalty_lst = [0] * n
    correct = 0
    penalty = 0

    for i in range(m):
        problem = int(ps_lst[i][0]) - 1
        result = ps_lst[i][1]
        
        if judge_lst[problem] == 0:
            if result == 'AC':
                judge_lst[problem] = 1
            else:
                penalty_lst[problem] += 1

    for i in range(n):
        if judge_lst[i] == 1:
            correct += 1
            penalty += penalty_lst[i]
            
    print(correct, penalty)


if __name__ == '__main__':
    main()

Measured memory_bytes: 35048
//by spj
#include <bits/stdc++.h>
using namespace std;
vector < int > g[200005];
int n,dist1[200005],dist2[200005];
void dfs1(int pos,int depth)
{
	if(dist1[pos] != -1)
		return;
	dist1[pos] = depth;
	for(int i = 0;i < g[pos].size();i++)
		dfs1(g[pos][i],depth + 1);
}
void dfs2(int pos,int depth)
{
	if(dist2[pos] != -1)
		return;
	dist2[pos] = depth;
	for(int i = 0;i < g[pos].size();i++)
		dfs2(g[pos][i],depth + 1);
}
int main()
{
	cin >> n;
	for(int i = 0;i < n - 1;i++)
	{
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	memset(dist1,-1,sizeof(dist1));
	memset(dist2,-1,sizeof(dist2));
	dfs1(1,0);
	dfs2(n,0);
	int cnt1 = 0,cnt2 = 0;
	for(int i = 1;i <= n;i++)
		if(dist1[i] <= dist2[i])
			cnt1++;
		else
			cnt2++;
	if(cnt1 > cnt2)
		puts("Fennec");
	else
		puts("Snuke");
	return 0;
}

Measured memory_bytes: 14336
#include <stdio.h>

int main(void)
{
	int h,w,i,k;
	scanf("%d%d",&h,&w);
	char s[h+2][w+3];
	for(i=0;i<=h+1;i++)
		{
		if(i==0 || i==h+1)
			{for(k=0;k<=w+1;k++){s[i][k]='0';}}
		else	{scanf("%s",s[i]);}
		}
	for(i=1;i<=h;i++)
		{
		for(k=w+1;k>=0;k--)
			{
			if(k==w+1 || k==0){s[i][k]='0';}
			else {s[i][k]=s[i][k-1];}
			}
		}
	for(i=1;i<=h;i++)
		{
		for(k=1;k<=w;k++)
			{if(s[i][k]!='#')
				{
				s[i][k]='0';
				if(s[i-1][k-1]=='#'){s[i][k]++;}
				if(s[i-1][k]=='#'){s[i][k]++;}
				if(s[i-1][k+1]=='#'){s[i][k]++;}
				if(s[i][k-1]=='#'){s[i][k]++;}
				if(s[i][k+1]=='#'){s[i][k]++;}
				if(s[i+1][k-1]=='#'){s[i][k]++;}
				if(s[i+1][k]=='#'){s[i][k]++;}
				if(s[i+1][k+1]=='#'){s[i][k]++;}
				}
			}
		}
	for(i=1;i<=h;i++)
		{
		for(k=1;k<=w;k++)
			{printf("%c",s[i][k]);}
		printf("\n");
		}
return 0;
}




Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
int main(){
    int n;
    cin>>n;
    vector<char> c(n);
    bool four=false;
    rep(i,n){
        cin>>c[i];
        if(c[i]=='Y'){
            four = true;
        }
    }
    if(four){
        cout<<"Four"<<endl;
    }
    else{
        cout<<"Three"<<endl;
    }
}

Measured memory_bytes: 256
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]

check = []
for i in range(n-1):
    for j in range(i+1,n):
        check.append([xy[i][0]-xy[j][0],xy[i][1]-xy[j][1]])
#print(check)
ans = 10**9
for i in check:
    b = []
    for j in range(n):
        b.append([xy[j][0]-i[0],xy[j][1]-i[1]])
    c = n
    for j in range(n):
        if b[j] in xy:
            c -= 1
    if c < ans:
        ans = c
if n == 1:
    print(1)
else:
    print(ans)

Measured memory_bytes: 41564
#include "bits/stdc++.h"
using namespace std;
#define ll long long
using namespace std;

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	string str;
	int ans;
	int foot[10] = { -1,1,2,3,1,-1,3,1,2,3 };
	while (cin >> str) {
		if (str == "#") break;
		ans = (1 << 30);
		int l = 1, r = 3;
		int next = 0;  // 0 : l   ,   1 : r
		int cnt = 0;
		for (int i = 0; i < str.length();i++) {
			//cout << "l = " << l << " / r = " << r << endl;
			int key = str[i] - '0';
			if (next == 0) {
				if (foot[key] <= r) {
					l = foot[key];
					next = 1;
				}
				else {
					r = foot[key];
					cnt++;
				}
			}
			else {
				if (foot[key] >= l) {
					r = foot[key];
					next = 0;
				}
				else {
					l = foot[key];
					cnt++;
				}
			}
		}
		ans = min(ans, cnt);

		l = 1, r = 3;
		next = 1;
		cnt = 0;
		for (int i = 0; i < str.length();i++) {
			//cout << "l = " << l << " / r = " << r << endl;
			int key = str[i] - '0';
			if (next == 0) {
				if (foot[key] <= r) {
					l = foot[key];
					next = 1;
				}
				else {
					r = foot[key];
					cnt++;
				}
			}
			else {
				if (foot[key] >= l) {
					r = foot[key];
					next = 0;
				}
				else {
					l = foot[key];
					cnt++;
				}
			}
		}

		ans = min(ans, cnt);
		cout << ans << endl;
	}
}

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

int main(){
    int n,k;
    cin >> n >> k;
    ll cnt = 0;
    while(n > 0){
        n /= k;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

int main() {
	int K;
  	cin>>K;
  	int sum=0;
  
    for(int a=1;a<=K;a++){
		for(int b=1;b<=K;b++){
         	for(int c=1;c<=K;c++){
             	 sum+=gcd(gcd(a,b),c);
            }
        }
    }
  	
  	cout<<sum<<endl;
  	
}

Measured memory_bytes: 3636
n=int(input());S=list(map(sorted,[input() for _ in [1]*n]))
dicList=[]
for s in S:
    dic={}
    for c in list(s):
        dic[c]=dic.get(c,0)+1 
    dicList.append(dic)
result=''
c=[chr(i) for i in range(97, 97+26)]
count=0
while count<26:
    m = min([dic.get(c[count],0) for dic in dicList])
    if m==0:count+=1
    else:
        for dic in dicList:
            dic[c[count]]-=1
        result+=c[count]
print(result)

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

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define forn(i,n) for(ll i=0;i<n;i++)
#define fore(i,a,b) for(ll i=a;i<=b;i++)
#define ford(i,n) for(ll i=n-1;i>=0;i--)
#define fi first
#define se second
#define endl "\n"
#define all(a) a.begin(),a.end()
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PI 3.14159265

/*************************************************************************************/
void file(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
}
/*************************************************************************************/

const ll maxn=2e5+1,mod=1e9+7;



int main(){
    sync
  //  file();
   	int n,k;
   	cin>>n>>k;
   	vector<ll> dp(k+1);
   	dp[0] = 1;
   	forn(i,n){
   		int x;
   		cin>>x;
   		vector<int> fake(k+2);
   		for(int j=k;j>=0;--j){
   			int l = j+1;
   			int r = j+min(x,k-j)+1;
   			if(l<r&&l<=k){
   				fake[l]+=dp[j];
   				fake[l]%=mod;
   				// if(r<=k){
   				fake[r]-=dp[j];
   				fake[r]+=mod;
   				fake[r]%=mod;
   			// }
   			}
   		}
   		ll pre = 0;
   		fore(lel,0,k){
   			pre+=fake[lel];
   			pre%=mod;
   			dp[lel]+=pre;
   			dp[lel]%=mod;
   		}
   	}
   	cout<<dp[k]<<endl;

	return 0;
}


Measured memory_bytes: 1408
#include <atcoder/convolution>
#include <atcoder/dsu>
#include <atcoder/fenwicktree>
#include <atcoder/lazysegtree>
#include <atcoder/math>
#include <atcoder/maxflow>
#include <atcoder/mincostflow>
#include <atcoder/modint>
#include <atcoder/scc>
#include <atcoder/segtree>
#include <atcoder/string>
#include <atcoder/twosat>

#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;

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

for(int i=0;i<N;i++){
  cout<<"ACL";
}

cout<<endl;
}


Measured memory_bytes: 3520
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <deque>
#include <math.h>
#include <cstring>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <stack>
#include<cassert>
#include <cfloat>
#include <list>
using namespace std ;
#define ll long long
#define submitStage int TCF = 1 ;
#define testStage int TCF = 1000 ;
#define testMyStupedCode TCF--
void FastInputOutput(){
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}
void ReadFromFile( string name , string extention ){
    string fullPath = name + "." + extention ;
    freopen( fullPath.c_str() , "r" , stdin ) ;
}
inline int D(){
    int t ;
    scanf( "%d" , &t ) ;
    return t ;
}
inline ll LLD(){
    ll t ;
    scanf( "%lld" , &t ) ;
    return t ;
}
inline char C(){
    char c ;
    scanf( "%c" , &c ) ;
    return c ;
}
inline ll power(ll x, ll p, ll m){
    ll res = 1;
    while(p){
        if(p & 1)
            res = (res * x) % m;
        x = (x * x) % m;
        p >>= 1;
    }
    return res;
}
long double ModLog(long double base, long double x) {
    return (logl(x) / logl(base));
}

const int N = 1e5 + 5;
ll dp[N];
int v[N], w[N];
int main(){
     int n = D(), W = D();
     for(int i = 0; i < n; ++i)
          w[i] = D(), v[i] = D();
     dp[0] = 0;
     for(int i = 1; i <= W; ++i)
          dp[i] = -1;
     ll ans = 0;
     for(int i = 0; i < n; ++i)
          for(int j = W; j >= 0; --j){
               if(~dp[j] && j + w[i] <= W){
                    dp[j + w[i]] = max(dp[j] + v[i], dp[j + w[i]]);
                    ans = max(ans, dp[j + w[i]]);
               }
               ans = max(ans, dp[j]);
          }
     printf("%lld", ans);
     return 0;
}



Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC166
{
    class D
    {
        static void Main(string[] args)
        {
            long X = long.Parse(Console.ReadLine());
            // A- B = 1 とする。
            // A^5 - B^5 = X の時、まずAとBが取りうる範囲を決める。
            /*
            long ans = 0;
            long A = 1;
            long B = 0;
            while (ans < X)
            {
                if (X < Math.Pow(A, 5) - Math.Pow(B, 5))
                {
                    break;
                }
                A++;
                B++;
            }
            */

            for (long i = -120; i < 120; i++)
            {
                for (long j = -120; j < 120; j++)
                {
                    if (X == Math.Pow(i, 5) - Math.Pow(j, 5))
                    {
                        Console.WriteLine("{0} {1}", i, j); return;
                    }

                }
            }
        }
    }
}


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

using namespace std;

void solve() {
    int a, b, k; cin >> k >> a >> b;
    if (b / k - (a - 1) / k > 0)
        cout << "OK";
    else
        cout << "NG";
}

int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(20);
    solve();
}


Measured memory_bytes: 3652
#include <iostream>

using namespace std;

int main()
{
	// 入力
	int H, N;
	cin >> H >> N;

	for( int i=0 ; i<N ; i++ )
	{
		int damage;
		cin >> damage;
		H -= damage;
	}

	// 出力
	cout << ( ( H <= 0 ) ? "Yes" : "No" ) << endl;


	return 0;
}

Measured memory_bytes: 256
require 'prime'
a, b = gets.split.map(&:to_i)

divs = Array.new(0)
for i in 1..10**6
  break if a < i && b < i
  divs.push(i) if a % i == 0 && b % i == 0
  divs.push(a/i) if a % i == 0 && b % (a/i) == 0
  divs.push(b/i) if b % i == 0 && a % (b/i) == 0
end
divs.uniq!
#puts divs.join(" ")
cnt = 0
for i in 0..(divs.length-1)
  cnt += 1 if Prime.prime?(divs[i]) || divs[i] == 1
end
puts cnt

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

int main(){

    int a,b; cin >> a >> b;

    if(a > 0 and b > 0){
	cout << "Positive" << endl;
	return 0;
    }
    if(a==0 or b == 0){
	cout << "Zero" << endl;
	return 0;
    }
    if(a < 0 and b > 0){
	cout << "Zero" << endl;
	return 0;
    }
    if( (b-a)%2 != 0 ){
	cout << "Positive" << endl;
	return 0;
    }
    else{
	cout << "Negative" << endl;
	return 0;		
    }
    
    
}


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

int main() {
    vector<int> input;
    for (int i = 0; i < 10; i++) {
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    sort(input.rbegin(), input.rend());
    for (int i = 0; i < 3; i++) {
        cout << input[i] << endl;
    }
}

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

int main(){
    int N, M;
    cin >> N >> M;
    int A[M];
    int sum = 0;
    for (int i = 0; i < M; i++)
    {
        cin >> A[i];
        sum += A[i];
    }

    if (N >= sum)
    {
        cout << N - sum << endl;
    } else
    {
        cout << -1 << endl;
    }
      
    return 0;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll r;
  cin >> r;
  cout << r * r << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int>P;
#define Z(a,b)v.push_back(make_pair(a,b))

struct C{bool operator()(P a,P b){return a.first*a.second<b.first*b.second;}};
int main(){
	int n,w,d,p,s;
	for(;scanf("%d%d%d",&n,&w,&d),w;puts("")){
		vector<P>v;
		for(Z(w,d);n--;){
			scanf("%d%d",&p,&s);p--;
			s%=v[p].first+v[p].second;
			int x=v[p].first,y=v[p].second,state=0,_x=0,_y=0,x1,x2,y1,y2;
			for(;s--;)if(state==0){_x++;if(_x==x)state=1;}else _y++;
			if(state==0)x1=_x,x2=x-_x,y1=y2=y;
			else x1=x2=x,y1=_y,y2=y-_y;
			v.erase(v.begin()+p);
			if(x1*y1>x2*y2)Z(x2,y2),Z(x1,y1);
			else Z(x1,y1),Z(x2,y2);
		}
		for(sort(v.begin(),v.end(),C());v.size();){
			printf("%d",v[0].first*v[0].second);
			v.erase(v.begin());
			if(v.size())printf(" ");
		}
	}
}

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

const int MAX = 100, INF = 1e9, white = 0, gray = 1, black = 2;
int G[MAX][MAX], color[MAX], d[MAX], p[MAX], n;

int prim(){
    int u, minv;
    for (int i = 0; i < n; i++)
    {
        d[i] = INF;
        p[i] = -1;
        color[i] = white;
    }
    d[0] = 0;
    while (true)
    {
        minv = INF;
        u = -1;
        for (int i = 0; i < n; i++)
        {
            if (color[i] != black && d[i] < minv)
            {
                minv = d[i];
                u = i;
            }
        }
        if (u == -1)
        {
            break;
        }
        color[u] = black;
        for (int i = 0; i < n; i++)
        {
            if (color[i] != black && G[u][i] != INF)
            {
                if (d[i] > G[u][i])
                {
                    d[i] = G[u][i];
                    p[i] = u;
                    color[i] = gray;
                }
                
            }
            
        }
        
    }
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (p[i] != -1){
            sum += G[i][p[i]];
        }
    }
    return sum;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int v;
            cin >> v;
            G[i][j] = (v == -1) ? INF : v;
        }
    }
    cout << prim() << endl;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
#define M 1000000007
using namespace std;

typedef long long int ll;

int main()
{
    int n;
    cin>>n;
    set<string>ss;
    while(n--)
    {
        string s;
        cin>>s;
        ss.insert(s);

    }
    cout<<ss.size()<<endl;
}


Measured memory_bytes: 19052
// Template
#include <bits/stdc++.h>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003LL;
template <typename T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Mod-Int
constexpr int MOD = 1000000007;
struct ModInt {
    ll val;
    ModInt() = default;
    ModInt(ll x) : val(x % MOD + (x < 0 ? MOD : 0)) {}
    ModInt &operator+= (const ModInt &x) {if ((val += x.val) >= MOD) val -= MOD; return *this;}
    ModInt &operator-= (const ModInt &x) {if ((val -= x.val) < 0) val += MOD; return *this;}
    ModInt &operator*= (const ModInt &x) {(val *= x.val) %= MOD; return *this;}
    ModInt operator+ (const ModInt &x) const {return ModInt(*this) += x;}
    ModInt operator- (const ModInt &x) const {return ModInt(*this) -= x;}
    ModInt operator* (const ModInt &x) const {return ModInt(*this) *= x;}
    ModInt pow(ll t) const {
        if (!t) return ModInt(1);
        ModInt m = pow(t / 2);
        m *= m;
        if (t & 1) m *= *this;
        return m;
    }
    ModInt inv() const {return pow(MOD - 2);}
    ModInt &operator/= (const ModInt &x) {return *this *= x.inv();}
    ModInt operator/ (const ModInt &x) const {return ModInt(*this) /= x;}
    friend istream &operator>> (istream &is, ModInt &x) {is >> x.val; return is;}
    friend ostream &operator<< (ostream &os, const ModInt &x) {os << x.val; return os;}
};
vector<ModInt> fact, ifact;
void comb_init(int n) {
    fact.resize(n + 1);
    ifact.resize(n + 1);
    fact[0] = ModInt(1);
    rep(i, 1, n + 1) fact[i] = fact[i - 1] * ModInt(i);
    ifact[n] = fact[n].inv();
    per(i, n) ifact[i] = ifact[i + 1] * ModInt(i + 1);
}
ModInt comb(int x, int y) {
    if (y < 0 || y > x) return ModInt(0);
    else return fact[x] * ifact[y] * ifact[x - y];
}

// Main
int main() {
    int s;
    cin >> s;
    comb_init(2 * s);
    ModInt ans(0);
    rep(i, 1, s / 3 + 1) {
        ans += comb(s - i * 3 + i - 1, i - 1);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3700
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int main(){
    string s;
    long long k;
    int p = 0;
    cin >> s;
    cin >> k;
    for(int i = 0;i<s.size();i++){
        if(s[i] != '1'){
            p = i+1;
            break;
        }
    }
    int ans;
    if(p == 0){
        ans = 1;
    }
    else if (k < p){
        ans = 1;
    }
    else{
        ans = s[p - 1] - '0';
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <bitset>
using namespace std;


const double EPS = 1e-9;
const double PI = 3.14159265359;

const int SIZE = 18;

int main(){

	int n;
	while(cin >> n, n){
		int table[SIZE][SIZE] = {0};
		int num = 1;
		int x = n/2;
		int y = n/2+1;
		table[y++][x++] = num++;
		while(num <= n*n){
			x%=n;
			y%=n;
			if(table[y][x] != 0){
				x+=n-1;
				y++;
			}else{
				table[y++][x++] = num++;
			}
		}

		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				printf("%4d", table[i][j]);
			}
			cout << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll A, B;
  cin >> A >> B;

  vector<string> S(100);
  ll y, x;

  for (ll i = 0; i < 50; i++)
  {
    S.at(i) = string(100, '#');
  }
  y = 0, x = 0;
  for (ll i = 0; i < A - 1; i++)
  {
    S.at(y).at(x) = '.';

    x += 2;
    if (x >= 100)
      y += 2, x = 0;
  }

  for (ll i = 50; i < 100; i++)
  {
    S.at(i) = string(100, '.');
  }
  y = 51, x = 0;
  for (ll i = 0; i < B - 1; i++)
  {
    S.at(y).at(x) = '#';

    x += 2;
    if (x >= 100)
      y += 2, x = 0;
  }

  cout << "100 100" << endl;
  for (ll i = 0; i < 100; i++)
  {
    cout << S.at(i) << endl;
  }
}

Measured memory_bytes: 256
n = int(input())
s = [_ for _ in input()]

l, r = 0, n-1
if not('R' in s):
    print(0)
    exit()

if not('W' in s):
    print('0')
    exit()

ans = 0
while 1:
    while s[l] == "R":
        l += 1
    while s[r] == "W" and l != r:
        r -= 1

    if l != r:
        s[l], s[r] = s[r], s[l]
        ans += 1
        # print(s)
    if l == r:
        break

print(ans)


Measured memory_bytes: 11000
#include <iostream>

using namespace std;

int main( void )
{
	double v;
	
	while (cin >> v)
	{
		double t = v / 9.8;
		int y = (4.9 * t * t) + 5;
		cout << y / 5 + 1 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	int n, m, x[100000], d[99999], i;
	cin >> n >> m;
	for(i = 0; i < m; i++) cin >> x[i];
	sort(x, x+m);
	for(i = 1; i < m; i++){
		d[i - 1] = x[i] - x[i - 1];
	}
	sort(d, d+(m-1), greater<>());
	int result = x[m - 1] - x[0];
	for(i = 0; i < n - 1; i++){
		result -= d[i];
	}
 
	cout << result << endl;
	return 0;
}


Measured memory_bytes: 1024
def main():
    K = int(input())
    if K%2 == 0:
        return -1
    ans = 1
    amari_reserve = 7%K
    amari = amari_reserve
    if amari_reserve == 0:
        return ans

    while (ans <= K):
        ans += 1
        amari = (10*amari+7) % K
        if amari == 0:
            return ans
        if amari == amari_reserve:
            return -1

    return -1


print(main())


Measured memory_bytes: 9188
import sys
from bisect import bisect_left
a,b,q = map(int, sys.stdin.readline().split())
S = []
for _ in range(a):
  S.append(int(sys.stdin.readline()))
T = []
for _ in range(b):
  T.append(int(sys.stdin.readline()))
X = []
for _ in range(q):
  X.append(int(sys.stdin.readline()))

INF = 10 ** 11
def dfs(direction, tors, pos, count):
  if tors == 1:
    L = T
  elif tors == -1:
    L = S
  i = bisect_left(L, pos)
  if i == len(L):
    if direction == 1:
      return INF
    elif direction == -1:
      res = abs(L[i-1]-pos)
      next_pos = L[i-1]
  elif L[i] == pos:
    res = 0
    next_pos = pos
  else:
    if direction == 1:
      res = abs(L[i]-pos)
      next_pos = L[i]
    elif direction == -1:
      if i == 0:
        return INF

      res = abs(L[i-1]-pos)
      next_pos = L[i-1]

  if count == 1:
    return res

  res0 = res + dfs(direction, tors*(-1), next_pos, count-1)
  res1 = res + dfs(direction*(-1), tors*(-1), next_pos, count-1)

  return min(res0, res1)

for x in X:
  res0 = dfs(1, 1, x, 2)
  res1 = dfs(-1, 1, x, 2)
  res2 = dfs(1, -1, x, 2)
  res3 = dfs(-1, -1, x, 2)

  print(min(res0, res1, res2, res3))

Measured memory_bytes: 16160
// https://atcoder.jp/contests/abc097/tasks/arc097_a

#include <algorithm>
#include <cmath>
#include <iostream>
#include <regex>
#include <set>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

#define EPS (1e-7)
#define INF (1e9)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

// long gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// long lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, ans = INF;
    string s;
    cin >> s;
    cin >> n;

    // Kが5以下のため、aを検索してなかったらb
    char cmin = *std::min_element(ALL(s));
    string smin{cmin};
    vector<string> v;

    // 最小の文字に対して4文字以下続く文字列を正規表現で検索すると、5通り以上になる
    // a, ab, abc, abcd, abcde
    smatch match;
    string word = "";

    string str = s;
    // 正規表現A+は最長一致。A+?は最短一致
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            word = ".";
        } else if (i == 1) {
            word = "..";
        } else if (i == 2) {
            word = smin + "..";
        } else if (i == 3) {
            word = smin + "...";
        } else if (i == 4) {
            word = smin + "....";
        }
        regex reg(word);
        for (auto it = str.cbegin(); regex_search(it, str.cend(), match, reg);
             it += match.position(0) + 1) {
            v.push_back(match.str(0));
        }
    }

    // ソートする
    sort(ALL(v));
    // 隣接する重複要素を削除
    unique(ALL(v));

    // FOREACH(x, v) { cout << x << endl; }
    cout << v[n - 1] << endl;

    return 0;
}


Measured memory_bytes: 1660
#include<iostream>
#include<string>
#include <cmath>
#include <ctype.h>
#include<vector>
using namespace std;
int W, a, b;
const int n=1e9+7;
int main() {
    cin >> W >> a >> b;
    if(b+W<a) cout << a-(b+W) << endl;
    else if(a+W<b) cout << b-(a+W) << endl;
    else if(b+W>=a||a+W>=b) cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = INT32_MAX;
const long long int Mod = 1000000007;
const long long int mod = 100000;//10^5
using ll = long long int; //long long int は64bit
using ci = const int; using vi = vector<int>; using Vi = vector<long long int>; using pii = pair<int,int>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
template<class T>bool chmax(T &former, const T &b) { if (former<=b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define fill(x,num) memset(x,num,sizeof(x));
typedef vector<vector<ll> > matrix;
//       cin.tie(0);ios::sync_with_stdio(false);
void cinit(){cin.tie(0);ios::sync_with_stdio(false);}
///////////////////////////////////////////////////////////////////////////////////

Vi v;

int main(){
    ll n,k;ll xx;
    cin>>n>>k;
    rep(i,n){
        cin>>xx;
        v.pb(xx);
    }
    sort(all(v));
    ll min=1000000001;
    for(int i=v.size()-1;i>=0;i--){
        if(i-k+1<0)break;
        chmin(min,v[i]-v[i-k+1]);
    }
    cout<<min<<endl;
    return 0;
}

Measured memory_bytes: 1400
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int total = n;
    int ok = 0;
    int two = 0;
    for(int i = 0;i<n;i++){
      int a = sc.nextInt();
      if(a%4==0){
        ok++;
      }else if(a%2==0){
        if(two==0){
          two++;
        }else{
          two=0;
          total-=2;
        }
      }
    }
    total-=ok;
    if(ok>=total-1){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 58616
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    int a[1010];
    rep(i, N) cin >> a[i];
    vector<int> v;
    rep(i, N) {
        int sum = 0;
        REP(j, i, N - 1) {
            sum += a[j];
            v.push_back(sum);
        }
    }
    int ans = 0;
    bool first = true;
    RREP(i, 50, 0) {
        vector<int> nx_v;
        rep(j, v.size()) {
            if (v[j] & (1LL << i)) nx_v.push_back(v[j]);
        }
        if(first && nx_v.size() < K) continue;
        if(nx_v.size() >= K) {
            ans += (1LL << i);
            v = nx_v;
            first = false;
        }
    }
    cout << ans << endl;


    return 0;
}
// 010, 101, 010, 101


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

using namespace std;


int main(int, char**)
{
	string s;
	unsigned int n;

	std::cin >> s >> n;
    string pstr = "print";
    string prep = "replace";
    for (unsigned int i = 0; i < n; ++i) {
        string inst;
        unsigned int x, y;
        cin >> inst >> x >> y;
        if( inst == pstr) {
            cout << s.substr(x, y - x + 1) << endl;
        } else if (inst==prep) {
            string s2;
            cin >> s2;
            s.replace(x, y - x + 1, s2);
        } else {
            string s2 = s.substr(x, y - x +1);
            for (unsigned int i = 0; i + x <= y; ++i)
                s2[i] = s[y - i];
            s.replace(x, y - x +1, s2);
        }
    }
    
	return 0;
}
  



Measured memory_bytes: 3228
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
// template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE


typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define Mod 1000000007
#define MAX 5002

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n;cin>>n;
	priority_queue<double,vector<double>,greater<double> > p;
	For(i,0,n){
		double x;cin>>x;
		p.push(x);
	}
	while(p.size()>1){
		double x = p.top();p.pop();
		double y = p.top();p.pop();
		p.push((x+y)/2);
	}
	cout<<setprecision(6)<<fixed;
	cout<<p.top()<<endl;
































	
}

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

cnt = 0
for Ai in A:
    cnt += int(Ai < 0)

if cnt % 2 == 0:
    print(sum([abs(Ai) for Ai in A]))
else:
    ans_sum = 0
    ans_min = 10 ** 9 + 7
    for Ai in A:
        ans_sum += abs(Ai)
        ans_min = min(ans_min, abs(Ai))
    #
    print(ans_sum - 2 * ans_min)


Measured memory_bytes: 14412
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long int
#define pb push_back

int main() {
  int a, b;
  string s;
  cin >> a >> s >> b;
  if(s=="+") print(a+b);
  else print(a-b);

}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<string>
#include<stack>
#include<algorithm>

using namespace std;

void slove(){
    int n,k;
    int x;
    vector<int> logs;
    
    cin>>n>>k;
    for(int i = 0; i < n; ++i){
        cin>>x;
        logs.push_back(x);
    }

    if(k == 0){
        cout<<*max_element(logs.begin(),logs.end())<<endl;
        return;
    }
        
    int l = 1;
    int r = 1e9+7;
    int ans = 0;
    while(l <= r){
        int mid = (l+r)>>1;
        int cut = 0;
        if(mid == 0) break;
        for(int i = 0; i < logs.size(); ++i){
            if(logs[i] > mid){
                cut += (logs[i] - (logs[i]%mid))/mid;
            }
        }

        if(cut <= k){
            ans = mid;
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }

    cout<<ans<<endl;
}

int main(){
    slove();
}

Measured memory_bytes: 3912
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

bool flag;
int col[100005];
ll cnt[2];

vector<int> G[100001];
void dfs(int v){
	cnt[col[v]]++;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i];
		if(col[nv]==-1){
			col[nv]=1-col[v];
			dfs(nv);
		}else if(col[v]==col[nv]){
			flag=true;
		}
	}
}

int n,m;

int main(void){
	scanf("%d%d",&n,&m);
	flag=false;
	memset(col,-1,sizeof(col));
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;
		v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	col[0]=0;
	dfs(0);
	if(!flag)printf("%lld\n",(ll)cnt[0]*cnt[1]-m);
	else printf("%lld\n",(ll)n*(n-1LL)/2LL-m);
	return 0;
}

Measured memory_bytes: 6912
#!/usr/bin/env python3
#EDPC N

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [0] + list(accumulate(a))
dp = [[inf]*(n) for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
for l in range(n-1)[::-1]:
    for r in range(l+1,n):
        s = b[r+1] - b[l]
        if r - l == 1:
            dp[l][r] = s
            continue
        for c in range(l,r):
            dp[l][r] = min(dp[l][r],s + dp[l][c] + dp[c+1][r])
print(dp[0][-1])

Measured memory_bytes: 46556
n = input().split()
n = [int(i) for i in n]
count = 0

a = n[0]*1
b = n[1] 
c = n[2]*-1
while n[-1] > 0:
    if n[0] >= n[-1] and n[0] != 0:
        count = n[-1]*1
        n[-1] = 0
    elif n[0] < n[-1] and n[0] != 0:
        count += n[0]
        tmp = n[0]+n[1]
        n[-1] -= tmp
        n[0] = 0
    elif n[2] >= n[-1]:
        count += n[-1]*-1
        n[-1] = 0
    elif n[2] < n[-1]:
        count += c
        n[-1] = 0

print(count)

Measured memory_bytes: 9240
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int n, s;
bool used[10];
ll total[12][10000];

void dfs (int curr, int sum )
{
	if (curr == n ){
		total[n][sum]++;
		return;
	} // end if

	int res = 0;
	rep (i, 10 ){
		if (!used[i] ){
			used[i] = true;
			dfs (curr+1, sum + (curr+1)*i );
			used[i] = false;
		} // end if
	} // end rep
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.CNS", "r", stdin );
	memset (total, 0, sizeof (total ) );

	for (n = 1; n <= 10; n++ ){
		memset (used, 0, sizeof (used ) );
		dfs (0, 0 );
	} // end for

	while (scanf ("%d %d", &n, &s ) != EOF ){
		printf ("%d\n", total[n][s] );
	} // end loop
		
	return 0;
}

Measured memory_bytes: 2132
#include "iostream"
#include "vector"
#include "set"
#include "algorithm"

using namespace std;
using LL = long long;

const int N = 1e5 + 5;

LL size[N];
int link[N];

int find(int a) {
    return link[a] == a ? a : link[a] = find(link[a]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (size[a] < size[b]) swap(a, b);
    size[a] += size[b];
    link[b] = a;
}

bool same(int a, int b) {
    return find(a) == find(b);
}

int main() {
    for (int i = 0; i < N; ++i) size[i] = 1, link[i] = i;
    int n, m;
    scanf("%d %d", &n, &m);
    vector< pair< int, int> > Vp(m);

    for (auto &i : Vp) {
        scanf("%d %d", &i.first, &i.second);
    }

    vector< LL> ans(m);

    LL res = n * 1LL * (n - 1) / 2;

    for (int i = m - 1; i >= 0; i--) {
        ans[i] = res;
        int a = Vp[i].first, b = Vp[i].second;
        if (same(a, b)) continue;
        LL x = size[find(a)], y = size[find(b)];
        unite(a, b);
        res -= x * y;
    }

    for (auto &x : ans) printf("%lld\n", x);
}

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


int main() {

    string s;

    cin >> s;

   bool flag = true;

    set <char> w;

    for (int i = 0; i<s.size(); ++i) {
        if (!w.count(s[i])) w.insert(s[i]); else flag = false;
    }

    if (flag) cout << "yes" << '\n'; else cout << "no" << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    string s;
    cin >> s;
    int n=0,w=0,S=0,e=0;
    bool hantei=true;
    rep(i,s.size()){
        if(s[i] == 'N') n =1;
        else if(s[i] == 'W') w = 1;
        else if(s[i] == 'S') S =1;
        else if(s[i] == 'E') e = 1;
    }
    if(n != S) hantei =false;
    if(w != e) hantei =false;

    if(hantei) cout << "Yes"<<endl;
    else    cout << "No" <<endl;
}
    


Measured memory_bytes: 256
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#include<climits>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf;
inline int read() {
	bool f=0;int x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c==EOF)exit(0);if(c=='-')f=1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return !f?x:-x;
}
#define MAXN 2000000
#define INF 0x3f3f3f3f
#define Mod (int)(1e9+7)
LL fac[MAXN+5],inv[MAXN+5];
LL Pow(LL x,LL y){
	LL ret=1;
	while(y){
		if(y&1) ret=ret*x%Mod;
		x=x*x%Mod,y>>=1;
	}
	return ret;
}
void Prepare(){
	fac[0]=1;
	for(int i=1;i<=MAXN;i++)
		fac[i]=fac[i-1]*i%Mod;
	inv[MAXN]=Pow(fac[MAXN],Mod-2);
	for(int i=MAXN-1;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%Mod;
	return ;
}
vector<LL> Ball[MAXN+5];
struct node{
	LL c,w;
	friend bool operator < (node a,node b){return a.w<b.w;}
}ball[MAXN+5];
LL Max[MAXN+5];
bool vis[MAXN+5];
int main(){
	Prepare();
	LL n=read(),x=read(),y=read();
	for(int i=1;i<=n;i++){
		int c=read(),w=read();
		ball[i]=(node){c,w};
		Ball[c].push_back(w);
	}
	sort(ball+1,ball+n+1);
	vis[ball[1].c]=1;
	int t=1;
	while(t<=n&&ball[1].c==ball[t].c) t++;
	for(int i=2;i<=n;i++)//
		if(ball[1].c!=ball[i].c&&ball[1].w+ball[i].w<=y)//!!!!!!
			vis[ball[i].c]=1,Max[ball[i].c]++;
	for(int i=1;i<=n&&t<=n&&t!=1;i++)
		if(ball[i].c==ball[1].c&&ball[t].w+ball[i].w<=y)
			Max[ball[i].c]++;
	for(int i=1;i<=n;i++){
		sort(Ball[i].begin(),Ball[i].end());
		if(Ball[i].size())
			Max[i]=max(Max[i],1ll);
		for(int j=1;j<(int)Ball[i].size();j++)
			if(Ball[i][0]+Ball[i][j]<=x)
				Max[i]=max(Max[i],1ll*j+1);
	}//
	LL ans=1;
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(vis[i])
			cnt+=Max[i];
	ans=fac[cnt];
	for(int i=1;i<=n;i++)
		if(vis[i])
			ans=ans*inv[Max[i]]%Mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 93184
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define ssort(a) sort(a.begin(), a.end())
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;


const int MAX = 510000;//階乗の配列数
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


int main(){
  int n;
  cin >> n;
  int sn=n/3;
  ll ans=0;
  COMinit();
  repo(i, sn){
    ans+=COM(n-2*i-1, i-1);
    ans%=mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 15520
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<62;
const int IINF = 1000000000;
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; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;

string ABCD;

bool isEnd = false;

void dfs(int total, string signs, int index){
    if (isEnd) return;
    if(index == 4){
        if (total == 7){
            string ans = "";
            ans += ABCD[0];
            for (int i = 0; i < 3; i++){
                ans += signs[i];
                ans += ABCD[i+1];
            }
            cout << ans+"=7" << endl;
            isEnd = true;
        } 
        return;
    }
    dfs(total+(ABCD[index]-'0'), signs+"+", index+1);
    dfs(total-(ABCD[index]-'0'), signs+"-", index+1);
    
}

int main(){
    cin >> ABCD;

    dfs(ABCD[0]-'0', "", 1);
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int n,m,f;
int sum,ans;
int dx[8]={0,0,1,-1};
int dy[8]={1,-1,0,0};
int a[1010][1010];
char s[10000];
struct point
{
    int x;
    int y;
    int step;
}p,t;
void bfs(int x,int y)
{
    p.x=x;
    p.y=y;
    p.step=0;
    queue<point> q;
    q.push(p);
    while(!q.empty())
    {
        p=q.front();q.pop();
        if(p.x==n-1 && p.y==m-1)
        {
        	ans=sum-p.step-1;
        	printf("%d\n",ans);
        	f=1;
            exit(0);
        }
        for(int i=0;i<4;i++)
        {
            t.x=p.x+dx[i];
            t.y=p.y+dy[i];
            if(t.x>=0 && t.x<n && t.y>=0 && t.y<m && a[t.x][t.y]==0)
            {
                a[t.x][t.y]=1;
                t.step=p.step+1;
                q.push(t);
            }
        }
        
    }
}
int main()
{
    cin>>n>>m;
    for(int k=0; k<n; k++)
    {
        cin>>s;
        for (int j=0; j<m; j++)
        if (s[j]=='#') a[k][j]=1;
        else sum++;
    }
    a[0][0]=1;
    bfs(0,0);
    if (f==0) cout<<"-1"<<endl;
}

Measured memory_bytes: 3792