akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <numeric>
#include<algorithm>
using namespace std;

int abs(int num){
   if (num > 0)
      return num;
   else
      return -num;
}

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

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

int main(){
  int N;
  int ans = 0;
  cin >> N;
  for(int i = 0;i<=N;i++){
    ans = ans + i;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

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

    if (n == 4) {
        cout << "4\n";
        cout << "1 2\n";
        cout << "1 3\n";
        cout << "4 2\n";
        cout << "4 3\n";
    } else if (n % 2 == 0) {
        cout << 2 * n << endl;

        auto k = n / 2;
        for (auto i : irange(1L, k)) {
            cout << i << " " << i + 1 << "\n";
            cout << i << " " << n - i << "\n";
            cout << n - i + 1 << " " << i + 1 << "\n";
            cout << n - i + 1 << " " << n - i << "\n";
        }
        cout << 1 << " " << k << "\n";
        cout << 1 << " " << k + 1 << "\n";
        cout << n << " " << k << "\n";
        cout << n << " " << k + 1 << "\n";
    } else if (n == 3) {
        cout << "2\n";
        cout << "1 3\n";
        cout << "2 3\n";
    } else {
        cout << 2 * n - 2 << endl;

        auto k = n / 2; // == (n - 1) / 2
        for (auto i : irange(1L, k)) {
            cout << i << " " << i + 1 << "\n";
            cout << i << " " << 2 * k - i << "\n";
            cout << 2 * k - i + 1 << " " << i + 1 << "\n";
            cout << 2 * k - i + 1 << " " << 2 * k - i << "\n";
        }
        cout << 1 << " " << n << "\n";
        cout << 2 * k << " " << n << "\n";
        cout << k << " " << n << "\n";
        cout << k + 1 << " " << n << "\n";
    }


}

Measured memory_bytes: 256
// AtCoder Beginner Contest 167 D.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	long long n, k, loop = 0, now = 1, i;
	cin >> n >> k;
	vector<int>a(n);
	vector<bool>d(n, false);
	vector<int>z;
	for (auto& i : a)
	{
		cin >> i;
	}
	while (!d[now - 1]) {
		d[now - 1] = true;
		z.push_back(now);
		now = a[now - 1];
		loop++;
	}
	for (i = 0; i < z.size(); i++) {
		if (now == z[i]) {
			loop -= i;
			break;
		}
	}
	if (k < z.size()) {
		cout << z[k] << endl;
	}
	else {
		cout << z[(k - i) % loop + i] << endl;
	}
}


Measured memory_bytes: 5132
N,M = map(int,input().split())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
a = 0
b = 0
mod = 10**9+7

for n in range(N):
  a+=(2*n-N+1)*X[n]
  a%=mod

for m in range(M):
  b+=(2*m-M+1)*Y[m]
  b%=mod

print(a*b%mod)

Measured memory_bytes: 24512
#include <cstdio>
#include <algorithm>
using namespace std;

int pi[233333][2],pp[233333],pd[233333];

bool bj(int a,int b)
{
	return pi[a][1]<pi[b][1];
}

int main()
{
	int n; scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		int a,b; scanf("%d%d",&a,&b);
		pi[i][0]=max(0,a-b); pi[i][1]=a+b; pp[i]=i;
	}
	sort(pp+1,pp+1+n,bj);
	int p=0,sum=0;
	for(int i=1; i<=n; i++) if(pi[pp[i]][0]>=p)
	{
		p=pi[pp[i]][1]; sum++;
	}
	printf("%d",sum);
	return 0;
}

Measured memory_bytes: 1408
#include<stdio.h>

