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

const int N = 50 + 5;
int n,m;

struct node{
    int x, y;
    node(int x = 0,int y = 0):x(x), y(y){}
    bool operator < (const node& rhs) const {
        return x!=rhs.x? x<rhs.x:y<rhs.y;
    }
};

node stu[N], check[N];
int d[N][N];


int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    for (int i = 1; i <= n; i++){
        cin>>stu[i].x>>stu[i].y;
    }
    
    for (int j = 1; j <= m; j++){
        cin>>check[j].x>>check[j].y;
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            d[i][j] = abs(stu[i].x-check[j].x) + abs(stu[i].y - check[j].y);
        }
    }
    
    for (int i = 1; i <= n; i++){
        int mind = 1e9, pos = -1;
        for (int j = 1; j <= m; j++){
            if(d[i][j]<mind){
                mind = d[i][j];
                pos = j;
            }
        }
        cout<<pos<<endl;
    }

    
    
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
#define ll long long
#define REP(i, x) for(int (i) = 0; (i) < (x); (i) ++)
#define pi 3.1415926535
const int MOD = 1000000007;
using namespace std;

int main() {
	ll r, d, x;
	cin >> r >> d >> x;
	REP(i, 10) {
		x *= r;
		x -= d;
		cout << x << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define yes "yes"
#define Yes "Yes"
#define no "no"
#define No "No"

namespace mydef
{
  void say(string some){
    cout << some << "\n";
  }
} // namespace mydef
using namespace mydef;

typedef long long ll;

const int INF = 1001001001;

int a[12][12];

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> c(n);
  rep(i, n){
    cin >> c[i];
    rep(j, m) cin >> a[i][j];
  }

  int ans = INF;
  
  rep(s, 1<<n){
    int cost = 0;
    vector<int> d(m);
    rep(i, n){
      if(s>>i&1) {
        cost += c[i];
      rep(j, m) d[j] += a[i][j];
      }
    }
    bool ok = true;
    rep(j, m) if(d[j] < x) ok = false;
    if(ok) ans = min(ans, cost);

  }
  if(ans == INF) cout << -1 << endl;
  else cout << ans << "\n";


  return 0;
}




Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
     vector<int64_t> vec(87);
  vec.at(0)=2LL;
  vec.at(1)=1LL;
  int i;
  for(i=2;i<=n;i++){
    vec.at(i)=vec.at(i-1)+vec.at(i-2);
  }
  cout<<vec.at(n)<<endl;}

    

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define ALL(c) (c).begin(), (c).end()
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;}
const int MOD = 1000000007;
const int INF = 1000000001;

int main() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> v(n, 0);
    int a;
    REP(i, q) {
        cin >> a;
        a--;
        v[a]++;
    }

    REP(i, n) {
        if (k > q - v[i]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0; i<N; i++)

using namespace std;

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

  string ans = "";
  if(s == "Sunny") {
    ans = "Cloudy";
  }else if( s == "Cloudy"){
    ans = "Rainy";
  }else if( s == "Rainy"){
    ans = "Sunny";
  }

  cout << ans << endl;
}

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

def solve(h):
    if len(h)==1:
        return h[0]
    elif len(h)==0:
        return 0
    for i in range(len(h)):
        if h[i]==0:
            return solve(h[0:i]) + solve(h[i+1:len(h)])
    m = min(h)
    h = [hi-m for hi in h]
    return m + solve(h)

print(solve(h))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define MOD 1000000007
const int INF = 1LL<<30;

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

    ll ans=0;
    rep(i,n){
        ll sf=0;
        rep(j,i){
            if(a[i]>a[j]) sf++; 
        }
        ll tmp=sf;
        if(k%2==0){
            tmp=(tmp*(k/2))%MOD;
            tmp=(tmp*(k-1))%MOD;
        }
        else{
            tmp=(tmp*((k-1)/2))%MOD;
            tmp=(tmp*k)%MOD;
        }
        ans=(ans+tmp)%MOD;
        ll sb=0;
        for(int j=i+1;j<n;j++){
            if(a[i]>a[j]) sb++;
        } 
        tmp=sb;
        if(k%2==0){
            tmp=(tmp*(k/2))%MOD;
            tmp=(tmp*(k+1))%MOD;
        }
        else{
            tmp=(tmp*((k+1)/2))%MOD;
            tmp=(tmp*k)%MOD;
        }
        ans=(ans+tmp)%MOD;
    }

    cout<<ans<<endl;
}

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

int main()
{
    int n, m, e, a[101] = {0}, b[101] = {0}, c[101] = {0}, d[101] = {0};

    cin >> n;

    cin >> m;
    for( int i = 0; i < m; i++ )
    {
        cin >> e;
        a[e]++;
    }

    cin >> m;
    for( int i = 0; i < m; i++ )
    {
        cin >> e;
        b[e]++;
    }

    cin >> m;
    for( int i = 0; i < m; i++ )
    {
        cin >> e;
        c[e]++;
    }

    for( int i = 1; i <= n; i++ ){
        if( a[i] == 0 && c[i] == 1 || b[i] == 1 && c[i] == 1 )
            d[i]++;
    }
    
    int cnt = 0;
    
    for( int i = 1; i <= n; i++ ){
        if( d[i] == 1 )
            cnt++;
    }
    
    cout << cnt << endl;

    return 0;
}




