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

// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //

#define int                                       long long
#define lop(i,s,e)                                for(int i=s;i<(int)e;i++)
#define rlop(i,e,s)                               for(int i=e;i>=s;i--)
#define prvec(v)                                  lop(R15,0,v.size())cout << v[R15] <<" "; cout << endl;
#define prarr(arr,s1,e1)                          lop(R15,s1,e1)cout << arr[R15] << " "; cout << endl;

#define endl                                      '\n'
#define ff                                        first
#define ss                                        second
#define pii                                       pair<int,int>

#define pb                                        push_back
#define all(v)                                    v.begin(),v.end()

// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //
#define bug(...)                                  __f (#__VA_ARGS__, __VA_ARGS__)
#define rtn                                       if(0)return;
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { rtn cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{    rtn
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 3e6 + 7, M = 1000000007, inf = INT_MAX;
const long long INF = LLONG_MAX;

class quad
{
public:
     int a, b, c, d;

};
vector<quad> res;
int n, m, q;
int arr[N + 2];
int cnt = 0, ans = 0;

void print(int id, int x, vector<int> &vec)
{
     if (id == n)
     {
          cnt++;
          int sum = 0;
          lop(i, 0, q)
          {
               if ( vec[ res[i].b ] - vec[ res[i].a ] == res[i].c ) sum += res[i].d;
          }
          ans = max(ans, sum);
          return;
     }

     lop(i, x, m + 1)
     {
          vec.pb(i);
          print(id + 1, i, vec);
          vec.pop_back();
     }
}
void solve()
{
     cin >> n >> m >> q;
     res.resize(q);
     lop(i, 0, q)
     {
          cin >> res[i].a >> res[i].b >> res[i].c >> res[i].d;
          res[i].a--;
          res[i].b--;
     }

     vector<int> vec;
     print(0, 1, vec);
     // bug(cnt);

     cout << ans << endl;

}

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

     cout << setprecision(9) << fixed;
     clock_t z = clock();

     int test = 1;
     // cin >> test;
     while (test--)solve();
     // cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);


}





Measured memory_bytes: 3688
import java.util.*;
public class Main 
{
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int T = in.nextInt();
		ArrayList<Integer> arr = new ArrayList<Integer>();
		for (int i = 0 ; i < N ; i++)
		{
			int c = in.nextInt();
			int t = in.nextInt();
			if (t <= T)
			{
				arr.add(c);
			}
		}
		if (arr.size() == 0)
		{
			System.out.println("TLE");
			return;
		}	
		int ans = arr.get(0);
		for(int i = 0; i < arr.size(); i++)
		{
			if(ans > arr.get(i))
				ans = arr.get(i);
		}
		System.out.println(ans);
	}
}

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

