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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/03/03  Problem: code-festival-2017-final_c / Link: https://cf17-final.contest.atcoder.jp/tasks/cf17_final_c?lang=en  ----- */
/* ------問題------

XXXX年のCODE FESTIVALには、世界中から高橋君を含めて N+1 人の参加者が集まりました。
高橋君の都市と他の N 人の都市の時刻の差を調べてみたところ、i 番目の人の都市との時刻の差は Di 時間でした。 ただし 2 つの都市について、片方の都市で 0 時の瞬間にもう一方の都市で d 時であるようなとき、これらの都市の時刻の差は min(d,24−d) であるものとします。 ここで、時刻の表記には 24 時間表記を用いるものとします。 つまり、例えば高橋君の都市で 0 時の瞬間には i 番目の人の都市は Di 時または 24−Di 時のいずれかとなります。
高橋君は次に、N+1 人のうちの全ての 2 人組についてその人の都市どうしの時刻の差を書き出し、それらの時刻の差のうちの最小値を s としました。
s として考えられる最大値を求めて下さい。

-----問題ここまで----- */
/* -----解説等-----

時間について愚直にシュミレション？
3人以上同じ時間にあるときはans = 0
2人のときはバラバラに分け、1人のときは両方試すのが良い
2^24ぐらい

----解説ここまで---- */

LL N;

