akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

long long X = 1000000007;

long long func(long long n, long long t){
  //cout << t << " " << n << endl;
  if(n == 1) return t % X;
  if(n % 2 == 0) return func(n / 2, t * t % X) % X;
  else return func(n / 2, t * t % X) * t % X;
}

long long func2(long long n, long long x){
  long long u = 1, d = 1, d2;
  for(int i = n; i >= n - x + 1; i--){
    u = u * i % X;
  }
  for(int i = x; i >= 1; i--){
    d = d * i % X;
  }
  d2 = func(X - 2, d);
  return u * d2 % X;
}

void solve(){
  long long n, a, b, ans; cin >> n >> a >> b;
  ans = (func(n, 2) - 1 - func2(n, a) - func2(n, b)) % X;
  if(ans < 0) ans += X;
  cout << ans % X << endl;
  return;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace D
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var abn = Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray();
            Func<long, long> f = x => (long)(Math.Floor((abn[0] * x) / (double)abn[1]) - abn[0] * Math.Floor(x / (double)abn[1]));
            Console.WriteLine(f(Math.Min(abn[1] - 1, abn[2])));
        }
    }
}


Measured memory_bytes: 28248
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <list>
#include <numeric>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

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

// 最小公倍数
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}*/

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

	int n, m;
	cin >> n >> m;
	vector<int> k(m);
	vector<vector<int>> s(m, vector<int>());
	rep(i, m) {
		cin >> k[i];
		rep(j, k[i]) {
			int tmp;
			cin >> tmp;
			s[i].push_back(tmp);
		}
	}
	vector<int> p(m);
	rep(i, m) cin >> p[i];

	// n個のスイッチでオンオフの2^10通り試す

	ll ans = 0;

	rep(bit, 1 << n) {
		bool ok = true;
		rep(i, m) {
			int cnt = 0;
			rep(j, k[i]) {
				if (bit & (1 << (s[i][j] - 1))) {
					cnt++;
				}
			}
			if (cnt % 2 != p[i]) {
				ok = false;
				break;
			}
		}
		if (ok) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}


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

int main(){

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0) ;

    int n ;
    cin >> n ;
    int a = 0 ;
    int ans = 0 ;

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

        int t ;
        cin >> t ;
        if(t >= a){

            ans ++ ;
            a = t ;

        }

    }
    cout << ans ;

}


Measured memory_bytes: 256
#if __has_include("D:/dhiraj/Programming/debug.h")
    #include "D:/dhiraj/Programming/debug.h"
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define d(...) 11
#endif

// Loops --------------------------------------------------------------------

#define loop(i,s,e)         for(ll i=(s); i<(e); i++)
#define rloop(i,s,e)        for(ll i=(s); i>=(e); i--)
#define iter(it,var)        for(auto it=var.begin(); it!=var.end(); it++)
#define riter(it,var)       for(auto it=var.rbegin(); it!=var.rend(); it++)

// Extra --------------------------------------------------------------------

#define fast                ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ull                 unsigned long long int
#define ll                  long long int
#define ld                  long double
#define endl                '\n'
#define all(x)              x.begin(),x.end()
#define rall(x)             x.rbegin(),x.rend()

// Template -----------------------------------------------------------------

template <typename T> 
inline bool inrange(T a, T l, T r) {
    if(l>r) swap(l,r);
    return (a>=l and a<=r);
}
template <typename T, typename U> 
inline bool exist(T val, U &any) {
    return (any.find(val) != any.end());
}
// multiple input
template <typename T> 
inline void inp(T &any) {
    cin >> any;
}
template <typename T, typename... U> 
inline void inp(T &a, U &...b) {
    cin >> a; inp(b...);
}
// scan vector
template <typename T> 
inline istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x : a) in >> x;
    return in;
}
// scan pair
template <typename T, typename U> 
inline istream &operator>>(istream &in, pair<T,U> &a) {
    in >> a.first >> a.second; 
    return in;
}

// Solve --------------------------------------------------------------------

const ll Mod = 1e9 + 7;
ll md(ll x, ll M = Mod)
{
    while(x<0) {
        x += M;
    }
    return x % M;
}

void solve(ll &T)
{
    ll n, k;
    std::cin>>n>>k;

    vector<ll> pre(n+1);
    pre[0] = 0;
    loop(i,1,n+1) {
        pre[i] += pre[i-1] + i;
    }

    ll ans = 0;
    loop(i,k,n+1)
    {
        ll s1 = pre[i-1];
        ll s2 = pre[n] - pre[n-i];
        d(i,s1,s2);
        ans = md(ans + md(s2-s1+1));
    }
    ans = md(ans+1);
    std::cout<<ans<<endl;
}

// Main ---------------------------------------------------------------------

int main()
{
    #ifdef Dhiraj
        freopen("D:/dhiraj/Programming/i1.txt","r",stdin);
        freopen("D:/dhiraj/Programming/o1.txt","w",stdout);
    #endif
    
    fast;
    int t = 1;
    loop(i,1,t+1)
    {
        cerr<<"Case #"<<i<<"\n";
        solve(i);
    }
    return 0;
}