int main(){
    int n;  cin >> n;
    if(n%10==9 || (n-n%10)/10 == 9){
	cout << "Yes" << endl;
    }else{
	cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdlib>
#include <queue>
#include <utility>
#include <climits>
using namespace std;

struct edge{
    int to;
    long long cost;
    edge(const int to_, const long long cost_):to(to_), cost(cost_){}
};

using Graph = vector<vector<edge>>;

vector<long long> bfs(const Graph& G, const int s){
    vector<long long> d(G.size(), LONG_MAX);
    queue<int> q;
    q.push(s);
    d[s] = 0;
    vector<bool> visited(G.size(), false);

    while(!q.empty()){
        const int current_v = q.front();
        q.pop();
        visited[current_v] = true;

        for(const auto& e : G[current_v]){
            if(visited[e.to]) continue;
            q.push(e.to);
            d[e.to] = d[current_v] + e.cost;
        }
    }

    return d;
}

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

    Graph G(n);
    for(int i = 0; i < n-1; ++i){
        int a, b; 
        long long c;
        cin >> a >> b >> c;
        a--; b--;

        G[a].emplace_back(edge(b, c));
        G[b].emplace_back(edge(a, c));
    }

    int q, k; cin >> q >> k;
    k--;

    vector<long long> d = bfs(G, k);

    for(int i = 0; i < q; ++i){
        int x, y; cin >> x >> y;
        x--; y--;

        cout << d[x] + d[y] << endl;
    }

    return EXIT_SUCCESS;
}


Measured memory_bytes: 10112
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
 
int main(){
	int n,q;
	cin>>n>>q;
	int s[n],t[n],x[n];
	rep(i,n)cin>>s[i]>>t[i]>>x[i];
	set<pair<int,int>> st;
	rep(i,q){
		int a;
		cin>>a;
		st.insert({a,i});
	}
	st.insert({inf,-1});
	vector<int> ord(n);
	iota(ord.begin(),ord.end(),0);
	sort(ord.begin(),ord.end(),[&](int u,int v){
		return x[u]<x[v];
	});
	vector<int> ans(q,-1);
	for(auto i : ord){
		auto itr=st.lower_bound({-x[i]+s[i],-1});
		while(itr->first<-x[i]+t[i]){
			ans[itr->second]=x[i];
			itr=st.erase(itr);
		}
	}
	for(auto e : ans)cout<<e<<endl;
	return 0;
}

Measured memory_bytes: 15232
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int a,b;

int main(){
  cin >> a >> b;
  if(a + b == 15){
    cout << "+" << endl;
  }
  else if(a * b == 15){
    cout << "*" << endl;
  }
  else{
    cout << "x" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;

class UnionFind {
  public:
  // 親の番号を格納。ルートだった場合は-(その集合のサイズ)
  vector<ll> parents;

  UnionFind(ll N) {
    parents = vector<ll>(N, -1);
  }

  // iがどのグループに属しているか
  ll root(ll i) {
    if (parents[i] < 0) {
      return i;
    } else {
      return parents[i] = root(parents[i]);
    }
  }

  // iが属しているグループの大きさ
  ll size(ll i) {
    return -parents[root(i)];
  }

  // root(a)とroot(b)を接続する
  bool connect(ll a, ll b) {
    ll rootA = root(a);
    ll rootB = root(b);
    if (rootA == rootB) {
        return false;
    } else {
      // 大きいほう(a)に小さいほう(b)をくっつける
      // 大小が逆の場合はスワップ
      if (size(rootA) < size(rootB)) {
        swap(rootA, rootB);
      }

      // aグループのサイズを増やす
      parents[rootA] += parents[rootB];
      // bの親をaのルートに変更する
      parents[rootB] = rootA;

      return true;
    }
  }

};

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> A(M), B(M);
	for (int i = 0; i < M; i++)
	{
		cin >> A[i] >> B[i];
		A[i]--;
		B[i]--;
	}

	vector<long long> ans(M);
	ans[M - 1] = (long long)N * (N - 1) / 2;

	UnionFind Uni(N);

	for (int i = M - 1; i >= 1; i--)
	{
		ans[i - 1] = ans[i];

		//繋がってなかったのが繋がった時
		if (Uni.root(A[i]) != Uni.root(B[i])) {
			ans[i - 1] -= (long long)Uni.size(A[i]) * Uni.size(B[i]);
			Uni.connect(A[i], B[i]);
		}
	}

	for (int i = 0; i < M; i++)
	{
		cout << ans[i] << endl;
	}
}



Measured memory_bytes: 3712
# -*- coding: utf-8 -*-
"""
C - 2D Plane 2N Points
https://beta.atcoder.jp/contests/abc091/tasks/arc092_a

"""
import sys
from sys import stdin
from collections import namedtuple, deque
input = stdin.readline


edge = namedtuple('edge', ['to', 'cap', 'rev'])

def add_edge(G, f, t, c):
    G[f].append(edge(t, c, len(G[t])))
    G[t].append(edge(f, 0, len(G[f]) - 1))


def bfs(G, level, s):
    for i in range(len(level)):
        level[i] = -1
    que = deque()
    level[s] = 0
    que.append(s)
    while que:
        v = que.popleft()
        for e in G[v]:
            if e.cap > 0 and level[e.to] < 0:
                level[e.to] = level[v] + 1
                que.append(e.to)


def dfs(G, iter, level, v, t, f):
    if v == t:
        return f
    for i in range(iter[v], len(G[v])):
        e = G[v][i]
        if e.cap > 0 and level[v] < level[e.to]:
            d = dfs(G, iter, level, e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
                return d
    return 0


def max_flow(G, V, s, t):
    level = [0] * V
    flow = 0
    while True:
        bfs(G, level, s)
        if level[t] < 0:
            return flow
        iter = [0] * V
        while True:
            f = dfs(G, iter, level, s, t, float('inf'))
            if f > 0:
                flow += f
            else:
                break


def main(args):
    """
    - 追加したソースノードID: 0
    - 赤い点ID: 1〜N
    - 青い点ID: N+1 〜2N
    - 追加したシンクノードID: 2N + 1(2N + 2 - 1)
    として、ノード0 → 2N+1 への最大流を求める
    """
    N = int(input())
    G = [[] for _ in range(N*2 + 2)]
    red_points = []
    for ri in range(1, N+1):
        rx, ry = map(int, input().split())
        red_points.append([rx, ry])
        add_edge(G, 0, ri, 1)   #  ソースノードは全ての赤い点と繋ぐ

    for bi in range(1, N+1):
        bx, by = map(int, input().split())
        add_edge(G, bi+N, N*2+1, 1) #  全ての青い点はシンクノードに繋ぐ
        for i, r in enumerate(red_points, start=1):
            rx = r[0]
            ry = r[1]
            if rx < bx and ry < by:
                add_edge(G, i, bi+N, 1) #  仲良しペアを作ることができるので辺を作成

    ans = max_flow(G, 2*N+2, 0, 2*N+1) #  ソースとシンク間の最大流
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3956
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 (a == 5 && b == 5 && c == 7 ||
        a == 5 && b == 7 && c == 5 ||
        a == 7 && b == 5 && c == 5)
      System.out.println("YES");
    else
      System.out.println("NO");
  }
}

Measured memory_bytes: 21844
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0643
n, m = list(map(int, input().split()))
A = [[0 for _ in range(m)] for _ in range(n)]

rowA = [0 for _ in range(n)]
colA = [0 for _ in range(m)]

for i in range(n):
    for j, Aij in enumerate(input().split()):
        aij = int(Aij)
        A[i][j] = aij
        # rowA[i] += aij
        # colA[j] += aij

# maxR = rowA.index(max(rowA))
# maxC = colA.index(max(colA))

mdist = float("Inf")
for maxR in range(n):
    for maxC in range(m):
        dist = 0
        for i in range(n):
            if i == maxR:
                continue
            for j in range(m):
                if j == maxC:
                    continue

                dr = abs(i - maxR)
                dc = abs(j - maxC)
                dist += min(abs(i - maxR), abs(j - maxC)) * A[i][j]
        mdist = min(dist, mdist)

print(mdist)

# print(A)
# print(rowA)
# print(colA)
# print(maxR, maxC)


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int a,b,k; cin>>a>>b>>k;
	for(int i=a;i<min(a+k,b);++i)cout<<i<<"\n"s;
	for(int i=min(b,max(b-k+1,a+k));i<=b;++i)cout<<i<<"\n"s;
}

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



#define SIZE 100005


int N;
ll max_data[SIZE*8],add_data[SIZE*8];