int main()
{
	char str[17], str2[17]= "CODEFESTIVAL2016";
	int i, count= 0;

	scanf("%s", str);
	for(i= 0; i<= 16; i++)
		if(str[i]!= str2[i])
				count++;
	printf("%d\n", count);

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(all(x));
#define RSORT(x) sort(rall(x));
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vd = vector<double>;
using vb = vector<bool>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;
const ll inf = 1ll<<29;
const ll mod = 1000000007;
const double eps = 1e-9;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

int main() {
  int N, X; cin >> N >> X;
  vi L(N); rep(i,N) cin >> L.at(i);

  int ans = 0;
  int D = 0;
  if(D<=X) ++ans;
  rep(i,N) {
    D = D + L.at(i);
    if(D<=X) ++ans;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,x,i,j,k,ans=0;
  cin>>n>>x;
  ll a[n],b[n];
  for(i=0;i<n;i++) cin>>a[i],b[i]=a[i],ans+=a[i];
  for(k=0;k<n;k++){
    j=0;
    for(i=0;i<n;i++) j+=b[i]=min(b[i],a[(i+n-k)%n]);
    ans=min(ans,x*k+j);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e15);


int main()
{
    IOS();
    string s;
    cin>>s;
    s[3]='8';
    cout<<s<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<(e);i++)
#define REP(i,n) FOR(i,0,n)
#define all(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const LL mod = 1000000007;
LL dp[101010][4];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    dp[0][0] = 1;
    REP(i, s.size()){
        REP(j, 4){
           if(s[i] == '?'){
               (dp[i+1][j] += 3*dp[i][j]) %= mod; 
               if(j != 3) (dp[i+1][j+1] += dp[i][j]) %= mod;
           }else{
               (dp[i+1][j] += dp[i][j]) %= mod;
               if(j != 3 && j+1 == s[i]-'A'+1) (dp[i+1][j+1] += dp[i][j]) %= mod;
           }
        }
    }

    cout << dp[s.size()][3] << endl;

}




Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }

int mod = 1000000007;

class BIT
{
public:
    vector<int> bit;
    int M;

    BIT(int M):
        bit(vector<int>(M+1, 0)), M(M) {}

    int sum(int i) {
        if (!i) return 0;
        return (bit[i] + sum(i-(i&-i))) % mod;
    }

    void add(int i, int x) {
        if (i > M) return;
        bit[i] += x;
        bit[i] %= mod;
        add(i+(i&-i), x);
    }
};

signed main(){

    int N, M; cin >> N >> M;
    vec x(N), y(M);
    readv(x); readv(y);

    set<int> X, Y;
    REP(i, N){
        int n = Lower_bound(y, x[i]);
        if(n == 0 || n == M) continue;
        X.insert(x[i] - y[n - 1]);
        Y.insert(y[n] - x[i]);
    }
    vec a(0), b(0);
    for(int i: X) a.push_back(i);
    for(int i: Y) b.push_back(i);    

    set<Pii> s;
    REP(i, N){
        int n = Lower_bound(y, x[i]);
        if(n == 0 || n == M) continue;
        int x0 = Lower_bound(a, x[i] - y[n - 1]);
        int y0 = Lower_bound(b, y[n] - x[i]);
        s.insert(Pii(x0, -y0));
    }

    BIT bit(b.size() + 1);
    bit.add(1, 1);
    for(Pii p: s){
        int x0 = p.first;
        int y0 = -(p.second);
        //int s1 = bit.sum(y0 + 2), s2 = bit.sum(y0 + 1);
        bit.add(y0 + 2, bit.sum(y0 + 1));
    }

    cout << bit.sum(b.size() + 1);
    
    return 0;
}

Measured memory_bytes: 18808
#include <iostream>
#include <cstdlib>
using namespace std;
int n,m,x,y,z,cnt;
const int MAXN=1e5+5;
int f[MAXN];
int find_set(int x)
{
	if(x!=f[x]) f[x]=find_set(f[x]);
	return f[x];
}
void union_set(int a,int b)
{
	a=find_set(a);
	b=find_set(b);
	if(a!=b) f[b]=a;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		union_set(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(f[i]==i) cnt++;
	}
	cout<<cnt;
	return 0;
}

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

int main()
{
    int N;
    cin >> N;
    int B[N];
    int B_sorted[N];
    for (int i = 0; i < N; i++)
    {
        cin >> B[i];
        B_sorted[i] = B[i];
    }
    sort(B_sorted, B_sorted + N);
    int l = B_sorted[N / 2 - 1];
    int r = B_sorted[N / 2];
    for (int i = 0; i < N; i++)
    {
        if (B[i] >= r)
        {
            cout << l << endl;
        }
        else
        {
            cout << r << endl;
        }
    }
}


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

int main() {
  int Q; cin >> Q;
  int l[Q],r[Q]; rep(i,0,Q) cin >> l[i] >> r[i];
  
  bool primeC[100001]; primeC[1] =false; primeC[2] = true;
  int like2017[100001]; like2017[0] = 0; like2017[1] = 0;
  rep(i,2,100001) {
    primeC[i] = true;
    like2017[i] = like2017[i-1];
    if (i >=3) rep(j,2,sqrt(i)+1) if (i % j ==0) primeC[i] = false;
    if (primeC[i] && primeC[(i+1)/2]) like2017[i]++;
  }
  rep(i,0,Q) cout << like2017[r[i]] - like2017[l[i]-1] << endl;
}

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

int a[105];
int dp[105][100005];

#define MOD 1000000007

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

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

    for(int i = 0; i <= k; ++i){
        if(i)
            dp[0][i] = dp[0][i-1];
        if(i <= a[0])
            dp[0][i]++;
    }

    for(int i = 1; i < n; ++i){
        dp[i][0] = 1;
        for(int j = 1; j <= k; ++j){
            dp[i][j] = dp[i][j - 1];
            dp[i][j] += (dp[i - 1][j] - (j - a[i] - 1 >= 0 ? dp[i - 1][j - a[i] - 1] : 0) + MOD) % MOD;
            dp[i][j] %= MOD;
        }
    }

    cout << (dp[n - 1][k] - dp[n - 1][k - 1] + MOD) % MOD << "\n";
    return 0;
}


