akhauriyash/Code-Regression huggingface dataset:
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;

int a[1000];

int main()
{
	int A,B;
	for (int i=1;i<=999;i++)
	{
		int sum=0;
		for (int j=1;j<=i;j++)
			sum+=j;
		a[i]=sum;
	}
	scanf("%d%d",&A,&B);
	for (int i=1;i<=999;i++)
		if (a[i]-A == a[i+1]-B) {
			printf("%d\n",a[i]-A);
			return 0;
		}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <random>
#include <atcoder/all>
using namespace std; typedef unsigned long long _ulong; typedef long long int lint; typedef pair<lint, lint> plint; typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define endk '\n'
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
const lint MOD = 1e9 + 7, INF = 1e18;
lint dx[8] = { 0, -1, 1, 0, 1, -1, 1, -1 }, dy[8] = { 1, 0, 0, -1, -1, -1, 1, 1 };
typedef pair<lint, char> pa;

using namespace atcoder;
lint N, Q;
lint q, u, v;
int main() {
	cin >> N >> Q;
	dsu tree(N);
	REP(i, Q) {
		cin >> q >> u >> v;
		if (q == 0) tree.merge(u, v);
		else cout << tree.same(u, v) << endk;
	}
}

Measured memory_bytes: 4000
#include <iostream>
#include <ctime>
#include <iomanip>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <chrono>
#include <stack>
#include <cassert>
#include <queue>
#include <deque>
#include <climits>
#include <cstring>
#include <random>
#include <bitset>

using namespace std;

string num(int p, int num) {
    string ps = to_string(p);
    string ns = to_string(num);
    while (ps.size() < 6) {
        ps.insert(ps.begin(), '0');
    }
    while (ns.size() < 6) {
        ns.insert(ns.begin(), '0');
    }
    return ps + ns;
}

vector<int> p;
vector<int> y;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    #ifdef LOCAL
    assert(freopen("input.txt", "r", stdin));
    assert(freopen("output.txt", "w", stdout));
    #endif
    
    int cnt, n;
    cin >> cnt >> n;
    p.resize(n);
    y.resize(n);
    map<int, vector<int>> bp;
    for (int i = 0; i < n; i++) {
        cin >> p[i] >> y[i];
        bp[p[i]].push_back(y[i]);
    }
    for (auto &t : bp) {
        sort(t.second.begin(), t.second.end());
    }
    vector<string> ans(n);

    for (int i = 0; i < n; i++) {
        int ind = lower_bound(bp[p[i]].begin(), bp[p[i]].end(), y[i]) - bp[p[i]].begin();
        ans[i] = num(p[i], ind + 1);
    }
    for (auto t : ans) {
        cout << t << '\n';
    }
}


Measured memory_bytes: 18688
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int a,b,c,d;
  
  scanf("%d %d %d %d", &a, &b, &c, &d);
  
  if (abs(a - c) <= d) {
    printf("Yes");
  } else if (abs(a - b) <= d && abs(b - c) <= d) {
    printf("Yes");
  } else {
    printf("No");
  }
  
  return 0;
}

Measured memory_bytes: 128
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <string>
#include <random>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int inf = 1e9;
const ll mod = 1e9 + 7;


int main() {
	int n;
	string s;
	cin >> n >> s;
	

	while (s.size() != 1) {
		int cnt = 0;
		vector<int> count;
		for (int i = 1; i < s.size(); ++i) {
			if (s[i-1] == s[i]) {
				count.push_back(i);
				i++;
			}
			if (i >= s.size() - 1) break;
		}

		if (count.size() >= 1) {
			rep(i, count.size()) {
				s.erase(s.begin() + (count[i] - cnt));
				cnt++;
			}
		}
		else break;
	}
	cout << s.size() << endl;
	return 0;
}

Measured memory_bytes: 768
A,B,K=map(int,input().split())

if abs(A-B)<=K:
    for i in range(A,B+1):
        print(i)
    exit()
a=set()
for i in range(A,A+K):
    a.add(i)
    print(i)
for i in range(B-K+1,B+1):
    if i in a:
        continue
    print(i)

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    string S;
    int w;
    cin>>S>>w;

    for(int i=0;i<S.size();i+=w)cout<<S[i];
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
def main():
	s = int(input())
	import math
	from functools import reduce
	import itertools
	def gcd(*numbers):
		return reduce(math.gcd, numbers)

	ans = 0
	for a in range(1,s+1):
		for b in range(1,s+1):
			for c in range(1,s+1):
				m = gcd(a,b,c)
				ans += m
	print(ans)

