akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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<class T> vector<int> z_algorithm(const T& s) {
  vector<int> prefix(s.size());
  prefix[0] = s.size();
  int i = 1, j = 0;
  while (i < s.size()) {
    while (i + j < s.size() && s[j] == s[i + j]) ++j;
    prefix[i] = j;
    if (j == 0) { ++i; continue; }
    int k = 1;
    while (i + k < s.size() && k + prefix[k] < j) { prefix[i + k] = prefix[k]; ++k; }
    i += k; j -= k;
  }
  return prefix;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  vector<int> a2(n), b2(n);
  rep(i, n) {
    a2[i] = a[i]^a[(i+1)%n];
    b2[i] = b[i]^b[(i+1)%n];
  }
  vector<int> s = b2;
  rep(i, 2) rep(j, n)
    s.push_back(a2[j]);
  auto res = z_algorithm(s);
  for (int i = n; i < n*2; i++) {
    if (res[i] >= n) {
      int x = a[i-n]^b[0];
      cout << i-n << ' ' << x << '\n';
    }
  }
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}


signed main() {
  string a, b, c;
  cin >> a >> b >> c;

  cout << (char)(a[0] - 32) << (char)(b[0] - 32) << (char)(c[0] - 32) << endl;
}


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

using namespace std;
typedef long long ll;
const ll INF=100000000000000LL;

int main() {
	int x,a,b;
	cin>>x>>a>>b;
	if(a>=b)cout<<"delicious"<<endl;
	else if(a+x>=b)cout<<"safe"<<endl;
	else cout<<"dangerous"<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        int C = scan.nextInt();
        
        if(A == B) System.out.println(C);
        if(A == C) System.out.println(B);
        if(B == C) System.out.println(A);
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int INF = 1<<29;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする

long long int i,j;

int main(){
	int a[9];
	for(i=0;i<9;i++){
		cin>>a[i];
	}
	int x,y;
	x=a[1]-a[0];
	y=a[2]-a[1];
	if(a[4]-a[3]==x && a[5]-a[4]==y && a[7]-a[6]==x && a[8]-a[7]==y){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
typedef unsigned long long uLL;
typedef long double ldb;
typedef pair<int,int> pii;
 
int A[200001];
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, k;
    cin>>n>>k;
    for(int i = 0; i < n; ++i)
    {
        int inp;
        cin>>inp;
        ++A[inp];
    }
    sort(A, A+n+1);
    int ans = 0;
    for(int i = 0; i <= n-k; ++i)
        ans += A[i];
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI = 3.141592653589793238462643383279;
ll getDigit(ll x) {
  return x == 0 ? 1 : log10(x) + 1;
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

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

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

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

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

signed main() {
  ll N, K;
  cin >> N >> K;
  K--;
  string S;
  cin >> S;

  if (S[K] == 'A') {
    S[K] = 'a';
  }
  if (S[K] == 'B') {
    S[K] = 'b';
  }
  if (S[K] == 'C') {
    S[K] = 'c';
  }
  COUT(S);
  return 0;
}

Measured memory_bytes: 256
def solve(N, TAs):
    T, A = 1, 1
    for t, a in TAs:
        m = (t * A) % a
        y = max(0, (T * a - t * A) // t)
        while True:
            if (m + (y * t)) % a == 0:
                break
            y += 1
        x = (t * A + t * y) // a - T

        T += x
        A += y
    return T + A


#        T + x : A + y = t : a
#       <=> t * A + y * t = a * T + x * a
#       <=> x =  (t * A + y * t) / a -  T => 整数
# 　　　<=> y =  (a * T + x * a) / t -  A => 整数
# 以下二つが両方とも整数
# (a * T + x * a) / t
# (t * A + y * t) / a
#  t - (a * T mod t) = (x * a) mod t

if __name__ == "__main__":
    N = int(input())
    TAs = [(tuple)(map(int, input().split(" "))) for l in range(N)]
    print(solve(N, TAs))


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }


/*
 <url:https://onlinejudge.u-aizu.ac.jp/services/room.html#RitsCamp18Day1/problems/C>
 問題文============================================================
 長さ N の数列 ai が与えられる。 次の条件を満たす整数 K(1≤K≤N) を全て出力せよ。
 
 条件: a1,⋯,aK をうまく並び替えると aN−K+1,⋯,aN と一致する。
 
 =================================================================
 
 解説=============================================================
 
 Kを大きくしていくにつれて、mapなどで、左から見て行った時、右から見て行った時の
 要素が出現した個数を保持して、条件を満たすか判定していく
 
 ================================================================
 */
void solve(){
    ll N; cin >> N;
    vector<ll> a(N); for(auto& in:a) cin >> in;
    map<ll,ll> mp1,mp2;
    vector<ll> ans;
    for(int i = 1; i <= N;i++){
        mp1[a[i-1]]++;
        mp2[a[N-i]]++;
        [&]{
            for(auto it:mp1){
                if(it.second == mp2[it.first]) continue;
                return;
            }
            ans.push_back(i);
        }();
    }
    cout << ans << endl;
}
int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    solve();
    return 0;
}



Measured memory_bytes: 10008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
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; }


int main(){
    ll N, x;
    cin >> N >> x;
    vector<ll> a(N);
    rep(i, N) cin >> a.at(i);
    ll sum = 0;
    rep(i, N-1) {
        if(a.at(i) + a.at(i+1) > x) {
            if(a.at(i+1) >= a.at(i) + a.at(i+1) - x) {
                sum += a.at(i) + a.at(i+1) - x;
                a.at(i+1) -= a.at(i) + a.at(i+1) - x;
            }
            else {
                sum += (a.at(i) + a.at(i+1)) - x;
                a.at(i) = x;
                a.at(i+1) = 0;
            }
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 4040
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n,k] <- getIntList
    print $ if n `mod` k == 0 then 0 else 1

Measured memory_bytes: 380
#include <vector>
#include <stdio.h>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <random>
#include <time.h>
#include <cassert>

#define prev askdnsajd
#define rank asasdmdnasd
#define next lsjndajbs
#define hash asmdklansd

using namespace std;

typedef long long ll;
typedef long double dbl;

template<class T>
void print(vector<T> s){
	for (T x : s)
		cout << x << " ";
	cout << endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < s.size(); i++)
		cnt += (s[i] == 'o' ? 1 : 0);
	if (cnt + 15 - s.size() >= 8)
		cout << "YES\n";
	else
		cout << "NO\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;
#define inf 1e12
typedef long long ll;
ll dist[300][300];
void wf(int n){
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}
int main(void)
{
    int n, m, l; cin >> n >> m >> l;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++){
        if(i==j) dist[i][j] = 0;
        else dist[i][j] = inf;
    }
    for(int i=0;i<m;i++){
        int a,b,c; cin >> a >> b >> c; a--; b--;
        dist[a][b]=dist[b][a]=c;
    }
    wf(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dist[i][j] <= l) dist[i][j]=1;
            else dist[i][j]=inf;
        }
    }
    wf(n);
    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(dist[i][j]>=inf) cout << "inf ";
            else printf("%3lld ",dist[i][j]);
        }puts("");
    }*/
    int q; cin >> q;
    for(int i=0;i<q;i++){
        int s,t; cin >> s >> t; s--; t--;
        if(dist[s][t] == inf) cout << -1 << endl;
        else cout << dist[s][t] -1 << endl;
    }
}


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