Measured memory_bytes: 41216
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main(){
    int N, x = 0, ans = 0;
    string str;
    cin >> N >> str;
    for(size_t i = 0; i < str.size(); ++i){
        if(str[i] == 'I'){
            ++x;
        }else{
            --x;
        }
        ans = max(x, ans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

#ifdef DEBUG
    #define IFD if(true)
#else
    #define IFD if(false)
#endif

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

    vector<int> A(N);
    vector<int> B(N);
    rep(i, N) {
        cin >> A[i];
        B[i] = A[i];
    }
    sort(B.begin(), B.end());

    rep(i, N) {
        cout << (A[i] == B[N - 1] ? B[N - 2] : B[N - 1]) << endl;
    }

    return 0;
}


Measured memory_bytes: 3200
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, K, A, F):
    A.sort()
    F.sort(reverse=True)

    def k(max_t):
        res = 0
        for a, f in zip(A, F):
            t = a * f
            if t > max_t:
                r = t - max_t
                res += (r + f - 1) // f
        return res

    l = -1
    r = 10**12
    while r - l > 1:
        m = (l + r) // 2
        if k(m) <= K: r = m
        else: l = m
    print(r)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    *F, = map(int, input().split())
    main(N, K, A, F)


Measured memory_bytes: 120340
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector <int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
	}

	bool flag = true;
	for (int i = 0; i < N; i++) {
		if (A.at(i) % 2 == 0 && A.at(i) % 3 != 0 && A.at(i) % 5 != 0){
			flag = false;
		}
	}

	if (flag) {
		cout << "APPROVED" << endl;
	}
	else {
		cout << "DENIED" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
x,y=map(int,input().split())
ans=10**18
if x<=y:
    ans=min(ans,y-x)
if -x<=y:
    ans=min(ans,y+x+1)
if x<=-y:
    ans=min(ans,-y-x+1)
if -x<=-y:
    ans=min(ans,-y+x+2)
print(ans)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define L_T_S_K ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
const int mod = 1e9 + 7;
const int N = 1e5 + 9;

int32_t main(){
 L_T_S_K;
 int a , b ;
 cin >> a >> b;
 cout << 6 - a - b;
 return 0;
}

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

void show( long long arr[], long long size )
{
	cout<<arr[0]<<flush;
	for( int i=1; i<size; i++ ){
		cout<<' '<<arr[i]<<endl;
	}
	cout<<endl;
}
/////////////////////////////////////////////////////////////////

int check( long long maxcarry, int w[],int w_size, int t ){
	int w_i=0;
	for( int t_j=0; t_j<t; t_j++ ){
		long long sum=0;
		for( ; sum + w[w_i] <=maxcarry ; w_i++ ){
			sum +=w[w_i];
			if( w_i == w_size ) {
				return w_size;
			}
		}
	}
	return w_i;
}

long long solve( int w[], int w_size, int t ){

	long long maxcarry_front =0, maxcarry_back =100000*10000, maxcarry_center;
	while( maxcarry_back - maxcarry_front > 1 ){
		maxcarry_center= (maxcarry_front+maxcarry_back) /2;
		int canCarry= check(maxcarry_center, w, w_size, t);
		if( canCarry >= w_size ) {
//			printf("?????§?????????(%d )???????????????????????????????????°( %d ) >= ???????????°( %d )\n", maxcarry_center, canCarry, w_size);

			maxcarry_back= maxcarry_center;
		}else{
//			printf("?????§?????????(%d )???????????????????????????????????°( %d )??? ???????????°( %d )??????????°???????!\n", maxcarry_center, canCarry, w_size);

			maxcarry_front=maxcarry_center;
		}
	}
	return maxcarry_back;
}


int main()
{
	int w_size, t;
	cin>>w_size>>t;
	int *w=new int[w_size];
	for( int i=0; i<w_size; i++ ) cin>>w[i];

	cout<<solve(w, w_size, t)<<endl;
}

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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args&&... args) {
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#define pi 3.141592653589
#define MOD 1000000007
#define to() int t; cin>>t; while(t--)
#define pb push_back
#define in insert
#define mp make_pair
#define ff first
#define ss second
#define si(s) s.size()
#define fori(it,v) for(it=v.begin();it!=v.end(); it++) 
#define for1(low,high,k) for(int i=low;i<high;i+=k)
#define for11(low,high,k) for(int j=low;j<high;j+=k)
#define for2(low,high,k) for(int i=low;i<=high;i+=k)
#define rev(high,low,k)  for(int i=high;i>=low ;i-=k)
#define all(x) x.begin(), x.end()
#define fil(x,i) memset(x,i,sizeof(x));
#define setbits(x) __builtin_popcount(x)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout) 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const int N=1e3+5;
int d[N][N];
string g[N];
int h,w;
bool chk(int x, int y){
	if(x>=0 && x<h && y>=0 && y<w) return true;
	return false;
}

int dxx[]={0,0,1,-1};
int dyy[]={1,-1,0,0};

int main()
{
	boost;
	cin>>h>>w;
	int sx,sy,dx,dy;
	cin>>sx>>sy;
	cin>>dx>>dy;
	sx--,sy--,dx--,dy--; 
	if(g[dx][dy]=='#' && (sx!=dx && sy!=dy) ){
		cout<<"-1"<<endl;
		return 0;
	}
	for(int i=0;i<h;i++) cin>>g[i];
	for(int i=0;i<h;i++) for(int j=0;j<w;j++) d[i][j]=1e9;
	
	d[sx][sy]=0;
	set<pair<int,pair<int,int> > >s;
	s.in(mp(0,mp(sx,sy)));
	while(!s.empty()){
		pair<int,pair<int,int> >p=*s.begin();
		s.erase(s.begin());
		int x=p.ss.ff,y=p.ss.ss;
		if(x==dx && y==dy) break;
		for(int i=0;i<4;i++){
			int x1=x+dxx[i], y1=y+dyy[i];
			if(chk(x1,y1) && g[x1][y1]!='#' && d[x1][y1]>d[x][y]){
				if(s.find(mp(d[x1][y1],mp(x1,y1)))!=s.end())
					s.erase(s.find(mp(d[x1][y1],mp(x1,y1))));
				d[x1][y1]=d[x][y];
				s.in(mp(d[x1][y1],mp(x1,y1)));
			}
		}
		for(int i=x-2;i<x+3;i++){
			for(int j=y-2;j<y+3;j++){
				int x1=i, y1=j;
				if(chk(x1,y1) && g[x1][y1]!='#' && d[x1][y1]>d[x][y]){
					if(s.find(mp(d[x1][y1],mp(x1,y1)))!=s.end())
						s.erase(s.find(mp(d[x1][y1],mp(x1,y1))));
						d[x1][y1]=d[x][y]+1;
						s.in(mp(d[x1][y1],mp(x1,y1)));
					}
			}
		}
	}
	
	if(d[dx][dy]!=1e9)
		cout<<d[dx][dy]<<endl;
		else
			cout<<"-1"<<endl;
	

return 0;
}


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

vector<vector<long long> > G(200000);
vector<long long> counter(200000 ,0);
void dfs(long long i , long long p = -1){
    for(long long v = 0; v < G[i].size(); v++){
        if(p == G[i][v]){
            continue;
        }
        counter[G[i][v]] += counter[i];
        dfs(G[i][v], i);
    }
    return;
}
int main(){
    long long n ,q;
    cin >> n >> q;

    vector<vector<long long> > children(n);
    
    for(long long i = 0; i < n-1; i++){
        long long a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        
        children[a].push_back(b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    
    for(long long i = 0; i < q; i++){
        long long p, x;
        cin >> p >> x;
        p -= 1;
        counter[p] += x;

    }

    /*for(long long i = 0; i < n; i++){
        for(long long j = 0; j < children[i].size(); j++){
            counter[children[i][j]] += counter[i];
        }
    }*/

    dfs(0);

    for(long long i = 0; i < n; i++){
        printf("%lld ", counter[i]);
    }
    printf("\n");

    return 0;
}

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

int main(){
    string s;
    cin >> s;
    s[5] = ' ';
    s[13] = ' ';
    cout << s << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
#include <iostream>
#include <vector>

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

    std::vector<int> c(N, 0);

    for (int i = 0; i < M; ++i) {
        int x, y;
        std::cin >> x >> y;
        ++c[x - 1];
        ++c[y - 1];
    }

    for (int i = 0; i < N; ++i) {
        std::cout << c[i] << std::endl;
    }

    return 0;
}


Measured memory_bytes: 888
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#define PI acos(-1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define dd(x) cout<<#x<<" = "<<x<<","
#define de(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e6+5;
int a[N],cnt[N];
int main()
{
	int n;
	scanf("%d",&n);
	ll sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
		sum+=a[i];
	}
	int q;
	scanf("%d",&q);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		sum+=1ll*(y-x)*cnt[x];
		cnt[y]+=cnt[x];
		cnt[x]=0;
		printf("%lld\n",sum);
	}
}


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

int main(){
    int N, A;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A;
        if(A%2 == 0){
            if(A%3 != 0 && A%5 != 0){
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SPEED ios_base::sync_with_stdio(false); cin.tie(NULL)
#define REP(i,a,b) for(int i=a,_b=b;i<=_b;i++)
#define rep(i,n) REP(i,0,n-1)
#define FORD(i,b,a) for(int i=b,_a=a;i>=_a;i--)
#define ford(i,n) FORD(i,n-1,0)
#define sqr(x) ((x)*(x))
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pi>
#define vll vector<ll>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define add push_back
#define len(arr) arr.size()
#define print(x) cout<<(x)<<endl
using namespace std;

vi a;
int dp[100005];

void init(){
	a.add(1);
	REP(i, 1, 6) a.add(pow(6, i));
	REP(i, 1, 5) a.add(pow(9, i));
	sort(all(a));
}


int main() {
	SPEED;
	//freopen("in.txt", "r", stdin);
	init();
	int N;
	cin >> N;
	
	REP(i, 1, N) dp[i] = N + 3;
	dp[0] = 1;
	for(auto x : a){
		REP(i, x, N) dp[i] = min(dp[i], dp[i - x] + 1);
	}
	
	print(dp[N] - 1);
	
	return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<map>
#include<vector>

using namespace std;
typedef long long ll;
int main()
{
  int N,n;
  cin >> N;
  map<ll,ll> exam1,exam2;
  for(int i=0;i<N;i++)
    {
      cin >> n;
      if(i == 0)
	{
	  exam1[n] = 1;
	  continue;
	}
      else if(i == N-1)
	cout << exam1[n] << endl;
      
      for(map<ll,ll>::iterator it = exam1.begin(); it != exam1.end();it++)
	{
	  int m,s;
	  s = (*it).first + n;
	  m = (*it).first - n;
	  if(20>= s)
	  exam2[s] += exam1[(*it).first];
	  if(m >= 0)
	    exam2[m] += exam1[(*it).first];	  
	}
      exam1 = exam2;
      exam2.clear();
    }
  
  return 0;
}

Measured memory_bytes: 1192
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
        int s[] = new int[5];
        int x1,x2,y1,y2,i;
        for(i = 0;i<5;i++){
            s[i] = sc.nextInt();
        }
        x1 = s[2]-s[4];
        x2 = s[2]+s[4];
        y1 = s[3]-s[4];
        y2 = s[3]+s[4];
        
        if(x1>=0&&x2<=s[0]){
            if(y1>=0&&y2<=s[1]){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
                sc.close();
                return;
            }
        }
        else{
            System.out.println("No");
        }
        
        sc.close();

	}

}


Measured memory_bytes: 26308
//#pragma GCC optimize ("O3")
//#pragma GCC target ("avx")
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<ll> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	ll mx=0;
	ll res=0;
	for(int i=0;i<n;i++){
		if(mx<=a[i]){
			mx=a[i];
		}
		else{
			res+=mx-a[i];
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 4836
import sys, re
def i_input(): return int(input())
def s_input(): return input()
sys.setrecursionlimit(10 ** 6)

def main():
    n = i_input()
    s = list(s_input())

    r_count = s.count('R')
    w_count = n - r_count

    if r_count == n or w_count == n:
        print(0)
        exit()

    r_s = s[::-1]

    count = 0

    index = 0
    for i in range(len(s)):
        if r_s[i] == 'W':
            continue
        for j in range(index, n - i - 1):
            if s[j] == 'R':
                index = j + 1
                continue
            index = j + 1
            count += 1
            break

    print(min(count, min(r_count, w_count)))

if __name__ == '__main__':
    main()


Measured memory_bytes: 79156
fun main(args: Array<String>) {
    var S = next().toCharArray()
    var f = false
    for (n in 1 until 4) {
        if (S[n-1] == S[n]) f = true
    }
    val ans = if (f) "Bad" else "Good"
    println("${ans}")
}
fun next() = readLine()!!


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

bool isPrime(int n) {
    if (n <= 2) return true;
    if (n % 2 == 0) return false;
    for (int i=3; i<=sqrt(n); i+=2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, sp, lp;
    while (cin >> n) {
        for (int i=n-1; i>=2; --i) {
            if (isPrime(i)) {
                sp = i;
                break;
            }
        }
        for (int i=n+1; i<=50021; ++i) {
            if (isPrime(i)) {
                lp = i;
                break;
            }
        }
        cout << sp << " " << lp << endl;
    }
    return 0;
}

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

using namespace std;
int main()
{
    int n;
    cin>>n;
    double a[n],b[n],t=0,c[n];
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    int f=1;
    for(int i=1;i<=n;i++){
        f=f*i;
    }
    //cout<<f<<endl;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            t=t+sqrt(pow((a[i]-a[j]),2)+pow((b[i]-b[j]),2));
        }
    }

    t=t*2/n;
    printf("%.6lf",t);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
bool graph[55][55] = {};
bool visited[55] = {};
int n, m;

void DFS(int x)
{
	if (visited[x]) return;
	visited[x] = true;
	for (int i = 0; i < n; i++){
		if (graph[x][i]){
			DFS(i);
		}
	}
}

int main() {
	cin >> n >> m;
	int p[m], q[m];
	for (int i = 0; i < m; i++){
		cin >> p[i] >> q[i];
		p[i]--; q[i]--;
		graph[p[i]][q[i]] = true;
		graph[q[i]][p[i]] = true;
	}

	int res = 0;

	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++) visited[j] = false;
		graph[p[i]][q[i]] = false;
		graph[q[i]][p[i]] = false;
		bool connected = true;
		DFS(0);
		for (int i = 0; i < n; i++){
			if (!visited[i]){
				connected = false;
				break;
			}
		}
		if (!connected) res++;
		graph[p[i]][q[i]] = true;
		graph[q[i]][p[i]] = true;
	}

	cout << res << endl;

}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int i,j,n,a;
    scanf("%d",&n);
    int day[n];
    for (j=1; j<=n; j++)
        {
        scanf("%d",&a);
        day[j] = a;
        } 
        
        for(i = n;i > 0; i--)
        {
            if(i>1)
            printf("%d ",day[i]);
            
            else
            printf("%d\n",day[i]);
            
        }
    return 0;
} 


Measured memory_bytes: 2104
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max({a * c, a * d, b * c, b * d}) << '\n';
}



Measured memory_bytes: 3656
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
struct node
{
	int id,a,b;
}a[N];
int n,i,j,k,b[N],p[N];
bool v[N];
bool cmp(node a,node b)
{
	return a.a<b.a;
}
bool cmq(node p,node q)
{
	return p.b<q.b;
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a[i].a);
		a[i].id=i;
	}
	for(i=1;i<=n;++i)
		scanf("%d",&a[i].b);
	sort(a+1,a+1+n,cmq);
	for(i=1;i<=n;++i)
		a[i].id=i;
	for(i=1;i<=n;++i)
		b[i]=a[i].b;
	sort(a+1,a+1+n,cmp);
	for(i=1;i<=n;++i)
		if(a[i].a>b[i])
		{
			printf("No");
			return 0;
		}
	for(i=1;i<=n;++i)
		p[a[i].id]=i;
	for(i=1,k=0;i<=n;++i)
		if(!v[i])
		{
			++k;
			for(j=i;!v[j];j=p[j])
				v[j]=true;
		}
	if(k>1)
	{
		printf("Yes");
		return 0;
	}
	for(i=2;i<=n;++i)
		if(a[i].a<=b[i-1])
		{
			printf("Yes");
			return 0;
		}
	printf("No");
	return 0;
}