void init(ll first_N){
	while(N < first_N)N *= 2;
}

void add(int left,int right,ll value,int node_id,int node_left,int node_right){

	if(right < node_left || left > node_right){
		return;
	}
	else if(left <= node_left && right >= node_right){

		add_data[node_id] += value;

		while(node_id != 0){

			node_id = (node_id-1)/2;
			max_data[node_id] = max(max_data[2*node_id+1]+add_data[2*node_id+1],max_data[2*node_id+2]+add_data[2*node_id+2]);
		}
	}else{

		add(left,right,value,2*node_id+1,node_left,(node_left+node_right)/2);
		add(left,right,value,2*node_id+2,(node_left+node_right)/2+1,node_right);
	}
}


ll getMax(int left,int right,int node_id,int node_left,int node_right){
	if(right < node_left || left > node_right)return -HUGE_NUM;
	else if(left <= node_left && right >= node_right){
		return max_data[node_id]+add_data[node_id];

	}else{

		ll  left_max  = getMax(left,right,2*node_id+1,node_left,(node_left+node_right)/2);
		ll  right_max = getMax(left,right,2*node_id+2,(node_left+node_right)/2+1,node_right);
		return max(left_max,right_max)+add_data[node_id];
	}
}

int main(){

	int first_N,Q;
	scanf("%d %d",&first_N,&Q);

	N = 1;
	init(first_N);

	for(ll i = 0; i <= 2*N-2; i++){
		max_data[i] = 0;
		add_data[i] = 0;
	}

	int from,to;
	ll num;

	int tmp = 0;

	for(int loop = 0; loop < Q; loop++){

		scanf("%d %d %lld",&from,&to,&num);
		from--;
		to--;

		while(tmp < to){
			tmp++;
			add(tmp,N-1,1,0,0,N-1);
		}

		add(from,to,num,0,0,N-1);
		printf("%lld\n",getMax(0,N-1,0,0,N-1));
	}

	return 0;
}



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

// 最大公約数
long long gcd(long long a, long long b) {
   if (a%b == 0) {
       return(b);
   } else {
       return(gcd(b, a%b));
   }
}

// 最小公倍数
long long lcm(long long a, long long b) {
   return a * b / gcd(a, b);
}

int main(){
    long long A, B, C, D; cin >> A >> B >> C >> D;

    // B以下のCの倍数の個数とB以下のDの倍数の個数を足し、両者で重複したものを引く。
    long long b_c = B / C;
    long long b_d = B / D;
    long long b_c_d = B / lcm(C, D);

    long long a_c = (A - 1) / C;
    long long a_d = (A - 1) / D;
    long long a_c_d = (A - 1) / lcm(C, D);

    cout << (B - ((b_c + b_d) - b_c_d)) - (((A - 1) - a_c - a_d) + a_c_d)  << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
 #include<functional>

#define INPUT_FROM_FILE (0) 
#if INPUT_FROM_FILE
#include <fstream>
#endif

int main(int argc, char **argv){
	std::vector<int> v(5);

#if INPUT_FROM_FILE
	std::ifstream ifs("test.txt");
#endif

#if INPUT_FROM_FILE
	ifs >> v[0] >> v[1] >> v[2] >> v[3] >> v[4];
#else
	std::cin >> v[0] >> v[1] >> v[2] >> v[3] >> v[4];
#endif

	std::sort(v.begin(), v.end(), std::greater<int>());
	
	std::cout << v[0];
	for(int i = 1; i < 5; i++){
		std::cout << " " << v[i];
	}
	std::cout << std::endl;
	return 0;
}


Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MOD = 998244353;

int n, ga, gb, sa, sb, ba, bb;
LL maxg[25000005];

int main()
{
	scanf("%d%d%d%d%d%d%d", &n, &ga, &sa, &ba, &gb, &sb, &bb);
	
	rep1(i, n) maxg[i] = 0;
	rep1(i, n) {
		maxg[i] = maxg[i - 1] + 1;
		if(i >= ga) maxg[i] = max(maxg[i], maxg[i - ga] + gb);
		if(i >= sa) maxg[i] = max(maxg[i], maxg[i - sa] + sb);
		if(i >= ba) maxg[i] = max(maxg[i], maxg[i - ba] + bb);
	}
	
	n = maxg[n];
	swap(ga, gb);
	swap(sa, sb);
	swap(ba, bb);
	
	rep1(i, n) maxg[i] = 0;
	rep1(i, n) {
		maxg[i] = maxg[i - 1] + 1;
		if(i >= ga) maxg[i] = max(maxg[i], maxg[i - ga] + gb);
		if(i >= sa) maxg[i] = max(maxg[i], maxg[i - sa] + sb);
		if(i >= ba) maxg[i] = max(maxg[i], maxg[i - ba] + bb);
	}
	
	printf("%lld\n", maxg[n]);
	return 0;
}

Measured memory_bytes: 195584
//==============================================================================================================
//     Anything is possible as long as you keep working at it , and don't back it down.( Believe That )   
//==============================================================================================================
//"Everything in the universe is balanced. Every disappointment
//  you face in life will be balanced by something good for you!
//             Keep going, never give up."           
//==============================================================================================================
/*------U Have To DO It------*/
#include<bits/stdc++.h>
using namespace std;
#define fast() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll  long long
#define f(i,a,b) for(int i=a; i<b; i++)
#define ff(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define MP make_pair
#define int long long int
#define vi vector<int>
#define M map<int,int >
#define F     first
#define S    second
#define lb lower_bound
#define ub upper_bound
#define mem(a,n)  memset(a, n, sizeof(a))
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(),x.rend())
#define std(v) sort(v.begin(),v.begin(),greater<int>()); 
#define double   long long  double
const int N = 2e3+5;
bool visit[N];
vi v[N];
int a[N];
int val;
int root;
int cnt=0;
int q[N];
signed main()
{
fast();
int n;
cin>>n;
cout<<n*n*n;;

return 0;
 

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <cstdio>
#include <complex>
#include <numeric>
#include <string.h>
#include <random>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
double PI = 3.141592653589793238462643383279;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int n;
ll a[100001];
bool tmp[100001];
ll A = 0;
ll ans = 0;
map<int, vector<int>> v;

int main() {
    cin >> n;
    rep(i,n) cin >> a[i];
    /*
    rep(i,n) {
        cout << bitset<10>(a[i]) << endl;
    }
    */
    rep(i,n) A ^= a[i];
    for (ll i = 59; i >= 0; i--) {
        if (A&(1LL<<i)) {
            ans += (1LL<<i);
            continue;
        }
        /*
        if (i == 0) {
        cerr << "v" <<  " " << ans << endl;
        for (auto it = v.begin(); it != v.end(); it++) {
            cerr << (*it).first << endl;
            vector<int> &hoge = (*it).second;
            rep(i,hoge.size()) cerr << hoge[i] << " ";
            cerr << endl;
        }
        }
        */
        memset(tmp, 0, sizeof(tmp));
        int f = inf;
        rep(j,n) {
            if (!(a[j]&(1LL<<i))) continue;
            tmp[j] = true;
            f = min(f,j);
        }
        if (f == inf) continue;
        tmp[n] = true;
        for (auto it = v.begin(); it != v.end(); it++) {
            if (!tmp[(*it).first]) { continue; }
            if ((*it).first > f) {  continue; }
            vector<int> &tv = (*it).second;
            f = inf;
            rep(j,tv.size()) {
                tmp[tv[j]] ^= 1;
                if (tmp[tv[j]]) f = min(f,tv[j]);
            }
            /*
            if (i == 0) {
                cerr << f << endl;
                for (int _ = 0; _ <= n; _++) {
                    cerr << tmp[_];
                }
                cerr << endl;
            }
            */
        }
        vector<int> tv;
        f = inf;
        rep(j,n+1) {
            if (tmp[j]) {
                tv.push_back(j);
                f = min(f,j);
            }
        }
        if (tv.size() == 0) {
            ans += (1LL<<i)*2;
            continue;
        }
        if (f == n) {
            continue;
        }
        ans += (1LL<<i)*2;
        v[f] = tv;
    }
    cout << ans << endl;
}

Measured memory_bytes: 13112
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n,a[201001]={};
	cin>>n;
	priority_queue<pair<int,int>> pq;
	map<int,int> mp;
	LL ans=0LL;
	FOR(i,0,n){
		cin>>a[i];
		pq.push(MP(-a[i],i+1));
	}
	mp[0]=1;mp[n+1]=1;
	while(pq.size()){
		pair<int,int> pr=pq.top();
		pq.pop();
		pr.ST=-pr.ST;
		mp[pr.ND]=1;
		auto it=mp.find(pr.ND);
		auto itl=--it;
		it++;
		auto itr=++it;
		it--;
		ans+=1LL*pr.ST*(it->ST-itl->ST)*(itr->ST-it->ST);
		//cerr<<pr.ST<<" "<<ans<<endl;
	}

	cout<<ans;
    return 0;
}


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