if __name__ == '__main__':
	main()

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

            #define rep(i,a,b) for(int i=a;i<b;i++)
            #define repe(i,a,b) for(ll i=a;i>=b;i--)

            #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

            #define ll long long
            #define ld long double

            #define V vector<ll>
            #define pp pair<ll,ll>
            #define pb push_back
            #define mp make_pair
            #define Pr pair<ll,ll>
            #define all(A) A.begin(),A.end()
            #define allr(A) A.rbegin().A.rend()
            #define ff first
            #define ss second
            #define len length()
            ll max3(ll a,ll b,ll c)
            {
                if(a>=b&&a>=c)
                    return a;
                else if(b>=a&&b>=c)
                    return b;
                else
                    return c;
            }
            int min3(int a,int b,int c)
            {
                if(a<=b&&a<=c)
                    return a;
                else if(b<=a&&b<=c)
                    return b;
                else
                    return c;
            }
            ll binarySearch(ll arr[], ll l, ll r, ll x)
            {      ll mid = l + (r - l) / 2;
                if (r >= l) {


                    if (arr[mid] == x)
                        return mid;

                    if (arr[mid] > x)
                        return binarySearch(arr, l, mid - 1, x);


                    return binarySearch(arr, mid + 1, r, x);
                }

                return mid;
            }
            vector<ll> divisors(ll n)
            {   vector<ll> v;
                for(ll i=1;i*i<=n;i++)
                 {
                     if(n%i==0)
                     {
                         if(n/i==i)
                            v.pb(i);
                         else
                            v.pb(i),v.pb(n/i);
                     }
                 }
                 return v;
            }
            vector<ll> factors(ll n)
            {   vector<ll> v;
              ll f=n;
                for(ll i=2;i<=sqrt(f);i++)
                {
                    if(n%i==0)
                        while(n%i==0)
                            {
                                v.pb(i);
                                n=n/i;
                            }
                }
                if(n!=1)
                v.pb(n);
                return v;
            }
            int main()
            {
                    
                        ll a;
                        cin>>a;
                        ll ans=0;
                        ans+=a;
                        ans+=a*a;
                        ans+=a*a*a;
                        cout<<ans<<endl;
                    
                return 0;
            }


Measured memory_bytes: 3688
def solve(x):
    s = 0
    for i in range(360):
        s += x
        if s % 360 == 0:
            return i + 1
    return 0


def main():
    x = int(input())
    res = solve(x)
    print(res)


def test():
    assert solve(90) == 4
    assert solve(1) == 360


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 9176
#include "bits/stdc++.h"
using namespace std;

const long long INF = 1000000000000000007;
// -------------------------------------------------------

const long long MAX_V = 1010101;

using cost_type = long long;
// costが浮動小数点数の場合
// using cost_type = double;

struct edge {
  long long to;
  cost_type cost;
};

using Pll = pair<cost_type, long long>;

long long V;
vector<edge> Graph[MAX_V];
bool used[MAX_V];

cost_type prim(long long s) {
  priority_queue<Pll, vector<Pll>, greater<Pll>> que;

  used[s] = true;

  for (auto e : Graph[s]) {
    que.push(Pll(e.cost, e.to));
  }

  // 使用済みの辺のコスト
  cost_type res = 0;
  // 使用済みの頂点の数
  long long v_count = 1;

  while (!que.empty() && v_count < V) {
    auto elem = que.top();
    que.pop();

    auto nc = elem.first;
    auto nv = elem.second;

    if (used[nv]) continue;

    used[nv] = true;
    res += nc;
    ++v_count;

    for (auto e : Graph[nv]) {
      if (!used[e.to]) {
        que.push(Pll(e.cost, e.to));
      }
    }
  }

  return res;
}

long long E;

// AOJの以下URLでテストできる
// https://onlinejudge.u-aizu.ac.jp/problems/GRL_2_A
int main() {
  cin >> V >> E;
  for (int i = 0; i < E; ++i) {
    int s, t, w;
    cin >> s >> t >> w;
    Graph[s].push_back(edge{t, w});
    Graph[t].push_back(edge{s, w});
  }

  cout << prim(0) << endl;
}



Measured memory_bytes: 33840
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K, X, Y;
  cin >> N >> K >> X >> Y;
  
  if(N>K){
    cout << K*X + (N-K)*Y << endl;
  }
  
  else{
    cout << N*X << endl;
  }
    
}


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

long long getMin (long long *arr, int size) {
    long long mn = arr[0];
    for (int i = 1; i < size; ++i) {
        if (arr[i] < mn) mn = arr[i];
    }
    return mn;
}

long long getMax (long long *arr, int size) {
    long long mx = arr[0];
    for (int i = 1; i < size; ++i) {
        if (arr[i] > mx) mx = arr[i];
    }
    return mx;
}

int main() {
    int n;
    cin >> n;
    long long a[n];
    long long sum[4];
    sum[3] = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i < 3) sum[i] = a[i];
        else sum[3] += a[i];
    }
    int l = 1, r = 3;
    long long mn, mx, ans;
    mn = getMin(sum, 4);
    mx = getMax(sum, 4);
    ans = mx - mn;
    for (int m = 2; m < n-1; ++m) {
        while (l < m-1 && abs(sum[0] - sum[1] + 2*a[l]) < abs(sum[0] - sum[1])) {
            sum[0] += a[l]; sum[1] -= a[l];
            ++l;
        }
        while (r < n-1 && abs(sum[2] - sum[3] + 2*a[r]) < abs(sum[2] - sum[3])) {
            sum[2] += a[r]; sum[3] -= a[r];
            ++r;
        }
        mn = getMin(sum, 4);
        mx = getMax(sum, 4);
        if (mx - mn < ans) ans = mx - mn;
        if (m + 1 == r) {
            sum[2] += a[r]; sum[3] -= a[r];
            ++r;
        }
        sum[1] += a[m];
        sum[2] -= a[m];
    }
    cout << ans << endl;   
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200003;
const ll INF=1LL<<60;

template<typename T>
struct SegmentTree{
    using F=function<T(T,T)>;
    
    int n;
    vector<T> dat;
    F f;
    T ti;
    
    SegmentTree(int n_ ,F f ,T ti) :f(f),ti(ti){
        n=1;
        while(n<n_) n*=2;
        dat.assign(2*n-1,ti);
    }
    