LL ans = 0LL;

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

	cin >> N;
	VI a(N);
	VI cnt(13, 0);

	FOR(i, 0, N) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	cnt[0]++;
	FOR(i, 0, 13) {
		if (cnt[i] > 2) {
			cout << 0 << endl;
			return 0;
		}
	}

	if (cnt[0] > 1 || cnt[12] > 1) {
		cout << 0 << endl;
		return 0;
	}
	VI base(24, false);
	base[0] = true;
	if (cnt[12] == 1) {
		base[12] = true;
	}
	FOR(i, 0, 13) {
		if (cnt[i] == 2) {
			base[i] = base[24 - i] = true;
		}
	}
	ans = 0;
	FOR(i, 0, (1 << 11)) {
		VI used(48,0);
		FOR(i, 0, 24) {
			used[i] = base[i];
		}
		FOR(j, 0, 11) {
			if (cnt[j + 1] != 1) continue;
			if ((i >> j) & 1) {
				used[j + 1] = true;
			}
			else {
				used[24 - (j + 1)] = true;
			}
		}
		FOR(j, 0, 24) used[j + 24] = used[j];
		int l = 0;
		int tans = INF;
		FOR(r, 1, 48) {// 2周
			if (used[r]) {
				int t = min(r - l, 24 - (r - l));
				tans = min(tans, t);
				l = r;
			}
		}
		ans = max(ans, (LL)tans);
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
global A

def max_heapfy(i):
    left = 2*i+1
    right = 2*i+2

    max_val = 0
    if left< H and A[i] < A[left]:
        max_val = left
    else:
        max_val = i

    if right<H and A[max_val] < A[right]:
        max_val = right

    if max_val != i:
        temp = A[i]
        A[i] = A[max_val]
        A[max_val] = temp
        max_heapfy(max_val)

if __name__ == '__main__':
    global H
    H = int(input())
    A = [int(i) for i in input().split()]
    for i in reversed(range(H//2)):
        max_heapfy(i)

    for a in A:
        print(" {}".format(a),end='')
    print('')

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

int main() {
	string s; cin>>s;
	string t; cin>>t;
	//sort(s.begin(), s.end());
	int ans=0;
	//sort(t.begin(), t.end());
	for(int i=0; i<s.size(); i++){
		if(s[i]!=t[i]) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3860
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main(){
  int R[MAX], n;

  cin>>n;
  for(int i = 0; i < n; i++){
    cin >>R[i];
  }
  int maxv = -2000000000;
  int minv = R[0];

  for (int i =1; i < n; i++){
    maxv = max(maxv, R[i] -minv);
    minv = min(minv, R[i]);
  }
  cout << maxv <<endl;

  return 0;
}

Measured memory_bytes: 3860
package main

import "fmt"

func main() {
	// Code for B - Stone Monument
	var a, b int
	fmt.Scanf("%d %d", &a, &b)

	var sum int = 0
	var A int = 0
	for i := 1; i <= 1000; i++ {
		sum += i
		if sum-A == b-a {
			fmt.Println(sum - b)
			break
		} else {
			A = sum
		}
	}

}


Measured memory_bytes: 1832
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>P;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll cmp(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;
    cin>>n;
    double x;
    for(int i=1;i<50000;i++){
        int a=i*1.08;
        if(a==n){
            cout<<i<<endl;
            return 0;
        }
    }
        cout<<":("<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


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

const int MAX_N = 200005;

vector<int> vec[MAX_N];

int N, M, mx[MAX_N << 2], tag[MAX_N << 2];

void build(int x, int l, int r) {
  if (l == r) {
    mx[x] = -M + l - 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}

void push_down(int x) {
  if (tag[x]) {
    mx[x << 1] += tag[x], tag[x << 1] += tag[x];
    mx[x << 1 | 1] += tag[x], tag[x << 1 | 1] += tag[x];
    tag[x] = 0;
  }
}

void update(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    mx[x]++, tag[x]++;
    return;
  }
  push_down(x);
  int mid = (l + r) >> 1;
  if (mid >= L) update(x << 1, l, mid, L, R);
  if (mid < R) update(x << 1 | 1, mid + 1, r, L, R);
  mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}

int query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R)
    return mx[x];
  push_down(x);
  int mid = (l + r) >> 1, res = -100000000;
  if (mid >= L) res = query(x << 1, l, mid, L, R);
  if (mid < R) res = max(res, query(x << 1 | 1, mid + 1, r, L, R));
  return res;
}

int main() {
  scanf("%d%d", &N, &M);
  
  for (int i = 1, L, R; i <= N; ++i) {
    scanf("%d%d", &L, &R);
    vec[L].push_back(R);
  }

  build(1, 1, M + 1);
  
  int res = N - M;

  for (int i = 0; i <= M - 1; ++i) {
    for (int x : vec[i]) 
      update(1, 1, M + 1, 1, x);

    res = max(res, query(1, 1, M + 1, i + 2, M + 1) - i);
  }
  
  printf("%d\n", res);
  return 0;
}


Measured memory_bytes: 14720
from collections import deque
h,w = map(int, input().split())

m = [list(input()) for _ in range(h)]

start_points = [(y,x) for y in range(h) for x in range(w) if m[y][x] == '#']

def bfs(start_points):
    que = deque(start_points)
    step = 0
    count_flag = False
    while len(que):
        for _ in range(len(que)):
            y,x = que.popleft()
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + dy
                nx = x + dx
                if not (0<=ny<h and 0<=nx<w) or m[ny][nx] != '.':
                    continue
                m[ny][nx] = '#'
                count_flag = True
                que.append((ny,nx))

        if count_flag:
            step += 1
            count_flag = False
        else:
            break
    return step

print(bfs(start_points))

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

std::pair<int, int> calc(int h, int H){
	int a = 2 * (H / h);
	int b = 2 * h * (H / h) + 1 - a;
	return {a, b};
}

int main(){
    int H, W, h, w;
	scanf("%d%d%d%d", &H, &W, &h, &w);
	if(!(H % h) && !(W % w)) return printf("No\n"), 0;
	
	printf("Yes\n");
	if(H % h){
		std::pair<int, int> p = calc(h, H);
		for(int i = 1; i <= H; ++ i){
			for(int j = 1; j <= W; ++ j){
				printf("%d%c", i % h ? p.first : - p.second, " \n"[j == W]);
			}
		}
	}
	else{
		std::pair<int, int> p = calc(w, W);
		for(int i = 1; i <= H; ++ i){
			for(int j = 1; j <= W; ++ j){
				printf("%d%c", j % w ? p.first : - p.second, " \n"[j == W]);
			}
		}
	}
	return 0;
}

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

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

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

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

signed main() {
	ll a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  b *= 5, c *= 10, d *= 50, e *= 100, f *= 500;
  if(a + b + c + d + e + f >= 1000) cout << 1 << endl;
  else cout << 0 << endl;
	return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
#include<vector>
using namespace std;
  vector<vector<bool>>c(3,vector<bool>(3));
int main() {
  vector<vector<int>> a(3,vector<int>(3));
  for(int i=0;i<3;i++){
      for(int o=0;o<3;o++){
         cin>>a.at(i).at(o);
      }
  }
  int n,b;
  cin>>n;
    for(int i=0;i<n;i++){
    cin>>b;
      for(int i=0;i<3;i++){
      for(int o=0;o<3;o++){
         if(a.at(i).at(o)==b){
           c.at(i).at(o)=true;
         }
      }
  }
  }
  for(int i=0;i<3;i++){
  if(c.at(i).at(0)&c.at(i).at(1)&c.at(i).at(2)){
    cout<<"Yes";
    return 0;
  }
    if(c.at(0).at(i)&c.at(1).at(i)&c.at(2).at(i)){
      cout<<"Yes";
      return 0;
    }
  }
  if(c.at(0).at(0)&c.at(1).at(1)&c.at(2).at(2)){
    cout<<"Yes";
    return 0;
  }
  if(c.at(2).at(0)&c.at(1).at(1)&c.at(0).at(2)){
    cout<<"Yes";
    return 0;
  }
  cout<<"No";
}

Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    l = [0] * N
    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if H[a] == H[b]:
            l[a] = 1
            l[b] = 1
        elif H[a] > H[b]:
            l[b] = 1
        else:
            l[a] = 1
    return l.count(0)
print(main())


Measured memory_bytes: 86336
#include<stdio.h>
double MIN(double a,double b){return a<b?a:b;}
int main(){
  int n,m,i,j,k,a,b,e[610],c[610][610]={};
  double s,min=1e9,d[1010]={};
  scanf("%d %d",&n,&m);
  for(i=0;i<=n;i++)d[i]=1e9;
  d[n]=0;
  for(i=0;i<=n;i++)e[i]=-1;
  while(m--){
    scanf("%d %d",&i,&j);
    c[i][j]=1;
  }
  for(i=n-1;i;i--){
      s=b=a=0;
      for(j=i;j<=n;j++){
	if(c[i][j]){
	  s+=d[j]+1;
	  if(b==0||d[b]<d[j])b=j;
	  a++;
	}
      }
      d[i]=s/a;
      if(a>1)e[i]=b;
      //printf("%lf ",d[i][k]);
  }//printf("\n");
  min=d[1];
  for(k=1;k<=n;k++){//printf("%d\n",e[k]);
    if(e[k]==-1)continue;
    for(j=0;j<n;j++)d[j]=1e9;
    d[n]=0;
    for(i=n-1;i;i--){
      s=a=0;
      for(j=i;j<=n;j++){
	if(c[i][j]==0||(i==k&&j==e[k]))continue;
	s+=d[j]+1;
	a++;
      }
      d[i]=s/a;
      //for(j=1;j<=n;j++)printf("%d:%lf ",j,d[j]);printf("\n");
    }//printf("\n");
    if(min>d[1])min=d[1];
  }
  printf("%.10lf\n",min);
  return 0;
}


Measured memory_bytes: 1664
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define ff first
#define ss second
vector<pair<int,int>> v;
signed main(){
    int h, n, x = 0;
    cin >> h >> n >> n;
    v.resize(n);
    for(auto& i: v)
        cin >> i.ss >> i.ff;
    sort(v.begin(),v.end());
    for(auto p: v){
        if(p.ss > p.ff+x)h = min(h, p.ss-1);
        if(p.ss == p.ff+x)x++;
    }
    cout << h << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int num[100009];
bool is[100009];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)num[i] = 1;
    is[0] = 1;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        x--;y--;
        if(is[x])is[y] = 1;
        num[x]--;
        num[y]++;
        if(num[x]==0)is[x]=0;
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        if(num[i]>0&&is[i])ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 768
#include <stdio.h>
int main(void){
    int i,n,x;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        x=i;
        if(x%3==0){
            printf(" %d",i);
        }
        else{
            while(x){
                if(x%10==3){
                    printf(" %d",i);
                    break;
                }
                x=x/10;
            }
        }
    }
    printf("\n");
    return 0;
}


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

int main(){
  int n, t;
  cin >> n >> t;
  vector<int> nums(t, 0);
  for(int i = 0; i < n; ++i){
    int l, r;
    cin >> l >> r;
    ++nums[l]; --nums[r];
  }
  int sum = 0, max = 0;
  for(auto num : nums){
    sum += num;
    if(max < sum)
      max = sum;
  }
  cout << max << endl;
  return 0;
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LI list<int>
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ff first
#define ss second
#define bg begin()
#define sf(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define sff(a,b) scanf("%d%d",&a,&b);
#define sfffl(a,b) scanf("%lld%lld",&a,&b);
#define nwln() printf("\n");
#define prd(a) printf("%d",a);
#define prld(a) printf("%lld",a);
#define space printf(" ");
#define ft cout<<"for test"<<endl;
#define read(v) for(auto &it:v)cin>>it;
#define PI 2*acos(0.0)
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main()
{
    FIO;
    int n,i,j;
    cin>>n;
    vi v(n),a(n),b(n);
    read(v);
    for(i=0; i<n; i++)
    {
        a[i] = i+v[i];
        b[i] = i-v[i];
    }
    ll ans=0;
    sort(all(a));
    sort(all(b));
    for(i=0; i<n; i++)
    {
        auto l = lower_bound(all(a),b[i]);
        auto r = upper_bound(all(a),b[i]);
        ///cout<<l-a.bg<<' '<<r-a.bg<<endl;
        ans+=(r-l);
    }
    cout<<ans<<endl;
}


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

#define pb push_back
#define fi first
#define se second
#define ll long long
#define pq priority_queue
#define mp make_pair
#define pii pair<int,int>
#define mod 998244353

int lowbit(int x) {return x&(-x);}

int n;
int a[19][19];
ll score[(1<<16)+10];
ll f[(1<<16)+10];

int main(){
	memset(f,-1,sizeof(f));
	scanf("%d",&n);
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++) scanf("%d",&a[i][j]);
	for (int i=0;i<(1<<n);i++) {
		vector <int> tmp;
		int t=i,cnt=0;
		while (t) {
			if (t&1) tmp.pb(cnt);
			cnt++;
			t>>=1;
		}
		for (int j=0;j<tmp.size();j++)
			for (int k=j+1;k<tmp.size();k++) 
				score[i]+=(ll)a[tmp[j]][tmp[k]];
		f[i]=score[i];
	}
	for (int i=0;i<(1<<n);i++) 
		for (int j=i;j;j=i&(j-1)) f[i]=max(f[i],f[j]+score[i^j]);
	cout<<f[(1<<n)-1];
	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
const double pi=3.14159265358979323846;
int main()
{
	double a,b,h,m,anm,anh,ans;
	cin>>a>>b>>h>>m;
	anm=360*m/60;
	anh=360*h/12;
	ans=anm-anh-anm/12;
	if(ans<0)
		ans+=360;
//	deg=360*h/12-360*m/60/12;
	cout<<fixed<<setprecision(10)<<sqrt(a*a+b*b-2*a*b*cos(ans/180*pi));
	return 0;
}

Measured memory_bytes: 4228
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<complex>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)

int main() {
    int n; cin >> n;
    vector<vector<int> > to(n), cost(n);
    rep(i, n - 1) {
        int a, b, w; cin >> a >> b >> w;
        a--; b--;
        to[a].push_back(b);
        cost[a].push_back(w);
        to[b].push_back(a);
        cost[b].push_back(w);
    }
    vector<int> ans(n, -1);
    queue<int> q;
    ans[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        rep(i, to[v].size()) { //3以上もありうる
            int u = to[v][i];
            int w = cost[v][i];
            if (ans[u] != -1) continue;
            ans[u] = (ans[v] + w) % 2;
            q.push(u);
        }
    }
    rep(i, n) cout << ans[i] << endl;
}


Measured memory_bytes: 11904
from itertools import combinations_with_replacement as cwr

n, m, q  = map(int, input().split())
scores = [[int(j) for j in input().split()] for _ in range(q)]

combs = cwr(range(1, m+1), n)
ans = 0
for comb in combs:
  cand = 0
  for a, b, c, d in scores:
    if comb[b-1] - comb[a-1] == c:
      cand += d
  ans = max(ans, cand)
print(ans)

Measured memory_bytes: 9096
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<sstream>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define inf 0x7FFFFFFF
#define waru 1000000007
////////////////////////////////////////////////////////////

int main(){
	long n;
	cin >> n;
	
	long ans = 0;
	
	long long s[n+1] = {};
	map<long long , int > mp;
	mp[0]++;
	rep(i,0,n){
		long a;
		cin >> a;
		s[i+1] = s[i] + a;
		mp[s[i+1]]++;
		ans += mp[s[i+1]]-1;
	}
	

	P(ans);
	ret 0;

}

Measured memory_bytes: 14336
// #include<iostream>
// #include<vector>
// #include<algorithm>
// #include<map>
// #include<cstring>
// #include<math.h>
// #include<bitset>
// #include<queue>
// #include<set>
// #include<iomanip>
// #include<math.h>
// #include<assert.h>
// #include<string>
// #include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// ----------------------------------------------------------------------------
  int main(){
    int N;
    cin >> N;
    set<string> se;
    string S;
    cin >> S;
    bool can = true;
    se.insert(S);
    for(int i=1; i<N; i++){
      string temp;
      cin >> temp;
      if(se.count(temp)){
        can = false;
      }
      if(S[S.size()-1] != temp[0]){
        can = false;
      }
      se.insert(temp);
      S = temp;
    }
    if(can){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  return 0;
}


Measured memory_bytes: 256
X,Y=map(str,input().split())

if X=='A':
    X==1
elif X=='B':
    X==2
elif X=='C':
    X==3
elif X=='D':
    X==4
else :
    X==5

if Y=='A':
    Y==1
elif Y=='B':
    Y==2
elif Y=='C':
    Y==3
elif Y=='D':
    Y==4
else :
    Y==5

if X>Y:
    print('>')
elif X==Y:
    print('=')
else :
    print('<')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
     
int main(){
    int N;
    cin >> N;
    int a;
    a=50;
    for(int i=0;i<N;i++){
        int b;
        cin>>b;
        for(int j=0;j<100;j++){
            if(b%2==1){
                if(a>j){
                    a=j;
                }
                break;
            }
            else {
                b/=2;
            }
        }
    }
    cout << a <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,k;
	cin>>n>>k;
	ll a[n+5];
	for(ll i=1;i<=n;i++)
		cin>>a[i];

	ll p[n+5];
	memset(p,0,sizeof(p));
	p[1] = 1;
	ll i = 1;
	ll cnt = 1;
	ll s;
	vector<ll> q;
	while(cnt<n)
	{
		ll k1 = i;
		i = a[i];
		if (p[i]>0)
		{
			s = i;
			while(i!=k1)
			{
				q.push_back(i);
				i = a[i];
			}
			q.push_back(k1);
			break;
		}
		else
		{
			p[i] = ++cnt;
		}
	}
	
	if (k<=p[s])
	{
		i = 1;
		while(k>0)
		{
			i = a[i];
			k--;
		}
		cout<<i;
	}
	else
	{
		k-=p[s]-1;

		ll sz = q.size();
		cout<<q[k%sz];
	}

}

Measured memory_bytes: 8316
n,q = map(int,input().split())
s = input()
li = [0 for _ in range(n+1)]

for i in range(1,n):
    li[i+1] = li[i] + s[i-1:i+1].count("AC")

for i in range(q):
    l,r = map(int,input().split())
    print(li[r]-li[l])


Measured memory_bytes: 7724
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
const int INF = 1 << 29;
const ll LINF = 1l << 61;
const ld PI = abs(acos(-1));
#define pq priotity_queue
#define pb push_back
#define mp make_pair
#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define cbuf(buf, init) memset(buf, init, sizeof(buf))

template <class T>
constexpr T modp(T x, T y)
{
    return (y + x % y) % y;
}
template <class T>
constexpr T sq(T x)
{
    return x * x;
}
template <class T>
constexpr double divd(T x, T y)
{
    static_cast<double>(x) / static_cast<double>(y);
}

template <class T>
T nextInput()
{
    T t;
    cin >> t;
    return t;
}

#define netint nextInput<ll>()
#define netstr nextInput<string>()

template <class T>
void print(T&& t)
{
    cout << forward<T&&>(t) << endl;
}

void print(double t) { cout << fixed << setprecision(14) << t << endl; }

//

int main()
{
    //
    ll N = netint;
    std::string S[200000];
    map<char, ll> m;
    rep(i, 0, N)
    {
        S[i] = netstr;
        m[S[i][0]]++;
    }

    std::string MARCH = "MARCH";
    ll ans = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = i + 1; j < 5; j++) {
            for (int k = j + 1; k < 5; k++) {
                ans += (m[MARCH[i]] * m[MARCH[j]] * m[MARCH[k]]);
            }
        }
    }

    print(ans);
}


Measured memory_bytes: 6912
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int n,tmp,H;
bool flag;
vector<int> x(100),y(100),h(100);

int check(int nx,int ny)
{
  flag=true;
  H=h.at(tmp)+abs(nx-x.at(tmp))+abs(ny-y.at(tmp));

  rep(k,n)
  {
    if(max(H-abs(nx-x.at(k))-abs(ny-y.at(k)),0)!=h.at(k))
    {
      flag=false;
      break;
    }
    else continue;
  }

  if(flag) return H;
  else return 0;
}

int main()
{
  cin>>n;
  rep(i,n)
  {
    cin>>x.at(i)>>y.at(i)>>h.at(i);
    if(h.at(i)>0) tmp=i;
  }

  rep(nx,101)
  rep(ny,101)
  {
    if(check(nx,ny))
    {
      cout<<nx<<" "<<ny<<" "<<H<<endl;
      break;
    }
  }
}

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

# define F first
# define S second
# define mp make_pair
# define pii pair<int,int>

# define long long long
# define pb push_back
# define sz(a) (int)(a.size())

# define y1     tipa_y1
# define left   tipa_left
# define right  tipa_right

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const long MXLL = 4611686018427387903;
const int Sz = 1110111;

using namespace std;

inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0);
}
long n;

inline int f (long a) {
  int res = 0;
  while (a) {
    res ++;
    a /= 10;
  }
  return res;
}

inline int f (long a, long b) {
  return max (f(a), f(b));
}

int main()
{
  Read_rap ();
  cin >> n;

  int mn = MX;    
  for (long i = 1;i * i <= n;i ++) {
    if (n % i == 0)
      mn = min (mn, f(i, n / i));
  }
  cout << mn;

  return 0;
}









// Coded by Z...


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <cmath>
#include <utility> // pair make_pair
#include <algorithm>
#include <iomanip>

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define ll long long
//#define int ll

using namespace std;
using Graph = vector<vector<int> >;


int main() {
  int N; cin >> N;
  set<int> Mochi;
  for (int i = 0; i < N; i++) {
    int d;
    cin >> d;
    Mochi.insert(d);
  }

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


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define scanf(a, b) (fflush(0), scanf(a,b))
int main(void) {
	int N;
	char S[100];
	int total1 = 0, total2 = 0, i;

	scanf("%d", &N);
	scanf("%s", S);

	if (N % 2 == 0){
		for (i = 0; i < (N / 2); i++){
			total1 += S[i];
			total2 += S[i + (N / 2)];
		}
		if (total1 == total2){
			printf("Yes");
		} else {
			printf("No");
		}
	} else {
		printf("No");
	}
	return EXIT_SUCCESS;
}

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16>>(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF = 1e9;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

int main()
{
    int N; cin >> N;
    vector<int> A(N);
    vector<int> num(100);
    bool ok = true;

    int dist = 0;
    rep(i, N) {
        cin >> A[i];
        num[A[i]]++;
        dist = max(dist, A[i]);
    }

    if (dist%2 == 0) {
        for (int i=dist; i>dist/2; i--) {
            num[i] -= 2;
        }
        num[dist/2] -= 1;
    } else {
        for (int i=dist; i>=(dist+1)/2; i--) {
            num[i] -= 2;
        }
    }

    rep(i, 100) {
        if (i > (dist+1)/2 && num[i] < 0) {
            ok = false;
        } else if (i <= (dist+1)/2 && num[i] > 0) {
            ok = false;
        }
    }

    cout << (ok ? "Possible" : "Impossible") << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<ctype.h>
int main(void){
   char s;
   int a[26];
   int i;

   for(i=0;i<26;i++){
      a[i] = 0;
   }

   while((s=getchar())!=EOF){
      s=tolower(s);
      a[s-'a'] += 1;
   }
   for(i=0;i<26;i++){
      s = 'a'+i;
      printf("%c : %d\n",s,a[i]);
   }
   return 0;
}

Measured memory_bytes: 524
import java.io.*
import java.util.*

fun solve(ABCD: String){
    // A op1 B op2 C op3 D = 7 (op = + or -)
    val (A, B, C, D) = ABCD.map{ it - '0' }
    val ops = listOf(1, -1)
    val opsShow = "+-"
    for (i in 0..1){
        for(j in 0..1){
            for (k in 0..1){
                if (A + B*ops[i] + C*ops[j]+D*ops[k] == 7){
                    println("$A${opsShow[i]}$B${opsShow[j]}$C${opsShow[k]}$D=7")
                    return
                }
            }
        }
    }
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val ABCD = sc.next()
    solve(ABCD)
}



Measured memory_bytes: 34048
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
#include <random>
#include <stack>
#include <iomanip>

using namespace std;
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; }

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
typedef long double ldouble;

typedef vector<llong> vecllong;
typedef vector<vecllong> vvecllong;

const llong MOD = 1e9 + 7;
const llong INF = 1e17;

#define FOR(i, n) for (llong i = 0; i < n; i++)
#define FORS(i, a, b) for (llong i = a; i < b; i++)
#define FORR(i, n) for (llong i = n; i > 0; i++)

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

    llong N, K;
    cin >> N >> K;

    vecllong take(N);

    FOR(i, N) {
        cin >> take[i];
    }

    bool dp[K + 1] = {false};  // dp[count] = 先手必勝

    FORS(i, 1, K + 1) {
        FOR(j, N) {
            if(i - take[j] >= 0) {
                dp[i] |= !dp[i - take[j]];
            }
        }
    }

    if(dp[K]) {
        cout << "First" << endl;
    } else {
        cout << "Second" << endl;
    }

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i=0, d1, d2; i<n; i++) {
        cin >> d1 >> d2;
        if (d1 == d2) {
            cnt++;
        } else {
            cnt = 0;
        }
        if (cnt == 3) {
            cout << "Yes" << '\n';
            return 0;
        }
    }
    cout << "No" << '\n';
    return 0;
}

Measured memory_bytes: 3628
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
x = []
y = []
for i in range(n):
    xx,yy = inm()
    x.append(xx)
    y.append(yy)
dif = [x[i]-y[i] for i in range(n)]
sum = [x[i]+y[i] for i in range(n)]
print(max(max(dif)-min(dif),max(sum)-min(sum)))


Measured memory_bytes: 123720
#include<bits/stdc++.h>
#define ll long long int 
#define fori(i,n) for(int i=0; i<n; ++i)
#define ford(i,n) for(int i=n-1; i>=0; --i)
#define vi vector<int> 
#define vs vector<string>
#define vll vector<ll>
#define di deque<int>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define pqi priority_queue<int>
#define pqll priority_queue<ll>
#define mod1 1000000007
#define mod2 998244353
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gcd __gcd


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

using namespace std;
using namespace std::chrono;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> i_set;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ll_set; 
/* new_data_set p; */
/* *p.find_by_order(3); The value at third place */
/* p.order_of_key(7); The expected index in the set in sorted order */

ll modexp(ll a, ll b, ll m){
    ll res=1;
    a%=m;
    while(b>0){
        if(b&1) res=(res*a)%m;
        b>>=1;
        a=(a*a)%m;
    }
    return res;
}

ll mod_inv(ll a,ll m){
    return modexp(a,m-2,m);
}

ll ncr(ll n, ll r, ll m){
    ll min1=min(r,n-r);
    ll res=1,s1=n,s2=1;
    for(ll i=0; i<min1; ++i){
        res=(res*s1)%m;
        res=(res*mod_inv(s2,m))%m;
        s1--;
        s2++;
    }
    return res;
}

int main(int argc, char const *argv[]){
	fast_cin();
    ll n,a,b;
    cin>>n>>a>>b;
    cout<<(modexp(2,n,mod1)+2*mod1-ncr(n,a,mod1)-ncr(n,b,mod1)-1)%mod1<<"\n";
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
#define N 1000102
const int p=998244353;
int n,m,f[N],finv[N],inv[N];
inline int C(int nn,int mm)
{
    if(nn<mm)return 0;
    return 1ll*f[nn]*finv[mm]%p*finv[nn-mm]%p;
}
inline int ksm(int d,int k){int ret=1;while(k){if(k&1)ret=1ll*ret*d%p;d=1ll*d*d%p;k>>=1;}return ret;}
int main()
{
    f[0]=finv[0]=f[1]=finv[1]=inv[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        inv[i]=1ll*(p-p/i)*inv[p%i]%p;
        f[i]=1ll*f[i-1]*i%p;finv[i]=1ll*finv[i-1]*inv[i]%p;
    }
    scanf("%d%d",&n,&m);if(n>m)swap(n,m);
    int ans=0;
    for(int i=0;i<=n;i++)
    {
        int te=1ll*C(n,i)*C(m,i)%p*f[i]%p*ksm(m+1,n-i)%p*ksm(n+1,m-i)%p;
        if(i&1)ans=(ans-te+p)%p;
        else ans=(ans+te)%p;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 15468
#include <iostream>

using namespace std;

int main() {
  int x;
  cin >> x;
  int ans = 0;
  for (int b = 0; b <= 100; b++) {
    for (int c = 0; c <= 50; c++) {
      for (int d = 0; d <= 34; d++) {
        for (int e = 0; e <= 25; e++) {
          for (int f = 0; f <= 20; f++) {
            int rem = x - 101 * b - 102 * c - 103 * d - 104 * e - 105 * f;
            if (rem >= 0 && rem % 100 == 0) {
              ans = 1;
              break;
            }
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define Lens 2000010
#define range 10005

using namespace std;
int N;
int A[Lens], B[range], ans[Lens];

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

	for (int i = 0; i < N; i++)
	{
		B[A[i]]++;
	}
	for (int i = 1; i < range; i++)
	{
		B[i] += B[i - 1];
	}
	for (int i = 0; i < N; i++)
	{
		ans[B[A[i]]] = A[i];
		B[A[i]]--;
	}
	for (int i = 1; i <= N; i++)
	{
		if (i > 1) cout << ' ';
		cout << ans[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 18728
fn manhattan(p: (i32, i32), q: (i32, i32)) -> i32 {
    (p.0 - q.0).abs() + (p.1 - q.1).abs()
}

fn main() {
    let inputs = {
        use std::str::FromStr;
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let n = buf.trim().parse().unwrap();
        (0..n)
            .map(|_| {
                buf.clear();
                std::io::stdin().read_line(&mut buf).unwrap();
                let row = buf
                    .trim()
                    .split(' ')
                    .map(i32::from_str)
                    .collect::<Result<Vec<_>, _>>()
                    .unwrap();
                ((row[0], row[1]), row[2])
            })
            .collect::<Vec<_>>()
    };
    let &(xy0, h0) = inputs.iter().find(|&&(_, h)| h != 0).unwrap();
    for cx in 0..101 {
        for cy in 0..101 {
            let center = (cx, cy);
            let height = manhattan(center, xy0) + h0;
            let height_at = |xy| std::cmp::max(height - manhattan(center, xy), 0);
            if inputs.iter().all(|&(xy, h)| height_at(xy) == h) {
                println!("{} {} {}", cx, cy, height);
                return;
            }
        }
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define pii pair<int, int>
ld const pi = 3.141592653589793238462;
int const mod = 1e9+7;

int power(int a,int b){
    int f=1;
    while(b>0){
        if(b&1){
            f=f*a;
        }
        a=a*a;
        b=b/2;
    }
    return f;
}

int32_t main(){
    IOS;
    int a,p,i,j,l;
    cin>>a>>p;
    a = 3*a + p;
    cout<<a/2<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(ll i=0;i<N;++i)
typedef long long int ll;
typedef long double ld;
const ll INF = 1<<30;

int main(){
    ll H,W; cin >> H >> W;
    ll S = H*W;
    ll ans = INF;
    //SmaxとSminの横幅についての全探索をswap前後2回行う
    rep(w,W){
        ll S1 = H*w;
        //全体の長方形からS1を除いた長方形を２つに分ける方法を縦横でやる
        ll x1 = floor(((ld)(S - S1) / 2.0) / H);
        ll x2 = ceil(((ld)(S - S1) / 2.0) / H);
        ll S2 = H*x1, S3 = H*x2;
        ll Smax = max(max(S1,S2),S3), Smin = (min(min(S1,S2),S3));
        ans = min(ans , Smax-Smin);

        ll y1 = floor(((ld)(S - S1) / 2.0) / (W-w));
        ll y2 = ceil(((ld)(S - S1) / 2.0) / (W-w));
        S2 = (W-w)*y1, S3 = (W-w)*y2;
        Smax = max(max(S1,S2),S3), Smin = (min(min(S1,S2),S3));
        ans = min(ans , Smax-Smin);
    }
    swap(H,W);
    rep(w,W){
        ll S1 = H*w;
        //全体の長方形からS1を除いた長方形を２つに分ける方法を縦横でやる
        ll x1 = floor(((ld)(S - S1) / 2.0) / H);
        ll x2 = ceil(((ld)(S - S1) / 2.0) / H);
        ll S2 = H*x1, S3 = H*x2;
        ll Smax = max(max(S1,S2),S3), Smin = (min(min(S1,S2),S3));
        ans = min(ans , Smax-Smin);

        ll y1 = floor(((ld)(S - S1) / 2.0) / (W-w));
        ll y2 = ceil(((ld)(S - S1) / 2.0) / (W-w));
        S2 = (W-w)*y1, S3 = (W-w)*y2;
        Smax = max(max(S1,S2),S3), Smin = (min(min(S1,S2),S3));
        ans = min(ans , Smax-Smin);
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
unittest
{
	assert( [ "10", "1 2 5 3 4 6 7 3 2 4", "1 2", "2 3", "3 4", "4 5", "3 6", "6 7", "1 8", "8 9", "9 10" ].parse.expand.solve == "1\n2\n3\n3\n4\n4\n5\n2\n2\n3" );
	
	assert( [ "9", "1 2 3 1 2 3 1 2 3", "1 2", "2 3", "3 4", "4 5", "5 6", "6 7", "7 8", "8 9" ].parse.expand.solve == "1\n2\n3\n3\n3\n3\n3\n3\n3" );		// 追加ケース
	assert( [ "9", "10 20 30 40 50 1 2 3 4", "1 2", "2 3", "3 4", "4 5", "6 2", "6 7", "7 8", "8 9" ].parse.expand.solve == "1\n2\n3\n4\n5\n2\n2\n3\n4" );		// 追加ケース
}



import std.container;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	auto uvs = new long[ 2 ][ n - 1 ];
	foreach( ref uv; uvs )
	{
		input.popFront;
		uv = input.front.split.to!( long[] );
		uv[] -= 1;
	}
	return tuple( as, uvs );
}

auto solve( long[] as, long[ 2 ][] uvs )
{
	// dfs + lis する
	auto anss = new long[ as.length ];
	
	auto l = 0L;
	auto dp = new long[ as.length ];
	dp[] = long.max;
	auto dp_s = dp.assumeSorted;
	
	auto nss = toAdjacencyList!true( as.length, uvs );
	auto stack_f = SList!( long )( 0L );					// 進む用スタック
	auto stack_b = SList!( Tuple!( long, long ) )();		// 戻る用スタック
	while( !stack_f.empty )
	{
		auto f = stack_f.front;
		stack_f.removeFront;
		
		if( 0 <= f )
		{
			// 葉に向かって進む
			auto i = dp_s.lowerBound( as[ f ] ).length.signed;
			stack_b.insertFront( tuple( i, dp_s[ i ] ) );
			dp_s[ i ] = as[ f ];
			if( l <= i ) l = i + 1;
			anss[ f ] = l;
			
			stack_f.insertFront( -1L );		// 戻るタイミングを入れておく
			foreach( t; nss[ f ] )
			{
				if( anss[ t ] == 0 ) stack_f.insertFront( t );
			}
		}
		else
		{
			// 根に向かって戻る
			auto i = stack_b.front[ 0 ];
			auto a = stack_b.front[ 1 ];
			stack_b.removeFront;
			
			dp[ i ] = a;
			if( a == long.max ) l = i;
		}
	}
	return anss.to!( string[] ).join( "\n" );
}

// 辺配列から隣接リストを作成
auto toAdjacencyList( bool undirected = false )( long n, long[ 2 ][] es )
{
	auto nss = new long[][ n ];
	foreach( e; es )
	{
		nss[ e[ 0 ] ] ~= e[ 1 ];
		static if( undirected ) nss[ e[ 1 ] ] ~= e[ 0 ];
	}
	return nss;
}


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

int main(void) {
 
    long long int N,K;
    cin >> N >> K;
  
  	long long int lli = N / K;
    
    cout << min(abs(N - K * lli),abs(N - K * (lli+1))) << endl;
 
    return 0;
}


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

#define pi pair<int, int>

using namespace std;
 
// achar número de vértices na maior componente conexa
void solve() {
    int n, m;
    cin >> n >> m;

    set<pi> edges;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;

        if (edges.find(make_pair(u, v)) != edges.end()) {
            continue;
        }

        edges.insert(make_pair(u, v));
        edges.insert(make_pair(v, u));

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

    vector<bool> vis(n, false);
    function<int(int)> dfs = [&] (int s) {
        vis[s] = true;

        int count = 1;
        for (auto &v : adj[s]) {
            if (!vis[v]) {
                count += dfs(v);
            }
        }

        return count;
    };

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            ans = max(ans, dfs(i));
        }
    }

    cout << ans << endl;
}

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

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t = 1;
    // cin >> t;

    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 45424
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
for _ in range(n):
    s = input().rstrip()
    minima = 0
    fin = 0
    for ch in s:
        if ch == ")":
            fin -= 1
            if fin < minima:
                minima = fin
        else:
            fin += 1
    if fin >= 0:
        increasing.append((minima, fin))
    else:
        decreasing.append((minima - fin, fin))

increasing.sort(reverse=True)
decreasing.sort()

current = 0
for minima, diff in increasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in decreasing:
    if current + minima + diff < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

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

const int N=3010;
typedef long long ll;
int mod,n,jc[N],jc2[N],inv[N],pww[N],pw[N*N],dp[N][N],ans;
int ksm(ll a,int b,int c=1){
	for(;b;b/=2,a=a*a%mod)
		if(b&1)c=c*a%mod;
	return c;
}
void init(){
	jc[0]=jc2[0]=pww[0]=1;
	for(int i=1;i<=n;++i){
		jc[i]=(ll)jc[i-1]*i%mod;
		inv[i]=ksm(i,mod-2);
		jc2[i]=(ll)jc2[i-1]*inv[i]%mod;
		pww[i]=pww[i-1]*2%(mod-1);
	}
	pw[0]=1;
	for(int i=1;i<=n*n;++i)pw[i]=pw[i-1]*2%mod;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>mod;init();
	for(int j=0;j<=n;++j)dp[0][j]=jc2[j];
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;++j)
			dp[i][j]=((ll)(dp[i][j-1]+dp[i-1][j-1])*i+dp[i][j-1])%mod*inv[j]%mod;
	for(int i=0;i<=n;++i){
		int sum=0;
		for(int j=0;j<=i;++j)
			sum=(sum+(ll)dp[j][i]*pw[j*(n-i)]%mod*jc2[j])%mod;
		sum=ksm(2,pww[n-i],sum);sum=(ll)sum*jc[n]%mod*jc2[n-i]%mod;
		if(i&1)ans=(ans-sum+mod)%mod;
		else ans=(ans+sum)%mod;		
	}
	cout<<ans<<'\n';
	return 0;
}


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

using namespace std;

using int64 = long long;
//const int mod = 1e9 + 7;
const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  int K;
  cin >> K;
  while(K--) {
    cout << "ACL";
  }
  cout << "\n";
}

Measured memory_bytes: 3652
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var a, b int
	var aStr,bStr string
	fmt.Scan(&a, &b)
	for i:= 0 ; i < b ; i++ {
		aStr += strconv.Itoa(a)
	}
	for i:= 0 ; i < a ; i++ {
		bStr += strconv.Itoa(b)
	}

	if aStr < bStr{
		fmt.Println(aStr)
	} else {
		fmt.Println(bStr)
	}

}



Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  vector<int> v(n+1,0);
  for(int i=0;i<k;i++)
  {
    int d;
    cin>>d;
    while(d--)
    {
      int a;
      cin>>a;
      v[a]=1;
    }
  }
  int ans=0;
  for(int i=1;i<=n;i++)
  {
    if(v[i]==0)
      ans++;
  }
  cout<<ans;
  return 0;
}

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

vector<long long> f(int k){
  vector<long long> v(k, 0);
  v[k - 1] = pow(2, k - 1);
  for(int i = k - 2; i >= 0; i--){
    v[i] = v[i + 1] - pow(10,k-2-i) * pow(2,i+1) + 11 * pow(10,k-2-i) * pow(2,i);
  }
  return v;
}

int main(){
  long long n;
  cin >> n;
  string s = to_string(n);
  long long sum = 0;
  vector<long long> v1(s.size(), 0);
  v1 = f(s.size());
  for(int i = 0; i < s.size(); i++){
    for(int j = 0; j < 10; j++){
      if(s[i] == j + 48){sum += j * v1[i];}
    }
  }
  cout << sum << endl;

}       

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
int a[200005];
bool compare(int a,int b){
	return a>b;
}
int main(){
	ios::sync_with_stdio(0);
	int n,k,x;
	cin>>n>>k;
	memset(a,0,sizeof(a));
	for(int i=0;i<n;i++){
		cin>>x;
		a[x]++;
	}
	int ans=0;
	sort(a,a+n,compare);
	for(int i=k;i<=n;i++){
		ans+=a[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024