int main(){
	int Q;
	cin >> Q;
	long long ans=0;
	int a=0;
	vector<long long> ans1;
	vector<long long> ans2;
	priority_queue<long long> que1;
	priority_queue<long long,vector<long long>,greater<long long>> que2;
	for(int q=0;q<Q;q++){
		int c;
		cin >> c;
		if(c==1){
			long long a,b;
			cin >> a >> b;
			ans+=b;
			if(q==0){
				que1.push(a);
				que2.push(a);
			}
			else{
				if(a<que1.top()){
					ans+=que1.top()-a;
					que2.push(que1.top());
					que1.pop();
					que1.push(a);
					que1.push(a);
				}
				else if(a>que2.top()){
					ans+=a-que2.top();
					que1.push(que2.top());
					que2.pop();
					que2.push(a);
					que2.push(a);
				}
				else{
					que1.push(a);
					que2.push(a);
				}
			}
			//printf("que1.top=%lld,que2.top=%lld\n",que1.top(),que2.top());
		}
		else{
			ans1.push_back(que1.top());
			ans2.push_back(ans);
			a++;
		}
	}
	for(int i=0;i<a;i++)cout << ans1[i] << " " << ans2[i] << endl;
	return 0;
}

Measured memory_bytes: 6100
#include <cstdio>

int g[300000];
int i,m,n,s,t;

int main()
{
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d",&g[i]);
	t=1;
	for (i=2;i<=n;i++)
		if (g[i]-g[t]>=m)
			if (g[i]-g[i-1]>=m)
				s=s+g[i-1]-g[t]+m,t=i;
			else
				s=s+g[i-1]-g[t],t=i-1;
	if (t!=n)
		s=s+g[n]-g[t];
	s=s+m;
	printf("%d",s);
	return 0;
}

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

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

using namespace std;

typedef pair<int,int> P;
#define P_NUM 4

void Move2Zero(P p0,P &p1) {
    p1.first -= p0.first;
    p1.second -= p0.second;
}