using ll = long long;
int main(){
    int N;
    cin >> N;
    vector<ll> A(N);
    
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    vector<ll> count(N + 1);
    for(int i = 0; i < N; i++){
        count[A[i]]++;
    }

    ll a = 0;
    for(int i = 1; i <= N; i++){
        a += count[i] * (count[i] - 1) / 2;
    }

    for(int i = 0; i < N; i++){
        ll b = a - count[A[i]] * (count[A[i]] - 1) / 2;
        b += (count[A[i]] - 1) * (count[A[i]] - 2) / 2;
        cout << b << endl;
    }

    return 0;
}

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

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

    int ans = 0;

    for(int i = 3; i <= N; i += 2) {
        int cnt = 0;
        //cout << i;
        for(int j = 1; j <= i; j++) {
            if(i % j == 0) {
                cnt++;
                //cout << "a";
            }
        }
        //cout << endl;
        if(cnt == 8) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pll pair<ll,ll>
#define sll set<ll>
#define msll multiset<ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define vpl vector<pll>
#define gll greater<ll>
#define spl set<pll>
#define mspl multiset<pll>
#define lb lower_bound
#define ub upper_bound
#define prq priority_queue
#define mp make_pair
#define pb push_back
#define mem(x,y) memset(x, y, sizeof x)
#define endl "\n"
#define sz(x) (ll)x.size()
#define sqr(x) x*x
#define rapido ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef long double ld;
ll mx=INT_MIN;
ll mn=INT_MAX;
ll MOD=1e9+7;
ll INF = 1e18;
const int maxs=2e5+10;
const int lg=22;

void code_idhr_h(){
    ll a,b; cin>>a>>b;
    cout<<a*b;
}

int main(){
    rapido;
    ll T=1; //cin>>T;
    while(T--){
        code_idhr_h();
    }
    return 0;
}

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

int main() {
  int n, r;
  cin >> n >> r;
  int i;
  if (n >= 10) {
    i = r;
  } else {
    i = r + 100 * (10 - n);
  }
  cout << i << endl;
}



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

int main() {
	int N;
	cin >> N;
	int p[N];
	int a;
	int k = 0;
	for (int i = 0;i < N;i++) 
		cin >> p[i];
	
	
	for (int j = 0;j < N;j++)
		for (int l = 0;l < N-1;l++)
			if (p[l] > p[l+1]) {
				a = p[l];
				p[l] = p[l +1];
				p[l + 1] = a;
				k++;
				}
				
			
	for (int i = 0;i < N;i++) {
		cout << p[i] ;
		if (i != N - 1)
			cout <<" ";

	}
	cout << endl;;
	cout << k << endl;

	return 0;
	
	

	
}


Measured memory_bytes: 3124
n = gets.chomp.split[0].to_i

list = []

for i in 1..n do
    input = gets.chomp.split
    s = input[0]
    pt = input[1].to_i
    rest = [s,pt,i]
    list.push(rest)
end

list.sort! {|x,y| (x[0] <=> y[0]).nonzero? || (y[1] <=> x[1]) }

for i in 1..n do
    puts list[i-1][2]
end


Measured memory_bytes: 1788
import numpy as np

from sys import stdin


def main():
    n, m = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a = np.array(a)

    ans = n - np.sum(a)

    print(-1) if ans < 0 else print(ans)


if __name__ == "__main__":
    main()


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

using namespace std;

#define FOR(i,l,r) for( int i = l; i <= r; i++ )
#define st string

int mod = 1e9+7;

void addMod( int & a, int b ) {
    a += b;
    if( a >= mod ) a -= mod;
}

int main() {
    int n; cin>>n;
    int dp[n+1][n+1];
    FOR(i,0,n) FOR(j,0,n) dp[i][j] = 0;
    st s; 
    cin>>s;
    dp[1][1] = 1;
    FOR(len,2,n) {
        int pref[n];
        memset(pref,0,sizeof(pref));
        FOR(i,1,len-1) {
            addMod(pref[i],dp[len-1][i]);
            addMod(pref[i],pref[i-1]);
        }
        FOR(curr,1,len) {
            int L,R;
            if( s[len-2] == '<' ) {
                L = 1;
                R = curr-1;
            } else {
                L = curr;
                R = len-1;
            }
            if( R >= L ) addMod(dp[len][curr],(pref[R]-pref[L-1]+mod)%mod);
        }
    } 
    int ans = 0;
    FOR(i,1,n) addMod(ans,dp[n][i]);
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 35456
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
typedef long long ll;
const int MOD = 1000000007;
#define PI 3.141592653589
using namespace std;

int main() {
	ll a, b, n;
	cin >> a >> b >> n;
	ll x = min(n, b - 1);
	cout << a * x / b << endl;
	return 0;
}


Measured memory_bytes: 3568
#include <cstdio>

int main()
{
	int grid[3][3], x[3], y[3];
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			scanf("%d", &grid[i][j]);
		}
	}
	for(int i=0; i<3; i++){
		x[i] = grid[i][0] - (grid[i][1] + grid[i][2])/2;
		y[i] = grid[0][i] - (grid[1][i] + grid[2][i])/2;
	}
	bool flag = true;
	if(x[0] != x[1] || x[1] != x[2]){
		flag = false;
	}	
	if(y[0] != y[1] || y[1] != y[2]){
		flag = false;
	}
	if(flag) printf("Yes\n");
	else printf("No\n");

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define INF 1e9L
#define EPS 1e-9
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define pb push_back
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> intint;

int main(void)
{
    int a,b;
    cin >> a >> b;
    if(a % 2 && b % 2) pr("Yes");
    else pr("No");
}

Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

int main()
{
	int n, m = 0;

	cin >> n >> m;
	multimap<int, int> r;
	for (int i = 0; i < m; ++i)
	{
		int a, b = 0;
		cin >> a >> b;
		r.emplace(a, b);
		r.emplace(b, a);
	}

	vector<int> ans(n - 1, 0);
	set<int> target = { 1 };
	set<int> found = { 1 };

	while (!target.empty())
	{
		set<int> next;
		for (auto t : target)
		{
			auto range = r.equal_range(t);
			for (auto it = range.first; it != range.second; ++it)
			{
				if (found.find(it->second) == found.end())
				{
					ans[it->second - 2] = t;
					next.insert(it->second);
					found.insert(it->second);
				}
			}
		}
		target = next;
	}

	if(found.size() != n)
	{
		cout << "No";
		return 0;
	}
	
	cout << "Yes" << endl;

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



Measured memory_bytes: 35960
n,k=map(int,input().split())
res=set()
ans=0
for i in range(k):
    m=int(input())
    s=list(map(int,input().split()))
    for j in range(m):
        res.add(s[j]-1)
for i in range(n):
    if i not in res:
        ans=ans+1
print(ans)

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

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<int> l(n);
    rep(i, n - 1)
    {
        l[i + 1] = gcd(l[i], a[i]);
    }
    vector<int> r(n);
    for (int i = n - 2; i >= 0; i--) {
        r[i] = gcd(r[i + 1], a[i + 1]);
    }

    int ans = 0;
    rep(i, n) {
        ans = max(ans, gcd(l[i], r[i]));
    }

    cout << ans << endl;
}


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

#define int int64_t

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

    int k, n; cin >> k >> n;
    vector<int> v(n);
    for(int i = 0; i<n; ++i){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    int m = 0;
    for(int i = 1; i<n; ++i){
        if(v[i]-v[i-1] > m) m = v[i]-v[i-1];
    }
    if((k - v[n-1]) + v[0] > m) m = (k - v[n-1]) + v[0];
    cout << k-m << "\n";
    
}

Measured memory_bytes: 1792
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Coin struct {
	Num        int
	IsSearched bool
}

func main() {
	s := IOInitialize()
	H := Int(s)
	W := Int(s)
	coinMap := scanNums(s, H, W)
	res := []string{}
	cnt := 0
	for i := 1; i <= H; i++ {
		for j := 1; j <= W; j++ {
			coin := coinMap[j][i]
			if coin.Num%2 == 1 {
				if j < W {
					coin.Num--
					coinMap[j+1][i].Num++
					res = append(res, fmt.Sprintf("%d %d %d %d", i, j, i, j+1))
					cnt++
				} else if i < H {
					coin.Num--
					coinMap[j][i+1].Num++
					res = append(res, fmt.Sprintf("%d %d %d %d", i, j, i+1, j))
					cnt++
				}
			}
		}
	}
	fmt.Println(cnt)
	for _, r := range res {
		fmt.Println(r)
	}

	/*
		cnt := 0
		for i := 1; i <= H; i++ {
			for j := 1; j <= W; j++ {
				coin := coinMap[j][i]
				fmt.Println(coin.Num)
				if coin.Num%2 == 0 {
					cnt++
				}
			}
		}
		fmt.Println("res", cnt)
		if _num%2 == 0 {
			fmt.Println("target", H*W)
		} else {
			fmt.Println("target", H*W-1)
		}
	*/
}

func IOInitialize() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)
	return s
}