Measured memory_bytes: 4844
# -*- coding: utf-8 -*-
def main():
    S = list(str(input()))
    S2 = list(reversed(S))
    N = len(S)//2
    ans = 0
    for i in range(N):
        if S[i] != S2[i]:
            ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
char ch;
int main() {
	cin>>ch;
	if (ch=='A') cout<<'T'<<endl;
	else if (ch=='T') cout<<'A'<<endl;
	else if (ch=='C') cout<<'G'<<endl;
	else cout<<'C'<<endl;
	return 0;
}

Measured memory_bytes: 256
# A,Bそれぞれの最大値は40 * 10である
# dp[i][j] = Aがiグラム、Bがjグラム含まれた薬品の最小コスト

import sys
readline = sys.stdin.readline

N,Ma,Mb = map(int,readline().split())
INF = 10 ** 10
dp = [[INF] * (401) for i in range(401)]
dp[0][0] = 0

for _ in range(N):
  a,b,c = map(int,readline().split())
  for i in range(len(dp) - 1, -1, -1):
    for j in range(len(dp[i]) - 1, -1, -1):
      if dp[i][j] == INF:
        continue
      if dp[i + a][j + b] > dp[i][j] + c:
        dp[i + a][j + b] = dp[i][j] + c

ans = INF
import math
for i in range(1, len(dp)):
  for j in range(1, len(dp)):
    g = math.gcd(i,j)
    if i // g == Ma and j // g == Mb:
      if ans > dp[i][j]:
        ans = dp[i][j]
      
if ans == INF:
  print(-1)
else:
  print(ans)

Measured memory_bytes: 10796
n = int(input())

data = list(map(int, input().split()))
sum1 = 0
sum2 = 0
for i in range(n):
    sum1 += data[i]

ans = abs(sum1 - sum2)

for i in range(n):
    sum1 -= data[i]
    sum2 += data[i]
    if abs(sum1 - sum2) < ans:
        ans = abs(sum1 - sum2)

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iomanip>
#include <algorithm>

using namespace std;

#define rep(countName, left, right) for (int countName = left; countName < right; countName++)

/* ****************************** ユークリッド互除法 ****************************** */
long long GCD(long long a, long long b)
{
    if (a % b == 0)
    {
        return b;
    }
    else
    {
        return GCD(b, a % b);
    }
}
/* ****************************** ユークリッド互除法 ****************************** */

/* ****************************** 累積和 ****************************** */
vector<long long> CUSUM(vector<long long> &&v)
{
    int n = v.size();
    vector<long long> cusum(n);
    cusum[0] = v[0];
    rep(i, 1, n)
    {
        cusum[i] = v[i] + cusum[i - 1];
    }
    return cusum;
}

//部分和

long long partSum(vector<long long> &&v, long long left, long long right)
{
    return (v[right] - v[left]);
}

/* ****************************** 累積和 ****************************** */

/* ****************************** 二項係数 ****************************** */
//けんちょんさん作

const int MAX = 800000;
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;
}

/* ****************************** 二項係数 ****************************** */

int main(void)
{
    int n;
    cin >> n;
    cout << n*n<<endl;
    return 0;
}

Measured memory_bytes: 256
//author: zekigurbuz (Zeki Gurbuz) 2020
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;

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

#define mp make_pair
#define pb push_back
#define lb lower_bound
#define all(x) begin(x),end(x)

const int N = 1e5 + 10;
const int M = 1e9 + 7;

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

template<class T>void ckmin(T&a,T b){a=min(a,b);}
template<class T>void ckmax(T&a,T b){a=max(a,b);}

void precomp() {

}


void solve() {
	int n, m; cin >> n >> m;
	int h[n];
	for (int i = 0; i < n; i++) cin >> h[i];
	set<int> ans; for (int i = 0; i < n; i++) ans.insert(i);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		if (h[u] >= h[v]) {
			if (ans.find(v) != ans.end()) ans.erase(v);
		}
		if (h[v] >= h[u]) {
			if (ans.find(u) != ans.end()) ans.erase(u);
		}
	}
	cout << ans.size() << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	precomp();
	int t = 1; // cin >> t;
	for (int i = 1; i <= t; ++i) {
		solve();
	}
	return 0;
}



Measured memory_bytes: 8692
#include<iostream>

using namespace std;

#define MAX 200001

int L[MAX/2+1],R[MAX/2+1];

long long cnt=0;

void merge(int A[],int left,int right,int mid)
{
    int n1=mid-left;
    int n2=right-mid;

    for (int i = 0; i < n1; ++i)
    {
        L[i]=A[i+left];
    }
    for (int i = 0; i < n2; ++i)
    {
        R[i]=A[i+mid];
    }

    L[n1]=R[n2]=1000000001;

    int j=0,k=0;
    for (int i = left; i < right; ++i)
    {
        if(R[j]>=L[k])
        {
            A[i]=L[k++];
        }
        else {
            A[i] = R[j++];
            cnt += n1 - k;
        }
    }
}