Measured memory_bytes: 3116
h,w=map(int,input().split())
wall=[list(input()) for i in range(h)]
dp=[[0 for i in range(w)] for j in range(h)]
dp[0][0]=1
for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      continue
    tmp=0
    if i > 0 and wall[i-1][j]=='.':
      tmp+=dp[i-1][j]
    if j > 0 and wall[i][j-1]=='.':
      tmp+=dp[i][j-1]
    dp[i][j]+=tmp
print(dp[h-1][w-1] % 1000000007)



Measured memory_bytes: 245212
#include <bits/stdc++.h>
#define ll long long
#define PB push_back
#define MP make_pair

#define REP(i, n) for(int i=0;i<(int)(n);++i)
#define FOR(i,l,h) for(int i=(int)(l);i<=(int)(h);++i)
#define FORD(i,h,l) for(int i=(int)(h);i>=(int)(l);--i)

#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

#define dump(x)  cerr << #x << " = " << (x) << endl
#define ALL(t) (t).begin(),(t).end()

using namespace std;
const ll int INF = 1e9+5;
int n,m,l;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m>>l;
    //ll int gr[n+2][n+2];
    vector<vector<int> > gr(n+2,vector<int>(n+2,INF));

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            gr[i][j] = INF;
        }
        //cout<<"\n";
    }
    //memset(gr , INF , sizeof(gr));
    /*cout<<"graph is Before: \n";
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<gr[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        a--;b--;
        gr[a][b] = c;
        gr[b][a] = c;

    }
    //
    for(int i=0;i<n;i++){
        gr[i][i] = 0;
    }
    for(int k =0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                gr[i][j] = min(gr[i][j] , gr[i][k] + gr[k][j]);
                //dump(gr[i][j]);
            }
        }
    }
    vector<vector<int> > dist(n,vector<int>(n,INF));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(gr[i][j] <= l){
                dist[i][j] = 1; // sirf usi ko store kr rahe hai jo less
            }                // hai l se baki sab ko INF kr diye hai
        }                  // because unreacheble hoga
    }
    /*cout<<"graph is Before dist: \n";
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<dist[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    for(int k =0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
            }
        }
    }
    //dump(INF);

/*    cout<<"graph is after gr: \n";
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<gr[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"graph is after dist: \n";
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<dist[i][j]<<" ";
        }
        cout<<"\n";
    }
    //
    //floyd_warshall(gr);*/
    int t;cin>>t;
    while (t--) {
        int s1,t1;cin>>s1>>t1;
        s1--;t1--;
        if(dist[s1][t1] == INF){
            cout<<"-1\n";
        }
        else{
            //ll int ans = ceil(1.0*gr[s1][t1]/l) - 1 ;//question thora
            // different hai sahi se padho bich road me tank khali nahi
            // honi chahiye agar total distance / l karenge tohs ho saktA
            //  hain bich me kahile ho jaye
                  cout<<dist[s1][t1]-1<<"\n";
        }
    }
    return 0;
}