void MoveFromZero(P p0,P &p1,P &p2,P &p3){
    p1.first += p0.first;
    p1.second += p0.second;

    p2.first += p0.first;
    p2.second += p0.second;

    p3.first += p0.first;
    p3.second += p0.second;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    //[[0,-1],[1,0]]

    P p0;
    P p1;
    P p2;
    P p3;

    cin >> p0.first;
    cin >> p0.second;

    cin >> p1.first;
    cin >> p1.second;

    Move2Zero(p0,p1);

    p2.first = p1.first - p1.second;
    p2.second = p1.first + p1.second;

    p3.first = -p1.second;
    p3.second = p1.first;

    MoveFromZero(p0,p1,p2,p3);

    printf("%d %d %d %d", p2.first,p2.second,p3.first,p3.second);


    return 0;
}

Measured memory_bytes: 256
def p_d():
    x, y = map(int, input().split())
    if y > x:
        x, y = y, x
    if (x + y) % 3 != 0:
        print(0)
        exit()
    if x - y > (x + y) // 3:
        print(0)
        exit()
    x, y = x - (x + y) // 3, y - (x + y) // 3

    mod = 10 ** 9 + 7  # 出力の制限
    N = x + y
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return g1[n] * g2[r] * g2[n - r] % mod

    print(cmb(x + y, y, mod))
    
p_d()

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

using namespace std;

int main() {
	int K, T,before,ans = 0;
	cin >> K >> T;
	vector<int> a(T);
	for (int i = 0; i < T; i++)cin >> a[i];

	//まずは一番多いケーキを食べる
	int idx = max_element(a.begin(), a.end()) - a.begin();
	a[idx]--;
	before = idx;
	for (int i = 1; i < K; i++) {
		//一番多くてbeforeでないケーキを食べる
		int maxC = 0;
		idx = 0;
		for (int j = 0; j < a.size(); j++) {
			if (maxC < a[j] && before != j) idx = j, maxC = a[j];
		}
		//ケーキを食べきってないにも関わらずmaxCが０の時一番大きなケーキだけが余ってるということなのでそれがans
		if (maxC == 0) { ans = *max_element(a.begin(), a.end()); break; }
		//さってケーキ食べりゅうううう
		a[idx]--;
		before = idx;
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define rint register int
using namespace std;
const int N=200001;
int n,f[N][21],g[N][21],a[N],Log[N];
ll ans=0;
inline int read()
{
	int s=0; char ch;
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s; 
}
int ask1(int l,int r)//区间[l,r]的最小值
{
  	int k=Log[r-l+1];
  	if(f[l][k]<f[r-(1<<k)+1][k])
  	  return f[l][k];
  	return f[r-(1<<k)+1][k];
} 
int ask2(int l,int r)//区间[l,r]的最小值的位置 
{
	int k=Log[r-l+1];
	if(f[l][k]<f[r-(1<<k)+1][k])
	  return g[l][k];
	return  g[r-(1<<k)+1][k];
} 
inline void solve(int l,int r)
{
  	if(r<l) return;
  	if(l<0||r<0) return;
	int mid=ask2(l,r);  ;
  	solve(l,mid-1),solve(mid+1,r);
  	ans+=(ll)(mid-l+1)*(r-mid+1)*ask1(l,r);
  	
} 
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
  n=read(); Log[1]=0; 
  for(int i=2;i<=200000;i++)
    Log[i]=Log[i>>1]+1;  
  for(int i=1;i<=n;i++) a[i]=read(),f[i][0]=a[i],g[i][0]=i;
  for(int i=1;i<=Log[n]+1;i++)
    for(int j=1;j+(1<<i)-1<=n;j++)
      {
        if(f[j][i-1]<f[j+(1<<(i-1))][i-1])
        {
        	f[j][i]=f[j][i-1];
        	g[j][i]=g[j][i-1];
		}
		else f[j][i]=f[j+(1<<(i-1))][i-1],g[j][i]=g[j+(1<<(i-1))][i-1];
	  }
  solve(1,n);
  printf("%lld\n",ans);
  return 0;
}


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


int main()
{
	int a, b, c, x;
	cin >> a >> b >> c >> x;
	int ans = 0;
	int total;
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				total = i * 500 + j * 100 + k * 50;
				if (total == x) {
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
from sys import stdin

n, m = [int(x) for x in stdin.readline().rstrip().split()]
hn = list(map(int, input().split()))

route_map = {}


def add_routemap(a, b):
    if a not in route_map:
        route_map[a] = [b]
    else:
        route_map[a].append(b)


def add_route(a, b):
    add_routemap(a, b)
    add_routemap(b, a)


for i in range(1, m+1):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    add_route(a, b)

#print(route_map)

sum = 0
for i in range(n):
    good = True
    me = hn[i]
    number = i+1
    if number in route_map:
        for j in range(len(route_map[number])):
            other = hn[route_map[number][j]-1]
            if me <= other:
                good = False
                break
    #print(number,good)
    if good:
        sum +=1

print(sum)

Measured memory_bytes: 96480
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int main(void) {
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;
        int a[n];
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }

        int mindif = 10000000;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                mindif = min(mindif, abs(a[i] - a[j]));
            }
        }

        cout << mindif << endl;
    }
    return 0;
}


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

int main(){
  int64_t lenS,lenT;
  string S,T;
  cin >> lenS >> lenT >> S >> T;

  int64_t cand= lcm(lenS, lenT);
  int64_t Nmatch= gcd(lenS, lenT);
  int64_t fracS= lenS/ Nmatch;
  int64_t fracT= lenT/ Nmatch;

  bool satisfied= true;
  for(int64_t i=0; i<Nmatch; i++){
    satisfied= satisfied && (S.at(i* fracS)==T.at(i* fracT));
  }

  int64_t ans= satisfied ? cand
                         : -1;
  cout << ans << endl;
}

Measured memory_bytes: 3772
public class Main {
	public static void main(String args[]) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
		int N = sc.nextInt();
		int[] H = new int[N];
		int max = 0;

