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

using namespace std;
using P = pair<long, long>;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))

#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define concat(xs, ys) (xs).insert((xs).end(), (ys).begin(), (ys).end())

const int mod = 1000000007;

int cnts[100005];

struct mint {
    ll x;
    mint(ll x=0):x(x%mod){}

    mint& operator+=(const mint a) {
        if((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint& operator-=(const mint a) {
        if (x < a.x) {
          x += mod;
        }
        x -= a.x;
        return *this;
    }

    mint& operator*=(const mint a) {
        x = (x * a.x) % mod;
        return *this;
    }

    mint& operator/=(const mint a) {
        *this *= a.inv();
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }

    mint pow(ll n) const {
        mint a(*this);
        mint res = 1;
        while (n > 0) {
            if (n & 1) res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }

    mint inv() const {
        return pow(mod - 2);
    }
};

const int MAX_V = 100005;

mint fac[MAX_V];
mint inv[MAX_V]; 

void initFact() {
  fac[0] = 1;
  inv[0] = 1;
  for (int i = 1; i <= MAX_V; i++) {
    fac[i] = (fac[i - 1] * i);
    inv[i] = fac[i].inv();
  }
}

mint combi(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * inv[k] * inv[n - k];
}

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

  int n;
  cin >> n;

  vector<long> a(n+1);
  int tgt = -1; 
  rep(i, n+1) {
    cin >> a[i];
    cnts[a[i]]++;
    if (cnts[a[i]] >= 2) {
      tgt = a[i];
    }
  }

  int x = 0;
  int z = 0;
  int i = 0;
  while(a[i] != tgt) {
    i++;
  }
  x = i;
  i++;
  while(a[i] != tgt) {
    i++;
  }
  z = n-i;

  initFact();
  if (n == 1) {
    cout << 1 << endl;
    cout << 1 << endl;
  } else {
    rep(i, n+1) {
      mint res = 0;
      int k = i+1;
      if (k >= 2) {
        res += combi(n-1, k);
        res += combi(n-1, k-2);
        res += combi(n-1, k-1);
        res += combi(n-1, k-1);
        res -= combi(x+z, k-1);
      } else {
        res = n;
      }
      cout << res.x << endl;
    }
  }
}


Measured memory_bytes: 3968
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>
#include <new>
#include <typeinfo>

typedef  long long ll;
#define mop 1000000007
#define mop2 998244353

using namespace std;

int main() {
	
	ll n, k;
	cin >> n >> k;
	vector <ll> v;
	ll tmp = 0;
	for (ll i = 0; i <= n; i++) {
		tmp += i;
		v.push_back(tmp);
	}
	ll ans = 0;
	for (ll i = k; i <= n; i++) {
		ll minv = v[i - 1];
		ll maxv = v[n] - v[n - i];
		ans += maxv - minv + 1;
		ans %= mop;
	}
	ans++;
	ans %= mop;
	cout << ans << endl;
	
}

Measured memory_bytes: 5368
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,k;
ll ans=1;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		if(i==1)
			ans*=k;
		else
			ans*=k-1;
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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; }

int main() {
  int n;
  cin >> n;
  deque<int> deq;
  rep(i, n) {
    int a;
    cin >> a;
    deq.push_back(a);
  }
  sort(deq.begin(), deq.end());
  vector<ll> high, low;
  bool b = 0;
  while (!deq.empty()) {
    if (b) {
      high.push_back(deq.back());
      deq.pop_back();
    } else {
      low.push_back(deq.front());
      deq.pop_front();
    }
    b ^= 1;
  }
  ll ans = 0;
  if (n%2) {
    rep(i, high.size())
      ans += high[i]*2;
    ans += low.back()+low[low.size()-2];
    rep(i, low.size())
      ans -= low[i]*2;
    high.push_back(low.back());
    low.pop_back();
    ll tmp = 0;
    rep(i, low.size())
      tmp -= low[i]*2;
    tmp -= high.back()+high[high.size()-2];
    rep(i, high.size())
      tmp += high[i]*2;
    chmax(ans, tmp);
  } else {
    rep(i, high.size()-1)
      ans += high[i]*2;
    ans += high.back()+low.back();
    rep(i, low.size())
      ans -= low[i]*2;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, qq;
  cin >> n >> qq;
  string a;
  cin >> a;
  vector<int> pref(n);
  pref[1] = (a[1] == 'C' && a[0] == 'A');
  for (int i = 2; i < n; i++) {
    pref[i] = pref[i - 1] + (a[i] == 'C' && a[i - 1] == 'A');
  }
  while (qq--) {
    int l, r;
    cin >> l >> r;
    l--; r--;
    cout << pref[r] - pref[l] << '\n';
  }
  return 0;
}

Measured memory_bytes: 1488
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define reps(i,s,n) for(ll (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define reptr(i,n) for(ll (i)=(n);(i)>=0;--(i))
#define All(x) (x).begin(),(x).end()
using namespace std;

int main() {
  ll A,B,Q;
  cin >> A >> B >> Q;
  vector<ll> s(A),t(B);
  rep(i,A){
    cin >> s[i];
  }
  rep(i,B){
    cin >> t[i];
  }
  rep(i,Q){
    vector<ll> ss,tt;
    ll x;
    cin >> x;
    ll ans=LLONG_MAX;
    //神社
    /*
    ll j=0;
    while(s[j]<=x&&j<A){
      j++;
    }
    */
    auto itrS=lower_bound(All(s),x);
    if(itrS-s.begin()>=1) ss.push_back(s[itrS-s.begin()-1]);
    //if(itrS-s.begin()>=2) ss.push_back(s[itrS-s.begin()-2]);
    if(itrS-s.begin()<A) ss.push_back(s[itrS-s.begin()]);
    //if(itrS-s.begin()<A-1) ss.push_back(s[itrS-s.begin()+1]);
    //寺
    /*
    ll k=0;
    while(t[k]<=x&&k<B){
      k++;
    }
    */
    auto itrT=lower_bound(All(t),x);
    if(itrT-t.begin()>=1) tt.push_back(t[itrT-t.begin()-1]);
    //if(itrT-t.begin()>=2) tt.push_back(t[itrT-t.begin()-2]);
    if(itrT-t.begin()<B) tt.push_back(t[itrT-t.begin()]);
    //if(itrT-t.begin()<B-1) tt.push_back(t[itrT-t.begin()+1]);

    for(ll tmpS=0;tmpS<ss.size();tmpS++){
      ll tmpAns=llabs(ss[tmpS]-x);
      for(ll tmpT=0;tmpT<tt.size();tmpT++){
        tmpAns+=llabs(ss[tmpS]-tt[tmpT]);
        if(ans>tmpAns) ans=tmpAns;
        tmpAns-=llabs(ss[tmpS]-tt[tmpT]);
      }
    }
    for(ll tmpT=0;tmpT<tt.size();tmpT++){
      ll tmpAns=llabs(tt[tmpT]-x);
      for(ll tmpS=0;tmpS<ss.size();tmpS++){
        tmpAns+=llabs(ss[tmpS]-tt[tmpT]);
        if(ans>tmpAns) ans=tmpAns;
        tmpAns-=llabs(ss[tmpS]-tt[tmpT]);
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 2944
#include<iostream>
#include<algorithm>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(),(x).end()

using ll = long long;

using namespace std;

template<typename T>
void dump(T *arr, int h, int w){
	rep(i,h){
		rep(j,w) cout << arr[i][j] << "\t";
		cout << "\n";
	}
}

template<typename T>
void dump(T *arr, int a){
	rep(i,a) cout << arr[i] << "\t";
	cout << "\n";
}

const int INF = 1e9;
const int MOD = 1e9+7;

ll dp[100000][13];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	int a[n+1], b[n];
	rep(i,n+1) cin >> a[i];
	rep(i,n) cin >> b[i];

	ll ans=0;
	int tmp;
	tmp = min(a[0],b[0]);
	b[0] -= tmp;
	ans += tmp;
	tmp = min(a[n],b[n-1]);
	b[n-1] -= tmp;
	ans += tmp;
	repi(i,1,n){
		tmp = min(a[i],b[i-1]);
		a[i] -= tmp;
		b[i-1] -= tmp;
		ans += tmp;
		tmp = min(a[i],b[i]);
		a[i] -= tmp;
		b[i] -= tmp;
		ans += tmp;
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
ll n,i,c=0;
string s[200005];
int main()
{
	scanf("%lld",&n);
	for (i=1;i<=n;++i) cin>>s[i];
	sort(s+1,s+1+n);
	for (i=1;i<=n;++i) if(s[i]!=s[i-1]) ++c;
	printf("%lld",c);
}

Measured memory_bytes: 10080
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

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

    for (int i = 0; i < S.length(); i++)
    {
        if (S.at(i) + N > 90)
        {
            S.at(i) = (S.at(i) + N) - 26;
        }
        else
        {
            S.at(i) += N;
        }
    }
    
    for (int i = 0; i < S.length(); i++)
    {
        cout << S.at(i);
    }
    cout << endl;
}


Measured memory_bytes: 256
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

int main() {
  int n,r;
  while(cin>>n>>r){
    if(n==0 && r==0) return 0;
    
    vector<pair<int,int>> A(n);
    rep(i,n) A[i]={i,n-i};
    
    int p,c;
    rep(i,r){
      cin>>p>>c;
      for(int j=p-1;j<p+c-1;j++){
        A[j].first=j-p+1;
      }
      for(int j=0;j<p-1;j++){
        A[j].first=c+j;
      }
      sort(ALL(A));
    }
    cout<<A[0].second<<endl;
  }
  
  return 0;
}


Measured memory_bytes: 3024
N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])

Measured memory_bytes: 47196
/* imports all std modules {{{*/
import
  std.algorithm,
  std.array,
  std.ascii,
  std.base64,
  std.bigint,
  std.bitmanip,
  std.compiler,
  std.complex,
  std.concurrency,
  std.container,
  std.conv,
  std.csv,
  std.datetime,
  std.demangle,
  std.encoding,
  std.exception,
  std.file,
  std.format,
  std.functional,
  std.getopt,
  std.json,
  std.math,
  std.mathspecial,
  std.meta,
  std.mmfile,
  std.net.curl,
  std.net.isemail,
  std.numeric,
  std.parallelism,
  std.path,
  std.process,
  std.random,
  std.range,
  std.regex,
  std.signals,
  std.socket,
  std.stdint,
  std.stdio,
  std.string,
  std.system,
  std.traits,
  std.typecons,
  std.uni,
  std.uri,
  std.utf,
  std.uuid,
  std.variant,
  std.zip,
  std.zlib;
/*}}}*/

/+---test
5
1 3 5 4 2
---+/

/+---test
9
9 6 3 2 5 8 7 4 1
---+/

void main(string[] args) {
  readln;
  const P = readln.split.map!(to!long).array;

  long ans;
  foreach (i; 1..P.length-1) {
    if (min(P[i-1], P[i+1]) < P[i] && P[i] < max(P[i-1], P[i+1])) ++ans;
  }
  ans.writeln;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include<list>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e9
typedef long long ll;
using namespace std;

struct student{
    int club;
    bool seen;
    vector<int> withHim;
};

void tell(student* p,int t){
    p[t].seen = true;
    rep(i, p[t].withHim.size()){
        if(!p[p[t].withHim[i]].seen){
            p[p[t].withHim[i]].club = p[t].club;
            tell(p, p[t].withHim[i]);
        }
    }
}

void initialize(student* p,int t){
    p[t].seen = false;
    rep(i, p[t].withHim.size()){
        if(p[p[t].withHim[i]].seen){
            initialize(p, p[t].withHim[i]);
        }
    }
}

int main() {
    int n, m ,k;
    cin >> n >> m >> k;
    student* students;
    students = new student[n];
    rep(i, n){
        students[i].club = 0;
    }

    rep(i, k){
        int flag, a, b;
        cin >> flag >> a >> b;
        if(flag == 1){
            if(students[a-1].club == 0){
                if(students[b-1].club != 0){
                    students[a-1].club = students[b-1].club;
                    tell(students, a-1);
                    initialize(students,a-1);
                }
                students[a-1].withHim.push_back(b-1);
                students[b-1].withHim.push_back(a-1);
            }else{
                if(students[b-1].club == 0){
                    students[b-1].club = students[a-1].club;
                    tell(students, b-1);
                    initialize(students, b-1);
                    students[a-1].withHim.push_back(b-1);
                    students[b-1].withHim.push_back(a-1);
                }else{
                    if(students[a-1].club != students[b-1].club){
                        cout << i+1 << "\n";
                        return 0;
                    }
                }
            }
        }else{
            if(students[a-1].club == 0){
                students[a-1].club = b;
                tell(students, a-1);
                initialize(students, a-1);
            }else{
                if(students[a-1].club != b){
                    cout << i+1 << "\n";
                    return 0;
                }
            }
        }
    }

    cout << 0 << "\n";

    return 0;
}


Measured memory_bytes: 9740
//File: abc174d.cpp
//Author: yanyanlongxia
//Date: 2020/8/3
//
#include <bits/stdc++.h>

using namespace std;
int n,cnt,ans;
string s;
int main() {
    scanf("%d",&n);
    cin>>s;
    for(int i=0;i<n;i++)
        if(s[i]=='W')
            cnt++;
    for(int i=n-cnt;i<n;i++)
        if(s[i]!='W')
            ans++;
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 3920
#include<bits/stdc++.h>
# define ll long long
# define mo 1000000009
# define maxi 100005
using namespace std;
int main()
{
	deque<char> s;
    string y;
    cin>>y;
    for(int i=0;i<y.size();i++)
    s.push_back(y[i]);
    int n,cnt=0;
    cin>>n;
    while(n--)
    {
    	int x;
    	cin>>x;
    	if(x==1){
    	cnt++;}
    	else
    	{
    		int f;char c;
    		cin>>f>>c;
    		if(f==1){
    		if(cnt%2==0)
    		s.push_front(c);
			else
			s.push_back(c);}
    		else{
    		if(cnt%2==0)
    		s.push_back(c);
    		else
    		s.push_front(c);}
		}
	}
		
	if(cnt%2==1)
	reverse(s.begin(),s.end());
	for(int i=0;i<s.size();i++)
	cout<<s[i];
	return 0;
}

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

int main() {
  vector<int> vec(5);
  for (int i = 0; i < 5; i++) cin >> vec.at(i);

  int A = 10;

  for (int i = 0; i < 5; i++) {
    if (vec.at(i) % 10 != 0) A = min(A, vec.at(i) % 10);
  }

  int ans = 0;

  for (int i = 0; i < 5; i++) {
    if (vec.at(i) % 10 == 0) ans += vec.at(i);
    else {
      int X = vec.at(i) / 10 * 10 + 10;
      ans += X;
    }
  }

  if (A == 10) cout << ans << endl;
  else cout << ans - (10 - A) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  for(string s;cin>>s;) {
    int const sz=s.size();
    int joi=0;
    {
      vector<int> jpos;
      for(int i=0;i<sz;i++) {
	if(s[i]=='J')jpos.push_back(i);
      }
      for(int i=0;i<jpos.size();i++){
	if((jpos[i]+2<sz)&&(s[jpos[i]+1]=='O')&&(s[jpos[i]+2]=='I'))joi++;
      }
    }
    int ioi=0;
    {
      vector<int> ipos;
      for(int i=0;i<sz;i++) {
	if(s[i]=='I')ipos.push_back(i);
      }
      for(int i=0;i<ipos.size();i++){
	if((ipos[i]+2<sz)&&(s[ipos[i]+1]=='O')&&(s[ipos[i]+2]=='I'))ioi++;
      }
    }
    cout <<joi<<endl<<ioi<<endl;
  }
  return 0;
}

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

int main(){
  int n;
  int a,b;
  cin >> n;
  cin >> a >> b;
  for(int i=a; i<=b; i++){
    if(i % n == 0){
      cout << "OK\n";
      return 0;;
    }
  }
  cout << "NG\n";
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,x;
  cin>>N;
  x=0;
  vector<int> vec(N);
  for(int b=0;b<N;b++){
    cin>>vec.at(b);
  }
  sort(vec.begin(),vec.end());
  for(int i=0;i<N-2;i++){
    int a=vec.at(i);
    for(int j=i+1;j<N-1;j++){
      int b=vec.at(j);
      for(int k=j+1;k<N;k++){
        int c=vec.at(k);
        if(c<a+b){
          x++;
        }
       
      }
    }
  }
  cout<<x<<endl;
}
        

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

signed main() {
  int H, W, K; 
  cin >> H >> W >> K;

  vector<string> s(H);
  REP(i, H) cin >> s[i];

  int sx, sy;
  REP(i, H) REP(j, W){
    if(s[i][j] == 'S'){
      sx = i;
      sy = j;
    }
  }

  queue<pair<int, int>> q;
  q.push({sx, sy});

  vector<vector<int>> dist(H, vector<int>(W, INF));
  dist[sx][sy] = 0;

  int MIN = INF;
  while(!q.empty()){
    int x = q.front().first;
    int y = q.front().second; q.pop();
    chmin(MIN, min(min(x, H-x-1), min(y, W-y-1)));
    if(dist[x][y] > K) break;

    REP(i, 4){
      int xx = x+dx[i];
      int yy = y+dy[i];
      if(OUT(0, xx, H)) continue;
      if(OUT(0, yy, W)) continue;
      if(s[xx][yy] == '#') continue;
      if(dist[xx][yy] > dist[x][y]+1){
        dist[xx][yy] = dist[x][y]+1;
        q.push({xx, yy});
      }
    }
  }

  cout << 1+(MIN+K-1)/K << "\n";

  return 0;
}

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

using namespace std;
using ll = long long;

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

  int n;
  cin >> n;
  vector<int> v(n);
  map<int, int> m;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    m[v[i]]++;
  }

  vector<bool> dp(1e6 + 1, true);

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

  int ans = 0;
  for (auto a : v) {
    if (dp[a]) {
      if (m[a] == 1) {
        ans++;
      }
      for (int x = a; x < 1e6 + 1; x += a) {
        dp[x] = false;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 13656
#pragma region

#include "bits/stdc++.h"
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define _rep3(i, begin, end) for (register int i = (begin), i##_end = (end); i < i##_end; i++)
#define _irep3(i, begin, end) for (register int i = (end)-1, i##_begin = (begin); i >= i##_begin; i--)
#define _rep2(i, n) _rep3(i, 0, n)
#define _irep2(i, n) _irep3(i, 0, n)
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__, _rep3, _rep2, )(__VA_ARGS__)
#define irep(...) _overload3(__VA_ARGS__, _irep3, _irep2, )(__VA_ARGS__)
#define out(x) cout << (x) << '\n';
#define debug(x) cerr << #x << " = " << (x) << " (line: " << __LINE__ << ") " << endl;

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[ ";
  rep(i, vec.size()) i == 0 ? os << vec[i] : os << ", " << vec[i];
  os << " ]";
  return os;
}

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

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

void init() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10) << boolalpha;
}

#pragma endregion

#define MOD 1000000007
#define INF 2147483647

main() {
  init();

  string s, t;
  cin >> s >> t;

  int S = s.length(), T = t.length();

  vector<vector<pair<int, pair<int, int>>>> dp(S + 1, vector<pair<int, pair<int, int>>>(T + 1, make_pair(0, make_pair(0, 0))));

  rep(y, T) {
    rep(x, S) {
      int x_ = dp[x][y + 1].first;
      int y_ = dp[x + 1][y].first;
      int xy_ = dp[x][y].first + (s[x] == t[y]);
      if (x_ > y_ && x > xy_) {
        dp[x + 1][y + 1] = make_pair(x_, make_pair(x, y + 1));
      } else if (y_ > xy_) {
        dp[x + 1][y + 1] = make_pair(y_, make_pair(x + 1, y));
      } else {
        dp[x + 1][y + 1] = make_pair(xy_, make_pair(x, y));
      }
    }
  }

  int step = dp[S][T].first;
  string ans = "";
  int x = S, y = T;
  while (step) {
    pair<int, pair<int, int>> prev = dp[dp[x][y].second.first][dp[x][y].second.second];
    if (prev.first != step) {
      ans += s[x - 1];
      step--;
    }
    int _x = dp[x][y].second.first;
    y = dp[x][y].second.second;
    x = _x;
  }

  irep(i, ans.length()) {
    cout << ans[i];
  }
  cout << "\n";
}


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

ans = 0
for _ in range(n):
    Ai=list(map(int,input().split()))
    tmp=0
    for i in range(m):
        tmp += Ai[i]*B[i]
    tmp+=c
    if tmp > 0:
        ans+=1

print(ans)

Measured memory_bytes: 3060
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

int main() {
	ll n, a;
	ll count[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
	ll cou = 0;
	ll ans1 = 0;
	ll ans2 = 0;

	cin >> n;

	REP(i, n) {
		cin >> a;

		if (a >= 1 && a <= 399) {
			if (count[0] != 1) {
				count[0] = 1;
			}
		}
		else if (a >= 400 && a <= 799) {
			if (count[1] != 1) {
				count[1] = 1;
			}
		}
		else if (a >= 800 && a <= 1199) {
			if (count[2] != 1) {
				count[2] = 1;
			}
		}
		else if (a >= 1200 && a <= 1599) {
			if (count[3] != 1) {
				count[3] = 1;
			}
		}
		else if (a >= 1600 && a <= 1999) {
			if (count[4] != 1) {
				count[4] = 1;
			}
		}
		else if (a >= 2000 && a <= 2399) {
			if (count[5] != 1) {
				count[5] = 1;
			}
		}
		else if (a >= 2400 && a <= 2799) {
			if (count[6] != 1) {
				count[6] = 1;
			}
		}
		else if (a >= 2800 && a <= 3199) {
			if (count[7] != 1) {
				count[7] = 1;
			}
		}
		else {
			cou++;
		}
	}

	REP(i, 8) {
		ans1 += count[i];
		ans2 += count[i];
	}

	if (ans1 == 0) {
		ans1 = 1;
	}

	ans2 += cou;

	cout << ans1 << " " << ans2 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200006
#define LL long long int
LL k;
int n,piroid,nxt[MAXN];
int vis[MAXN];
int town[MAXN];
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&nxt[i]);
    }
    town[0]=1;
    int cur=1,step=0;
    memset(vis,-1,sizeof vis);
    while(1)
    {
       
        
        vis[cur]=step;
        town[step++]=cur;
        cur=nxt[cur];
        if(step==k)
        {
            printf("%d\n",cur);
            return 0;
        }
        if(vis[cur]!=-1)
        {
            piroid=step-vis[cur];
            break;
        }
    }
    k=vis[cur]+(k-vis[cur])%piroid;
    printf("%d\n",town[k]);
    return 0;
}

Measured memory_bytes: 5892
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;

namespace disco20201
{
    class Program
    {
        static void Main(string[] args)
        {
            //Console.SetIn(new StreamReader("input.txt"));
            solve_disco20201A();
        }

        public static void solve_disco20201B()
        {

        }

        public static void solve_disco20201A()
        {
            int[] xy = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int x = xy[0];
            int y = xy[1];

            int total = 0;
            if (x == 1)
            {
                total = 300000;
            }
            else if (x == 2)
            {
                total = 200000;
            }
            else if (x == 3)
            {
                total = 100000;
            }
            if (y == 1)
            {
                total += 300000;
            }
            else if (y == 2)
            {
                total += 200000;
            }
            else if (y == 3)
            {
                total += 100000;
            }

            if (x == 1 && y == 1)
            {
                total += 400000;
            }

            Console.WriteLine(total);
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
#define m_p make_pair
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ll n;
    ll ans=0;
    cin >> n;
    vll v(n),w(n);
    rep(i,n) cin >> v[i];
    rep(i,n) cin >> w[i];
    rep(i,n) if(v[i] - w[i] > 0) ans += v[i] - w[i];
    cout << ans << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	ll n, h;
	cin >> n >> h;
	ll maxa = 0;
	priority_queue<ll> bs;
	for (int i=0; i<n; i++) {
		ll a, b;
		cin >> a >> b;
		if (a > maxa) maxa = a;
		bs.push(b);
	}
	ll ret = 0;
	while (!bs.empty()) {
		if (bs.top() < maxa) {
			bs.pop();
			continue;
		}
		h -= bs.top();
		bs.pop();
		ret++;
		if (h <= 0) {
			cout << ret << endl;
			return 0;
		}
	}
	cout << ret + (h + maxa - 1)/maxa << endl;
	
	return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	int N;
	cin >> N;
	if (N < 1200)
		cout << "ABC" << endl;
	else
		cout << "ARC" << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> s;
  vector<int> a(26);
  for ( int i = 0; i < s.length(); ++ i) {
    a[s[i]-'A'] = 1;
  }
  if( a['N'-'A']^a['S'-'A'] || a['W'-'A']^a['E'-'A']) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
  }
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <cctype>
#include <functional>
#include <climits>
 
using namespace std;
#define pr(...) do { _ost << #__VA_ARGS__ << " = "; ~(_ost,__VA_ARGS__); } while(0);
ostream & _ost = cout;
template <class T>
ostream &operator,(ostream& ost, const T& value) { return ost << value << ","; }
ostream &operator~(ostream& ost) { return ost << endl; }
template <class T>
string tos(const T& var){ ostringstream ss; ss << var; return ss.str(); }
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
 
typedef vector<int> vi;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long ul;
typedef unsigned long long ull;
 
const int mod = 1000000007;
const int INF = 1000000;
const double EPS = 1e-10;

int m,n;

int f(int c,int a,int n){
    int res=0;
    if(c<0||a<0||n<0) // empty
        res=0;
    else if(c>=1&&a>=1&&n>=1)
        res=f(c-1,a-1,n-1)+1; // balla
    else if(c>=2&&a>=1) // speed
        res=max(f(c-2,a-1,n),f(c-1,a-1,n-1))+1;
    else if(c>=3){ // algo
        res=max(res,f(c-3,a,n)+1);
        res=max(res,f(c-2,a-1,n)+1);
        res=max(res,f(c-1,a-1,n-1)+1);
    }
    else res=0;
    
    return res;
}

int main(){
    cin>>n;
    while(n--){
        int c,a,n;cin>>c>>a>>n;
        cout<<f(c,a,n)<<endl;
    }
}

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

int64_t count_bottom(int W, int H, int K) {
    int64_t answer = 0;

    for (int s = 0; s < H - 1; s++)
        for (int x = 1; x < W && x * s <= 2 * K + W - 2; x++) {
            int R = 2 * K - 2 - x * s + __gcd(W, s);

            if (R >= 0) {
                int y = min(R / W + 1, H - s - 1);
                int success = W * y - __gcd(x, y) - __gcd(W - x, y + s) <= R;
                success += y - 1;
                answer += (s == 0 ? 1 : 2) * success;
            }
        }

    return answer;
}

int main() {
    int W, H, K;
    cin >> W >> H >> K;
    cout << 2 * count_bottom(W, H, K) + 2 * count_bottom(H, W, K) << '\n';
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int t=1,a,b,c,d,e,f,g,h;
   // cin>>t;
    while(t--)
    {
        cin>>a>>b>>c>>d;
        e=a*c;
        f=b*c;
        g=a*d;
        h=b*d;
        cout<<max(max(max(e,f),g),h)<<endl;
    }
}


Measured memory_bytes: 3656
n, m = map(int, input().split())

point = []
for _ in range(m):
    atari, hazure = map(int, input().split())
    point.append([atari, hazure])

point.sort(reverse=True)

ans = 0
for [atari, _] in point[:m-1]:
    if atari >= n:
        continue
    else:
        ans += n - atari

print(ans)



Measured memory_bytes: 5616
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define endl "\n"
#define pi 3.14159265358979323846264338327950288
#define MODD 1000000000000000000
#define INF -100000000000000
#define ordered_set tree<pair< ll int ,ll  int>, null_type,less<pair<ll int, ll int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
using namespace std;
#define lld long double
using namespace __gnu_pbds; 
int main()
{
    fast;
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //#endif
    ll int n;
    cin>>n;
    lld a[n]; 
    lld  ans=1;   
    lld MOD=1000000000000000000;
    for(ll int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(ll int i=0;i<n;i++)
        {
            if(a[i]==0)
            {
                cout<<0<<endl;
                exit(0);
            }

        ans=ans*a[i];

        if(ans>MOD)
        {
            cout<<"-1\n";exit(0);
        }
    }
    cout<<(ll int)(ans)<<endl;
}


Measured memory_bytes: 5380
N = int(input())
A = list(map(int, input().split()))
num = [0] * (N+1)
for x in A:
    num[x] += 1
sum = 0
for x in num:
    sum += x * (x - 1) // 2
for x in A:
    print(sum - num[x] * (num[x] - 1) // 2 + (num[x] - 1) * (num[x] - 2) // 2)


Measured memory_bytes: 26268
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

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> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> d(n);
    REP(i,n) cin>>d[i];
    VSORT(d);
    int ans = 0;
    ans += d[n/2] - d[n/2-1];
    cout<<ans<<endl;
}

Measured memory_bytes: 640
#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second               
#define mp make_pair
#define ll long long

#define pb push_back
#define pbb pop_back
#define pf push_front
#define pff pop_front

#define sz(x) x.size()       
#define in(x) insert(x)                          
#define ioi exit(0);
#define bit(x) __builtin_popcount(x)

#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define upper(x,y,z) upper_bound(x + 1, x + 1 + y, z) - x
#define lower(x,y,z) lower_bound(x + 1, x + 1 + y, z) - x

using namespace std;
using namespace __gnu_pbds;
          
const int N = (int)1e5 + 5;
const int M = (int)1e6 + 6;
const ll INF = (ll)2e18 + 1;
const int mod = (int)1e9 + 7;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

long long a,b,c;

inline void solve(){
	cin >> a >> b >> c;
	if(c == 0){
		cout << a;
		return;
	}
	long long ans = 0;
	if(a == 0){
		if(b + 1 >= c){
			cout << b + c;		
		}  
		else cout << b + 1 + b;
		return;
	}
	if(b == 0){
		if(a + 1 >= c){
			cout << c; 
		}
		else cout << a + 1;
		return;
	}
	long long x = min(c,a + 1);
	ans += x;
	c -= x;
	x = min(b,c);
	ans += x * 2;
	b -= x;
	ans += b;
	cout << ans;
}

int main(){
   	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   	int tt = 1;
   	//cin >> tt;
   	while(tt--){
   		solve();
   	}
   	return 0;
}                                

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

#define F first
#define S second
#define pb push_back
#define mp make_pair

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

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

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

	string s;
	cin >> s;
	ll cnt = 0 , flag = 0;
	vector <ll> v;
	for(ll i=0;i<3;i++)
	{
		if(s[i] == 'R' && flag == 0)
		{
			flag = 1;
			cnt = 1;
		}
		else if(s[i] == 'R' && flag == 1)
			cnt++;
		else if(s[i] == 'S' && flag == 1)
		{	
			v.pb(cnt);
			cnt = 0;
			flag = 0;
		}
	}

	v.pb(cnt);

	sort(v.begin() , v.end() , greater<ll>());

	if(!v.empty())
		cout << v[0] << endl;
	else
		cout << 0 << endl;
}

Measured memory_bytes: 3652
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
#include "cstring"
#include "stack"
#include "queue"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main()
{
  ll n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;
  bool ans = false;
  for (int i = 0; i < n; i++)
  {
    if (c * i - d * (n - 1 - i) <= b - a && b - a <= d * i - c * (n - 1 - i))
    {
      ans = true;
    }
  }
  cout << (ans ? "YES" : "NO") << "\n";
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD7 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> H(N);
    for(int i = 0; i < N; i++) cin >> H[i];
    sort(all(H));
    reverse(all(H));
    for(int i = 0; i < K; i++){
        if(i >= N) break;
        H[i] = 0;
    }
    ll sum = 0;
    for(int h : H) sum+= h;
    cout << sum << endl;
}


Measured memory_bytes: 3976
#include <bits/stdc++.h>
#include<vector>
#include<stdlib.h>
#include<math.h>

using namespace std;

int main() {
    long long n, x, t;
    vector<long long> ara;
    long long arr[100007];
    cin >> n;
    t = n;
    while(n--){
        cin >> x;
        ara.push_back(x);
    }
    arr[0] = 0;
    for (int i = 1; i < t; i++){
        i==1? arr[i] = abs(ara[i]-ara[i-1]) : arr[i] = min(arr[i-2]+abs(ara[i]-ara[i-2]), arr[i-1]+abs(ara[i]-ara[i-1]));
    }
    //for(int j = 0; j<t; j++) printf("%lld %lld\n", ara[j], arr[j]);
    cout << arr[t-1] << endl;
    return 0;
}


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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N;
  cin >> N;
  ll a[N];
  rep(i, N) cin >> a[i];
  ll ans=0;
  rep(i, N) ans += (a[i]-1);
  cout << ans << endl;

  return 0;
    

}


Measured memory_bytes: 256
#include <cstdio>

#define MAX 10000
#define NIL -1

struct Node { int parent, left, right; };

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u, int d)
{
    if (u == NIL) return;
    D[u] = d;
    setDepth(T[u].left, d + 1);
    setDepth(T[u].right, d + 1);
}

int setHeight(int u)
{
    int h1 = 0, h2 = 0;

    if (T[u].left != NIL)
        h1 = setHeight(T[u].left) + 1;
    if (T[u].right != NIL)
        h2 = setHeight(T[u].right) + 1;

    return H[u] = (h1 > h2 ? h1 : h2);
}

// 節点 u の兄弟を返す
int getSibling(int u)
{
    if (T[u].parent == NIL) return NIL;
    if (T[T[u].parent].left != u && T[T[u].parent].left != NIL)
        return T[T[u].parent].left;
    if (T[T[u].parent].right != u && T[T[u].parent].right != NIL)
        return T[T[u].parent].right;
    return NIL;
}

void print(int u)
{
    int deg = 0;

    printf("node %d: ", u);
    printf("parent = %d, ", T[u].parent);
    printf("sibling = %d, ", getSibling(u));

    if (T[u].left != NIL) deg++;
    if (T[u].right != NIL) deg++;
    printf("degree = %d, ", deg);
    printf("depth = %d, ", D[u]);
    printf("height = %d, ", H[u]);

    if (T[u].parent == NIL) {
        printf("root\n");
    } else if (T[u].left == NIL && T[u].right == NIL) {
        printf("leaf\n");
    } else {
        printf("internal node\n");
    }
}

int main()
{
    int v, l, r, root = 0;
    int i;

    scanf("%d", &n);

    for (i = 0; i < n; i++) T[i].parent = NIL;

    for (i = 0; i < n; i++) {
        scanf("%d %d %d", &v, &l, &r);
        T[v].left = l;
        T[v].right = r;
        if (l != NIL) T[l].parent = v;
        if (r != NIL) T[r].parent = v;
    }

    for (i = 0; i < n; i++) if (T[i].parent == NIL) root = i;

    setDepth(root, 0);
    setHeight(root);

    for (i = 0; i < n; i++) print(i);

    return 0;
}


Measured memory_bytes: 2752
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define repR(i, n) for(ll i = n; i >= 0; i--)
#define For(i, m, n) for(ll i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
ll gcd(ll a, ll b){
    ll r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll lcm(ll x, ll y)
{
    if(x == 0 || y == 0) {
        return -1;
    }
    
    return (x * y / gcd(x, y));
}


using namespace std;

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll nCr(ll n, ll r) {
    if ( r * 2 > n ) r = n - r;
    ll dividend = 1;
    ll divisor  = 1;
    for ( ll i = 1; i <= r; ++i ) {
        dividend *= (n-i+1);
        divisor  *= i;
    }
    return dividend / divisor;
}

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main(int argc, char *argv[]) {
    ll N, Q;
    cin >> N >> Q;
    vector<pair<ll, ll>> ab;
    vector<pair<ll, ll>> px;
    
    rep(i, N-1){
        ll a, b;
        cin >> a >> b;
        
        ab.push_back(make_pair(a, b));
    }
    sort(ALL(ab));
    
    rep(i, Q){
        ll p, x;
        cin >> p >> x;
        px.push_back(make_pair(p, x));
    }
    sort(ALL(px));
    
    vector<ll> result(N);
    ll posLast1 = -1;
    rep(i, Q){
        if(px[i].first == 1){
            result[0] += px[i].second;
        }else{
            posLast1 = i;
            break;
        }
    }
    
    if(posLast1 != -1){
        For(i, posLast1, Q){
            result[px[i].first - 1] += px[i].second;
        }
    }
    
    /*
    rep(i, N){
        cout << result[i] << endl;
    }
    */
    
    rep(i, N-1){
        if(ab[i].first == 1){
            result[ab[i].second - 1] += result[0];
        }else{
            result[ab[i].second - 1] += result[ab[i].first - 1];
        }
    }
    
    rep(i, N){
        cout << result[i] << " ";
    }
    
    return 0;
}


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

#define len(x)  (int((x).size()))
#define append push_back
#define pp make_pair
#define ff(a, b)    for (int a = 0; a < int(b); ++a)
#define kk(n)    ff(k, n)
#define xx(n)    ff(x, n)
#define yy(n)    ff(y, n)
#define ii(n)    ff(i, n)
#define fff(a, b, c) for (int a = int(b); a < int(c); ++a)
#define kkk(a, b) fff(k, a, b)
#define xxx(a, b) fff(x, a, b)
#define yyy(a, b) fff(y, a, b)
#define iii(a, b) fff(i, a, b)
#define bb begin()
#define ee end()
#define uu first
#define vv second
#define all(x)  (x).bb, (x).ee
#define ite(v)   decltype((v).bb)
#define fe(i, v) for(ite(v) i = (v).bb; i != (v).ee; ++i)
#define err(...)    { fprintf(stderr, __VA_ARGS__); fflush(stderr); }
#define zz(array, byte)   memset(array, byte, sizeof(array));

using LL = long long;
using DD = long double;
using pii = pair<int, int>;



const LL  INFLL  = 0x7f7f7f7f7f7f7f7fLL;
const int INFint = 0x7f7f7f7f;  //Works with memset(..).
 
     
vector<vector<int> > al;
vector<int> labels;
vector<pii> constraints;


pii gather(int from, int up) {
    int low = -1000111;
    int high = 1000111;
    ii (len(al[from])) {
        if (al[from][i] == up)
            continue;

        pii below = gather(al[from][i], from);
        if (below.vv == 1000111)    //No constraint.
            continue;
        if (below.uu == INFint)
            return pp(INFint, INFint);
        if (high != 1000111 && (high - below.vv) % 2 == 0)
            return pp(INFint, INFint);
        low = max(low, below.uu-1);
        high = min(high, below.vv+1);
    }

    if (low > high)
        return pp(INFint, INFint);
    if (-1 != labels[from]) {
        if (high != 1000111 && (high - labels[from]) % 2 == 1)
            return pp(INFint, INFint);
        if (!(low <= labels[from] && labels[from] <= high))
            return pp(INFint, INFint);
        return constraints[from] = pii(labels[from], labels[from]);
    }
    return constraints[from] = pii(low, high);

}

void push(int from, int up, int here) {
    labels[from] = here;
    
    ii (len(al[from])) {
        if (al[from][i] == up)
            continue;
        int nei = al[from][i];
        pii c = constraints[nei];
        if (c.vv == 1000111) {
            push(nei, from, here + 1);
        } else {
            if (c.uu <= here+1 && here+1 <= c.vv)
                push(nei, from, here + 1);
            else
                push(nei, from, here - 1);
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);     cin.tie(NULL);
    //cout << '\n';
    cout.precision(16);
    

    int N, K;
    cin >> N;
    al.resize(N);
    constraints.resize(N);
    labels.resize(N, -1);
    ii (N-1) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        al[a].append(b);
        al[b].append(a);
    }
    cin >> K;
    ii (K) {
        int v, p;
        cin >> v >> p;
        labels[--v] = p;
    }

    pii ok = gather(0, -1);
    if (ok.uu == INFint)
        cout << "No\n";
    else {
        cout << "Yes\n";
        push(0, -1, ok.uu);
        ii (N)
            cout << labels[i] << "\n";
    }
    

    return 0;
}



Measured memory_bytes: 15360
#include<cstdio>
using namespace std;
const int maxn=200005,maxe=maxn<<1;
int n,a,b,c,ans[maxn];
int e,lnk[maxn],nxt[maxe],son[maxe];
inline char nc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	int ret=0;bool f=0;char ch=nc();
	while(ch>'9'||ch<'0') f^=ch=='-',ch=nc();
	while(ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=nc();
	return f?-ret:ret;
}
inline void add_e(int x,int y){son[++e]=y;nxt[e]=lnk[x];lnk[x]=e;}
void DFS(int x,int fa,int y){
	if(y==0) if(a<=n) ans[x]=a,a+=3;else
			 if(b<=n) ans[x]=b,b+=3;else ans[x]=c,c+=3;
	if(y==1) if(a<=n) ans[x]=a,a+=3;else ans[x]=c,c+=3;
	if(y==2) if(b<=n) ans[x]=b,b+=3;else ans[x]=c,c+=3;
	if(y==3) ans[x]=c,c+=3;
	for (int i=lnk[x];i;i=nxt[i])
	if(son[i]^fa) DFS(son[i],x,y^3);
}
int main(){
	n=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		add_e(x,y),add_e(y,x);
	}
	a=1,b=2,c=3;DFS(1,-1,1);
	if(a<=n) a=1,b=2,c=3,DFS(1,-1,3);else
	if(b<=n) a=1,b=2,c=3,DFS(1,-1,0);
	for (int i=1;i<=n;i++) printf("%d ",ans[i]);
	return 0;
}

Measured memory_bytes: 12544