akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
 
int N;
vector<ll> A;
vector<vector<int>> G;
 
ll dfs(int v, int p) {
  vector<ll> edges;
  for (int u : G[v]) {
    if (u != p) {
      ll e = dfs(u, v);
      if (e < 0) {
        return -1;
      }
      edges.push_back(e);
    }
  }
  if (edges.empty()) {
    return A[v];
  }
  ll sum = accumulate(edges.begin(), edges.end(), 0ll);
  ll mx = *max_element(edges.begin(), edges.end());
  ll x = 2 * A[v] - sum;
  sum += x;
  mx = max(mx, x);
  if (x < 0 || mx > A[v]) {
    return -1;
  }
  return x;
}
 
bool solve() {
  if (N == 2) {
    return A[0] == A[1];
  }
  int r = -1;
  for (int v = 0; v < N; v++) {
    if (G[v].size() > 1) {
      r = v;
      break;
    }
  }
  return dfs(r, -1) == 0;
}
 
int main() {
  cin >> N;
  A.resize(N);
  G.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  cout << (solve() ? "YES" : "NO") << endl;
  return 0;
}

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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int h, w, n;
  while (cin >> h >> w >> n) {
    vector<int> a(n);
    cin >> a;

    vector<pair<int, int>> v;
    for (int i = 0; i < h; ++i) {
      if (i % 2) {
        for (int j = 0; j < w; ++j) {
          v.push_back(make_pair(i, j));
        }
      } else {
        for (int j = w - 1; 0 <= j; --j) {
          v.push_back(make_pair(i, j));
        }
      }
    }

    int g[h][w];
    int color = 1;
    each (i, a) {
      for (int j = 0; j < i; ++j) {
        pair<int, int> p = v.back();
        v.pop_back();
        g[p.first][p.second] = color;
      }
      ++color;
    }
    assert(v.empty());
    
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        cout << g[i][j] << ' ';
      }
      cout << endl;
    }
  }

  return 0;
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;
// 入力
int H, W;
vector<vector<char>> field;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int main() {

  int N; cin >> N;
  int ans;

  if(N % 2 == 1){
    ans = N / 2 + 1;
  } else {
    ans = N / 2;
  }

  cout << ans << endl;

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


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

void solve(int post[], int pre[], int in[], int l, int r, int *pos, int n, int *s)
{
    if (l >= r)
        return;
    int root = pre[*pos];
    *pos += 1;
    int m;
    for (int i = 0; i < n; i++)
    {
        if (root == in[i])
        {
            m = i;
            break;
        }
    }
    solve(post, pre, in, l, m, pos, n, s);
    solve(post, pre, in, m + 1, r, pos, n, s);
    post[*s] = root;
    *s += 1;
}

int main()
{
    int n;
    cin >> n;
    int pre[n];
    int in[n];
    for (int i = 0; i < n; i++)
        cin >> pre[i];
    for (int i = 0; i < n; i++)
        cin >> in[i];
    int post[n];
    int pos = 0;
    int s = 0;
    solve(post, pre, in, 0, n, &pos, n, &s);
    for (int i = 0; i < n; i++)
    {
        cout << post[i];
        if (i != n - 1)
            cout << ' ';
    }
    cout << endl;
}



Measured memory_bytes: 3092
#include<stdio.h>
#include<math.h>
 
int main(void)
{
  int w,h;
  char s[60][30];
  int i,j,m,n,c;
  int dp[60][30][2];
  int tmp1,tmp2,min;
 
  while(1){
    scanf("%d %d ",&w,&h);
    if(w==0 && h==0)break;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
    scanf("%c ",&s[i][j]);
      }
    }
 
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
    dp[i][j][0] = -1;
    dp[i][j][1] = -1;
      }
    }
 
    for(i=0;i<w;i++){
      if(s[h-1][i] == 'S'){
        dp[h-1][i][0] = 0;
        dp[h-1][i][1] = 0;
      }
    }
 
     
    while(1){
      c=0;
      for(i=0;i<h;i++){
    for(j=0;j<w;j++){ 
      if(dp[i][j][0] >= 0){
        for(m=-2;m<=2;m++){
          for(n=1;n<=3;n++){
        if(i+m>=0 && i+m<h && j+n<w && fabs(m)+n<=3 && s[i+m][j+n]!='X'){
          tmp1 = dp[i+m][j+n][1];
          if(s[i+m][j+n] == 'S' || s[i+m][j+n] == 'T'){
            tmp2 = dp[i][j][0];
          }else{
            tmp2 = dp[i][j][0] + s[i+m][j+n] - '0';
          }
          if(tmp1 < 0 || tmp1 > tmp2){
            dp[i+m][j+n][1] = tmp2;
            c++;
          }
        }
          }
        }
      }
      if(dp[i][j][1] >= 0){
        for(m=-2;m<=2;m++){
          for(n=1;n<=3;n++){
        if(i+m>=0 && i+m<h && j-n>=0 && fabs(m)+n<=3 && s[i+m][j-n]!='X'){
          tmp1 = dp[i+m][j-n][0];
          if(s[i+m][j-n] == 'S' || s[i+m][j-n] == 'T'){
            tmp2 = dp[i][j][1];
          }else{
            tmp2 = dp[i][j][1] + (int)(s[i+m][j-n] - '0');
          }
          if(tmp1 < 0 || tmp1 > tmp2){
            dp[i+m][j-n][0] = tmp2;
            c++;
              }
        }
          }
        }
      }
    }
      }
      if(c==0)break;
    }
 
    min = -1;
    for(i=0;i<w;i++){
      if(s[0][i] == 'T'){
     for(j=0;j<2;j++){
           if(min < 0 || (dp[0][i][j] > 0 && min > dp[0][i][j]))min = dp[0][i][j];
    }
      }
    }
 
    printf("%d\n",min);
     
  }
  return 0;
} 