func Int(s *bufio.Scanner) int {
	if !s.Scan() {
		panic("scan error")
	}

	value, err := strconv.Atoi(s.Text())
	if err != nil {
		panic("text to int error")
	}
	return value
}

var _num = 0

func scanNums(s *bufio.Scanner, H int, W int) (coinMap map[int]map[int]*Coin) {
	coinMap = map[int]map[int]*Coin{}
	for i := 1; i <= W; i++ {
		coinMap[i] = map[int]*Coin{}
		for j := 1; j <= H; j++ {
			coinMap[i][j] = &Coin{Num: 0, IsSearched: false}
		}
	}

	for i := 1; i <= H; i++ {
		for j := 1; j <= W; j++ {
			num := Int(s)
			_num += num
			coinMap[j][i].Num = num
		}
	}
	return
}


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

int main() {
	int n, k;
	cin >> n >> k;
	int mx = (n - 1) * (n - 2) / 2;
	if (k > mx) {
		puts("-1");
		return 0;
	}
	vector<P> ans;
	rep(i, n - 1) {
		ans.push_back(P(i+1,n));
	}
	int add = mx - k;
	vector<P> Edge;
	rep(a, n - 1) {
		rep(b,a) {
			Edge.push_back(P(a + 1, b + 1));
		}
	}
	rep(i, add) {
		ans.push_back(Edge[i]);
	}
	cout << ans.size() << endl;
	rep(i, ans.size()) {
		cout << ans[i].first << " " << ans[i].second << endl;
	}
}