		int cnt = 0;
		H[0] = sc.nextInt();
		for (int i = 1; i < N; i++) {
			H[i] = sc.nextInt();
			if (H[i - 1] < H[i]) {
				max = Math.max(max, cnt);
				cnt = 0;
			} else {
				cnt++;
			}
		}
		max = Math.max(max, cnt);
		System.out.println(max);
	}
}

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

int main(){
    int N,M;
    cin >> N >> M;
    int S[M];
    int C[M];
    for (int i = 0; i < M; i++){
        cin >> S[i];
        cin >> C[i];
    }

    int X[N];
    int Y[N];
    for (int i = 0; i < N; i++){
        X[i] = 0;
        Y[i] = 0;
    }

    int s,c;
    int flg = 0;

    for (int i = 0; i < M; i++){
        s = S[i] - 1;
        c = C[i];
        if (Y[s] == 1){
            if (X[s] != c){
                flg = 1;
                break;
            }
        }
        X[s] = c;
        Y[s] = 1;
    }

    if (flg == 1) {
        cout << -1 << endl;
        return 0;
    }

    if (N == 3){
        if (X[0] == 0 && Y[0] == 1){
            cout << -1 << endl;
            return 0;
        }
        else if (X[0] == 0 && Y[0] == 0) cout << 100 + 10 * X[1] + X[2] << endl;
        else cout << 100 * X[0] + 10 * X[1] + X[2] << endl;
    }
    if (N == 2){
        if (X[0] == 0 && Y[0] == 1){
            cout << -1 << endl;
            return 0;
        }
        else if (X[0] == 0 && Y[0] == 0) cout << 10 + X[1] << endl;
        else cout << 10 * X[0] + X[1] << endl;
    }
    if (N == 1){
        cout << X[0] << endl;
    }


}

Measured memory_bytes: 256
//*in the name of GOD*\\

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef long double ld;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int main(){
  string n;
  cin >> n;
  cout << "ABC" << n;
}


Measured memory_bytes: 256
#include <stdio.h>

//int check(int);

int main(void) {

	int n, i, x;

	scanf("%d", &n);

	for (i = 3; i < n + 1; i++) {
		x = i;
		if (x % 3 == 0) {
			printf(" %d", i);
		}
		else {
			while (1) {
				if (x == 0) {
					break;
				}

				if (x % 10 == 3) {
					printf(" %d", i);
					break;
				}
				else {
					x = x / 10;
				}
			}
		}
	}

	puts("");

	return 0;
}


Measured memory_bytes: 2080
using namespace std;
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#define w(x) int x;cin>>x;while(x--)

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

#define ll long long

void abc()
{
	FIO;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int mod = 1000000007;
vector<int> dp;
vector<int> v;


int go( int i) {

	if (i >= v.size() ) return INT_MAX / 2;
	if (i == v.size() - 1) return 0;
	if (dp[i] != -1) return dp[i];

	int x = INT_MAX / 2, y = INT_MAX / 2;

	if (i + 1 < v.size()) {
		x = abs(v[i] - v[i + 1]) + go(i + 1);
	}
	if (i + 2 < v.size()) {
		y = abs(v[i] - v[i + 2]) + go(i + 2);
	}

	return dp[i] = min(x, y);



}



int main()
{
	abc();


	int n;
	cin >> n;
	v.resize(n);
	dp.resize(n, -1);

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

	cout << go(0) << endl;








}

Measured memory_bytes: 8648
//https://atcoder.jp/contests/abc154/tasks/abc154_b
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int len;
    string s;
    cin>>s;
    len = s.length();
    while(len--) printf("x");
    printf("\n");   

    return 0;
}



Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final Scanner sc  = new Scanner(System.in);
    static final int     MOD = (int) 1E9 + 7;
    
    public static void main(String[] args) {
        int A = nint();
        int B = nint();
        System.out.println(Math.max(A - B * 2, 0));
    }
    
    private static int nint() {
        return sc.nextInt();
    }

    private static int[] nints(int n) {
        return nints(n, 0, 0);
    }

    private static int[] nints(int n, int padL, int padR) {
        int[] a = new int[padL + n + padR];
        for (int i = 0; i < n; i++)
            a[padL + i] = nint();
        return a;
    }

    private static long nlong() {
        return sc.nextLong();
    }

    private static long[] nlongs(int n) {
        return nlongs(n, 0, 0);
    }

    private static long[] nlongs(int n, int padL, int padR) {
        long[] a = new long[padL + n + padR];
        for (int i = 0; i < n; i++)
            a[padL + i] = nlong();
        return a;
    }

    private static double ndouble() {
        return sc.nextDouble();
    }

    private static double[] ndoubles(int n) {
        return ndoubles(n, 0, 0);
    }

    private static double[] ndoubles(int n, int padL, int padR) {
        double[] d = new double[n + padL + padR];
        for (int i = 0; i < n; i++) {
            d[padL + i] = ndouble();
        }
        return d;
    }

    private static String nstr() {
        return sc.next();
    }

    private static char[] nchars() {
        return sc.next().toCharArray();
    }

    private static char[] nchars(int padL, int padR) {
        char[] temp = sc.next().toCharArray();
        char[] ret = new char[temp.length + padL + padR];
        System.arraycopy(temp, 0, ret, padL, temp.length);
        return ret;
    }

    private static char[][] nchars2(int h, int w) {
        return nchars2(h, w, 0, 0);
    }

    private static char[][] nchars2(int h, int w, int padLU, int padRD) {
        char[][] a2 = new char[h + padLU + padRD][w + padLU + padRD];
        for (int i = 0; i < h; i++)
            System.arraycopy(nchars(), 0, a2[padLU + i], padLU, w);
        return a2;
    }

    private static long min(long... ls) {
        return Arrays.stream(ls).min().getAsLong();
    }

    private static int min(int... is) {
        return Arrays.stream(is).min().getAsInt();
    }

    private static long max(long... ls) {
        return Arrays.stream(ls).max().getAsLong();
    }

    private static int max(int... is) {
        return Arrays.stream(is).max().getAsInt();
    }

    private static long abs(long a, long b) {
        return Math.abs(a - b);
    }
}