Measured memory_bytes: 2176
INF = int(1e5)+5

def main():
    a, b, c, x, y = map(int, input().split())
    ans = INF*INF
    for i in range(INF):
        tmp = 2*i*c + a*max(x-i, 0) + b*max(y-i, 0) 
        ans = min(tmp, ans)
    print(ans)
main()


Measured memory_bytes: 3060
#if 1

#include <bits/stdc++.h>
using namespace std;
int n,m;
int q;
long long a[100005],b[100005];

int main()
{
    scanf("%d %d %d", &n, &m, &q);
    for(int i = 1;i <= n;i++)
    {
        scanf("%lld",&a[i]);
    }
    a[0] = -1e18;
    a[n+1] = 1e18;
    for(int i = 1;i <= m;i++)
    {
        scanf("%lld",&b[i]);
    }
    b[m+1] = 1e18;
    b[0] = -1e18;
    long long al,ar,bl,br,x,y,z;
    for(int i = 1;i <= q;i++)
    {
        scanf("%lld",&x);
        ar = upper_bound(a+1,a+n+1,x)-a;
        al = upper_bound(a+1,a+n+1,x)-a-1;
        br = upper_bound(b+1,b+m+1,x)-b;
        bl = upper_bound(b+1,b+m+1,x)-b-1;
        //cout << al << " " << ar << " " << bl << " " << br << '\n';
        printf("%lld\n",min(min(x-min(a[al],b[bl]),max(b[br],a[ar])-x),min(min(a[ar]-x,x-b[bl])*2+max(a[ar]-x,x-b[bl]),min(b[br]-x,x-a[al])*2+max(b[br]-x,x-a[al]))));
    }
}