Measured memory_bytes: 384
#include <stdio.h>

int a,b,c;
int i;
int max=0;
int min=0;
int mid=0;
main(){
scanf("%d%d%d",&a,&b,&c);
int num[] = {a,b,c};
for(i=0; i<3; i++){
  if(max<num[i]){
     min=mid;
     mid=max;
     max= num[i];
     if(mid<min){
     int a = mid;
      mid=min;
      min=a;
     }
   }else{
     if(mid>num[i]){
       min=num[i];
     }else{
       min=mid;
       mid=num[i];
     }
    }
}
printf("%d %d %d\n",min,mid,max);


return 0;
}

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

int main() {

  int a,b,c;
  cin >> a >> b >> c;
  if (a == b && a != c) {
    cout << "Yes" << endl;
    return 0;
  } else if (a == c && b != c) {
    cout << "Yes" << endl;
    return 0;
  } else if (b == c && c != a) {
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;

}


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

int main(){
    string x;
    while(1){
        int sum = 0;
        cin >> x;
        if(x == "0") break;
        for(int i = 0; i < x.length(); ++i){
            sum += x[i] - '0';
        }
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 3136
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

//
const int MAX_N = 51;
int SP[MAX_N][MAX_N];
int DI[MAX_N][MAX_N];

typedef priority_queue <Edge, vector<Edge> > QUEUE;

int main() {
    int s, d;
    while ( cin >> s >> d && s && d ) {
        memset( SP, 0, sizeof(SP) );
        memset( DI, 0, sizeof(DI) );
        for ( int i = 0; i < s; ++ i ) {
            for ( int j = 0; j < d; ++ j ) {
                cin >> SP[i][j];
            }
        }
        for ( int i = 0; i < d - 1; ++ i ) {
            for ( int j = 0; j < d - i - 1; ++ j ) {
                cin >> DI[i][i+j+1];
                DI[i+j+1][i] = DI[i][i+j+1];
            }
        }

        int res = 0;
        QUEUE Q;
        for ( int i = 0; i < s; ++ i ) {
            for ( int j = 0; j < d; ++ j ) {
                if ( SP[i][j] == 0 ) continue;
                Q.push( Edge( i, j + s, SP[i][j] ) );
            }
        }
        for ( int i = 0; i < d; ++ i ) {
            for ( int j = i + 1; j < d; ++ j ) {
                if ( DI[i][j] == 0 ) continue;
                Q.push( Edge( i + s, j + s, DI[i][j] ) );
            }
        }

        UnionFind uf( s + d );
        while ( ! Q.empty() ) {
            Edge e = Q.top();
            Q.pop();

            int a = e.src;
            int b = e.dst;
            if ( uf.findSet( a, b ) ) continue;

            bool f1 = false, f2 = false;
            for ( int i = 0; i < s; ++ i ) {
                if ( uf.findSet( i, a ) ) f1 = true;
                if ( uf.findSet( i, b ) ) f2 = true;
            }

            if ( f1 && f2 ) continue;
            
            int w = e.weight;
            res += w;
            uf.unionSet( a, b );
        }

        cout << res << endl;
    }
    return 0;
}

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

using namespace std ;

#define N  100010

int n , L , m ;
int a[ N ] , to[ N ] ;
int num , block , belong[ N ] ; 
int nxt[ N ] , val[ N ] ;

int find( int x ) {
	int l = x + 1 , r = n , ans = 0 ;
	while( l <= r ) {
		int mid = ( l + r ) >> 1 ;
		if( a[ mid ] - a[ x ] <= L ) l = mid + 1 , ans = mid ;
		else r = mid - 1 ;
	}
	return ans ;
}

int main() {
	scanf( "%d" , &n ) ;
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf( "%d" , &a[ i ] ) ;
	}
	sort( a + 1 , a + n + 1 ) ;
	scanf( "%d%d" , &L , &m ) ;
	for( int i = 1 ; i < n ; i ++ ) {
		to[ i ] = find( i ) ;
	}
	to[ n ] = n + 1 ;
	block = sqrt( n ) ;
	num = n / block ;
	if( n % block ) num ++ ;
	for( int i = 1 ; i <= n ; i ++ ) {
		belong[ i ] = ( i - 1 ) / block + 1 ;
	}
	for( int i = 1 ; i < n ; i ++ ) {
		int t = i , sp = 0 ;
		while( belong[ t ] == belong[ i ] ) {
			t=to[ t ] ;
			sp ++ ;
		}
		val[ i ] = sp ;
		nxt[ i ] = t ;
		if( i >= block * ( num - 1 ) + 1 ) val[ i ] -- , nxt[ i ] -- ;
	}
	for( int i = 1 ; i <= m ; i ++ ) {
		int x , y  , ans = 0 ;
		scanf( "%d%d" , &x ,&y ) ;
		if( x > y )swap( x , y ) ;
		while( belong[ x ] < belong[ y ] ) {
			ans += val[ x ] ;
			x = nxt[ x ] ;
		}
		while( x < y ) {
			x = to[ x ] ;
			ans ++ ;	
		} 
		printf( "%d\n" , ans  ) ;
	}
	return 0 ;
} 

Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(auto (i) = (n)*0; (i) < (n); (i)++)
#define RNG(i, a, b) for(auto (i) = (a); (i) < (b); (i)++)
#define RBF(i, v) for(auto& (i) : (v))
#define ALL(x) (x).begin(), (x).end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }

signed main() {
	int n, k;
	cin >> n >> k;
	V<int> p(n);
	RBF(pi, p) cin >> pi;

	V<double> kitai(n);
	double sum = 0.0, ans = 0.0;
	REP(i, k) {
		kitai[i] = 0.5 * (p[i] + 1);
		sum += kitai[i];
	}
	ans = sum;

	RNG(i, k, n) {
		kitai[i] = 0.5 * (p[i] + 1);
		sum = sum + kitai[i] - kitai[i - k];
		ans = max(ans, sum);
	}

	col(ans);
	return 0;
}


Measured memory_bytes: 5488
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M = map(int,input().split())
uf = UnionFind(N)
for _ in range(M): uf.union(*map(lambda x: int(x)-1, input().split())) # unite
print(uf.group_count()-1)



Measured memory_bytes: 12944
#include<stdio.h>

int main(){
  int a,b,c,d,e;
  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&c);
  scanf("%d",&d);
  if(a<b) e=a;
  else e=b;
  if(c<d) e+=c;
  else e+=d;
  printf("%d\n",e);
}

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

const ll MOD = 1e9 + 7;

ll mypow(ll b, ll n) {
    if (n == 0) return 1;
    if (n == 1) return b % MOD;
    if (n % 2 == 0) {
        return mypow(b * b % MOD, n / 2);
    } else {
        return mypow(b, n - 1) * b % MOD;
    }
}

ll fact(ll n) {
    return n == 0 ? 1 : n * fact(n - 1) % MOD;
}

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

    ll A[N + 1];
    for (ll i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    ll dsum[N + 1];
    dsum[0] = 0;
    for (ll i = 1; i <= N; ++i) {
        dsum[i] = dsum[i - 1] + mypow(i, MOD - 2);
        dsum[i] %= MOD;
    }

    ll ans = 0;
    for (ll i = 1; i <= N; ++i) {
        ans += (dsum[i] + dsum[N - i + 1] - 1) % MOD * A[i] % MOD;
        ans %= MOD;
    }

    cout << ans * fact(N) % MOD << endl;
    return 0;
}


Measured memory_bytes: 3328
import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))