void mergeSort(int A[],int left,int right)
{
    if (left+1==right)
    {
        return;
    }
    int mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,right,mid);
}

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

    mergeSort(A,0,n);

    cout<<cnt<<endl;
}


Measured memory_bytes: 4680
(function() {
    'use strict';

    var fs = require('fs');
    var contents = fs.readFileSync('/dev/stdin', 'utf-8');

    var binarySearch = function(S, t) {
        var min = 0;
        var max = S.length;
        var mid = Math.floor((min + max) / 2);

        while (min <= max) {
            if (t === S[mid]) {
                return true;
            } else if (t > S[mid]) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
            mid = Math.floor((min + max) / 2);
        }
        return false;
    }

    var search = function(contents) {
        var S = [];
        var n = 0;
        var q = 0;
        var C = 0;
        var t = 0;

        var lines = contents.trim().split("\n");
        n = parseInt(lines[0]);
        S.length = n;
        var a = lines[1].split(" ");
        for (var i = 0; i < a.length; i++) {
            S[i] = parseInt(a[i]);
        }

        q = parseInt(lines[2]);
        var T = lines[3].split(" ");
        for (var i = 0; i < q; i++) {
            t = parseInt(T[i]);
            if (binarySearch(S, t)) {
                C++;
            }
        }
        console.log(C);
    }
    search(contents);
})();

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

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
int cmp(const void *a, const void *b);
//your code here!

int main(void){
    ll A, B, C;
    scanf("%lld %lld %lld", &A, &B, &C);
    printf((A+B>=C)?"Yes\n":"No");
    return 0;
}

int cmp(const void *a, const void *b){
    ll A=*(ll *)a, B=*(ll *)b;
    if(A==B)return 0;
    else return A>B ? 1:-1;//昇順ソート
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

vector<ll>par(2e5+10);
void init(ll n) {
  for(ll i=0;i<n;i++) {
    par[i]=i;
  }
}

ll root(ll x) {
  if(par[x]==x) {
    return x;
  }
  else {
    return par[x]=root(par[x]);
  }
}


bool same(ll x, ll y) {
  return root(x)==root(y);
}

void unite(ll x, ll y) {
  if(same(x,y)) return;
  par[root(x)]=root(y);
}

int main() {
  ll n,m,k;
  cin >> n >> m >> k;
  vector<set<ll>> f(n);
  init(n);
  for(ll i=0;i<m;i++) {
    ll a,b;
    cin >> a >> b;
    a--;
    b--;
    unite(a,b);
    f[a].insert(b);
    f[b].insert(a);
  }
  vector<set<ll>> nf(n);
  for(ll i=0;i<k;i++) {
    ll a,b;
    cin >> a >> b;
    a--;
    b--;
    f[a].insert(b);
    f[b].insert(a);
  }
  map<ll,ll> num;
  for(ll i=0;i<n;i++) {
    num[root(i)]++;
  }
  vector<ll> ans(n,0);
  for(ll i=0;i<n;i++) {
    ans[i]=num[root(i)]-1;;
  }
  for(ll i=0;i<n;i++) {
    for(ll p:f[i]) {
      if(same(i,p)) {
        ans[i]--;
      }
    }
  }
  for(ll i=0;i<n;i++) {
    if(i!=0) {
      cout << " ";
    }
    cout << ans[i];
  }
  cout << endl;
}

Measured memory_bytes: 37120
import java.util.*;
import java.util.stream.*;
import java.util.function.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        
        System.out.println(b % a == 0 ? a + b : b - a);
    }
    
    // // パラメタ渡しもちゃんとクラス作るのも面倒なので手抜き
    // // 必要な値はここで全部取ってしまう
    // Scanner sc = new Scanner(System.in);
    // int n = Integer.parseInt(sc.next());
    // {sc.nextLine();}
    // int[] a = IntStream.range(0, n).map(i -> Integer.parseInt(sc.next())).toArray();
    
    // String solve() {
    //     return n + "" + Arrays.toString(a);
    // }
    
}


Measured memory_bytes: 22868
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <cstdlib>
using namespace std;

int N,M,D;
char a[999][999];
char t[2][2]={{'R','Y'},{'G','B'}};

void solve(){

	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			int x = (-i+j+N)/D, y = (i+j+N)/D;
			x%=2, y%=2;
			a[i][j]=t[x][y];
		}
	}

	for(int i=0;i<N;i++){
		puts(a[i]);
	}


}