Measured memory_bytes: 620
#include<stdio.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
  int S, W;
  scanf("%d %d", &S, &W);
  if(W>= S){
    printf("unsafe\n");
  }else{
    printf("safe\n");
  }
  return 0;
}

Measured memory_bytes: 1664
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

int A[MAXN];

long long qp2(int n) {
  long long res = 1, now = 2;
  while (n) {
    if (n & 1)
      res = res * now % MOD;
    n >>= 1;
    now = now * now % MOD;
  }
  return res;
}

bool check(int n) {
  sort(A + 1, A + 1 + n);
  if (n & 1) {
    for (int i = 1; i <= n; i++) {
      if (A[i] != i / 2 * 2)
        return false;
    }
  } else {
    for (int i = 1; i <= n; i++) {
      if (A[i] != (i - 1) / 2 * 2 + 1)
        return false;
    }
  }
  return true;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", &A[i]);
  printf("%lld\n", check(n) ? qp2(n / 2) : 0);
}


Measured memory_bytes: 640
n, k = map(int, input().split())

hs = []
for _ in range(n):
    hs.append(int(input()))

hs = sorted(hs)

min_diff = float('inf')
for i in range(len(hs) - k + 1):
    min_diff = min(min_diff, hs[i+k-1]-hs[i])

print(min_diff)

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

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

// r -> P, s -> R, p -> S
int main() {
    int N, K, R, S, P;
    string T;
    cin >> N >> K >> R >> S >> P >> T;
    vector<string> s(K);
    rep(i, N) s[i % K] = s[i % K] + T[i];
    int ans = 0;
    rep(i, K) {
        char c = 'n';
        rep(j, s[i].size()) {
            if(s[i][j] != c) {
                if(s[i][j] == 'r') {
                    ans += P;
                } else if(s[i][j] == 's') {
                    ans += R;
                } else if(s[i][j] == 'p') {
                    ans += S;
                }
                c = s[i][j];
            } else {
                c = 'n';
            }
        }
    }
    cout << ans << endl;
}

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

int main() {
    int n;
    double ans = 0;
    double x[101]={}, y[101]={};
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> x[i];
    }
    for(int i=0; i<n; i++){
        cin >> y[i];
    }
    double p1=0, p2=0, p3=0, infi=0;
    ans=0;
        for(int i=0; i<n; i++){
            ans=fabs(x[i]-y[i]);
            p1 += ans;
            p2 += pow(ans,2);
            p3 += pow(ans,3);
            infi
            = max(infi,ans);
        }
    p2=sqrt(p2);
    p3=pow(p3,1.0/3.0);
    printf("%8f\n", p1);
    printf("%8f\n", p2);
    printf("%8f\n", p3);
    printf("%8f\n", infi);
    return 0;
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;


ll M[110][110]; //edge weight
ll color[110];
ll white = 0, gray = 1, black = 2;
ll n; 

void dijkstra(){
  ll d[110];//d[v] vまでの最短経路
  ll minv;
  rep(i, 0, n){
    color[i] = white;
    d[i] = INF;
  }
  d[0] = 0;
  color[0] = gray;
  while(1){
    minv = INF;
    ll u = -1;
    rep(i, 0, n){
      if(minv > d[i] && color[i] != black){// はじめd[i]=0, u = 0, minv = 0
        u = i;
        minv = d[i];
      }
    }
    if(u == -1) break;
    color[u] = black;// 最も重さが小さいほうへすすむ
    rep(v, 0, n){
      if(color[v] != black && M[u][v] != INF){
        if(d[v] > d[u] + M[u][v]){
          d[v] = d[u] + M[u][v]; //d[v]を更新
          color[v] = gray;
        }
      }
    }
  }
  rep(i, 0, n){
    cout << i << " " << d[i] << endl;
  }
}

int main() {
  cin >> n;
  rep(i, 0, n){//始めに辺の重さをマックスに初期化
    rep(j, 0, n) M[i][j] = INF;
  }

  rep(i, 0, n){
    ll u; cin >> u;
    ll k; cin >> k;
    rep(j, 0, k){
      ll v, c; cin >> v >> c;
      M[u][v] = c;//辺の重さを入力
    }
  }

  dijkstra();

  return 0;
}