Measured memory_bytes: 23124
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 2000001

struct Node{
  int key;
  struct Node *next,*prev;
};
  
struct Node *nil;
  
struct Node* listSearch(int key){
  struct Node *cur=nil->next;
  while(cur!=nil&&cur->key!=key){
    cur=cur->next;
  }
  return cur;
}
  
void init(){
  nil=(struct Node *)malloc(sizeof(struct Node));
  nil->next=nil;
  nil->prev=nil;
}
  
void output(){
  struct Node *cur=nil->next;
  int i=0;
  while(1){
    if(cur==nil) break;
    if(i++>0) printf(" ");
    printf("%d",cur->key);
    cur=cur->next;
    }
  printf("\n");
}
  
void delNode(struct Node *t){
  if(t==nil) return;
  t->prev->next=t->next;
  t->next->prev=t->prev;
  free(t);
}
  
void delF(){
  delNode(nil->next);
}
  
void delL(){
  delNode(nil->prev);
}
  
void delKey(int key){
  delNode(listSearch(key));
}
  
void insert(int key){
  struct Node *a=(struct Node *)malloc(sizeof(struct Node));
  a->key=key;
  a->next=nil->next;
  nil->next->prev=a;
  nil->next=a;
  a->prev=nil;
}
  
int main(){
  int n,key,i,j,npoi=0,ndel=0,size=0;
  char c[12];
  
  scanf("%d",&n);
  
  init();
  for(i=0;i<n;i++){
    scanf("%s %d",c,&key);
  
    if(c[0]=='i'){
      insert(key);
      npoi++;
      size++;
    }
    else if(c[0]=='d'){
if(strlen(c)>6){
      if(c[6]=='F') delF();
      else if(c[6]=='L') delL();
    } else {
        delKey(key);
        ndel++;
      }
        size--;
      }
    }
    output();
  return 0;
}



Measured memory_bytes: 32964
// Author: getharshkumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n, a, b;
    cin >> n >> a >> b;
    if ((b - a) % 2 == 0)
        cout << (b - a) / 2;
    else
        cout << min(a + (b - a - 1) / 2, n - b + 1 + (n - (a + n - b + 1)) / 2);
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:

    int func(string S) {
        vector<string> vs;
        int idx = 0;
        for (; idx < S.size();) {
            if (idx == 0) {
                string tmp = S.substr(idx, 1);
                vs.push_back(tmp);
                idx++;
            } else {
                string tmp = S.substr(idx, 1);
                if (tmp == vs.back() && idx + 2 <= S.size()) {
                    tmp = S.substr(idx, 2);
                    vs.push_back(tmp);
                    idx += 2;
                } else {
                    vs.push_back(tmp);
                    idx++;
                }
            }
        }
        if (vs.size() > 2 && vs[vs.size() - 1] == vs[vs.size() - 2]) {
            return vs.size() - 1;
        }
        return vs.size();
    }

    void solve() {
        string S;
        cin >> S;

        int val1 = func(S);
        reverse(all(S));
        int val2 = func(S);
        int ans = max(val1,val2);

        cerr << val1 << " " << val2 << endl;
        cout << ans << endl;

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


Measured memory_bytes: 11968
#include<bits/stdc++.h>
using namespace std;
const int maxn = 606, mod = 119<<23|1;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> a(3*n);
	for(auto &i : a) cin >> i;sort(a.rbegin(), a.rend());
	long long ans = 0;
	for(int i = 0; i < n; i++) ans += a[2*i + 1];
	cout << ans;
	return 0;
}


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = 1e9+7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

vector<VI> r;

ll  fct[200200], inv[200200];
void finit(int cmx, ll mod){
	auto bin_pows =[](ll x, ll n, ll mod){
		ll res = 1LL;
		for(; n > 0; n >>=1, x = x*x %mod) if(n & 1) res = res * x %mod;
		return res;
	};
	fct[0] = fct[1] = inv[1] = 1;
	for(int i=2;i<cmx+3;i++) fct[i] = fct[i-1] * i % mod;
	inv[cmx] = bin_pows(fct[cmx], mod-2, mod);
	for(int i=cmx;i>=1;i--) inv[i-1] = inv[i] * i % mod;
}
ll nPk(ll n, ll k, ll mod = MD) {
	if(k > n) return 0;
	return fct[n] * inv[n-k] % mod;
}

ll ans = 1;
void rec(int s, int p, const int k){
	for(auto u: r[s]) if(u != p) rec(u, s, k);
	if(p ==-1) ans *= nPk( k , sz(r[s])+1);
	else ans *= nPk( k-2 , sz(r[s])-1);
	ans %=MD;

}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(false);
	finit(200010, MD);
	int n, k;
	cin >>n >>k;
	r.resize(n);
	rep(i, n-1){
		int a,b;
		cin >>a >>b;
		r[a-1].push_back(b-1);
		r[b-1].push_back(a-1);
	}
	rec(0, -1, k);
	cout << ans <<"\n";
	return 0;
 }