int main(){

	scanf("%d%d%d",&N,&M,&D);
	solve();

	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define uu first
#define vv second

using namespace std;

typedef long long ll;

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int n;
    cin >> n;
    string s, s2;
    cin >> s;
    s2 = s[0];
    for (int i = 1;i < s.size(); i++) {
        if (s2[s2.size()-1] != s[i]) s2 += s[i];
    }
    cout << s2.size() << '\n';
    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#define x 101
#define y 101

int main() {
	int r, c, s, i, j, sum;
	int cnt[x][y] = {0};
	int a[x] = {0};
	int b[y] = {0};
	sum = 0;

	scanf("%d %d", &r, &c);
	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			scanf("%d", &s);
			cnt[i][j] = s;
		}
	}
	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			a[j] += cnt[i][j];
		}
	}
	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			b[i] += cnt[i][j];
		}
	}
	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			printf("%d ", cnt[i][j]);
		}
		printf("%d\n", b[i]);
	}
	for (j = 0; j < c; j++) {
		printf("%d ", a[j]);
		sum += a[j];
	}
	printf("%d\n", sum);
	return 0;
}


Measured memory_bytes: 2148
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>

using namespace std;


int main(){
    int n;
    cin >> n;
    vector<pair<string,int>> p(n);
    vector<pair<string,int>> ptmp(n);
    for(int i = 0; i < n; i++){
        cin >> p[i].first >> p[i].second;
        ptmp[i].first = p[i].first;
        ptmp[i].second = p[i].second;
    }

    sort(p.begin(),p.end());

    vector<int> a;

    string tmp = p[0].first;
    for(int i = 0; i < n; i++){
        if(tmp != p[i].first){
            for(int k = a.size()-1; k >= 0; k--){
                cout << a[k] << endl;
            }
            a.clear();
            tmp = p[i].first;
        }
        for(int j = n-1; j >= 0; j--){
            if(p[i] == ptmp[j]){
                a.push_back(j+1);
            }
        }
    }
    for(int k = a.size()-1; k >= 0; k--){
        cout << a[k] << endl;
    }


    return 0;
}



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

int main()
{
 int n,x;
 cin>>n>>x;
 int flag =0;
 
 for(int i=0;i<=n;i++)
 {
if(i*2+(n-i)*4 == x)
{flag=1;break;}
     
}
if(flag)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
 
 
}

Measured memory_bytes: 3488
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(i = 1; i <= n; i++)
//2D::rep(i,j)rep(j,j)cin>>bin[i][j];
#define vec(n) vector<int> a(n)
#define A1 cout<<"No"<<endl
#define A2 cout<<"Yes"<<endl
#define A3 cout<<ans<<endl
#define AA(i) cout<<i<<endl
const int U=2e5+5;
const ll V=1000000007;

int main() {
  int i,N; cin>>N;
  ll K; cin>>K;
  vector<int> m(N+1);
  rep(i,N)cin>>m[i];
  vector<bool> l(N+1,false);
  vector<bool> ll(N+1,false);
  int k,j=1,x=0,z=0;
  if(K>N){
  while(true){
    if(l[j])break;
    else l[j]=true;
    x++;
    j=m[j];
  }
  while(true){
    if(ll[j])break;
    else ll[j]=true;
    z++;
    j=m[j];
  }
  K = (K-x)%z;
  int p=1;
  for(int j=0;j<K+x-z;j++){
    p =m[p];
  }
  AA(p);
  }
  else{
      int p=1;
  for(int j=0;j<K;j++){
    p =m[p];
  }
    AA(p);
  }
  return 0;
}

Measured memory_bytes: 4052
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <bitset>
#include <random>
#include <chrono>
#include <complex>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip> 

using namespace std;

#define mp make_pair
#define pb push_back
#define forn(i, n) for(int i = 0; i < (int)(n); ++i)
#define for1(i, n) for(int i = 1; i < (int)(n); ++i)
#define nfor(i, n) for(int i = int(n) - 1; i >= 0; --i)
#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define correct(x, y, n, m) (0 <= x && x < n && 0 <= y && y < m)
#define all(x) (x).begin(), (x).end()
#define fst first
#define snd second
#define endl "\n"

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef tuple<int,int,int> iii;

template<typename T> inline T abs(T a){ return ((a < 0) ? -a : a); }
template<typename T> inline T sqr(T a){ return a * a; }
template<class T> T gcd(T a, T b) { return a ? gcd (b % a, a) : b; }
template<class T> T lcm(T a, T b) { return a / gcd (a, b) * b; }
template<class T> T sign(T a) { return a > 0 ? 1 : (a < 0 ? -1 : 0); }

string to_string(string s) {
    return '"' + s + '"';
}
    
string to_string(const char* s) {
    return to_string((string) s);
}
    
string to_string(bool b) {
    return (b ? "true" : "false");
}
    
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
    
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

void fastIO() {
    cin.sync_with_stdio(false);
    cin.tie(0);
}

template<typename T>
vector<T> make_unique(vector<T> v) {
    sort(all(v));
    return v.resize(unique(all(v)) - v.begin());
}

int nxt() {
    int x;
    cin >> x;
    return x;
}

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int dxKn[8] = {-2, -1, 1, 2,  2,  1, -1, -2};
const int dyKn[8] = { 1,  2, 2, 1, -1, -2, -2, -1};
const int dxK[8] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dyK[8] = {1, -1, 0, 0, 1, -1, 1, -1};