Measured memory_bytes: 3172
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
class Program
{
    static void Main()
    {
        Dictionary<int, int> dic = new Dictionary<int, int>();
        string first = ReadLine();
        string[] firsts = first.Split(' ');
        int N, K;
        N = int.Parse(firsts[0]);
        K = int.Parse(firsts[1]);
        int[] array = new int[N];
        for (int i = 0; i < N; i++){
            array[i] = 200001;
        }

        string[] second = ReadLine().Split(' ');
        int[] nums = new int[N];
        int arrayIndex = 0;
        for (int i = 0; i < N; i++){
            nums[i] = int.Parse(second[i]);
            bool hasKey = dic.ContainsKey(nums[i]);
            if (!hasKey)
            {
                dic[nums[i]] = arrayIndex;
                arrayIndex++;
                array[dic[nums[i]]] = 0;
            }
            array[dic[nums[i]]]++; 
        }

        Array.Sort(array);
        int wantDeleteChar = dic.Count() - K;
        int deleteChar = 0;
        for (int i = 0; i < wantDeleteChar; i++){
            deleteChar += array[i];
        }
        //for (int i = 0; i < dic.Count(); i++)
        //{
        //    WriteLine(array[i]);
        //}
        WriteLine(deleteChar.ToString());
    }
}

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

int main(){
	bool n = false,s = false,e = false,w = false;
	string str;
	cin >> str;
	for(int i = 0;i < str.length();i++){
		if(str[i] == 'N') n = true;
		else if(str[i] == 'S') s = true;
		else if(str[i] == 'E') e = true;
		else w = true;
	}
	if((n ^ s) || (e ^ w)) cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 764
from collections import deque
S = input()
S  = deque(S)
Q = int(input())

# 0の時は普通、1の時は反転状態
Reverse_Flag = 0  

for _ in range(Q):
    string = (input())
    Query = string.replace(' ', '')
    Query = list(Query)

    if Query[0] == "1":
        if Reverse_Flag == 0:
            Reverse_Flag = 1
        else:
            Reverse_Flag = 0
    
    elif  Query[1] == "1":
        if Reverse_Flag == 0:
            S.appendleft(Query[2])
        else:
            S.append(Query[2])

    else:
        if Reverse_Flag == 0:
            S.append(Query[2])
        else:
            S.appendleft(Query[2])

if Reverse_Flag == 1:
    S = list(S)
    S = S[::-1]
    print("".join(S))
else:
    S = list(S)
    print("".join(S))


Measured memory_bytes: 14024
// finish date: 2019/1/26

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1000000007;
const long long INFll = 100000000000000000;


//最大公約数
int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (a < b) {
        swap(a, b);
    }
    int r = 1; //0以外であれば何でも
    while (r != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}


//足し算
int add(int a, int b) {
    return (int) (((ll) a + b + bigmod) % bigmod);
}

//引き算
int sub(int a, int b) {
    return (int) (((ll) a - b + bigmod) % bigmod);
}

//掛け算
int mul(int a, int b) {
    return (int) (((ll) (a % bigmod) * (b % bigmod)) % bigmod);
}

int modpow(int a, int b) {
    if (b == 0) return 1;
    int temp = modpow(a, b / 2);
    if (b % 2 == 1) return mul(mul(temp, temp), a);
    else {
        return mul(temp, temp);
    }
}


//割り算(分母だけ)  -  逆元(求めたい数とbigmodを渡す)
int divide(int a, int p = bigmod, int b = -1) {
    if (b < 0) b = p - 2;  //int gyakugen(int a, int p, int b = p - 2とできなかったため。)
    if (b == 0) return 1;
    else if (b % 2 == 0) {
        int d = divide(a, p, b / 2);
        return mul(d, d);
    } else {
        return mul(a, divide(a, p, b - 1));
    }
}

//素因数分解
map<int, int> p_fact(int n) {
    map<int, int> mp;
    int i = 2;
    while (n >= i * i) {
        while (n % i == 0) mp[i]++, n /= i;
        i++;
    }
    if (n != 1) mp[n]++;
    return mp;
}


int main() {
    int N;
    cin >> N;
    vi A(N);
    rep(i, N) cin >> A[i];

    int mul_A = 1;
    rep(i, N) mul_A = mul(mul_A, A[i]);

    map<int, int> mp;
    rep(i, N) {
        for (pii p: p_fact(A[i])) {
            mp[p.first] = max(mp[p.first], p.second);
        }
    }
    int lcm_value = 1;
    for (pii p: mp) {
        lcm_value = mul(lcm_value, modpow(p.first, p.second));
    }

    int sum = 0;
    rep(i, N) {
        sum = add(sum, mul(lcm_value, divide(A[i])));
    }
    cout << sum << endl;


    return 0;
}


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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int m1, d1, m2, d2; cin >> m1 >> d1 >> m2 >> d2;
    if (m1 == m2) {
        cout << 0 << '\n';
    }
    else {
        cout << 1 << '\n';
    }
}