#endif // 1++


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

#define int long long

using namespace std;



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

    int N;
    cin >> N;

    cout << (1000-N%1000)%1000 << '\n';

    return 0;
}

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

int main()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int ans = min(a, k);
    k -= min(a, k);
    k -= min(b, k);
    if (k)
    {
        ans -= min(k, c);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main() {
    long long int cub[2001]={}, x, i, j;
    cin>>x;
    for(i=0;i<=2000;i++)
    {
        cub[i]=(i-1000)*(i-1000)*(i-1000)*(i-1000)*(i-1000);
    }
    for(i=1;i<=1000;i++)
    {
        for(j=-1000;j<=1000;j++)
        {
            if((cub[i+1000]-cub[j+1000])==x)
            break;
        }
        if((cub[i+1000]-cub[j+1000])==x)
            break;
    }
    
    
    printf("%lld %lld", i, j);
    return 0;
}

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

#define PrintLn(X) cout << X << endl
#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define For(i, a, b) for(int i = a; i < (int)(b); ++i)
typedef long long ll;

int N, K;
ll x[50];
ll y[50];

ll minX;
ll maxX;
ll minY;
ll maxY;

int count()
{
	int res = 0;
	Rep(i, N){
		if(minX <= x[i] && x[i] <= maxX && minY <= y[i] && y[i] <= maxY){
			res++;
		}
	}
	return res;
}

int main(void)
{
	cin >> N >> K;
	Rep(i, N){
		cin >> x[i] >> y[i];
	}
	ll minS = 2000000000LL * 2000000000LL;

	Rep(a, N){
		For(b, a, N){
			For(c, b, N){
				For(d, c, N){
					minX = x[a];
					maxX = x[a];
					minY = y[a];
					maxY = y[a];
					if(x[b] < minX) minX = x[b];
					if(x[c] < minX) minX = x[c];
					if(x[d] < minX) minX = x[d];
					if(x[b] > maxX) maxX = x[b];
					if(x[c] > maxX) maxX = x[c];
					if(x[d] > maxX) maxX = x[d];
					if(y[b] < minY) minY = y[b];
					if(y[c] < minY) minY = y[c];
					if(y[d] < minY) minY = y[d];
					if(y[b] > maxY) maxY = y[b];
					if(y[c] > maxY) maxY = y[c];
					if(y[d] > maxY) maxY = y[d];
					if(minX == maxX) maxX++;
					if(minY == maxY) maxY++;
					ll S = (maxX - minX) * (maxY - minY);
					if(S < minS){
						if(count() >= K){
							minS = S;
						}
					}
				}
			}
		}
	}
	PrintLn(minS);

	return 0;
}


Measured memory_bytes: 256
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

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

	int n;
	cin>>n;
	vi in(n);
	rep(i,n)cin>>in[i];
	int c=0;
	rep(i,n-2)if(in[i+2]<in[i+1]&&in[i+1]<in[i]||in[i+2]>in[i+1]&&in[i+1]>in[i])c++;
	cout<<c<<endl;
}