Measured memory_bytes: 26784
X,Y,A,B,C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort(reverse=True)
P = P[:X]
Q.sort(reverse=True)
Q = Q[:Y]
sp = sum(P)
sq = sum(Q)
ans = sp+sq
R.sort(reverse=True)
import heapq  # heapqライブラリのimport
heapq.heapify(P)  # リストを優先度付きキューへ
heapq.heapify(Q)
p = heapq.heappop(P) # 最小値の取り出し
q = heapq.heappop(Q)
r = R.pop(0)
while p<r or q<r:
  #print(p,q,r,ans)
  if r-p > r-q:
    heapq.heappush(P, r)
    ans += r-p
    p = heapq.heappop(P)
  else:
    heapq.heappush(Q, r)
    ans += r-q
    q = heapq.heappop(Q)
  if len(R)==0:
    break
  r = R.pop(0)
  #print(p,q,r,ans)
print(ans)

#print(*ans[1:], sep='\n')

Measured memory_bytes: 22720
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int sort_strings(int N, int L, char String[128][128]) {
//int sort_strings(int N, int L, char **String) {
	int i, j;
	int sorted;
	char *temp;
	char a[128];

	sorted = 0;
	while(sorted < N - 1) {
		sorted = 0;
		for(i = 0; i < N - 1; i += 1) {
			for(j = 0; j < L; j += 1) {
				if(String[i][j] > String[i + 1][j]) {
					//switch
					sprintf(a, "%s", String[i]);
					sprintf(String[i], "%s", String[i + 1]);
					sprintf(String[i + 1], "%s", a);
					break;
				} else if(String[i][j] == String[i + 1][j]) {
					if(j == L - 1) {
						sorted += 1;
					}
					continue;
				} else {
					sorted += 1;
					break;	
				}
			}
		}
	}
	return 0;
}