    SegmentTree(int n_ ,vector<T> &v ,F f,T ti) :f(f),ti(ti){
        n=1;
        while(n<n_) n*=2;
        dat.assign(2*n-1,ti);
        
        for(int i=n-1;i-(n-1)<v.size();i++) dat[i]=v[i-(n-1)];
        
        for(int i=n-2;i>=0;i--) dat[i]=f(dat[i*2+1],dat[i*2+2]);
    }
    
    void update(int k,T x){
        k+=n-1;
        dat[k]=x;
        
        while(k){
            k=(k-1)/2;
            dat[k]=f(dat[k*2+1],dat[k*2+2]);
        }
    }
    
    void set(int k,T x){
        dat[n-1+k]=x;
    }
    
    void built(){
        for(int i=n-2;i>=0;i--) dat[i]=f(dat[i*2+1],dat[i*2+2]);
    }
    
    T query_(int a,int b,int k,int l,int r){
        if(r<=a||b<=l) return ti;
        if(a<=l&&r<=b) return dat[k];
        else{
            T vl=query_(a,b,2*k+1,l,(l+r)/2);
            T vr=query_(a,b,2*k+2,(l+r)/2,r);
            return f(vl,vr);
        }
    }
    
    T query(int a,int b){
        return query_(a,b,0,0,n);
    }
    
    T get(int k){
        return dat[k+n-1];
    }
    
};

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    vector<int> T(N),A(N);
    for(int i=0;i<N;i++) cin>>T[i]>>A[i];
    int Q;cin>>Q;
    vector<int> L(Q),R(Q);
    for(int i=0;i<Q;i++) cin>>L[i]>>R[i];
    map<int,int> MA;
    
    for(int i=0;i<N;i++){
        MA[T[i]]++;
    }
    for(int i=0;i<Q;i++){
        MA[L[i]]++;
        MA[R[i]]++;
    }
    int c=0;
    for(auto it=MA.begin();it!=MA.end();it++){
        MA[(*it).first]=c;
        c++;
    }
    for(int i=0;i<N;i++){
        T[i]=MA[T[i]];
    }
    for(int i=0;i<Q;i++){
        L[i]=MA[L[i]];
        R[i]=MA[R[i]]+1;
    }
    
    /*for(int i=0;i<N;i++){
        cout<<T[i]<<endl;
    }
    for(int i=0;i<Q;i++){
        cout<<L[i]<<" "<<R[i]<<endl;
    }*/
    
    vector<SegmentTree<int>> seg(8,SegmentTree<int>(N+2*Q,
                         [](int a,int b){return a+b;},
                         0));
    
    for(int i=0;i<N;i++){
        int a=seg[A[i]].get(T[i]);
        seg[A[i]].update(T[i],a+1);
    }
    
    for(int i=0;i<Q;i++){
        long double now=1000000000.0;
        
        for(int j=1;j<=7;j++){
            int cnt=seg[j].query(L[i],R[i]);
            now*=pow(1.0-0.1*j,cnt);
        }
        
        cout<<setprecision(25)<<now<<endl;
    }
}





Measured memory_bytes: 55388
s = input()
RL = []
LL = []
RR = []
LR = [-1]
for i in range(len(s)-1):
  if s[i] == "R" and s[i+1] == "L":
    RL.append(i)
  elif s[i] == "L" and s[i+1] == "L":
    LL.append(i)
  elif s[i] == "R" and s[i+1] == "R":
    RR.append(i)
  else:
    LR.append(i)
LR.append(len(s)-1)
k = [0]*len(s)
for i in range(len(RL)):
  L = LR[i+1] - RL[i]
  R = RL[i] - LR[i]
  l = int((R+1)/2)+int(L/2)
  r = int(R/2)+int((L+1)/2)
  k[RL[i]] = l
  k[RL[i]+1] = r
for i in range(len(s)-1):
  print(k[i],end = " ")
print(k[len(s)-1])

Measured memory_bytes: 9012
A = gets.to_i
B = gets.to_i
C = gets.to_i
X = gets.to_i
ans = 0
for i in 0..A do
  break if 500 * i > X
  for j in 0..B do
    break if 500 * i + 100 * j > X
    if (X - 500 * i - 100 * j) <= 50 * C
      ans += 1
    end
  end