const int MOD = int(1e9) + 7;
const int INF = int(1e9) + 100;
const ll INF64 = 2e18;
const ld PI = ld(3.1415926535897932384626433832795);
const ld e = ld(2.7182818284590452353602874713527);
const ld EPS = 1e-9;

//#############################
const int MAXN = 1000005;

int main() {
    fastIO(); 
    int n,k;
    cin >> n >> k;
    vector<int> v(n, 0);
    generate(all(v), nxt);

    sort(all(v));

    int ans = 0;
    forn(i,k)
        ans += v[i];

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

Measured memory_bytes: 3656
#include<stdio.h>
int n[100001];
int main(){
	int a,b;
	while(1){
		scanf("%d%d",&a,&b);
		if(a==0&&b==0)return 0;
		int temp=0;
		for(int i=1;i<a+1;i++){
			int val;
			scanf("%d",&val);
			n[i]=(temp+=val);
			//printf("%d\n",n[i]);
		}
		int max=-1000000000;
		for(int i=0;i<a-b+1;i++){
			if(max<n[i+b]-n[i])max=n[i+b]-n[i];
			//printf("%d\n",n[i+b]-n[i]);
		}
		printf("%d\n",max);
	}
}

Measured memory_bytes: 0
#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;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size() 

ll a[200005];

int main()
{
    ios_base::sync_with_stdio(false);
	ll n,i,j,k,x,y,t,m;

	cin >> n;
	x=0;
	for(i=1;i<=n;i++)
	{
		cin >> a[i];
		x^=a[i];
	}

	for(i=1;i<=n;i++)
		cout<<(x^a[i])<<" ";
	cout<<endl;
}	

Measured memory_bytes: 5196
N = int(input())
res = 99999
for a in range(1, N): 
        sum_ = 0 
        b = N - a 
        while (a > 0): 
                sum_ += a % 10
                a //= 10
        while (b > 0): 
                sum_ += b % 10
                b //= 10
        res = min(res, sum_)
print(res)

Measured memory_bytes: 3060
#include <stdio.h>
int main ()
{

  int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int b;
  scanf("%d",&b);
  printf("%d",a[b-1]);



  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
  long long d, t, s;
  cin >> d >> t >> s;
  if(d%s == 0){
    if((d/s) <= t ) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  else if(d/s < t ) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3584
S = input()
Q = int(input())
rev = 1

head = []
tail = []

for i in range(Q):
  line = input()
  if line == '1':
    rev *= -1
  else:
    line = line.split()
    F = int(line[1])
    C = line[2]
    if rev * F in [1, -2]:
      head.append(C)
    else:
      tail.append(C)

head = head[::-1]
S = ''.join(head + [S] + tail)

if rev == -1:
  S = S[::-1]
  
print(S)

Measured memory_bytes: 97960
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::prelude::BufRead;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufReader, BufWriter, Write};
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::str::FromStr;

fn main() {
    let n = read::<u64>();
    let mut minimum = std::u64::MAX;
    for _ in 0..5 {
        let a = read::<u64>();
        minimum = min(minimum, a);
    }
    let ans = 4 + if n % minimum == 0 { n / minimum } else { n / minimum + 1 };
    println!("{}", ans);

}

#[allow(dead_code)]
fn read<T>() -> T
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf.trim().parse().unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::with_capacity(100);
    stdin().read_line(&mut buf).unwrap();
    return buf.split_whitespace().map(|s| s.parse().unwrap()).collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    use std::io::prelude::*;
    let stdin = stdin();
    let mut reader = BufReader::with_capacity(100 * 1024, stdin);
    let mut line = String::with_capacity(100);
    let mut matrix: Vec<Vec<T>> = Vec::new();

    while reader.read_line(&mut line).unwrap() > 0 {
        matrix.push(
            line.trim()
                .split_whitespace()
                .map(|s| s.parse().unwrap())
                .collect(),
        );
        line.clear();
    }

    return matrix;
}

#[allow(dead_code)]
fn read_chars() -> Vec<char> {
    let stdin = stdin();
    let mut buf = String::new();
    let _bytes = stdin.read_line(&mut buf).unwrap();
    return buf.trim().chars().collect();
}


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

int main()
{
	int n = 0;
	int upper =10;
	while(cin >> n){
		int answer = 0;
		for(int i = 0; i < upper; ++i)
		{
			for(int j = 0; j < upper; ++j)
			{
				for(int k = 0; k < upper;++k)
				{
					for(int l = 0; l < upper; ++l)
					{
						if((i+j+k+l)==n)
						{
							answer++;
						}
					}
				}
			}
		}
		cout << answer << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
int main() {
	int N, M;
	cin >> N >> M;
	if (N >= M) {
		cout << 0 << endl;
		return 0;
	}
	vector<int> X;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		X.push_back(x);
	}
	sort(X.begin(), X.end());
	vector<int> L;
	ll sum = X[M - 1] - X[0];
	for (int i = 0; i + 1 < M; i++) {
		L.push_back(X[i + 1] - X[i]);
	}
	sort(L.begin(), L.end(), greater<int>());
	for (int i = 0; i < N - 1; i++) {
		sum -= L[i];
	}
	cout << sum << endl;

}


Measured memory_bytes: 1400
#include "bits/stdc++.h"
#define rep(i,N) for (int (i) = 0; (i) < (N); (i)++)

int main() {

	std::cin.tie(nullptr); std::ios::sync_with_stdio(false);
	
	int M; std::cin >> M;

	std::cout << (24 - M) + 24;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
#include <string>
#include <stack>
#include <queue>

#define INT_MAX 2147483647
#define INT_MIN -2147483647

using namespace std;

int main()
{
	int num; cin >> num;
	vector<int> data(num);
	for (int i = 0; i < num; ++i) cin >> data[i];

	for (int i = 0; i < num; ++i)
	{
		printf("node %d: key = %d, ", i + 1, data[i]);

		int idxP = (i + 1) / 2;
		if (idxP > 0) printf("parent key = %d, ", data[idxP - 1]);

		int idxL = (i + 1) * 2;
		int idxR = (i + 1) * 2 + 1;
		if (idxL <= num) printf("left key = %d, ", data[idxL - 1]);
		if (idxR <= num) printf("right key = %d, ", data[idxR - 1]);
		
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 3208
N = int(input())
a = list(map(int, input().split()))

s = [a[0]]
for i in range(1, N):
    s.append(a[i] + s[-1])

S = sum(a)
ans = 10000000000000000
for i in range(N - 1):
    ans = min(abs(2 * s[i] - S), ans)

print(ans)


Measured memory_bytes: 24800
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define out(a) cout << a << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)

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



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

int main(){
    int n,a;
    cin>>n>>a;
    vector<int> x(n);
    ll sum=0;
    rep(i,n){
        cin>>x[i];
        sum+=x[i];
    }
    vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(n+1, vector<ll>(sum+1)));
    dp[0][0][0]=1;
    for(int j=1;j<=n;j++){
        for(int k=0;k<=j;k++){
            for(int s=0;s<=sum;s++){
                if(s-x[j-1]<0) dp[j][k][s]=dp[j-1][k][s];
                else if(k>0) dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]];
            }
        }
    }
    ll ans=0;
    for(int k=1;k<=n;k++){
        if(k*a>sum) continue;
        ans+=dp[n][k][k*a];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 55108
N,M,X = map(int, input().split())
A = list(map(int, input().split()))
sorted_A = sorted(A)
for i in range(M):
    if A[i]>=X:
        cnt = i
        break
ans1 = len(A[cnt:])
ans2 = len(A[:cnt])
ans = min(ans1,ans2)
print(ans)


Measured memory_bytes: 3064
from itertools import accumulate

N, M, K = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

accAs = list(accumulate([0]+As))
accBs = list(accumulate([0]+Bs))
#print('accAs:', accAs)
#print('accBs:', accBs)

iB = M
ans = 0
for iA in range(N+1):
    num = iA
    accA = accAs[iA]
#    print('\niA:', iA, '/ accA:', accA)
    if accA > K:
        break
    while accA + accBs[iB] > K:
        iB -= 1
    num += iB
#    print('iA:', iA, '/ iB:', iB, '/ num:', num)
    if num > ans:
        ans = num

print(ans)


Measured memory_bytes: 50784
N = int(input())
p = list(map(float,input().split()))

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

dp[0][0] = 1-p[0]
dp[0][1] = p[0]

for i in range(1,N):
    dp[i][0] = (1-p[i])*dp[i-1][0]
    for j in range(1,i+2):
        dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i])
        
print(sum(dp[-1][(N+1)//2:]))

Measured memory_bytes: 263048
p = 998244353

a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for k in range(c+1)]
for i in range(a, c+1):
	for j in range(b, d+1):
		if i == a:
			if j == b:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i][j-1] * i % p
		elif j == b:
			dp[i][j] = dp[i-1][j] * j % p
		else:
			dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % p

print(dp[c][d])

Measured memory_bytes: 152964
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<char> > grid;
    grid.resize(h);
    rep(i,h)grid[i].resize(w);
    int res=0;
    rep(i,h)rep(j,w){
        char c;
        cin >> c;
        if(c=='#')res++;
        grid[i][j] = c;
    }
    
    vector<vector<int> > dist(h,vector<int>(w,0));
    
    queue<pair<int,int> > qu;
    qu.push(make_pair(0,0));
    while(!qu.empty()){
        auto cur = qu.front();qu.pop();
        if(cur==make_pair(h-1,w-1))break;
        rep(i,4){
            int nx = cur.first+dx[i],ny = cur.second+dy[i];
            if(0<=ny&&ny<h&&0<=nx&&nx<w&&grid[ny][nx]!='#'){
                if(dist[ny][nx]==0){
                    qu.push(make_pair(nx,ny));
                    dist[ny][nx]= dist[cur.second][cur.first]+1;
                }
            }
        }
    }
    if(dist[h-1][w-1]==0)cout << -1 << endl;
    else cout << h*w-(res+dist[h-1][w-1]+1) << endl;
    return 0;
}

Measured memory_bytes: 256
import collections

N = int(input())
a = list(map(int, input().split()))
a.sort()

C = collections.Counter(a)
L = len(C)
e = list(C.keys())
if (L == 1) and (C[0] > 0):
    print("Yes")
elif (L == 2) and (C[e[0]] * 2 == C[e[1]]):
    print(((e[0] ^ e[0] == e[1]) or (e[1] ^ e[1] == e[0])) and "Yes" or "No")
elif (L == 3) and (C[e[0]] == C[e[1]]) and (C[e[1]] == C[e[2]]):
    print(((e[0] ^ e[1]) == e[2]) and "Yes" or "No")
else:
    print("No")


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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debugF(ostream &os) {os << endl;}
template <typename Head, typename... Tail>
void debugF(ostream &os, Head H, Tail... T) { os << " " << H; debugF(os, T...); }
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debugF(cout, __VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); os << (i>0 ? " ":"") << v[i++]); return os;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, i;
    cin >> k;
    int d = 7;
    int seq = 7;
    for(i=1;i<=k;i++){
        if(seq%k == 0) break;
        seq = (seq*10 + d)%k;
    }
    if(i <= k){
        cout << i << "\n";
    }else{
        cout << -1 << "\n";
    }
    
    return 0;
}