int main(void) {
	int i;
	int N, L;
	char String[128][128];
	char result[16384];
	char buf[128], *ch;

	fgets(buf, sizeof(buf), stdin);
	ch = strtok(buf, " ");
	N = atoi(ch);
	ch = strtok(NULL, " ");
	L = atoi(ch);

	for(i = 0; i < N; i += 1) {
		String[i][0] = '0';
	}

	for(i = 0; i < N; i += 1) {
		fgets(buf, sizeof(buf), stdin);
		sprintf(String[i], "%s", strtok(buf, " "));
	}
	sort_strings(N, L, String);

	for(i = 0; i < N; i += 1) {
		sprintf(&(result[i * L]), "%s", String[i]);
	}
	printf("%s\n", result);

	return 0;
}


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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

int N;
ld memo[301][301][301];

ld dp(int i, int j, int k) {
  if(memo[i][j][k] >= 0) return memo[i][j][k];
  if((i == 0) && (j == 0) && (k == 0)) {
    memo[i][j][k] = 0;
    return memo[i][j][k];
  }
  memo[i][j][k] = 1 - (ld)(i + j + k) / N;
  if(i >= 1) memo[i][j][k] += (dp(i - 1, j, k) + 1) * i / (ld)N;
  if(j >= 1) memo[i][j][k] += (dp(i + 1, j - 1, k) + 1) * j / (ld)N;
  if(k >= 1) memo[i][j][k] += (dp(i, j + 1, k - 1) + 1) * k / (ld)N;
  memo[i][j][k] /= (ld)(i + j + k) / N;
  return memo[i][j][k];
}

int main(){
  cin >> N;
  vector<int> a(N);
  REP(i,N) cin >> a[i];

  REP(i,301)REP(j,301)REP(k,301) memo[i][j][k] = -1;

  int one = 0, two = 0, three = 0;
  REP(i,N) {
    if(a[i] == 1) ++one;
    else if(a[i] == 2) ++two;
    else ++three;
  }

  cout << fixed << setprecision(10) << dp(one, two, three) << endl;
  return 0;
}



Measured memory_bytes: 426496
//package com.company;
import java.util.Scanner;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Math.*;

public class Main {

    static class FastScanner {
        StringTokenizer tok = new StringTokenizer("");
        BufferedReader in;

        FastScanner()  {
            in = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (!tok.hasMoreElements())
                tok = new StringTokenizer(in.readLine());
            return tok.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }


    }



    public static void main(String[] args) throws IOException {

        FastScanner input = new FastScanner();
        Scanner in = new Scanner(System.in);


        int n ;
        n = input.nextInt();

        if( n >= 30 ){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }

    }

}

Measured memory_bytes: 35612
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>