end
puts ans


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
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()
{
    int64_t N;
    cin >> N;
    int64_t sum = 0;
    vector<pair<int64_t, int64_t>>vec(N);
    for (int64_t i=0; i<N; i++) {
        int64_t a, b;
        cin >> a >> b;
        vec[i] = make_pair(a, b);
    }

    for (int64_t i=N-1; i>=0; i--) {
        int64_t a = vec[i].first;
        int64_t b = vec[i].second;
        int64_t now = a + sum;
        if (now % b != 0) {
            int64_t c = now / b;
            sum += (b * (c + 1)) - now;
        }
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 4852
'''
Created on 2020/08/20

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  H=int(pin())
  W=int(pin())
  N=int(pin())
  t=max(H,W)
  if N%t==0:
    print(N//t)
  else:
    print(N//t+1)
  return 

main()

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

using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll k;
    cin >> k;
    ll v = 7 % k;
    for (int i = 1; i < (int) 2e6+11; ++i) {
        if (v == 0) {
            cout << i << '\n';
            return 0;
        }
        v = ((v * 10) + 7) % k;
    }

    cout << -1 << '\n';
    return 0;
}


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

int main(void)
{
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep (i, n) cin >> p[i];
    sort(p.begin(), p.end());
    int sum = 0;
    rep(i, k) sum += p[i];
    cout << sum << endl;
}


Measured memory_bytes: 3552
# パナソニックプログラミングコンテスト2020: A – Kth Term
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[int(input()) - 1])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <vector>
#include <string.h>

using namespace std;


int main(){

int n; cin>>n;
 int a[n];

 for(int i=0;i<n;i++)
    cin>>a[i];

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

   if(a[i-1] > a[i]){
     a[i]++;
     if(a[i-1] > a[i]){
        cout<<"No"<<endl;
        return 0; }
   }
 }

 cout<<"Yes"<<endl;

return 0;
}



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

bool compair(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}


int main(){
    int n, m;
    cin >> n >> m;

    vector<pair<int, int> > v;

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }

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

    int cur = -(1e9);
    int count = 0;
    for(int i = 0; i < m; i++){
        if(cur > v[i].first){
            continue;
        }
        cur = v[i].second;
        count++;
    }
    printf("%d\n", count);
    return 0;
}

Measured memory_bytes: 1400
#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << 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 if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 100000000;
typedef double D;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
typedef pair<int, int> P;

/** Problem1125 : Get Many Persimmon Trees **/
int main()
{
	int N, W, H;
	while (cin>>N, N) {
		cin>>W>>H;
		bool field[W][H];
		int num[W][H];
		
		fill(field[0], field[0]+W*H, false);
		fill(num[0], num[0]+W*H, 0);
		
		rep(i, N) {
			int x, y; cin>>x>>y;
			field[x-1][y-1] = true;
		}
		
		num[0][0] = field[0][0];
		
		REP(x, 1, W) {
			num[x][0] = num[x-1][0]+field[x][0];
		}
		
		REP(x, 1, H) {
			num[0][x] = num[0][x-1]+field[0][x];
		}
		
		REP(y, 1, H) {
			REP(x, 1, W) {
				num[x][y] = num[x-1][y] + num[x][y-1] + field[x][y] - num[x-1][y-1];
			}
		}
		
		int S, T; cin>>S>>T;
		int ans = 0;
		rep(y, H-T+1) {
			rep(x, W-S+1) {
				int tmp = num[x+S-1][y+T-1];
				
				if (x>0)
					tmp -= num[x-1][y+T-1];
				if (y>0)
					tmp -= num[x+S-1][y-1];
				if (x>0 && y>0)
					tmp += num[x-1][y-1];
				ans = max(ans, tmp);
			}
		}
		cout << ans << endl;
	}
}

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

struct edge
{
    int to;
    int id;
};

const int MAXDATA = 100000;
vector<vector<edge>> graph(MAXDATA);
vector<bool> seen(MAXDATA, false);
vector<int> ans(MAXDATA);

void dfs(int sv, int color)
{
    int temp = 1;
    int n = graph[sv].size();
    seen[sv] = true;
    rep (i, n)
    {
        int nv = graph[sv][i].to;
        if (seen[nv])
            continue;
        if (temp == color)
            temp++;
        ans[graph[sv][i].id] = temp++;
        dfs(nv, ans[graph[sv][i].id]);
    }
}

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

    rep (i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back((edge){b, i});
        graph[b].push_back((edge){a, i});
    }

    dfs(0, 0);

    int maxColor = -1;
    rep (i, n)
        maxColor = max(ans[i], maxColor);
    cout << maxColor << endl;
    rep (i, n - 1)
        cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 12324
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;




ll combination(ll n, ll r){
    if(n < r) return 0;
    if(r == 0||r == n) return 1;
    else if(r == 1) return n;
    return (combination(n - 1, r - 1) + combination(n - 1, r));
}

bool checkKaibun(string str){
    string checkStr = str;
    reverse(checkStr.begin(), checkStr.end());
    if(str == checkStr) return true;
    else return false;
}

int main(){
    int N;
    cin >> N;
    vector<ll> a(N);
    rep(i, N)cin >> a[i];
    map<ll,ll> m1;
    map<ll,ll> m2;
    rep(i, N){
        m1[a[i] + i]++;
        m2[i - a[i]]++;
    }
    ll ans = 0;
    for(auto x: m1){
        ans += x.second * m2[x.first];
    }
    cout << ans << endl;
}


Measured memory_bytes: 39084
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
	char c[8][8];
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cin>>c[i][j];
		}
	}

	cout<<"90"<<endl;
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<c[7-j][i];
		}
		cout<<endl;
	}

	cout<<"180"<<endl;
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<c[7-i][7-j];
		}
		cout<<endl;
	}

	cout<<"270"<<endl;
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			cout<<c[j][7-i];
		}
		cout<<endl;
	}

	return 0;
}

Measured memory_bytes: 1136
s = input()

ctr = {"g": 0, "p": 0}
ans = 0
for i in range(len(s)):
    if s[i] == "g":
        if ctr["p"] < ctr["g"]:
            ctr["p"] += 1
            ans += 1
        else:
            ctr["g"] += 1
    else:
        # s[i] == "p"
        if ctr["p"] < ctr["g"]:
            ctr["p"] += 1
        else:
            ctr["g"] += 1
            ans -= 1
            
print(ans)


Measured memory_bytes: 39792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
int n = 22;
vector<vector<int>> a(n,vector<int>(n,0));
vector<int> dp(pow(2,n),0);
 
int main() {
  cin >> n;
  rep(i,n)rep(j,n) cin >> a.at(i).at(j);
  dp.at(0) = 1;
  for(int i=0;i<=pow(2,n);i++){
    int j = 0;
    vector<int> used(n,0);
    rep(k,n){
      if(i>>k & 1){
        j ++;
        used.at(k) = 1;
      }
    }
    rep(k,n){
      if(used.at(k) == 0 && a.at(j).at(k) == 1){
        dp.at(i|(1<<k)) = (dp.at(i|(1<<k))+dp.at(i))%MOD;
      }
    }
  }
  cout << dp.at(pow(2,n)-1) << endl; 
  //rep(i,pow(2,n)+1) cout << dp.at(i) << " ";

  return 0;
}





Measured memory_bytes: 16640
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        int N = int.Parse(Console.ReadLine());
        bool[] b = new bool[100000];
        int p = 2;
        sb.Append(N+":");
        while(N != 1 && p < 100000){
            if(!b[p]){
                while(N % p == 0){
                    sb.Append(" "+p);
                    N /= p;
                }
                for(long i=(long)p*p;i<100000;i+=p){
                    b[(int)i] = true;
                }
            }
            p++;
        }
        if(N != 1){
            sb.Append(" "+N);
        }
        sb.Append("\n");
    }
}

Measured memory_bytes: 9276
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <map>
#include <queue>
#include <set>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll mod_pow(ll x, ll n, ll mod = MOD) {
  ll res = 1;

  while (n > 0) {
    if (n & 1) {
      res = res * x % mod;
    }

    x = x * x % mod;
    n >>= 1;
  }

  return res;
}

ll mod_inverse(ll x, ll mod = MOD) {
  return mod_pow(x, mod - 2, mod);
}

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

  cout << mod_pow(M, N) << endl;

  return 0;
}



Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
string s;

int main() {
    cin >> n >> s;
    int c = 0;
    int d = 0;
    rep(i,n) {
        if (s[i] == 'R') c++;
        else d++;
    }
    if (c > d) puts("Yes");
    else puts("No");
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 1145141919
#define MOD 1000000007
#define ALL(a) begin((a)),end((a))
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
typedef vector<edge> edges;
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

bool fld[5][5] = {};
int main()
{
	int n;
	while (cin >> n, n)
	{
		char s, t, b;
		cin >> s >> t >> b;
		vector<vector<edge>> es(9, vector<edge>(9));
		MS(fld, true);
		FOR(i, 1, 4)FOR(j, 1, 4) fld[i][j] = false;
		if (b == 'A') fld[1][1] = true;
		else if (b == 'B') fld[1][2] = true;
		else if (b == 'C') fld[1][3] = true;
		else if (b == 'D') fld[2][1] = true;
		else if (b == 'E') fld[2][2] = true;
		else if (b == 'F') fld[2][3] = true;
		else if (b == 'G') fld[3][1] = true;
		else if (b == 'H') fld[3][2] = true;
		else if (b == 'I') fld[3][3] = true;
		int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
		FOR(i, 1, 4)FOR(j, 1, 4)
		{
			REP(k, 4)
			{
				int p = (i - 1) * 3 + j - 1;
				int nx = i + dx[k]; int ny = j + dy[k];
				int q = (nx - 1) * 3 + ny - 1;
				if (nx > 0 && nx<4 && ny>0 && ny < 4 && fld[nx][ny]==false)
				{
					es[p].push_back(edge{ p, q, 1 });
				}
				else es[p].push_back(edge{ p, p, 1 });
			}
		}
		int st = s - 'A';
		int go = t - 'A';
		double ex[9][16] = {};
		ex[st][0] = 1;
		FOR(k,1, n+1)
		{
			REP(i, 9)
			{
				REP(j, es[i].size())
				{
					ex[es[i][j].to][k] += ex[es[i][j].from][k - 1] * es[i][j].cost* 0.25;
				}
			}
		}
		cout << D10 << ex[go][n] << endl;
	}
	return 0;
}

Measured memory_bytes: 1272
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps = 1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.answer"
int main() {
	int N, M; cin >> N >> M;
	vector<int>as(N);
	for (int i = 0; i < N; ++i) {
		cin >> as[i];
	}
	for (int bat = 1; bat <= M; ++bat) {
		for (int n = 0; n < N-1; ++n) {
			if (as[n] % bat > as[n + 1] % bat)swap(as[n], as[n + 1]);
		}
	}
	for (int i = 0; i < N; ++i)cout << as[i] << endl;
	return 0;
}

Measured memory_bytes: 3108
// Problem : D - Redistribution
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// Macros

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int, int>
#define mii map<pii, int>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(x) (int) x.size()
#define mod 1000000007
#define EPS 1e-9
#define inf 1e10
#define PI acos(-1.0)
#define int long long
#define N 2005

// Solution

int n;
int dp[N][N];

int f(int i, int rem) {
  if (rem == 0) return 1;
  if (rem < 3) return 0;
  int &ret = dp[i][rem];
  if (~ret) return ret;
  ret = 0;
  for (int k = 3; k <= rem; k++) {
    ret += f(i + 1, rem - k);
    ret %= mod;
  }
  return ret;
}

void solve() {
  int n;
  cin >> n;
  memset(dp, -1, sizeof(dp));
  cout << f(0, n);
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

  int tests;
  tests = 1;
  // cin>>tests;

  for (int test = 1; test <= tests; test++) {
    // cout<<"Case #"<<test<<": ";
    solve();
  }

  return 0;
}

Measured memory_bytes: 35088
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




#define SIZE 200005

ll N;
ll fact[SIZE],inverse_fact[SIZE];
ll num_nodes[SIZE];
ll dp[SIZE],dp2[SIZE];
vector<int> G[SIZE];

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

void dfs(int node_id,int pre){

	num_nodes[node_id] = 1;

	for(int i = 0; i < G[node_id].size(); i++){

		int child = G[node_id][i];
		if(child == pre)continue;

		dfs(child,node_id);
		num_nodes[node_id] += num_nodes[child];
	}

	dp[node_id] = fact[num_nodes[node_id]-1];

	for(int i = 0; i < G[node_id].size(); i++){

		int child = G[node_id][i];
		if(child == pre)continue;

		dp[node_id] *= dp[child];
		dp[node_id] %= MOD;
		dp[node_id] *= inverse_fact[num_nodes[child]];
		dp[node_id] %= MOD;
	}
}

void dfs2(int node_id,int pre){

	if(node_id == 0){

		dp2[node_id] = dp[node_id];
	}else{

		dp2[node_id] = fact[N-1];

		for(int i = 0; i < G[node_id].size(); i++){

			int child = G[node_id][i];
			if(child == pre){

				ll tmp = dp2[pre]*inverse_fact[N-1];
				tmp %= MOD;
				tmp *= (fact[N-(num_nodes[node_id]+1)]);
				tmp %= MOD;
				tmp *= (fact[num_nodes[node_id]]);
				tmp %= MOD;
				tmp *= mod_inverse(dp[node_id],MOD);
				tmp %= MOD;

				dp2[node_id] *= tmp;
				dp2[node_id] %= MOD;
				dp2[node_id] *= inverse_fact[N-num_nodes[node_id]];
				dp2[node_id] %= MOD;

			}else{

				dp2[node_id] *= dp[child];
				dp2[node_id] %= MOD;
				dp2[node_id] *= inverse_fact[num_nodes[child]];
				dp2[node_id] %= MOD;
			}
		}

	}

	for(int i = 0; i < G[node_id].size(); i++){

		int child = G[node_id][i];
		if(child == pre)continue;

		dfs2(child,node_id);
	}
}

int main(){

	fact[0] = 1;
	for(ll i = 1; i <= SIZE-1; i++){
		fact[i] = i*fact[i-1];
		fact[i] %= MOD;
	}

	inverse_fact[SIZE-1] = mod_inverse(fact[SIZE-1],MOD);
	for(ll i = SIZE-1; i >= 1; i--){

		inverse_fact[i-1] = inverse_fact[i]*i;
		inverse_fact[i-1]%= MOD;
	}

	scanf("%lld",&N);

	int from,to;

	for(ll loop = 0; loop < N-1; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;
		G[from].push_back(to);
		G[to].push_back(from);
	}

	dfs(0,-1);
	dfs2(0,-1);

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

		printf("%lld\n",dp2[i]);
	}

	return 0;
}


Measured memory_bytes: 21748
#include<bits/stdc++.h>
using namespace std;
struct activity
{
  int A,B,C;
};
int solve(vector<activity> vec,int n)
{
  int dp[n+1][3];
  dp[1][0]=vec[1].A;
  dp[1][1]=vec[1].B;
  dp[1][2]=vec[1].C;
  for(int i=2;i<=n;i++)
  {
    dp[i][0] = vec[i].A+ max(dp[i-1][1],dp[i-1][2]);
    dp[i][1] = vec[i].B + max(dp[i-1][0],dp[i-1][2]);
    dp[i][2] = vec[i].C + max(dp[i-1][0],dp[i-1][1]);
  }
  return max(dp[n][0],max(dp[n][1],dp[n][2]));
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int n;
  cin>>n;
  vector<activity> vec(n+1);
  for(int i=1;i<=n;i++)
  {
    cin>>vec[i].A;
    cin>>vec[i].B;
    cin>>vec[i].C;
  }
  cout<<solve(vec,n);
  return 0;
}


Measured memory_bytes: 3840
#include <stdio.h>
#include <math.h>

void triangle (int side1,int side2,int angle);

int main () {
    int side1,side2,angle;
    scanf ("%d %d %d",&side1,&side2,&angle);
    
    triangle (side1,side2,angle);
    
    return 0;
}

void triangle (int side1,int side2,int angle) {
    double S,L,h,side3,angle2;
    angle2 = angle * 2*M_PI / 360;
    
    h = side2 * sin (angle2);
    S = (side1 * h) / 2;
    
    side3 = sqrt (side1 * side1 + side2 * side2 - 2*side1*side2*cos (angle2));
    L = side1 + side2 + side3;
    
    printf ("%f\n%f\n%f\n",S,L,h);
}


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

struct Node{ int l=-1,r=-1,p=-1; };

int N;
int Pre[100];
int In[100];
int Post[100];

void MakePost(int pIn, int pPre, int pPost, int size){
 if(size==0) return;
 int v=Pre[pPre];
 int leftsize=0;
 rep(i,size) if(In[pIn+i]==v) leftsize=i;
 MakePost(pIn,pPre+1,pPost,leftsize);
 MakePost(pIn+1+leftsize,pPre+1+leftsize,pPost+leftsize,size-leftsize-1);
 Post[pPost+size-1]=v;
}

int main() {
 scanf("%d",&N);
 rep(i,N) scanf("%d",&Pre[i]);
 rep(i,N) scanf("%d",&In[i]);
 MakePost(0,0,0,N);
 rep(i,N){ if(i)printf(" "); printf("%u",Post[i]); } printf("\n");
}



Measured memory_bytes: 3212
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{   
    int N,X; cin>>N>>X;
    vint a(N);
    REP(i,N) cin>>a[i];

    sort(ALL(a));
    vint sum(N+1);
    REP(i,N) sum[i+1]=sum[i]+a[i];

    int ans;
    if(sum[N]<X) ans=N-1;
    else if(sum[N]==X) ans=N;
    else{
        REP(i,N+1) if(sum[i]<=X) ans=i;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define lli long long int
#define ld long double
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{
    lli n;
    cin>>n;
    lli ans = (n + 1) / 2;
    cout<<ans;
    cout<<'\n';
    return ;
}



/*
*/

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

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}


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

int main(){
  int h,w,k;
  cin>>h>>w>>k;
  string str[h];
  int kuro[h][w];
  int tkuro[h][w];
  for(int i=0; i<h; i++)
    cin>>str[i];
  int mmax=1;
  for (int i=0; i<h+w; i++)
    mmax=mmax*2;
  int kaunto;
  int hantei=0;

  //黒なら1の整数配列に移す
  for (int i=0; i<h; i++)
    for (int j=0; j<w; j++)
      if(str[i].substr(j,1)=="#"){
	kuro[i][j]=1;
      }else{
	kuro[i][j]=0;
      }
  for (int m=0; m<mmax; m++){
    //tmpに移す
    for (int j=0; j<w; j++)
      for (int i=0; i<h; i++)
	tkuro[i][j]=kuro[i][j];
    //フラグが立っていれば消す
    for (int i=0; i<h; i++)
      if(m&(1<<i)){
	for(int j=0; j<w; j++)
	  tkuro[i][j]=0;
      }
    for (int i=h; i<h+w; i++)
      if(m&(1<<i)){
	for (int j=0; j<h; j++)
	  tkuro[j][i-h]=0;
      }
    //数える
    kaunto=0;
    for (int j=0; j<w; j++)
      for (int i=0; i<h; i++)
	kaunto=kaunto+tkuro[i][j];
    if(kaunto==k){
      hantei++;
    }
  }

  cout<<hantei<<"\n";
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
#define fi first
#define se second
 
signed main(){
  int n,A=0,B=0;
  cin>>n;
  int a[n],b[n];
  r(i,n)cin>>a[i],A+=a[i];
  vector<int>v;
  r(i,n){
    cin>>b[i];B+=b[i];
    v.push_back((a[i]-b[i]));
  }
  sort(v.begin(),v.end(),greater<int>());
  int ans=0;
    if(A<B){
      cout<<-1<<endl;
      return 0;
    }
  int l=0,x=0;
  r(i,n){
    if(a[i]<b[i]){
      ans++;
      int s=b[i]-a[i];
      while(s){
        if(v[l]>=s)v[l]-=s,s=0,x=1;
        else s-=v[l],l++,x=0;
      }
    }
  }
  cout<<l+ans+x<<endl;
}

Measured memory_bytes: 2680
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
#define ll  long long 
#define mod 1000000007
  vector<ll>to[1000005];
int main(){
  ll a,b;cin>>a>>b;
  cout<<a*b;
}

Measured memory_bytes: 27060
N=int(input())
P=[]
for i in range(N):
    p=int(input())
    P.append(p)
Q=[0]*N
for i in range(N):
    Q[P[i]-1]=i

cnt=1
ans=1
for i in range(N-1):
    if Q[i]<Q[i+1]:
        cnt+=1
    else:
        cnt=1
    ans=max(cnt,ans)

print(N-ans)

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

int main() {
	int a, b, k;
	cin >> a >> b >> k;
	bool flag = 1;
	while (k) {
		if (flag == 1) {
			if (a % 2 == 1)a--;
			a /= 2;
			b += a;
			flag = 0;
		}
		else {
			if (b % 2 == 1)b--;
			b /= 2;
			a += b;
			flag = 1;
		}
		k--;
	}
	cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#  --*-coding:utf-8-*--

N = int(input())
A = list(map(int, input().split()))

Q = {}
for a in A:
    if not(a in Q):
        Q[a] = 0

    Q[a] += 1

S = sum(q*(q-1)//2 for q in Q.values())

for k in range(N):
    print(S - (Q[A[k]]-1))





Measured memory_bytes: 24748
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;

const ll N = 3e3 + 5, MOD = 1e15 + 7;
const double C = 1;

ll n;
ll a[N];
ll dp[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    for (int i = 0; i <= n + 1; i++)
        for (int j = i; j <= n + 1; j++)
            dp[i][j] = - MOD;
    for (int l = 0; l < n; l++)
        for (int i = 1; i + l <= n; i++)
            dp[i][i + l] = max (a[i] - dp[i + 1][i + l], a[i + l] - dp[i][i + l - 1]);
    cout<<dp[1][n]<<endl;
    return 0;
}


Measured memory_bytes: 70016
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep = ' ', end = '\n'):
    print(*var, file=sys.stderr, end = end, sep = sep)

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, = I()
d = dd(int)
maximum = 0
for i in range(n):
    s = input()
    d[s] += 1
    maximum = max(maximum, d[s])

ans = []
for i in d:
    if d[i] == maximum:
        ans.append(i)
ans.sort()
for i in ans:
    print(i)

Measured memory_bytes: 42320
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

long combination(int n, int r = 2)
{
    long num = 1;
    rrep (i, 1, r) num = num * (n - i + 1) / i;
    return num;
}

int main()
{
    int N; cin >> N;
    map<map<char, int>, int> res;
    rep (i, 0, N) {
        map<char, int> m;
        for (auto key = 'a'; key <= 'z'; ++key) m[key] = 0;

        string s; cin >> s;
        for (auto key : s) ++m[key];

        if (res.find(m) == res.end()) res[m] = 1;
        else ++res[m];
    }

    long ans = 0;
    for (const auto &map : res) {
        ans += combination(map.second);
    }

    cout << ans << endl;
}

Measured memory_bytes: 131456
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { os << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);	
}

int main()
{
	ios_init();
	LL x, y;
	while(cin >> x >> y) {
		LL t = y/x;
		int cnt = 0;
		while(t != 0) {
			cnt++;
			t >>= 1;
		}
		cout << cnt << endl;
	}
	return 0;
}


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

int main() {
	int n;
	cin >> n;
	vector<int> t(100);
	for(int i=0; i<n; i++){
		cin >> t[i];
	}
	int m;
	cin>> m;
	vector<int> p(100);
	vector<int> x(100);
	for(int j=0; j<m; j++){
		cin >> p[j] >> x[j];
	}
	int a=0;
	for(int k=0; k<n; k++){
		a= a+t.at(k);
	}
	for(int l=0; l<m; l++){
		cout<< a-t.at(p.at(l)-1)+x.at(l)<< endl;
	}
	;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct Node{
	int num,tmp;
}a[100010];
int n;
bool cmp(Node a,Node b){
	return a.num<b.num;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].num);
		a[i].tmp=i;
	}
	sort(a+1,a+n+1,cmp);
	cout<<a[1].tmp;
	for(int i=2;i<=n;i++){
		cout<<" "<<a[i].tmp;
	}
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main(){
      int H, W;
      cin >> H >> W;
      char a[H][W];
      for(int i=0;i<H;i++){
       for(int j=0;j<W;j++){
        cin >> a[i][j]; 
       }
      }
      for(int i=0;i<H;i++){
       for(int j=0;j<W;j++){
         bool flag1=true;
         bool flag2=true;
         for(int k=0;k<W;k++){
          if(a[i][k]=='#'){
           flag1=false; 
          }
         }
         for(int k=0;k<H;k++){
           if(a[k][j]=='#'){
            flag2=false; 
           }
         }
           if(flag1==false && flag2==false){
            cout << a[i][j]; 
           }
        if(j==W-1 &&( flag1==false || flag2==false) ){
         cout << endl; 
        }
         }
       }
 
      return 0;}

Measured memory_bytes: 256
N=int(input())
S=list(map(int,input().replace('#','1').replace('.','0')))
 
cum=[0]
for i in range(N):
  cum.append(cum[-1]+S[i])
  
ans=10**20
for i in range(N+1):
  b = cum[i]
  w = N-i-(cum[-1]-cum[i])
  ans = min(ans,b+w)
  
print(ans)

Measured memory_bytes: 18484
#include <iostream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

void print_vector(vector<int> num)
{
	for(int i = 0; i < num.size(); i++){
		if(i){
			cout << " ";
		}
		cout << num[i];
	}
	cout << endl;
}
int SelectionSort(vector<int> &A)
{	
	int count = 0;
	for(int i = 0; i <= A.size() - 1; i++){
		int mini= i;
		for(int j = i; j <= A.size() - 1; j++){
			if(A[j] < A[mini]){
				mini = j;
			}
		}
		if(A[i] != A[mini]){
			count++;
		}
		int a = A[i];
		A[i] = A[mini];
		A[mini] = a;
	}
	return count;
}
int main(void)
{
	int n;
	cin >> n;
	vector<int> A(n);
	for(int i = 0; i < n; i++){
		cin >> A[i];
	}
	
	int count = SelectionSort(A);
	
	print_vector(A);
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3140
#include <iostream>
#include <cassert>

using namespace std;

int A[2 * 100000];
int visited[2 * 100000];

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

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

  int city = 0;
  int cycle_start = -1;
  int cycle_length = -1;
  for (int i = 0; i < N; ++i) {
    visited[i] = -1;
  }
  visited[0] = 0;
  for (int i = 0; i < N; ++i) {
    city = A[city] - 1;
    if (visited[city] != -1) {
      cycle_start = visited[city];
      cycle_length = i + 1 - visited[city];
      break;
    }
    visited[city] = i + 1;
  }
  assert(cycle_start != -1);

  if (K >= cycle_start) {
    K = (K - cycle_start) % cycle_length + cycle_start;
  }

  int c = 0;
  for (int k = 0; k < K; ++k) {
    c = A[c] - 1;
  }
  cout << c + 1 << endl;
}

Measured memory_bytes: 5172
<?php
fscanf(STDIN, '%d %d', $N, $K);
$H = array_map('intval', explode(' ', trim(fgets(STDIN))));
if ($K > count($H)) {
    $ans = 0;
} else {
    rsort($H);
    $h = array_slice($H, $K);
    $ans = array_sum($h);
}
echo $ans;

Measured memory_bytes: 31348