Measured memory_bytes: 13568
#include <iostream>
#include <string>
using namespace std;
const char nc[20] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
string ans;
int main()
{
	int m, n, k, t, s;
cin >> m;
if(m==0)
printf("0\n");
	ans = "";
	s = m;
	while(m != 0){
	k = m % (-2);
	t = m / (-2);
	if(k < 0){
	k -= (-2);
	t++;
	}
	m = t;
	ans.push_back(nc[k]);
}
	for(int i = ans.length() - 1; i >= 0; i--){
	cout << ans[i];
	}
	
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(v)    begin(v), end(v)
#define in        []{lint n; cin>>n; return n;}()

int main() { cin.tie(0); ios::sync_with_stdio(false);
    int N = in, M = in;
    vector<vector<int>> to( N, vector<int>(0) );
    rep( i, M ) {
        int x = in-1, y = in-1;
        to[x].push_back(y);
    }

    vector<int> length( N, -1 );
    rep( i, N ) {
        if( length[i] != -1 ) continue;
        stack<tuple<int,int>> s; s.push( make_tuple(i,0) );
        while( !s.empty() ) {
            int x,j; tie(x,j) = s.top();
            if( j == to[x].size() ) {
                length[x] = 0;
                for( int y : to[x] ) length[x] = max( length[x], length[y]+1 );
                s.pop();
            } else if( length[to[x][j]] != -1 ) {
                s.pop();
                s.push( make_tuple(x,j+1) );
            } else {
                s.push( make_tuple(to[x][j],0) );
            }
        }
    }

    int longest = 0;
    rep( i, N ) longest = max( longest, length[i] );

    cout << longest << "\n";
}


Measured memory_bytes: 6544
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const long long INF = 1LL << 60;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
//

lint dp[110][101010];

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

  lint N, W;
  cin >> N >> W;
  vector<lint> w(N), v(N);
  rep(i, N) cin >> w[i] >> v[i];

  rep(i, 110) rep(j, 101010) dp[i][j] = INF;
  dp[0][0] = 0;

  rep(i, N) {
    rep(sum, 101010) {
      if (0 <= sum - v[i]) chmin(dp[i + 1][sum], dp[i][sum - v[i]] + w[i]);
      chmin(dp[i + 1][sum], dp[i][sum]);
    }
  }

  lint ans = 0;
  rep(sum, 101010) {
    if (dp[N][sum] <= W) ans = sum;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 87168
N = int(input())  
A = list(map(int,input().split()))
Q = int(input())
Query = [list(map(int,input().split())) for _ in range(Q)]

ls = [0] * (10**5+1)
for i in range(N):
    ls[A[i]] += 1

S = sum(A)    
for i in range(Q):
    b = Query[i][0]
    c = Query[i][1]
    S += ((c - b) * ls[b])
    ls[c] += ls[b]
    ls[b] = 0
    print(S)


Measured memory_bytes: 96792
#include<bits/stdc++.h>
using namespace std;
/* 変数名を被らせない
   デバッグコードを取り除く 
　　提出する問題を間違えない */
#define ANSWER(x) cout<<x<<endl
#define debug(x) cout<<#x<<": "<<x
typedef pair<int,int> P;
void bfs(int sx,int sy);
int H,W,N,a;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int cheese_x[10];
int cheese_y[10];
char ch[1001][1001];
int al[1001][1001];
int S_x,S_y,hp = 1,dis;
int main(){
  cin >> H >> W >> N;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin >> ch[i][j];
      if(ch[i][j] == 'S'){
	S_x = j;
	S_y = i;
      }
    }
  }
  for(int i=0;i<N;i++){
    bfs(S_x,S_y);
  }
  
  cout << a << endl;
}
void bfs(int sx,int sy){
  queue<P> que;
  que.push(P(sx,sy));
  al[sy][sx] = a;
  while(!que.empty()){
    P now = que.front();que.pop();
    int x = now.first;
    int y = now.second;
    if(ch[y][x] - '0' == hp){
      hp++;
      S_x = x;
      S_y = y;
      a = al[y][x];
      
      memset(al,0,sizeof(al));
      
      break;
    }
    for(int i=0;i<4;i++){
      int mx = x + dx[i];
      int my = y + dy[i];
      if(mx < 0 || my < 0 || mx >= W || my >= H)continue;
      if(ch[my][mx] != 'X' && al[my][mx] == false){
	que.push(P(mx,my));
	al[my][mx] = al[y][x] + 1;
      }
    }
  }
}

Measured memory_bytes: 6112
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = long.Parse(Console.ReadLine());
            var a = (from x in Console.ReadLine().Split(' ') select long.Parse(x));

            var num = new long[n];

            foreach (var p in a)
            {
                num[p - 1]++;
            }

            foreach (var p in num)
            {
                Console.WriteLine(p);
            }
        }
    }
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int c[3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> c[i][j];
        }
    }
    string res = "Yes";
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            if (c[i][j] + c[i + 1][j + 1] != c[i][j + 1] + c[i + 1][j]) {
                res = "No";
            }
        }
    }
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INT_INF = 2147483647;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef pair<int,int> P;

vector<P> to[100005];
vector<int> d(100005);
void dfs(int v, int p=-1) {
  for (auto u : to[v]) {
    if (u.first == p) continue;
    d[u.first] += d[v]+u.second%2;
    dfs(u.first,v);
  }
}

int main() {
  int n;
  cin >> n;
  rep(i,n-1) {
    int u,v,w;
    cin >> u >> v >> w;
    --u; --v;
    to[u].push_back(make_pair(v,w));
    to[v].push_back(make_pair(u,w));
  }
  d[0]=0;
  dfs(0);
  rep(i,n) {
    cout << d[i]%2 << endl;
  }
  return 0;
}


Measured memory_bytes: 8448