Measured memory_bytes: 256
import itertools
N=int(input())
L=list(map(int,input().split()))
ans=0
itr=list(itertools.combinations(L,3))
for i in itr:
    if i[0]!=i[1] and i[1]!=i[2] and i[2]!=i[0]:
        if i[0]+i[1]>i[2]and i[1]+i[2]>i[0]and i[2]+i[0]>i[1]:
            ans+=1
print(ans)

Measured memory_bytes: 20624
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(a%500 <= b) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 21588
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

struct mint{
	ll x;
	mint(ll x=0):x((x%mod+mod)%mod){}
	friend ostream &operator<<(ostream& os,const mint& a){
		return os<<a.x;
	}
	friend istream &operator>>(istream& is,mint& a){
		ll t;
		is>>t;
		a=mint(t);
		return (is);
	}
	mint& operator+=(const mint a){
		if((x+=a.x)>=mod) x-=mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x+=mod-a.x)>=mod)x-=mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x*=a.x)%=mod;
		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 pow(ll t) const{
		if (!t) return 1;
		mint a=pow(t>>1);
		a*=a;
		if(t&1) a*=*this;
		return a;
	}
	// for prime mod
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this)*=a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
};

struct combination{
  vector<mint> fact,ifact;
  combination(int n):fact(n+1),ifact(n+1){
	assert(n<mod);
	fact[0]=1;
	for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i;
	ifact[n]=fact[n].inv();
	for(int i=n;i>=1;i--) ifact[i-1]=ifact[i]*i;
  }
  mint operator()(int n,int k){
	if (k<0 || k>n) return 0;
	return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	rep(i,n){
		cin>>a[i];
	}
	mint ans=0;
	combination comb(200000);
	sort(begin(a),end(a));
	rep(i,n){
		if(i>=k-1){
			ans+=comb(i,k-1)*a[i];
		}
	}
	reverse(begin(a),end(a));
	rep(i,n){
		if(i>=k-1){
			ans-=comb(i,k-1)*a[i];
		}
	}
	cout<<ans<<endl;
}

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

Measured memory_bytes: 128
#include <iostream>
#include <vector>
using namespace std;
const long long mod = (1e9)+7;

int main(){
  int H, W, K;
  cin >> H >> W >> K;
  vector<int> DP(W,0);
  DP[0] = 1;
  for(int i = 0; i < H; ++i){
    vector<int> DP_(W,0);
    for(int j = 0; j < (1<<(W-1)); ++j){
      bool f = false;
      for(int k = 1; k < W-1; ++k){
        if((j>>k)&1 and (j>>(k-1))&1){
          f = true;
          break;
        }
      }
      if(f) continue;
      for(int k = 0; k < W; ++k){
        if(k > 0 and (j>>(k-1))&1){
          DP_[k-1] += DP[k];
          DP_[k-1] %= mod;
        }else if((j>>k)&1){
          DP_[k+1] += DP[k];
          DP_[k+1] %= mod;
        }else{
          DP_[k] += DP[k];
          DP_[k] %= mod;
        }
      }
    }
    DP = DP_;
  }
  cout << DP[K-1] << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int temp[100001];

void MergeSort(int x[],int left,int right);


int main(void){
  int N,C,K;
  int T[100001];
  int i,j,k,ans=1,first_time,passenger;
  scanf("%d %d %d",&N,&C,&K);
  for(i=0;i<N;i++){
    scanf("%d",&T[i]);
  }
  MergeSort(T,0,N-1);
  first_time=T[0];
  passenger=0;
  for(i=0;i<N;i++){
    if(T[i]-K <= first_time && passenger < C){
      passenger++;
    }else{
      first_time=T[i];
      ans++;
      passenger=1;
    }
  }
  printf("%d\n",ans);
  return 0;
}

void MergeSort(int x[],int left,int right){
  int mid,i,j,k;
  if(left >= right) return;
  mid = (left+right)/2;
  MergeSort(x,left,mid);
  MergeSort(x,mid+1,right);

  for(i=left;i<=mid;i++) temp[i] = x[i];
  for(i=mid+1,j=right;i<=right;i++,j--) temp[i]=x[j];

  i=left;
  j=right;

  for(k=left;k<=right;k++){
    if(temp[i] <= temp[j]) x[k] = temp[i++];
    else x[k] = temp[j--];
  }
}


Measured memory_bytes: 896
/*
t.me/ivanesipovvpered
*/
#pragma ARCENIY_KIRILLOV_POVELITEL_KROKODILOV
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i > -1; i--)
#define rer(i, x, n) for (int i = x; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef long double ld;

const double EPS = 1e-5;
const int mod = 1e9 + 7;
const ll INFLL = 1e18;
const int INF = 1e9;
const int maxn = 1e6 + 3;

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

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

bool is_prime(ll a){
    if (a == 2 | a == 3 || a == 5 || a == 7) return true;
    if (a % 2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0)
        return false;
    for (ll i = 11; i * i <= a; i += 2){
        if (a % i == 0)
            return false;
    }
    return true;
}

ll binpow(ll a, int n){
    if (a == 0)
        return 1;
    if (a % 2 == 0){
        ll q = binpow(a, n / 2);
        return (q * q)  ;
    }else return (a * binpow(a, n - 1) ) ;
}





















main(){
    int n, k;
    cin >> n;
    k = 3;
    vi a(n), b(n), c(n);
    rep(i, n)
        cin >> a[i] >> b[i] >> c[i];
    int dp[n][k];
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];
    for (int i = 1; i < n; i++){
        dp[i][0] = max (dp[i - 1][1], dp[i-1][2]) + a[i];
        dp[i][1] = max (dp[i - 1][2], dp[i-1][0]) + b[i];
        dp[i][2] = max (dp[i - 1][0], dp[i-1][1]) + c[i];
    }
    cout << max({dp[n-1][0], dp[n-1][1], dp[n-1][2]});




}


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

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
int A,B,C,D;
int main(){
	fast;
	
  cin>>A>>B>>C>>D;
  
  if (ceil(double(C) / double(B)) > ceil(double(A) / double(D))) cout<<"No";
  else cout<<"Yes";
	
}