Measured memory_bytes: 1408
from copy import *

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
      x+=1
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and ((node[-1]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

N,K=map(int,input().split())
A=0
X=[]
init(300001,X,0,lambda x,y:max(x,y))
for i in range(N):
  A=int(input())
  upd(X,A,query(X,max(0,A-K),min(300001,A+K+1))+1)
print(X[0])


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

const int mod = 1e9 + 7, N = 1e5 + 10;

ll pw(ll a, ll b) {
    ll r = 1;
    for( ; b ; b >>= 1, a = a * a % mod) {
        if(b & 1) {
            r = r * a % mod;
        }
    }
    return r;
}

ll getinv(ll n) {
    return pw(n, mod - 2);
}

void upd(ll &a, ll b) {
    a = (a + b) % mod;
}

int main() {
    ll l, r;
    cin >> l >> r;
    ll ans = (l % 2019) * ((l + 1) % 2019) % 2019;
    for(ll i = l ; i <= r ; ++ i) {
        for(ll j = i + 1 ; j <= r ; ++ j) {
            ans = min(ans, (i % 2019) * (j % 2019) % 2019);
            if(!ans) {
                cout << 0 << endl;
                return 0;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<string>
#include<cmath>
#include <functional>
using namespace std;
int R(int Cx, int Cy, int x, int y) {
	return abs(x-Cx)+abs(y-Cy);
}
int main(void) {
	int N,A,B;
	cin >> N ;
	if (N == 1) {
		cout << "Hello World" << endl;
	}
	else
	{
		cin >> A >> B;
		cout << A+B << endl;
	}



	return 0;

}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

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 (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int n, m;
string str;
main(){
	cin >> str;
	reverse(ALL(str));
	cout << str << endl;
	return 0;
}

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

int main () {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> l(m);
    std::vector<int> r(m);
    for (int i = 0; i < m; i++) {
        std::cin >> l[i];
        std::cin >> r[i];
    }


    int L, R;
    L = l[0];
    R = r[0];
    for (int i = 1; i < m; i++) {
        if(L < l[i]) {
            L = l[i];
        }

        if(R > r[i]) {
            R = r[i];
        }
    }

    int ans;
    if(R - L >= 0) {
        ans = R - L + 1;
    } else {
        ans = 0;
    }

    std::cout << ans << std::endl;
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

typedef pair<int,int> P;

class HashP {
public :
    size_t operator()(const P& source) const {
        return source.first*1000+source.second;
    }
};

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

    vector<int> mp[H];
    vector<P> pool;

    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            int temp;
            cin >> temp;
            mp[i].push_back(temp);
        }
    }

    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) {
            if((i==0 || mp[i][j]<mp[i-1][j]) && (i==H-1 || mp[i][j]<mp[i+1][j])
                && (j==0 || mp[i][j]<mp[i][j-1]) && (j==W-1 || mp[i][j]<mp[i][j+1])) pool.push_back(P(i,j));
        }
    }

    queue<P> q;
    unordered_map<P,int,HashP> check,m;
    int dh[4]={-1,0,1,0};
    int dw[4]={0,1,0,-1};
    int ans=0;

    for(auto x : pool) {
        q.push(x);
        m.clear();
        while(!q.empty()) {
            P p=q.front(); q.pop();
            int h=p.first;
            int w=p.second;

            if(m[p]!=0) continue;
            m[p]=1; ++check[p];
            if(check[p]==2) ++ans;

            for(int i=0; i<4; ++i) {
                if(h+dh[i]>=0 && h+dh[i]<H && w+dw[i]>=0 && w+dw[i]<W 
                    && mp[h][w]<mp[h+dh[i]][w+dw[i]]) q.push(P(h+dh[i],w+dw[i]));
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 116792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n)     for (ll i = 0; i < (n); ++i)
#define rep2(i, a, b) for (ll i = (a); i < (b); ++i)
#define repin(a, n)  \
    vector<ll> a(n); \
    rep(i, n) { cin >> a[i]; }
#define repins(a, n)     \
    vector<string> a(n); \
    rep(i, n) { cin >> a[i]; }
#define repind(a, n)     \
    vector<double> a(n); \
    rep(i, n) { cin >> a[i]; }
#define in(a) \
    ll a;     \
    cin >> a;
#define ins(a) \
    string a;  \
    cin >> a;
#define ind(a) \
    double a;  \
    cin >> a;
template <class T>
inline void out(T a) {
    cout << a << endl;
}
inline void out(double a) { printf("%.10f\n", a); }
#define all(x)  (x).begin(), (x).end()    //昇順
#define rall(x) (x).rbegin(), (x).rend()  //降順
#define yes     out("Yes");
#define no      out("No");

int main() {
    in(n);
    ll ans = 0;

    vector<ll> d(n + 1);
    rep2(i, 1, n + 1) {
        for (ll j = i; j <= n; j += i) {
            d[j]++;
        }
    }
    rep2(c, 1, n) {
        ans += d[n - c];
    }
    out(ans);
}

Measured memory_bytes: 11176
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<float.h>
using namespace std;


int main() {
    string  a;
    cin >> a;
    if (a[0] == a[1] ) {
        if (a[0] == a[2]) {
            cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
    else if (a[3] == a[1]) {
        if (a[3] == a[2]) {
            cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
    else cout << "No" << endl;
  
    return 0;
}

Measured memory_bytes: 256
A,B,C=map(int,input().split())
K=int(input())
i=0
while A>=B:
  B=B*2
  i+=1
  if A<B:
    break
while B>=C:
  C=C*2
  i+=1
  if B<C:
    break
if i>K:
  print("No")
else:
  print("Yes")

Measured memory_bytes: 9184
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    vvl G(n+1);
    vl indeg(n+1);
    rep(i, n-1+m) {
        ll a, b;
        cin >> a >> b;
        G[a].pb(b);
        indeg[b]++;
    }

    queue<ll> Q;
    exrep(v, 1, n) {
        if(indeg[v] == 0) {
            Q.push(v);
        }
    }

    vl ans(n+1);
    while(!Q.empty()) {
        ll v = Q.front();
        Q.pop();
        for(auto u : G[v]) {
            indeg[u]--;
            if(indeg[u] == 0) {
                ans[u] = v;
                Q.push(u);
            }
        }
    }

    exrep(i, 1, n) {
        out(ans[i]);
    }
    
    re0;
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  while(1){
    int h,w,t,p;
    cin >> w >> h >> t >> p;
    if(h==0) return 0;
    vector<vector<int>> paper(2*h,vector<int>(2*w,0));
    rep(i,h) rep(j,w) paper[i][j]=1;
    int d,c;
    rep(tt,t){
      cin >> d >> c;
      if(d==1){
        rep(i,2*h){
          repp(j,c,2*w){
            if(2*c-j-1>=0) paper[i][j]+=paper[i][2*c-j-1];
          }
        }
        rep(i,2*h){
          rep(j,2*w-c){
            paper[i][j]=paper[i][j+c];
          }
          repp(j,2*w-c,2*w){
            paper[i][j]=0;
          }
        }
      }else{
        rep(j,2*w){
          repp(i,c,2*h){
            if(2*c-i-1>=0) paper[i][j]+=paper[2*c-i-1][j];
          }
        }
        rep(j,2*w){
          rep(i,2*h-c){
            paper[i][j]=paper[i+c][j];
          }
          repp(i,2*h-c,2*h){
            paper[i][j]=0;
          }
        }
      }
    }
    int x,y;
    rep(tt,p){
      cin >> x >> y;
      cout << paper[y][x] << endl;
    }
  }
  return 0;
}





Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string ans="";
    string temp="ACL";
    int k;
    cin>>k;
    while(k--){
        ans+=temp;
    }
    
    cout<<ans<<endl;
    return 0;
}

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

int main() {
    int n;
    vector<int> a, ans;
    cin >> n;
    a.assign(n+1, 0);
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=n;i>=1;i--){
        for(int j=2*i;j<=n;j+=i){
            if(a[j] == 1)a[i] ^= 1;
        }
        if(a[i] == 1){
            ans.push_back(i);
        }
    }
    cout << ans.size() << endl;
    for(int i=0;i<ans.size();i++){
        cout << ans[i] << " ";
    }
    cout << endl;
	return 0;
}

Measured memory_bytes: 2424
# 定義、入力
n, m, l = (int(i) for i in input().split())
A = [[0 for j in range(m)] for i in range(n)]
B = [[0 for k in range(l)] for j in range(m)]
C = [[0 for k in range(l)] for i in range(n)]

for i in range(n):
    A[i] = [int(j) for j in input().split()]
for j in range(m):
    B[j] = [int(k) for k in input().split()]

# Cの計算
for i in range(n):
    for k in range(l):
        for j in range(m):
            C[i][k] += A[i][j]*B[j][k]

# Cの出力
for row in C:
    L = [str(k) for k in row]
    L = " ".join(L)
    print(L)


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

const int SIZE = 1e5 + 5;

int N;
int M;
int required_days;
int reward;
vector<int> job_list[SIZE];

int main() {
  scanf("%d%d", &N, &M);

  for (int i = 0; i < N; i++) {
    scanf("%d%d", &required_days, &reward);
    if (M - required_days >= 0) {
      // 0-M日後の期限内に実行できる仕事であれば候補とする
      // 添字が 0     -> 初日にのみ行える仕事
      // 添字が M - 1 -> 期限の一日前に行っても良い仕事
      job_list[M - required_days].push_back(reward);
    }
  }

  priority_queue<int> pq;

  long long ans = 0;
  for (int i = M - 1; i >= 0; i--) {
    // 期日の後ろから仕事を決定していく
    for (int j = 0; j < job_list[i].size(); j++) {
      // 優先順位付きキューにより報酬の降順に、実行可能な仕事を追加する
      pq.push(job_list[i].at(j));
    }

    if (pq.size()) {
      // 実行可能な仕事のうち、最も報酬の高い仕事を取りだす
      ans += pq.top();
      pq.pop();
    }
  }

  printf("%lld", ans);
  return 0;
}


Measured memory_bytes: 5632
#include <math.h>
#include <iostream>
#include<string>
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#include <stdlib.h>
using namespace std;

vector<bool> seen;
vector<int> first_order;
vector<int> last_order;

void dfs(const vector<vector<int>> &G, int v, int& count)
{
first_order[v]=count+1;
count++;
seen[v]=true;
for(auto next_v : G[v])
{
if(seen[next_v])continue;
dfs(G, next_v, count);
}
last_order[v]=count+1;
count++;
}

int main()
{
int n,u,k;scanf("%d", &n);
vector<vector<int>> G(n);
for(int i=0;i<n;i++)
{
scanf("%d %d", &u, &k);
for(int i=0;i<k;i++){int v;scanf("%d", &v);G[u-1].push_back(v-1);}
}
seen.assign(n,false);
first_order.resize(n);
last_order.resize(n);
int count=0;
for(int i=0;i<n;i++){if(seen[i])continue;dfs(G, i, count);}
for(int i=0;i<n;i++){printf("%d %d %d\n", i+1, first_order[i], last_order[i]);}
}



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

# define x first
# define y second
# define mp make_pair
// everything goes according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right

//put debug temp

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput(const char in[] = "s") {
  if (fopen (in, "r")) {
    freopen (in, "r", stdin);
  }
  else
    cerr << "Warning: Input file not found" << endl;
}


int main()
{
  # ifdef Local
    //localInput();
  # endif
  Read_rap();
  int n;
  cin >> n;
  for (int i = 1; i; i++) {
  	n -= i;
  	if (n <= 0) {
  		cout << i;
  		return 0;
  	}
  }

  return 0;
}





// Coded by Z..

Measured memory_bytes: 256
N = input()
if N[-1] == '2' or N[-1] == '4' or N[-1] == '5' or N[-1] == '7' or N[-1] == '9':
  print('hon')
elif N[-1] == '0' or N[-1] == '1' or N[-1] == '6' or N[-1] == '8':
  print('pon')
else:
  print('bon')

Measured memory_bytes: 9120
Num500, Num100, Num50, sum = [int(input()) for i in range(4)]

count=0
for i_500 in range(Num500+1):
    for i_100 in range(Num100+1):
        for i_50 in range(Num50+1):
            if 500 * i_500 + 100 * i_100 + 50 * i_50 == sum:
                count += 1

print(count)

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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int N; cin >> N;
    string S, T; cin >> S >> T;
    string res;
    REP(i, N) {
        res.push_back(S[i]);
        res.push_back(T[i]);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int d[200001];
	int e[200001];
	int n,m;
	int a;
	int b;
	cin >> n >> m;
	for(int i=0;i<n;i++)
	{
		d[i] = 0;
		e[i] = 0;
	}
	for(int i=0;i < m;i++)
	{
		cin >> a >> b;
		if(a == 1)
		{
			d[b-1] = 1;
		}
		else if(b == n)
		{
			e[a-1] = 1;
		}
	}
	for(int i=1;i < n-1;i++)
	{
		if(d[i] && e[i])
		{
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	cout << "IMPOSSIBLE" << endl;
	return 0;
}

Measured memory_bytes: 1792
N = int(input())

num = set()
for n in range(2, 10**7):
    if N % n == 0:
        num.add(tuple(sorted([n, N//n])))
    if N == n:
        break
ans = (10**12, 10**12)
if not num:
    print(N - 1)
else:
    for s in num:
        if s[0]+s[1] < ans[0]+ans[1]:
            ans = s
    print(ans[0] + ans[1] - 2)

Measured memory_bytes: 9332
#include <stdio.h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,t,b[MAX],e[MAX];
int A[MAX][MAX];
int color [MAX];

void dfs_init();
void dfs(int);

int main(){
  int i,j,u,k,v;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      A[i][j]=0;
    }
  }

  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      A[u][v]=1;
    }
  }

  dfs_init();
  
  return 0;
}

void dfs_init(){
  int i;
  for(i=0;i<n;i++){
    color[i]=WHITE;
  }
  t=0;

  for(i=0;i<n;i++){
    if(color[i]==WHITE) dfs(i);
  }
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,b[i],e[i]);
  }
}

void dfs(int i){
  int j;
  color[i]=GRAY;
  b[i]=++t;
  for(j=0;j<n;j++){
    if(A[i][j]==0) continue;
    if(color[j]==WHITE) dfs(j);
  }
  color[i]=BLACK;
  e[i]=++t;
}

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

int main() {
  int N, D;
  cin >> N >> D;
  int k;
  if (N%(2*D+1) ==0)  {
    k = N / (2*D + 1);
  } else {
    k = N / (2*D + 1) + 1;
  }
  
  cout << k << endl;
}


Measured memory_bytes: 256
<?php
    $s = explode(' ', trim(fgets(STDIN)));
    $n = (int)$s[0];
    $k = (int)$s[1];
 
    // 最初にひけるだけひく
 
    if ((int)$n > (int)$k) {
    // echo floor($n / $k) . PHP_EOL;
    // echo (int)$n . PHP_EOL;
    // echo (int)$k . PHP_EOL;
    // echo (int)(floor($n / $k)) * ((int)$k). PHP_EOL;
    
    $n = (int)$n % (int)$k;
    
    //$n = (int)$n - ((int)(floor((int)$n / (int)$k)) * (int)$k); 
    }        
    //echo $n . PHP_EOL;
 
    while (true) {
        # code...
        // echo 'n1 = ' . $n . PHP_EOL;
        // echo 'k1 = ' . $k . PHP_EOL;

        $a = abs((int)$n - (int)$k);
        
        // echo 'a = ' . $a . PHP_EOL;
 
        if ((int)$n > (int)$a){
            $n = (int)$a;
        } else {
            break;
        }
        
        //echo 'n = ' . $n . PHP_EOL;
    }
    echo $n;
?>

Measured memory_bytes: 3828
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct node{
  int p;
  int left;
  int right;
};
struct node T[MAX];
int n,D[MAX],H[MAX];

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

int setH(int u){
  int h1=0,h2=0;
  if(T[u].left!=NIL)h1=setH(T[u].left)+1;
  if(T[u].right!=NIL)h2=setH(T[u].right)+1;
  return H[u]=(h1>h2 ? h1 : h2);
}

int getS(int u){
  if(T[u].p==NIL)return NIL;
  if(T[T[u].p].left != u && T[T[u].p].left!=NIL)return T[T[u].p].left;
  if(T[T[u].p].right != u && T[T[u].p].right!=NIL)return T[T[u].p].right;
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("sibling = %d, ",getS(u));
  int deg=0;
  if(T[u].left!=NIL)deg++;
  if(T[u].right!=NIL)deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

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

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

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



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

int main() {
  int h,w;cin>>h>>w;
  vector<vector<char>> a(h,vector<char>(w));
  rep(i,h)rep(j,w)cin>>a[i][j];
  vector<bool> H(h),W(w);
  rep(i,h)rep(j,w){
    if(a[i][j]=='#')H[i]=W[j]=true;
  }
  rep(i,h){
    if(H[i]){
      rep(j,w){
        if(W[j])cout<<a[i][j];
        if(j==w-1)cout<<endl;
      }
    }
  }
}

Measured memory_bytes: 3596
MOVE_LIST = [
    [1,4],
    [0,2,5],
    [1,3,6],
    [2,7],
    [0,5],
    [1,4,6],
    [2,5,7],
    [3,6]
]

def swap(figure, n, m)
  tmp = figure.dup
  tmp[n], tmp[m] = tmp[m], tmp[n]
  tmp
end

def width_search(answers, queue)
  loop do
    move_num, figure = queue.shift
    break unless figure

    current_idx = figure.index('0')
    MOVE_LIST[current_idx].each do |new_idx|
      new_figure = swap(figure, current_idx, new_idx)
      next if answers[new_figure]
      answers[new_figure] = move_num + 1
      queue << [move_num + 1, new_figure]
    end
  end
  answers
end

goal = '01234567'
answers = { goal => 0 }
queue = [[0, goal]]
answers = width_search(answers, queue)

loop do
  str = gets.to_s.chomp.split(' ').map(&:to_i).join('')
  break if str.size == 0
  puts answers[str]
end

Measured memory_bytes: 12756
# include <bits/stdc++.h>
typedef long long lint;
using namespace std;

lint gcd(lint x, lint y) {
  if(x == 0) { return y; }
  else { return gcd(y%x,x); }
}

lint lcm(lint x, lint y) { return x/gcd(x,y)*y; }

lint C(lint n, lint k) {
  if(n == k) { return 1; }
  else if(n < k) { return 0; }
  else if(k == 0) { return 1; }
  else if(k == 1) { return n; }
  else return C(n-1,k-1) + C(n-1,k);
}

lint P(lint n, lint k) {
  if(k == 1) { return n; }
  return (n*(P(n-1,k-1)%1000000007)%1000000007);
}

int main() {
  lint n; cin >> n;
  vector<lint> a(n); for(int i=0;i<n;i++) { cin >> a[i]; }

  sort(a.begin(),a.end(),greater<lint>());
  lint n_max=a[0], r_max=a[1];
  for(lint i=2;i<n;i++) {
    if(abs(r_max-n_max/2) > abs(a[i]-n_max/2)) { r_max = a[i]; }
  }

  printf("%lld %lld\n",n_max,r_max);
  return 0;
}


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

int cnt;
int a[4005][3];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	string s;
	cin>>n>>s;
	
	for(int i=0; i<n; i++)
	{
		for(int j=i; j<n; j++)
		{
			if(s[j]=='R')
				a[i][0]++;
			else if(s[j]=='G')
				a[i][1]++;
			else if(s[j]=='B')
				a[i][2]++;
		}
	}
	
	for(int i=0; i<n-2; i++)
	{
		for(int j=i+1; j<n-1; j++)
		{
			if(s[j]!=s[i])
			{
				char re;
				if(s[i]!='R' && s[j]!='R')
					re='R';
				else if(s[i]!='G' && s[j]!='G')
					re='G';
				else if(s[i]!='B' && s[j]!='B')
					re='B';
				if(re=='R')
					cnt+=a[j+1][0];
				else if(re=='G')
					cnt+=a[j+1][1];
				else if(re=='B')
					cnt+=a[j+1][2];
				if(2*j-i<n && s[2*j-i]==re)
					cnt--;
			}
		}
	}
	
	cout<<cnt<< endl;
	return 0;
}


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

typedef long long ll;
struct edge{
    int to;
    ll cost;
    edge(int t, ll c) : to(t), cost(c) {}
};

vector<edge> tree[100001];
ll d[100001];

void dfs(int v, int p, ll c){
    d[v] = c;
    for(edge e : tree[v]){
        if(e.to == p)   continue;
        dfs(e.to, v, c+e.cost);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    
    int a, b;
    ll c;
    for(int i = 1; i < n; i++){
        scanf("%d %d %lld", &a, &b, &c);
        a--, b--;
        tree[a].push_back(edge(b,c));
        tree[b].push_back(edge(a,c));
    }

    int q, k;
    scanf("%d %d", &q, &k);

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

    int x, y;
    for(int i = 0; i < q; i++){
        scanf("%d %d", &x, &y);
        printf("%lld\n", d[--x]+d[--y]);
    }

    return 0;
}

Measured memory_bytes: 14336
/*
 * main.cpp
 *
 *  Created on: 2017/05/14
 *      Author: YamajiTakashi
 */

#include <iostream>
#include <string>
#include <stdint.h>
using namespace std;

void print_seq(int32_t *seq_, int32_t len_) {
	string str = "";
	for (int32_t i = 0; i < len_ ; i++) {
		str += to_string(seq_[i]) + ' ';
	}
	str.erase(--str.end());
	cout << str << endl;
}

int main(void) {
	uint32_t N;
	cin >> N;
	int32_t *A = new int32_t[N];

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

	print_seq(A, N);

	for (int32_t i = 1; i < N; i++) {
		int32_t v = A[i];
		int32_t j = i - 1;
		while(j >= 0 && A[j] > v) {
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = v;
		print_seq(A, N);
	}

}

Measured memory_bytes: 3236
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(" ").map(String::toInt).toMutableList()
    val bList = readLine()!!.split(" ").map(String::toInt)

    var count: Long = 0
    for (i in n-1 downTo 0) {
        val b = bList[i]
        if (aList[i+1] <= b) {
            count += aList[i+1]
            val b2 = b - aList[i+1]
            if (aList[i] <= b2) {
                count += aList[i]
                aList[i] = 0
            } else {
                count += b2
                aList[i] -= b2
            }
        }else{
            count += b
        }
    }
    println(count)
}

Measured memory_bytes: 82500
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
xx = lr()
x = sorted(xx)
min_m = x[n//2-1]
max_m = x[n//2]
for num in xx:
    if num <= x[n//2-1]:
        print(max_m)
    else:
        print(min_m)

Measured memory_bytes: 109672
#include <bits/stdc++.h>
using namespace std;
typedef  long long int ll;
#define pb push_back
typedef long double ld;
#define fi first
#define se second
#define mp make_pair
ll p=1e9+7;
ll inf=1e18;
vector<vector<ll>>adj(2001);
vector<ll>used(2001,0);
vector<ll>ans(2001,0);
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll i,j,w,h,y,r,k,d,m,t,a,b,n,x,temp;
	string s;
	cin>>s;
	if(s=="ABC")
	cout<<"ARC";
	else
	cout<<"ABC";
	return 0;
	
	
}

Measured memory_bytes: 3696
#include<bits/stdc++.h>
#define N 100010
#define RG register
using namespace std;
bool odd[N],even[N];
int a,b,k,n,v,hd[N],lef[N],num[N],rig[N],to[N<<1],nex[N<<1];
inline int gi(){
    RG int x=0;RG bool flag=0;RG char c=getchar();
    while((c<'0'||c>'9')&&c!='-') c=getchar();
    if(c=='-') c=getchar(),flag=1;
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return flag?-x:x;
}
inline bool dfs1(RG int x,RG int f){
    if(odd[x]||even[x])
	lef[x]=rig[x]=num[x];
    for (RG int i=hd[x];i;i=nex[i])
	if(f!=to[i]){
	    if(!dfs1(to[i],x)) return 0;
	    if((odd[x]&&odd[to[i]])||(even[x]&&even[to[i]])) return 0; 
	    if(!odd[x]&&!even[x]){
		if(odd[to[i]])  even[x]=1,lef[x]=lef[to[i]]-1,rig[x]=rig[to[i]]+1;
		if(even[to[i]]) odd[x]=1, lef[x]=lef[to[i]]-1,rig[x]=rig[to[i]]+1;
	    }
	    else if(odd[to[i]]||even[to[i]]){
		if(lef[to[i]]-1>rig[x]||rig[to[i]]+1<lef[x]) return 0;
		lef[x]=max(lef[x],lef[to[i]]-1);
		rig[x]=min(rig[x],rig[to[i]]+1);
	    }
	}
    return 1;
}
inline void dfs2(RG int x,RG int f){
    if(x==1&&(odd[x]||even[x])) num[x]=lef[x];
    if(!odd[x]&&!even[x]) lef[x]=rig[x]=num[x];
    for (RG int i=hd[x];i;i=nex[i])
	if(to[i]!=f){
	    if(!num[to[i]]){
		if(odd[to[i]]||even[to[i]])
		    if(num[x]-1>=lef[to[i]]&&num[x]-1<=rig[to[i]]) num[to[i]]=num[x]-1;
		    else                                           num[to[i]]=num[x]+1;
		else
		    num[to[i]]=num[x]-1;
	    }
	    dfs2(to[i],x);
	}
}
int main(){
    n=gi();
    for (RG int i=1;i<n;++i){
	a=gi();b=gi();
	to[i<<1]=b;  nex[i<<1]=hd[a];  hd[a]=i<<1;
	to[i<<1|1]=a;nex[i<<1|1]=hd[b];hd[b]=i<<1|1;
    }
    k=gi();
    for (RG int i=1;i<=k;++i){
        v=gi();
	num[v]=gi();
	if(num[v]&1) odd[v]=1;
	else         even[v]=1;
    }
    if(!dfs1(1,0)){
	puts("No");
	return 0;
    }
    puts("Yes");
    dfs2(1,0);
    for (RG int i=1;i<=n;++i)
	printf("%d\n",num[i]);
    return 0;
}

Measured memory_bytes: 6784
import sys

input = sys.stdin.readline

h, n = map(int, input().split())

magics = []
max_cost = 0
for _ in range(n):
    at, cost = map(int, input().split())
    max_cost = max(max_cost, cost)
    magics.append((at, cost))

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(len(dp)):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
print(min(dp[h:]))



Measured memory_bytes: 41964
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<long long int> a;
    long long int temp;

    for (int i = 0; i < n; i++) {
        cin >> temp;
        a.push_back(temp);
    }

    long long int ans = 0;
    long long int temp2;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (a[i] != a[j] && a[j] != a[k] && a[i] != a[k]) {
                    temp2 = a[i] + a[j] + a[k];
                    if (temp2 > 2 * a[i] && temp2 > 2 * a[j] && temp2 > 2 * a[k]) {
                        ans++;
                    }
                }
            }
        }
    }

    cout << ans / 6;
    

    return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<cmath>

int main() {
  int N;
  std::cin >> N;
  int t=0, x=0, y=0;
  int flag = 0;
  for (int i=0; i<N; i++) {
    int temp_t, temp_x, temp_y;
    std::cin >> temp_t >> temp_x >> temp_y;
    int t_diff = temp_t - t;
    int x_diff = temp_x - x;
    int y_diff = temp_y - y;
    t = temp_t;
    x = temp_x;
    y = temp_y;
    if (t_diff%2 != std::abs((x_diff + y_diff)%2) || t_diff < std::abs(x_diff)+std::abs(y_diff)) {
      flag = 1;
      break;
    }
  }
  if (flag) {
    std::cout << "No" << std::endl;
  }
  else {
    std::cout << "Yes" << std::endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <algorithm>
#include <vector>

int compare (const void *a, const void *b) {
  long long *A = (long long *)a;
  long long *B = (long long *)b;
  int ans = 0;
  if (*A < *B) {
    ans = 1;
  }
  if (*A > *B) {
    ans = -1;
  }
  return ans;
}

int main() {
  long long int n,m,i,j;
  scanf("%lld",&n);
  scanf("%lld",&m);
  long long int x[n],y[n],z[n];
  for(i=0;i<n;i++) {
    scanf("%lld",&x[i]);
    scanf("%lld",&y[i]);
    scanf("%lld",&z[i]);
  }
  long long int xs, ys, zs;
  long long int sum[n];
  long long int ans = -1000000000;
  for(xs=-1;xs<2;xs+=2) {
    for(ys=-1;ys<2;ys+=2) {
      for(zs=-1;zs<2;zs+=2) {
        for(j=0;j<n;j++) {
          sum[j] = xs * x[j] + ys* y[j] + zs* z[j];
        }
        qsort(sum, n, sizeof(long long int), compare);
        long long int anstemp = 0;
        for(j=0;j<m;j++) {
          anstemp += sum[j];
        }
        if(ans < anstemp) {
          ans = anstemp;
        }
      }
    }
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

A, B, K = map(int, input().split())

def operate(x, y):
    if x % 2 == 1:
        x -= 1
    x //= 2
    return (x, y + x)

for k in range(K // 2):
    A, B = operate(A, B)
    B, A = operate(B, A)
if K % 2 == 1:
    A, B = operate(A, B)

print(A, B)


Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int main()
{
    char a[10];
    int i;
    cin>>a;
    char b='8';
    for(int i=0; i<10; i++)
    {
        if(i==3) cout<<b;
        else cout<<a[i];

    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 500010
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,D,Q;
int pos[maxn];
ll f[maxn];
int d[maxn];
int main()
{
    n=read();D=read();
    for(int i=1;i<=n;i++)  d[i]=read();
    pos[0]=D;
    for(int i=1;i<=n;i++)  pos[i]=min(pos[i-1],abs(pos[i-1]-d[i]));
    f[n+1]=1;
    for(int i=n;i>=1;i--)
    {
        if(d[i]>=f[i+1]*2)  f[i]=f[i+1];
        else                f[i]=f[i+1]+d[i];
    }
    Q=read();
    while(Q--)
    {
        int x=read();
        if(pos[x-1]>=f[x+1])  puts("YES");
        else                  puts("NO");
    }
    return 0;
}

Measured memory_bytes: 9728
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int H = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int r = sc.nextInt();
        
        inOrOut(W, H, x, y, r);
        
    }
    public static void inOrOut(int W, int H, int x, int y ,int r){
        Boolean circleCheck = true;
        if(x < r || x + r > W){
            circleCheck = false;
        }else if(y < r || y + r > H){
            circleCheck = false;
        }
        
        if(circleCheck == true){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
        
    }
}



Measured memory_bytes: 26176
#include<stdio.h>

int main(void){
	int a, b, c, d, n = 0;
	int ans = 0;
	
	while(scanf("%d", &n) != EOF){
		ans = 0;
		if(n <= 36){
			for(a = 0; a <= 9; a++){
				for(b = 0; b <= 9; b++){
					for(c = 0; c <= 9; c++){
						for(d = 0; d <= 9; d++){
							if(a + b + c + d ==n){
								ans++;
							}
						}
					}
				}
			}
			printf("%d\n", ans);
		}else{
			printf("0\n");
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

long long n;
long long a[100005] = {0}, b[100004] = {0};
bool ch[100005] = {0};
vector<pair<pair<long long, long long>, long long>> v[2];

long long solve();

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) cin >> a[i] >> b[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long ans = 0;
  long long l = 0, r = 0;
  for(int i = 0; i < n; ++i) {
    v[0].push_back(
        make_pair(make_pair(a[i] + b[i], b[i]), a[i]));
    v[1].push_back(
        make_pair(make_pair(a[i] + b[i], a[i]), i));
  }

  for(int i = 0; i < 2; ++i)
    sort(
        v[i].begin(), v[i].end(),
        greater<
            pair<pair<long long, long long>, long long>>());
  for(int i = 0; i < n; ++i) {
    if(i % 2 == 0) { ans += v[0][i].se; }
    else {
      ans -= v[0][i].fi.se;
    }
  }
  return ans;
}

Measured memory_bytes: 8744
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn=new Scanner(System.in);
		int n=scn.nextInt();
		int x=scn.nextInt();
		for(int i=x-n+1;i<=x+n-1;i++) {
			System.out.print(i+" ");
		}
	}

}


Measured memory_bytes: 23764
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n, k;
const int maxN = (int)1e5 + 10;
int a[maxN];
ll pref[maxN];
ll prefMax[maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
        prefMax[i] = prefMax[i - 1] + max(a[i], 0);
    }
    ll best = 0;
    for (int i = 1; i + k - 1 <= n; i++) {
        best = max(best, max(pref[i + k - 1] - pref[i - 1], 0LL) + prefMax[i - 1] + (prefMax[n] - prefMax[i + k - 1]));
    }
    cout << best;
    return 0;
}

Measured memory_bytes: 2176