Measured memory_bytes: 3648
S=input()
N=len(S)
count=0
hatenadata=[]
Sinfo=[]
for i in range(0,N):
    if S[i]=='?':
        Sinfo.append('0')
        count+=1
        hatenadata.append(i)
    else:
        Sinfo.append(S[i])
X=''.join(Sinfo)
first=int(X)%13

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-k*10**((digit-1)%6))%13] for k in range(0,10))%(10**9+7)

print(dp[count][5]%(10**9+7))

Measured memory_bytes: 67828
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,d;
bool judge()
{
    if(b>d) return false;
    if(a<b) return false;
    ll k=__gcd(b,d),s=a-(a-c)/k*k-k,t=10;
    while(t--)
    {
        if(s>c&&s<b) return false;
        s+=k;
    }
    s=a-(a-c)/b*b;
    if(s>c&&s<b) return false;
    return true;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        if(judge()) printf("Yes\n");
        else printf("No\n");
    }
}


Measured memory_bytes: 256
using System;

public class Program
{
    private int N;
    private string[] S;
    private int[] T;
    private string X;
    public void Solve()
    {
        var sc = new Scanner();
        N = sc.NextInt();
        S = new string[N];
        T = new int[N];
        for (int i = 0; i < N; i++)
        {
            S[i] = sc.Next();
            T[i] = sc.NextInt();
        }

        X = sc.Next();

        bool f = false;
        long cnt = 0;
        for (int i = 0; i < N; i++)
        {
            if (f)
            {
                cnt += T[i];
            }
            if (S[i] == X)
            {
                f = true;
            }
        }
        
        Console.WriteLine(cnt);
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

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

const int W_MAX = 10010;
int dp[W_MAX];

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

    int n, w;
    cin >> n >> w;

    vector<int> V(n), W(n);
    for(int i = 0; i < n; i++){
        cin >> V[i] >> W[i];
    }

    for(int i = 0; i <= w; i++){
        for(int j = 0; j < n; j++){
            if(i - W[j] >= 0){
                dp[i] = max(dp[i], dp[i - W[j]] + V[j]);
            }
        }
    }

    cout << dp[w] << endl;

    return 0;
}


Measured memory_bytes: 3244
def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N
    
    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a
        
        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


N, M = read_values()
A = read_list()
uf = UF(N)
for _ in range(M):
    i, j = read_index()
    uf.make_pair(A[i] - 1, A[j] - 1)

res = 0
for i, a in enumerate(A):
    if uf.is_pair(i, A[i] - 1):
        res += 1

print(res)


Measured memory_bytes: 83364
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val t = readLine()!!.split(" ").map(String::toInt)
    val m = readLine()!!.toInt()