Measured memory_bytes: 256
//code by lynmisakura.wish to be accepted!
/****************************/
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<pair<int,int>> vpi;
 
const long long MOD = 998244353;
const long long mod = 1000000007;
const long long INF = 10000000000000;
 
#define itn int
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
 
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
 
#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
struct edge{ll f,t,c;};
int main(void){
   ll l;cin >> l;
   vector<edge> p;
   ll r = 0LL;
   l;
   while((1LL<<r) <= l) r++;
   rep(i,r-1){
      edge e1 = {i,i+1,0}; edge e2 = {i,i+1,(1LL<<i)};
      p.pb(e1);p.pb(e2);
   }
   l--;
   ll m = l - (1LL << r-1) + 1;
   /*for(ll i = r;i >= 0;i--){
      if((1LL<<i) <= m){
         m -= (1LL<<i);
         edge e = {i,r-1,l+1-(1LL<<i)};
         p.pb(e);
      }
   }*/
   ll tmp = (1LL << r - 1);
   
   for(ll i = r - 1;i >= 0;i--){
      if((1LL<<i) <= m){
         m-=(1LL<<i);
         edge e = {i,r-1,tmp};
         tmp += (1LL<<i);
         p.pb(e);
      }
   }
   cout << r << " " << p.size() << endl;
   rep(i,p.size()) cout << p[i].f + 1 << " " << p[i].t + 1 << " " << p[i].c << endl;
   return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int read()
{
    char c=getchar();int f=1,sum=0;
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){sum=sum*10+c-'0';c=getchar();}
    return sum*f;
}
int n;
long double a,x,ans;double g1,g2;
int main()
{
	n=read()*2;scanf("%lf%lf",&g1,&g2);a=g1;x=g2;
	while(n)
	{
		ans+=(a*2.0+(long double)(n-1)*x)/2.0;
		a=((long double)(n+2)*a+5.0*x)/(long double)n;
		x=((long double)(n+4)*x)/(long double)n;
		n-=2;
	}
	printf("%.15lf\n",(double)ans);
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int ans = 0;
    vector<pair<pair<int, int>, int> > ab(2*n);
    REP(i,n){
        cin >> ab[i].fi.fi >> ab[i].fi.se;
        ab[i].se = 0;
    }
    REP(i,n){
        cin >> ab[n+i].fi.fi >> ab[n+i].fi.se;
        ab[n+i].se = 1;
    }
    set<int> st;
    sort(ALL(ab));
    REP(i,2*n){
        if(ab[i].se==0){
            st.insert(ab[i].fi.se);
        }else{
            if((int)st.size()==0) continue;
            auto itr = st.upper_bound(ab[i].fi.se);
            if(itr==st.begin()) continue;
            itr--;
            st.erase(itr);
            ans++;
        }
    }
    cout<< ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

const int M = 1000005;

int main()
{
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(), a.end());
    int sum = a[0] + a[1] + a[2];
    if(sum % 2 == 0) {
        if(a[2] % 2 == 0) {
            cout << (3 * a[2] - sum) / 2 << endl;
        }
        else {
            cout << (3 * a[2] + 3 - sum) / 2 << endl;
        }
    }
    else {
        if(a[2] % 2 == 1) {
            cout << (3 * a[2] - sum) / 2 << endl;
        }
        else {
            cout << (3 * a[2] + 3 - sum) / 2 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-10;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}
long long fact[2100000];
long long inv[2100000];
long long finv[2100000];
long long C(int a,int b){
	if(b<0||b>a)return 0;
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
int main(){
	fact[0]=inv[1]=finv[0]=1;
	for(int i=2;i<2100000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<2100000;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
	int a;scanf("%d",&a);
	long long ret=0;
	for(int i=0;i<a;i++){
		long long ks=C(a-2-i,i);
		//printf("%d: %lld\n",i,ks);
		ret=(ret+fact[i]*ks%mod*fact[a-1-i])%mod;
	}
//	printf("%lld\n",ret);
	ret=(fact[a-1]*(a)%mod-ret+mod)%mod;
	printf("%lld\n",ret);
}

Measured memory_bytes: 49536
#include <bits/stdc++.h>
#define lld unsigned long long int
#define MAX 2005
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
using namespace std;

int a, b;
char c[MAX];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    scanf("%d %d  %s", &a, &b, c);
    c[b-1]+=32;

    cout<<c<<endl;
}


Measured memory_bytes: 256
/*ANKON GHOSH
  KUET,ECE 2K16*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define MAX 4003
#define mod 1000000007
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define Case(i) cout<<"Case #"<<i<<": "
#define pf(a) printf("%lld\n",a)
#define pfsn printf("NO\n")
#define pfs  printf("YES\n")
#define pff(a,b) printf("%lld %lld\n",a,b)
#define pfff(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define pffff(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define FOR(i,n) for(ll i=0;i<n;i++)
#define FOR1(i,n) for(ll i=1;i<=n;i++)
#define LOOP(x,y) for(ll r=x;r<=y;r++)
#define RFOR(i,n) for(ll i=n-1;i>=0;i--)
#define RFOR1(i,n) for(ll i=n;i>0;i--)
#define RLOOP(x,y) for(ll i=y;i>=x;i--)
#define m_p(a,b) make_pair(a,b)
#define p_b(a) push_back(a)
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
map<ll,ll>mp1,mp;
vector<pair<ll,pair<ll,ll> > >vpp,vpp1;
vector<pair<ll,ll> >vp,fin;
vector<ll>v1,v2,dummy;
map<pair<ll,ll>,bool>mbb;
map<ll,bool>mb;
ll n,k,a,b,c,d,ta,sum=0,cnt=0,m,l,req,sz,maxi;
bool sortbysec(const pair<pair<ll,ll>,ll> &a,const pair<pair<ll,ll>,ll> &b)
{
    return (a.second < b.second);
}
vector<ll>power;
int main()
{
    FOR1(i,9LL)
    {
        FOR1(j,9LL)
        {
            ll x=i*j;
            mb[x]=true;
        }
    }
    cin>>n;
    if(mb[n])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
/*
5
4
3
2
3
4
4
3
3
4
2
3
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int

using namespace std;

int main ()
{
	string s;
	cin >> s;
	if (s == "Sunny"){
		cout << "Cloudy" << endl;
	}
	else if (s == "Cloudy"){
		cout << "Rainy" << endl;
	}
	else if (s == "Rainy"){
		cout << "Sunny" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define all(a) (a.begin(),a.end())
#define fi first
#define sc second
#define ort(x,y) (x+y)/2
#define endl '\n'
#define FAST ios_base::sync_with_stdio(false);
#define d1(x) cerr<<#x<<":"<<x<<endl;
#define d2(x,y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl;
#define d3(x,y,z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl;
#define lim (int) (1e5+5)
#define inf (int) (1e7)
#define heap priority_queue
#define mem(a,val) memset(a,val,sizeof(a))
#define y1 asdassa
typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
char s[10];
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1;i<n;i++)
		if(s[i]=='A' && s[i+1]=='C') return printf("Yes"),0;
	printf("No");
}




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

#define infile "../test/sample-2.in"
#define int long long
// #define INF 2147483647
#define INF 1000000000000000000LL
#define MOD 1000000007LL

// {{{ define basic macro
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) repi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)(b-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)

#define foreach(x,a) for(auto& (x) : (a) )
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)

#define all(x) (x).begin(),(x).end()
#define sum(v) accumulate(all(v), 0)
#define sz(x) ((int)(x).size())
template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }
// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
#define fill(x,y) memset(x,y,sizeof(x))
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ten(n) ((int)1e##n)

template <class T = int>
T in() {T x; cin>>x; return (x);}

struct Fast {
  Fast(){
    std::cin.tie(0);
    ios::sync_with_stdio(false);
  }
} fast;
// }}}
//{{{ dump macro
#ifdef PCM
  #include "dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}
//{{{ others
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;
template<typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;

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

int n,a,b;
int h[100000];
bool check(int x){
  int cnt = 0;
  rep(i, n){
    cnt += (max(0LL, h[i]-b*x)+(a-b)-1)/(a-b);
  }
  if (cnt<=x) return true;
  else return false;
}

int bsearch(){
  int ng = 0;  //
  int ok = 1000000001; //
  int mid;
  while (ok-ng>1){
    mid = (ok+ng)/2;
    if (check(mid)) { ok = mid;}
    else{ ng = mid; }
  }
  return ok;
}

int solve(){
  cin>>n>>a>>b;
  rep(i, n){ cin>>h[i]; }
  dump_1d(h, n);

  int res = bsearch();
  cout << res << endl;

  return 0;
}

int test(){ //{{{
  return 0;
}
//}}}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
#ifdef PCM
  test();
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 1024
N = gets.to_i
weight = gets.split.map(&:to_i)
result = []
for i in 0..N-1 do
  left = weight[0..i]
  right = weight[i+1..N-1]
  result <<  (right.inject(:+) - left.inject(:+)).abs if left.any? && right.any?
end
p result.min

Measured memory_bytes: 1788
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}
long long gcd(long long x,long long y){
	return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
	return x/gcd(x,y)*y;
}

// konoshita kara kaku
		
int main(void){
	long long a=in(),b=in(),c=in(),x=in(),y=in();
	if(x>y)
		llprint(min(x*a+y*b,min(2*x*c,2*y*c+(x-y)*a)));
	else
		llprint(min(x*a+y*b,min(2*y*c,2*x*c+(y-x)*b)));
	return 0;
}

Measured memory_bytes: 128
N, M = map(int, input().split())
fact = [1]*(N+1)
rfact = [1]*(N+1)
for i in range(1, N+1):
    fact[i] = r = (i * fact[i-1]) % M
    rfact[i] = pow(r, M-2, M)

S = [1]

rev2 = pow(2, M-2, M)
base = pow(2, N, M)
ans = 0
S = [1]
for K in range(N+1):
    res = (fact[N] * rfact[K] * rfact[N-K]) % M
    res = (res * pow(2, pow(2, N - K, M-1), M)) % M
    b = 1
    v = 0
    T = [0]*(K+2)
    for L in range(K):
        T[L+1] = s = (S[L] + (L+1)*S[L+1]) % M
        v += s * b
        b = (b * base) % M
    v += b
    T[K+1] = 1
    S = T
    res = (res * v) % M
    if K % 2:
        ans -= res
    else:
        ans += res
    ans %= M

    base = (base * rev2) % M
print(ans)

Measured memory_bytes: 3436
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    ll n;cin>>n;
    ll m;cin>>m;
    vector<pair<ll,ll>> ab(n);
    For(i,0,n) cin >> ab[i].first >> ab[i].second;
    sort(ALL(ab));
    For(i,0,n){
        ll num = min(m,ab[i].second);
        ans += num * ab[i].first;
        m-=num;
        if(m==0) break;
    }
    cout << ans << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

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

int main () {
  int n;
  cin >> n;
  vector<int> l(n);
  rep(i,n) cin >> l[i];
  sort(l.begin(), l.end());
  int sum = 0;
  rep(i,n-1) sum += l[i];

  cout << (l[n-1] < sum ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
#include<vector>
#include<string>
#define ll long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vi vector<ll>
#define el printf("\n")
#define N 100001
using namespace std;



int main()
{   IOS;
cout.precision(30);
    ll n;
    cin >> n;
    vector<ll> L1,L;
    for(int i=0;i<n;i++)
    {
        ll x;
        cin >> x;
        L.push_back(x);
    }
    ll res=0;
   for(int i=0;i<n;i++)
    {
        ll x;
        cin >> x;
        res=res+x;

    }
    for(int i=0;i<n-1;i++)
    {
        ll x;
        cin >> x;
        L1.push_back(x);
    }
    for(int i=0;i<n-1;i++)
    {
        if(L[i+1]-L[i]==1)
        {
            res=res+L1[L[i]-1];
        }
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
  int n,m,l;
  int i,j,k;
  int a[100][100];
  int b[100][100];
  double c[100][100];

  scanf("%d",&n);
  scanf("%d",&m);
  scanf("%d",&l);

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

  for (i=0; i<n; i++) {
    for (j=0; j<l; j++) {
      for (k=0; k<m; k++) {
        c[i][j]+=a[i][k]*b[k][j];
      }
    }
  }

  for (i=0; i<n; i++) {
    for (j=0; j<l; j++) {
      if (j!=l-1) printf("%.lf ",c[i][j]);
      else printf("%.lf\n",c[i][j]);
    }
  }
  return 0;
}

Measured memory_bytes: 788
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    A = inputList()
    
    AA = []
    heapq.heapify(AA)
    for val in A:
        heapq.heappush(AA, val * (-1))
    
    for i in range(M):
        tmp = heapq.heappop(AA) * (-1)
        tmp = tmp // 2
        heapq.heappush(AA, tmp * (-1))
        
    ans = 0
    for i in range(N):
        tmp = heapq.heappop(AA) * (-1)
        ans += tmp
        
    print(ans)
    
    
if __name__ == "__main__":
	main()


Measured memory_bytes: 67564
#include <iostream>
    #include <vector>
    #include <cmath>
     
    using namespace std;
     
    vector<pair<long long, long long> > stu, pnt;
     
    int main() {
      int n, m;
      cin >> n >> m;
      
      int a, b;
      
      while(n--) {
        cin >> a >> b;
        stu.push_back({a, b});
      }
      n = stu.size();
      
      while(m--) {
        cin >> a >> b;
        pnt.push_back({a, b});
      }
      m = pnt.size();
      
      long long res;
      int indx;
      
      for(int i = 0; i < n; i++) {
        res = 1e18;
        
        for(int j = 0; j < m; j++) {
          if(abs(stu[i].first - pnt[j].first) + abs(stu[i].second - pnt[j].second) < res) {
            res = abs(stu[i].first - pnt[j].first) + abs(stu[i].second - pnt[j].second);
            indx = j;
          }
        }
        
        cout << indx + 1 << endl;
      }
      
      return 0;
    }

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

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2")
*/


#ifdef LOCAL
	#define dbg(x) cout << #x << " : " << x << endl;
#else 
	#define dbg(x)
#endif

#define int long long
#define fi(a,b) for (int i=a;i<b;i++)
#define fj(a,b) for (int j=a;j<b;j++)
#define fk(a,b) for (int k=a;k<b;k++)
#define fi1(a,b) for (int i=a-1;i>=b;i--)
#define fj1(a,b) for (int j=a-1;j>=b;j--)
#define fk1(a,b) for (int k=a-1;k>=b;k--)
#define fx(x,a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, T2 y) { if (x < y) x = y; }

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << ' ';
    return a;
}


typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 200010;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int a[MX];
vi g[MX];
int dp[MX];
int ans[MX];

void dfs(int v, int p = -1) {
	dbg(v);
	int ind = lb(dp, dp + MX, a[v]) - dp;
	int was = dp[ind];
	dp[ind] = a[v];
	dbg(ind);
	dbg(was);
	dbg(dp[ind]);

	
	ans[v] = lb(dp, dp + MX, INF) - dp - 1;
	fx(to, g[v]) {
		if (to != p)
			dfs(to, v);
	} 
	dp[ind] = was;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    fi(0, n)
    	cin >> a[i];
    fi(0, n - 1) {
    	int va, vb;
    	cin >> va >> vb;
    	--va;
    	--vb;
    	g[va].push_back(vb);
    	g[vb].push_back(va);
    }
    fill(dp + 1, dp + MX, INF);
    dfs(0);
    fi(0, n)
    	cout << ans[i] << '\n';
}

Measured memory_bytes: 33552
void main()
{
    string s, t;
    ipElems(s, t);
    long a, b;
    ipElems(a, b);
    string u = rdStr;

    if (u == s) --a;
    if (u == t) --b;

    writeln(a, " ", b);
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void ipElems(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
  int k;
  cin >> k;
  vector<ll> a;
  for (int i = 1; i <= 9; ++i) a.push_back(i);
  while (1) {
    if (k <= a.size()) {
      cout << a[k-1] << endl;
      return 0;
    }
    k -= a.size();
    vector<ll> old;
    swap(old, a);
    for (ll x : old) {
      for (int i = -1; i <= 1; ++i) {
        int d = x%10 + i;
        if (d < 0 || d > 9) continue;
        ll nx = x*10 + d;
        a.push_back(nx);
      }
    }
  }
  return 0;
}

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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)

typedef long long ll;

int main() {
  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;
  int ans = 0;
  if (d2 == 1) {
    ans = 1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m,a[20];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[200005],R[200005];
void make(){
	F[0] = 1;
	for(int i=1;i<200005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<200005;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}
ll dp[17][(1<<16)][17];
ll fff[20];
int pcnt[(1<<16)];
int main(){
    rep(MM,(1<<16)) pcnt[MM] = __builtin_popcount(MM);
	make();
	cin>>n>>m;
	rep(i,m) cin>>a[i];
	dp[m][0][0] = 1;
	for(int i=m;i>=1;i--){
		for(int mask=0;mask<(1<<n);mask++){
		rep(cnt,m+1){
			if(dp[i][mask][cnt] == 0) continue;
			//a[i-1] wo okanai
			dp[i-1][mask][cnt] = (dp[i-1][mask][cnt]+dp[i][mask][cnt])%mod;
			//a[i-1] wo oku
			int zan = pcnt[mask]+cnt;
			zan = m-i-zan;
			ll cc[20];
			for(int i=0;i<=zan;i++) cc[i] = C(zan,i);
			for(int j=0;j<n;j++){
				if(((mask>>j)&1)) continue;
				//a[i-1] wo 2^j no minimum ni suru
				//a[i]...a[m-1] ha hukumu?
				for(int M=0;M<=zan;M++){
					if((1<<n)-a[i-1]-mask-zan < (1<<j)-1-M) continue;
					if((1<<j)-1-M < 0) break;
					dp[i-1][mask+(1<<j)][cnt+M] = (dp[i-1][mask+(1<<j)][cnt+M]+dp[i][mask][cnt]*C((1<<n)-a[i-1]-mask-zan,(1<<j)-1-M)%mod*cc[M]%mod);
				}
			}
		}
		}
		for(int mask=0;mask<(1<<n);mask++){
		rep(cnt,m+1){
		    dp[i-1][mask][cnt]%=mod;
		}
		}
	}
	for(int i=0;i<=n;i++){
		ll coef = 1;
		for(int j=1;j<=(1<<i);j++) coef = coef*j%mod;
		fff[i] = coef;
	}
	ll ans = 0;
	for(int mask=1;mask<(1<<n);mask++){
		int sgn = (__builtin_popcount(mask)%2 == 1?1:-1);
		//dp[0][mask][*]
		ll val = 0;
		rep(cnt,m+1){
		    val += dp[0][mask][cnt];
		}
		val %= mod;
		int zan = (1<<n)-1-mask;
		for(int j=0;j<n;j++){
		    val = val*fff[j]%mod;
			if(((mask>>j)&1)) continue;
			val = val*C(zan,(1<<j))%mod;
			zan -= (1<<j);
		}
		ans += 1LL*sgn*val;
		ans %= mod;
	}
	ans = (ans%mod+mod)%mod;
	ans = ans*(1LL<<n)%mod;
	ans = fff[n]-ans;
	cout<<(ans%mod+mod)%mod<<endl;
}

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

#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define reset(a, v) memset((a), v, sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = (int)2e5 + 5;

int n;
ll dat[N];
ll dp1[N], dp2[N][2];

ll DP1(int cur) {
	if (cur >= n) return 0;
	ll& ret = dp1[cur];
	if (ret != -1) return ret;
	if (cur % 2 == 0) {
		ret = dat[cur] + max(DP1(cur+2), DP1(cur+3));
	}
	else {
		ret = dat[cur] + DP1(cur+2);
	}
	return ret;
}

ll DP2(int cur, int stat) {
	if (cur >= n) return 0;
	ll& ret = dp2[cur][stat];
	if (ret != -1) return ret;
	if (cur % 2 == 0) {
		if (stat == 0) {
			ll opt1 = DP2(cur+2, stat);
			ll opt2 = DP2(cur+3, stat);
			ll opt3 = DP2(cur+4, 1);
			ret = dat[cur] + max(opt1, max(opt2, opt3));
		}
		else {
			ret = dat[cur] + DP2(cur+2, stat);
		}
	}
	else {
		ll opt1 = DP2(cur+2, stat);
		ll opt2 = DP2(cur+3, 1);
		ret = dat[cur] + max(opt1, opt2);
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%lld", &dat[i]);
	reset(dp1,-1);
	reset(dp2,-1);
	if (n % 2 == 0) {
		printf("%lld\n", max(DP1(0), DP1(1)));
	}
	else {
		printf("%lld\n", max(DP2(2,1), max(DP2(0,0), DP2(1,0))));
	}
	return 0;
}

Measured memory_bytes: 14748
#include <stdio.h>

int main()
{
	int N, M;
	scanf ("%d %d", &N, &M); while (M--){
		int x; scanf ("%d", &x);
		N -= x;
		if (N < 0) N = -1;
	}
	printf ("%d\n", N);
	
	return 0;
}

Measured memory_bytes: 1736
N = int(input())
A = list(map(int, input().split()))

X = len([a for a in A if a < 0])
if X % 2 == 0:
    print(sum([abs(a) for a in A]))
else:
    MIN = float('inf')
    for a in A:
        if abs(a) < MIN:
            MIN = abs(a)
    print(sum([abs(a) for a in A]) - 2 * MIN)


Measured memory_bytes: 14208
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b) {
        cout << c << endl;
    }
    if (b == c) {
        cout << a << endl;
    }
    if (c == a) {
        cout << b << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(){
	int n;
	while(cin >> n,n){
		int field[20][20] = {{0}};
		int x = n/2,y = n/2+1;
		int cnt = 1;
		while(cnt <= n*n){
			if(x < 0) x = n - 1;
			else if(n <= x) x = 0;
			else if(n <= y) y = 0;
			else if(field[y][x] != 0) x--,y++;
			else{
				field[y][x] = cnt;
				cnt++;
				x++,y++;
			}
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				printf("%4d",field[i][j]);
			}
			puts("");
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,tot,h[N],fa[N],cnt,ans;
struct node{
	int x,y,num;
}a[N];
struct edge{
	int u,v,w;
}e[2*N];
bool cmp1(node a,node b){
	return  a.x<b.x;
}
bool cmp2(node a,node b){
	return a.y<b.y;
}
bool cmp3(edge a,edge b){
	return a.w<b.w;
}
void ins(int u,int v,int w)
{
	e[++tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
}
int find(int x)
{
	if(fa[x]==x)  return x;
	return fa[x]=find(fa[x]);
}
void unionn(int x,int y,int w)
{
	x=find(x),y=find(y);
	if(x==y)  return;
	cnt++;
	ans+=w;
	if(h[x]<h[y])
	{
		fa[x]=y;
		h[y]=max(h[y],h[x]+1);
	}
	else
	{
		fa[y]=x;
		h[x]=max(h[x],h[y]+1);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
		a[i].num=i;
		fa[i]=i;
		h[i]=1;
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<n;i++)
	  ins(a[i].num,a[i+1].num,a[i+1].x-a[i].x);
	sort(a+1,a+n+1,cmp2);
	for(int i=1;i<n;i++)
	  ins(a[i].num,a[i+1].num,a[i+1].y-a[i].y);
	sort(e+1,e+tot+1,cmp3);
	for(int i=1;i<=tot&&cnt<=n-1;i++)
	{
		int x=e[i].u,y=e[i].v,w=e[i].w;
		unionn(x,y,w);
	}
	cout<<ans;
}

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

// int/long:		-2147483648 - 2147483648 (-2^31 <= int < 2^31)
// long/long long:	-9223372036854775808 - 9223372036854775807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536870912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// bit: &/and, |/or, ^/xor, ~/not

#define	MOD 1000000007

int	main() {
	int X, t;
	cin >>X >>t;
	X -=t;
	X=max(X, 0);
	cout <<X <<endl;
	return 0;
}



Measured memory_bytes: 256