#define REP(n) for(int i = 0;i < n;i++)
#define LLREP(n) for(long long int  i = 0;i < n;i++)
typedef long long int ll;
using namespace std;
#define MAX_A 1000000

int main(){

    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;
    int dx = tx-sx,dy=ty-sy;

    cout << string(dy,'U') << string(dx,'R');
    cout << string(dy,'D') << string(dx,'L');
    cout << 'L' << string(dy+1,'U') << string(dx+1,'R') << 'D';
    cout << 'R' << string(dy+1,'D') << string(dx+1,'L') << 'U';
    cout << endl;





    return 0;
}

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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define M_PI 3.14159265358979323846

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }



int main()
{
    fast_io();
    #ifdef __LOCAL
        fs::path p = __FILE__;
        fs::path input,output;
        input = output = p.parent_path();
        input += string("/input/") + string(p.stem()) + string(".txt");
        output += string("/output/") + string(p.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    double X,T;
    cin >> T >> X;

    cout << T/X << endl;

    return 0;


}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back

signed main(){
    string s;
    cin>>s;
    
    int dp[19][2][2][1000]={};
    dp[0][0][0][999] = 1;
    rep(i,s.size()){
        rep(j,2){
            rep(k,2){
                rep(l,1000){
                    int D = s[i]-'0';
                    for(int d=0;d<=(j?9:D);d++){
                        dp[i+1][j or d!=D][k or (l/10==51 and d==3)][l%100*10+d] += dp[i][j][k][l];
                    }
                }
                
            }
        }
    }
    
    int ans = 0;
    rep(i,1000){
        ans += dp[s.size()][0][1][i];
        ans += dp[s.size()][1][1][i];
    }
    cout<<ans<<endl;
}



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

using namespace std;

const int maxn = 2e5+10;

typedef long long ll;

ll n, c[maxn], sz[maxn], used[maxn], ans[maxn];

vector<int> grafo[maxn];

void dfs(int u, int p = 0){
    sz[u] = 1;
    for(auto v : grafo[u]){
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

void solve(int u, int p = 0){
    ans[c[u]] += (n - sz[u] - used[c[u]] + 1) * sz[u];

    ll sum = sz[u] - 1;

    for(auto v : grafo[u]){
        if(v == p) continue;
        sum -= sz[v];
        ans[c[u]] += sz[v] * sum;
    }

    ll previous_used = used[c[u]];

    for(auto v : grafo[u]){
        if(v == p) continue;
        used[c[u]] = n - sz[v];
        solve(v, u);
    }

    used[c[u]] = previous_used + sz[u];
}

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

    cin >> n;

    for(int i=1; i<=n; i++) cin >> c[i];

    for(int i=1; i<n; i++){
        int u, v;

        cin >> u >> v;

        grafo[u].push_back(v);
        grafo[v].push_back(u);
    }

    dfs(1);
    solve(1);

    for(int i=1; i<=n; i++) cout << ans[i] << "\n";

    return 0;
}


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

// 各桁の和を計算する関数


int main() {
  int N,K;
  cin >> N>>K;
  vector<int>vec(N);
  for (int i = 0; i < N; ++i) 
    cin>>vec[i];
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  int sum=0;
  for(int i=0;i<K;i++)
    sum+=vec[i];

  cout << sum << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

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

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll N;
  cin >> N;
  vll A(N);
  REP(i, 0, N) {
    cin >> A[i];
  }

  ll ans = 0;
  REP(i, 0, N) {
    ans += A[i] - 1;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
### SNIPPET
  # n = gets.split.map(&:to_i)
  # array = n.times.map { gets.split.map(&:to_i) }
  # [].all?(&:even?)
  # a = [*1..m].repeated_combination(n).to_a
  # [1,2,3,4,5].select { |num| num.even? }  # => [2, 4]
  # ["a","a","b"].group_by(&:itself).map{|k,v| [k, v.count]}.to_h #=> {"a"=>2, "b"=>1}
  # 切り捨て: .floor(2).to_f ,切り上げ： .ceil(2).to_f,四捨五入: round(2)
  # 3.upto(6) do |i|, 6.downto(3) do |i|
  # 公約数125.gcd(100)、公倍数125.lcm(100)
  # PI = Math::PI
  # 高さ = a * Math.sin(w / 180.0 * Math::PI), 底辺 = a * Math.cos(w / 180.0 * Math::PI)
  # def chmax(a, b) a > b ? a : b end
  # INF = Float::INFINITY
  # def chmin(a, b) a < b ? a : b end

x,n = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)


a.sort!
if !a.include?(x)
  puts x
else
  num = 1
  while true
    if a.include?(x-num)
      if a.include?(x+num)
        num += 1
      else
        puts (x+num)
        break
      end
    elsif !a.include?(x-num)
      puts (x-num)
      break
    else
      puts (x+num)
      break
    end
  end
end

# 6 5
# 4 7 10 6 5




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

bitset <200010> ans, tmp;
int a[200010], b[200010];
int z[600010], s[600010];
int val[200010];
int n;

void get_z() {
	int L = 0, R = 0;
	for (int i = 1; i < 3 * n; i++) {
		if (i > R) {
			L = R = i;
			while (R < 3 * n && s[R - L] == s[R]) R++;
			z[i] = R - L, R--;
			continue;
		}
		if (i + z[i - L] - 1 < R) {
			z[i] = z[i - L];
			continue;
		}
		L = i;
		while (R < 3 * n && s[R - L] == s[R]) R++;
		z[i] = R - L, R--;
	}
}

void solve(int k) {
	for (int i = 0; i < n; i++) {
		s[i] = a[i] >> k & 1;
	}
	for (int i = n; i < n * 3; i++) {
		s[i] = b[i % n] >> k & 1;
	}
	get_z(), tmp.reset();
	for (int i = n; i < n + n; i++) {
		if (z[i] >= n) tmp.set(i - n, 1);
	}
	for (int i = n; i < n * 3; i++) {
		s[i] ^= 1;
	}
	get_z();
	for (int i = n; i < n + n; i++) {
		if (z[i] >= n) tmp.set(i - n, 1), val[i - n] |= 1 << k;
	}
	ans &= tmp;
}

int main () {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &b[i]);
	}
	for (int i = 0; i < n; i++) {
		ans.set(i);
	}
	for (int i = 0; i < 30; i++) {
		solve(i);
	}
	if (ans[0]) printf("%d %d\n", 0, val[0]);
	for (int i = n - 1; i >= 1; i--) {
		if (ans[i]) {
			printf("%d %d\n", (n - i) % n, val[i]);
		}
	}
	return 0;
}


Measured memory_bytes: 10496
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second

ll A, B;

const ll M = (1ll<<60);

ll left(ll x){
	while(x < M) x *= 2;
	return x-M;
}

ll right(ll x){
	while(x < M) x = 2*x+1;
	return x-M;
}

ll len(ll x){ return right(x)-left(x)+1; }

ll first_bit(ll x){
	for(int i=62; 1<=i; --i) if(1&(x>>i)) return i;
	return 0;
}

ll lca_diff(ll x, ll y){
	ll sh = left(x)+M;
	while(true){
		ll X=first_bit(x);
		ll Y=first_bit(y);
		if(X > Y) x/=2; else if(X < Y) y/=2; else break;
	}
	while(x!=y) x/=2, y/=2;
	int ans=0;
	while(sh != x) sh/=2, ++ans;
	return 1LL << (ans-1);
}

int main()
{
	cin >> A >> B;
	deque<ll> yl, yr;
	{
		ll l=M+A, r=M+B;
		while(l<=r){
			if(l%2==1) yl.pb(l++);
			if(r%2==0) yr.pb(r--);
			l/=2; r/=2;
		}
	}
	while(yr.size() > 1u){
		yr[1] /= 2;
		yr.pop_front();
	}
	if(yl.empty()){
		cout << len(yr[0]) << endl;
		return 0;
	}
	if(yr.empty()){
		ll ans = 0;
		for(ll x : yl) ans += len(x);
		cout << ans << endl;
		return 0;
	}
	ll df = lca_diff(yl.back(), yr[0]);
	ll sL = left(yl[0]) + df;
	ll sR = right(yl.back()) + df;
	ll ans = sR-sL+1;
	auto f = [&](ll l, ll r, ll el, ll er){
		if(el <= l && r <= er) return 0LL;
		if(r < el || er < l) return r-l+1LL;
		if(l <= el) return max(0LL, el-l);
		return max(0LL, r-er);
	};
	for(ll x : yl) ans += f(left(x), right(x), sL, sR);
	for(ll x : yr) ans += f(left(x), right(x), sL, sR);
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define per(i,a,b) for(int i=(b),i##_end=(a);i>=i##_end;--i)
#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;++i)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define Es(x,i) for(Edge *i=G[x];i;i=i->nxt)
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > 
#ifdef flukehn
#define debug(...) fprintf(stderr, __VA_ARGS__);
#else
#define debug(...)
#endif
typedef double db;
typedef long long L;
typedef long double lf;
typedef unsigned int uint;
typedef unsigned long long uL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mo=998244353;
template<typename T>inline void admo(int&a,const T&b){a=(a+b>=mo?a+b-mo:a+b);}
template<typename T>inline void sumo(int&a,const T&b){a=(a-b<0?a-b+mo:a-b);}
template<typename T,typename S>inline bool upmx(T&a,const S&b){return a<b?a=b,1:0;}
template<typename T,typename S>inline bool upmn(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T>inline T gcd(T a,T b){while(b)a%=b,swap(a,b);return a;}
inline int Pow(int a,int b,int p=mo){int r=1;for(;b;b>>=1,a=1ll*a*a%p)if(b&1)r=1ll*r*a%p;return r;}
const int N=2e5+11;
int main()
{
	int a,b,c;L k;
	cin>>a>>b>>c;
	cin>>k;
	if(k&1LL)
		cout<<b-a;
	else cout<<a-b;

}

Measured memory_bytes: 256