    (1..m).forEach {
        val (p, x) = readLine()!!.split(" ").map(String::toInt)
        println(t.sum() - t[p-1] + x)
    }
}

Measured memory_bytes: 36000
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int n, t;
    cin >> n >> t;

    vs32 a(n);
    for (auto& x : a)
    {
        cin >> x;
    }

    vs32 back_max(n);
    back_max.back() = a.back();
    int m = 0;
    int ans = 0;
    for (int i = n - 2; i >= 0; --i)
    {
        back_max[i] = max(back_max[i + 1], a[i]);
        int temp = back_max[i + 1] - a[i];
        if (m < temp)
        {
            m = temp;
            ans = 1;
        }
        else if (m == temp)
        {
            ++ans;
        }
    }

    cout << ans << "\n";

    return 0;
}



Measured memory_bytes: 3964
#include <stdio.h>
int main(){
    while (1) {
    int n,turn,ba,i,j;
    int hanako,tarou,point;
    point=0;
    turn=1;
    ba=-1;
    scanf("%d",&n);
    if (n==0) return 0;
    hanako=n;
    tarou=n;
    int c[2*n];
    for (i=0; i<2*n; i++) c[i]=0;
    for (i=0; i<n; i++) {
        int x;
        scanf("%d",&x);
        c[x-1]=1;
    }
    while (1){
        for (i=0; i<2*n; i++) {
            if(c[i]==turn&&i>ba) {
                c[i]=2;
                ba=i;
                if (turn){
                    tarou--;
                    if (tarou==0) {
                        for (j=0; j<2*n; j++) {
                            if (c[j]==0) point++;
                        }
                        printf("%d\n%d\n",point,0);
                        goto success;
                    }
                    turn=0;
                }else{
                    hanako--;
                    if (hanako==0) {
                        for (j=0; j<2*n; j++) {
                            if (c[j]==1) point++;
                        }
                        printf("%d\n%d\n",0,point);
                        goto success;
                    }
                    turn=1;
                }
            }
        }
        if (turn) turn=0;
        else turn=1;
        ba=-1;
    }
    success:;
}
}

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