Measured memory_bytes: 3652
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  int ab[n][2], c[m][2];
  rep(i, n) cin >> ab[i][0] >> ab[i][1];
  rep(i, m) cin >> c[i][0] >> c[i][1];

  rep(i, n) {
    int index = 0, mini[] = {(int)2e8, (int)2e8};
    rep(j, m) {
      int a = abs(ab[i][0] - c[j][0]), b = abs(ab[i][1] - c[j][1]);
      if ((a + b) < (mini[0] + mini[1])) mini[0] = a, mini[1] = b, index = j;
    }
    cout << index + 1 << endl;
  }
  return 0;
}


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

int main(void){
    int N, M;;
    cin >> N >> M;
    int a, b;
    map<int, vector<int>> vec;
    long int sum = 0;
    for(int i = 0; i < N; i++){
        cin >> a >> b;
        vec[a].push_back(b);
    }
    priority_queue<int> q;
    for(int j = 1; j <= M; j++){
        for(int i = 0; i < vec[j].size(); i++){
            q.push(vec[j].at(i));
        }
        if(q.empty()) continue;
        sum += q.top();
        q.pop();
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 10880
#include <cstdio>
#include <map>

using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	map<int, int> a;
	for (int x, i = 0; i < n; ++i)
		scanf("%d", &x), ++a[x];
	int ans = n, tot = 0;
	for (auto x: a){
		while (x.second > 2)
			x.second -= 2, ans -= 2;
		tot += x.second == 2;
	}
	printf("%d\n", ans - (tot + 1 >> 1 << 1));
	return 0;
}


Measured memory_bytes: 4864
import java.util.Scanner;

public class Main
{
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
	int B = sc.nextInt();
	int C = sc.nextInt();
	if(B-A == C-B){
		System.out.print("YES");
	}	else
	{
		System.out.print("NO");

		// TODO 自動生成されたメソッド・スタブ

	}


	}

}


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