bool isFirst[14];	//数字iを最初先手が持っているか？

//カード[l, r]が場にある。
//first…先手ならyes, 後手ならfalse
//戻り値：自分(first = true ⇔ 先手)が勝てるか？
bool dfs(int l, int r, bool first) {
	//相手のカードが無くなっていたら終了
	int i;
	for (i = 1; i <= 13; i++) {
		if (isFirst[i] != first) {
			if (!(l <= i && i <= r)) {
				break;
			}
		}
	}
	if (i > 13) { return false; }
	
	bool ret = false;
	bool canPut = false;
	if (l > 1 && isFirst[l - 1] == first) {
		ret |= !dfs(l - 1, r, !first);
		canPut = true;
	}
	if (r < 13 && isFirst[r + 1] == first) {
		ret |= !dfs(l, r + 1, !first);
		canPut = true;
	}
	if (canPut) { return ret; }
	
	return !dfs(l, r, !first);
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 14; j++) isFirst[j] = false;
		for (int j = 0; j < 6; j++) {
			int a; cin >> a;
			isFirst[a] = true;
		}
		if (dfs(7, 7, true)) { cout << "yes" << endl; }
		else { cout << "no" << endl; }
	}
	return 0;
}

Measured memory_bytes: 3080
# AGC023
# 方針：累積和を取る。同じ要素の個数nに対し、sum n(n-1)/2
n = gets.to_i
a = gets.split.map &:to_i

cs = Array.new(n+1,0)
n.times do |i|
  cs[i+1] = cs[i] + a[i]
end
# p cs
cnt = Hash.new(0)
(n+1).times do |i|
  cnt[cs[i]] += 1
end

ans = 0
cnt.values.each do |n|
  ans += n * (n-1) / 2
end

puts ans


Measured memory_bytes: 32132
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;


int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    cout<<*max_element(a.begin(), a.end())-*min_element(a.begin(), a.end())<<endl;
    
    
}


Measured memory_bytes: 256
#include<stdio.h>

/*構造体の定義*/
typedef struct {
	char suit;
	int value;
} Card ;


void BubbleSort(Card A[], int N) {
	int i, j;
	Card temp;

	for (i = 0; i < N; i++) {
		for (j = N - 1; j >= i + 1; j--) {
			if (A[j].value < A[j - 1].value) {
				temp = A[j];
				A[j] = A[j - 1];
				A[j - 1] = temp;
			}
		}
	}
}


void SelectionSort(Card A[], int N) {
	int i, j;
	int minj;
	Card temp;

	for (i = 0; i < N; i++) {
		minj = i;
		for (j = i; j < N; j++) {
			if (A[j].value < A[minj].value) {
				minj = j;
			}
		}
		temp = A[i];
		A[i] = A[minj];
		A[minj] = temp;
	}
}



int main()
{
	int N;
	scanf("%d\n", &N);

	int i,j;
	Card BC[36];
	Card SC[36];

	for (i = 0; i < N; i++) {
		Card c;
		scanf("%c", &c.suit);
		scanf("%d ", &c.value);
		BC[i] = c;
		SC[i] = c;
	}
    
    BubbleSort(BC,N);
    SelectionSort(SC,N);
	
	/* Output */
	for (i = 0; i < N - 1; i++) {
		printf("%c%d ", BC[i].suit, BC[i].value);
	}
	printf("%c%d\n", BC[N - 1].suit, BC[N - 1].value);
	puts("Stable");

	for (i = 0; i < N - 1; i++) {
		printf("%c%d ", SC[i].suit, SC[i].value);
	}
	printf("%c%d\n", SC[N - 1].suit, SC[N - 1].value);

	for (i = 0; i < N; i++) {
		if (BC[i].suit != SC[i].suit) {
			puts("Not stable");
			return 0;
		}
	}
	puts("Stable");

	return 0;
}


Measured memory_bytes: 2052