using namespace std;

int main(void) {
    int N, M, sum = 0, res;

    cin >> N >> M;

    vector<int> A(M);

    for (int i = 0; i < M; i++) {
        cin >> A.at(i);
        sum += A.at(i);
    }
    
    res = N - sum;
    if (res >= 0) {
        cout << res << endl;
    }
    else {
        cout << "-1" << endl;
    }

    return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 1<<30;
constexpr int mod = 1e9+7;
constexpr ll infl = 1ll<<60;

vector<bool> vis(55);
int n,m;
vector<vector<bool>> f(55,vector<bool>(55));
void dfs(int u){
        vis[u] = true;
        for(int v=0;v<n;++v){
            if(!f[u][v])continue;
            if(vis[v])continue;
            dfs(v);
        }
    }
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    cin>>n>>m;
    vector<pair<int,int>> p(m);
    for(int i=0;i<m;++i){
        int a,b;
        cin>>a>>b;
        a--;b--;
        f[a][b] = true;
        f[b][a] = true;
        p[i]={a,b};
    }
    int count = 0;

    for(int i=0;i<m;++i){
        f[p[i].first][p[i].second] = f[p[i].second][p[i].first] = false;
        for(int i=0;i<n;++i)vis[i] = false;
        dfs(0);
        bool bridge = false;
        for(int i=0;i<n;++i)if(!vis[i])bridge = true;
        if(bridge)count++;
        f[p[i].first][p[i].second] = f[p[i].second][p[i].first] = true;
        
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3664