akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
#define d 2019
typedef long long ll;

int main(){
   ll l,r;
   cin >> l >> r;
   if(r-l>=2019) cout << 0;
   else{
       if(l%d==0){
           cout << 0;
       }else if(l%d>r%d){
           cout << 0;
       }else{
           priority_queue<ll,vector<ll>,greater<ll>> pq;
           rep1(i,l%d,r%d){
               rep1(j,i+1,r%d+1){
                   pq.push((i*j)%d);
               }
           }
           cout << pq.top();
       }
   }
}

Measured memory_bytes: 17384
MOD = 10**9+7


def cmb2(n, r):
    x = 1
    y = 1
    for i in range(r):
        x = x * (n-i) % MOD
        y = y * (i+1) % MOD
    return x * pow(y, MOD-2, MOD) % MOD


def main():
    n, a, b = map(int, input().split())
    ans = pow(2, n, MOD)
    ans -= 1
    ans %= MOD
    ans -= cmb2(n, a)
    ans %= MOD
    ans -= cmb2(n, b)
    ans %= MOD
    print(ans)


main()


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

const int maxn = 100010;
char str[maxn];
int l[maxn], r[maxn];

int main() {
#ifdef HOME
  freopen("input.txt", "r", stdin);
#endif
  int n, k, qt = 0;
  scanf("%d%d\n", &n, &k);
  fgets(str, maxn, stdin);
  int b, e;
  b = e = 0;
  l[qt] = 0; r[qt] = 0; ++qt;
  while (e < n && b < n) {
    while (str[b] == '1') ++b;
    if (b == n) break;
    for (e = b; str[e] == '0' && e < n; ++e);
    l[qt] = b;
    r[qt] = e;
//    cerr << qt << ' ' << b << ' ' << e << endl;
    ++qt;
    b = e + 1;
  }
  l[qt] = n;
  r[qt] = n;
  ++qt;
  if (qt - 2 <= k) {
    cout << n;
    return 0;
  }
  int ans = 0;
  for (int itr = k + 1; itr < qt; ++itr) {
    ans = max(ans, l[itr] - r[itr - k - 1]);
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <list>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <chrono>
#include <valarray>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = std::vector<int>;
using Vlli = std::vector<lli>;
using Wint = std::vector<Vint>;
using Wlli = std::vector<Vlli>;
using Vbool = std::vector<bool>;
using Wbool = std::vector<Vbool>;
using pii = std::pair<int, int>;
using pll = std::pair<lli, lli>;
template <class T>
using Vec = std::vector<T>;

constexpr int MOD = 1e9 + 7;
constexpr int INFi = 2e9 + 1;
constexpr lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {std::make_pair(1, 0), std::make_pair(-1, 0), std::make_pair(0, 1), std::make_pair(0, -1)};
constexpr char BR = '\n';

#define DEBUG(x) std::cerr << #x << " = " << x << '\n';
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i))
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(ele, vec) for(auto &(ele) : (vec))
#define vREPcopy(ele, vec) for(auto (ele) : (vec))
#define SORT(A) std::sort((A).begin(), (A).end())
#define rSORT(A) std::sort((A).rbegin(), (A).rend())
// 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A)
#define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end())



template <class T> inline int argmin(std::vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(std::vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){if(a < b) a = b;}
template <class T> inline void chmin(T &a, T b){if(a > b) a = b;}
inline int BitI(int k){return 1 << k;}
inline lli BitL(int k){return 1LL << k;}
inline void putsDouble(double d){printf("%.16lf\n", d);}
inline int toInt(const string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res;
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;}
  std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~




int main(void){
  int n; scanf("%d", &n);
  const int theree_n = n + (n << 1), double_n = n << 1;
  Vint A(theree_n); REP(i, theree_n) scanf("%d", &A[i]);
  std::sort(A.begin(), A.end(), std::greater<int>());
  lli res = 0;
  for(int i = 1; i < double_n; i += 2) res += A[i];
  printf("%lld\n", res);
  return 0;
}

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fastt ios_base::sync_with_stdio(false); cin.tie(NULL)
#define debug1(x) cout<<#x<<" : "<<x<<endl
#define debug2(x,y) cout<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<endl
#define debug3(x,y,z) cout<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<" "<<#z<<" : "<<z<<endl

typedef long long ll;
typedef pair<ll,ll> pii;
const ll modd=1e9+7;

ll poww(ll a,ll b){
  ll ans=1;
  while(b>0){
    if(b%2==1) ans=(ans*a);
    a=(a*a);
    b=b/2;
  }
  return ans;
}

/*-----------------------------------------------------------------------*/

ll grundy[200000];

int main(){
   fastt;

   ll n,k;
   cin>>n>>k;

   vector <ll> a,b;

   for(ll i=0;i<n;i++){
   	  ll x;
   	  cin>>x;
   	  a.pb(x);
   }

   sort(a.begin(),a.end());
   ll last=a[0];

   for(ll i=0;i<a.size();i++){
   	   if(a[i]!=last){
   	   	  b.pb(last);
   	   	  last=a[i];
   	   }
   }

   b.pb(last);

   grundy[0]=0;

   for(ll i=1;i<=k;i++){
       set <ll> st;
       for(ll j=0;j<b.size();j++){
       	  if(i-b[j]>=0)
       	  	st.insert(grundy[i-b[j]]);
       }
       ll k=0;
       for(auto j : st){
       	 if(k!=j)
       	 	break;
       	 k++;
       }
       grundy[i]=k;
   }

   if(grundy[k]!=0)
   	  cout<<"First"<<endl;
   else
   	  cout<<"Second"<<endl;

   return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

struct RollingHash {
    static const ull mod1 = (1ULL << 61) - 1, mod2 = (1ULL << 31) - 1;
    static const ull base1 = 9733, base2 = 9973;
    static const ull p1 = mod1 * 4, p2 = mod2 * 2;

    int N;
    vector<ull> hash1, hash2, power1, power2;

    RollingHash(vector<int> &S) {
        N = S.size() - 1;
        hash1.assign(N + 1, 0);
        hash2.assign(N + 1, 0);
        power1.assign(N + 1, 1);
        power2.assign(N + 1, 1);
        for (int i = 0; i < N; ++i) {
            hash1[i + 1] = calcmod1(mul1(hash1[i], base1) + (S[i] ^ S[i + 1]));
            hash2[i + 1] = calcmod2(mul2(hash2[i], base2) + (S[i] ^ S[i + 1]));
            power1[i + 1] = calcmod1(mul1(power1[i], base1));
            power2[i + 1] = calcmod2(mul2(power2[i], base2));
        }
    }

    inline ull mul1(ull a, ull b) {
        ull au = a >> 31, ad = a & mod2;
        ull bu = b >> 31, bd = b & mod2;
        ull c = au * bd + ad * bu;
        ull cu = c >> 30, cd = c & (mod2 >> 1);
        return 2 * au * bu + ad * bd + cu + (cd << 31);
    }

    inline ull mul2(ull a, ull b) {
        ull c = a * b;
        ull cu = c >> 31, cd = c & mod2;
        return cu + cd;
    }

    inline ull calcmod1(ull a) {
        ull au = a >> 61, ad = a & mod1;
        ull res = au + ad;
        if (res >= mod1)
            res -= mod1;
        return res;
    }

    inline ull calcmod2(ull a) {
        while (a >= mod2)
            a -= mod2;
        return a;
    }

    inline pair<ull, ull> get(int l, int r) {
        ull res1 = calcmod1(hash1[r] + p1 - mul1(hash1[l], power1[r - l]));
        ull res2 = calcmod2(hash2[r] + p2 - mul2(hash2[l], power2[r - l]));
        return {res1, res2};
    }

    inline void solve(vector<int> &S, vector<int> &T) {
        int Tlen = T.size() - 1;
        if (Tlen > N)
            return;

        pair<ull, ull> t_hash = {0, 0};

        for (int i = 0; i < Tlen; ++i) {
            t_hash.first = calcmod1(mul1(t_hash.first, base1) + (T[i] ^ T[i + 1]));
            t_hash.second = calcmod2(mul2(t_hash.second, base2) + (T[i] ^ T[i + 1]));
        }

        for (int i = 0; i + Tlen <= N; ++i) {
            int tmp = S[i] ^ T[0];
            pair<ull, ull> s_hash = get(i, i + Tlen);
            if (s_hash == t_hash)
                cout << i << " " << tmp << '\n';
        }
    }
};

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

    int N;
    cin >> N;
    vector<int> a(2 * N), b(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i], a[i + N] = a[i];
    for (int i = 0; i < N; ++i)
        cin >> b[i];
    a.pop_back();

    RollingHash rhs(a);
    rhs.solve(a, b);

    return 0;
}


Measured memory_bytes: 18304
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1 << 28;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};

class Point
{
public:
  int x, y;
  Point(int _x = 0, int _y = 0)
    :x(_x), y(_y) {}
};

int N, cost[20][20][20][20], dist[11][11], dp[1 << 11][11];

int solve(int S, int v)
{
  if (dp[S][v] != -1)
    return dp[S][v];

  if (S == (1 << N)-1) {
    dp[S][v] = 0;
    return 0;
  }

  int ret = INF;
  for (int i = 0; i < N; ++i) {
    if (!(S & (1 << i)))
      ret = min(ret, solve(S | (1 << i), i)+dist[v][i]);
  }
  dp[S][v] = ret;
  return ret;
}

int main()
{
  int w, h;
  while (cin >> w >> h) {
    if ((w | h) == 0)
      break;

    // init
    for (int i = 0; i < 20; ++i) {
      for (int j = 0; j < 20; ++j) {
	for (int k = 0; k < 20; ++k) {
	  for (int l = 0; l < 20; ++l)
	    cost[i][j][k][l] = INF;
	}
      }
    }
    for (int i = 0; i < 11; ++i) {
      for (int j = 0; j < 11; ++j)
	dist[i][j] = 0;
    }
    for (int i = 0; i < (1 << 11); ++i) {
      for (int j = 0; j < 11; ++j)
	dp[i][j] = -1;
    }

    vector<string> floor(h);
    for (int i = 0; i < h; ++i)
      cin >> floor[i];

    Point robot;
    vector<Point> tiles;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
	if (floor[i][j] == 'x') {
	  continue;
	} else if (floor[i][j] == 'o') {
	  robot.x = j;
	  robot.y = i;
	} else if (floor[i][j] == '*') {
	  tiles.push_back(Point(j, i));
	}
      }
    }

    tiles.insert(tiles.begin(), robot);
    for (unsigned int i = 0; i < tiles.size(); ++i) {
      queue<Point> que;
      que.push(tiles[i]);
      cost[tiles[i].y][tiles[i].x][tiles[i].y][tiles[i].x] = 0;
      while (!que.empty()) {
	const Point p = que.front();
	que.pop();

	for (int d = 0; d < 4; ++d) {
	  Point pp(p.x + dx[d], p.y + dy[d]);
	  if (pp.x < 0 || pp.x >= w || pp.y < 0 || pp.y >= h || floor[pp.y][pp.x] == 'x')
	    continue;
	  if (cost[tiles[i].y][tiles[i].x][pp.y][pp.x] > cost[tiles[i].y][tiles[i].x][p.y][p.x]+1) {
	    cost[tiles[i].y][tiles[i].x][pp.y][pp.x] = cost[tiles[i].y][tiles[i].x][p.y][p.x]+1;
	    que.push(pp);
	  }
	}
      }
    }

    bool valid = true;
    for (unsigned int i = 0; i < tiles.size(); ++i) {
      for (unsigned int j = i+1; j < tiles.size(); ++j) {
	dist[i][j] = dist[j][i] = cost[tiles[i].y][tiles[i].x][tiles[j].y][tiles[j].x];
	if (dist[i][j] >= INF)
	  valid = false;
      }
    }

    if (!valid) {
      cout << "-1" << endl;
    } else {
      N = tiles.size();
      cout << solve(1, 0) << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1644
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

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

const int INF = 1e9;
const long long LINF = 1e18;

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

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

    int ans = 0;
    int index = 0;
    while (true) {
        if (a[index] == -1) {
            cout << -1 << endl;
            return 0;
        }
        else if (index == 1) {
            cout << ans << endl;
            return 0;
        }
        int nextIndex = a[index] - 1;
        a[index] = -1;
        ans++;
        index = nextIndex;
    }

    return 0;
}


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

int main(){
    int a,b,c,d;
    cin >> a >> b >> c;
    d=b+c-a;
    if(d<0) d=0;
    cout << d << endl;

    return 0;
}


Measured memory_bytes: 256
# ABC 135, C

n = int(input())
A = [int(el) for el in input().split(' ')]
B = [int(el) for el in input().split(' ')]

total = 0
for i in range(n):
    if i == 0:
        f = min(A[0], B[0])
        g = min(A[1], B[0]-f)
        total += f + g
    else:
        f = min(A[i] - g, B[i])
        g = min(A[i+1], B[i] - f)
        total += f + g



print(total)





Measured memory_bytes: 18348
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
// #define mp make_pair
#define pq priority_queue
const ll mod=1000000007;
#define f first
#define s second
#define pii pair< ll, ll >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace boost::multiprecision;
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int N=1000005;
ll fact[N],invfact[N];
ll power(ll x,ll y){
  if(y<=0) return 1LL;
  ll z=power(x,y/2);
  if(y%2) return (((z*z)%mod)*x)%mod;
  return (z*z)%mod;
}

void pre(){
  fact[0]=invfact[0]=invfact[1]=fact[1]=1;
  rep(i,2,N) fact[i]=(i*fact[i-1])%mod;
  rep(i,2,N) invfact[i]=(invfact[i-1]*power(i,mod-2))%mod;
}
ll nCr(ll n,ll k){ return (((fact[n]*invfact[n-k])%mod)*invfact[k])%mod; }



const int N1=1e6+1;
vector<int> isprime(N1,1),prime;
void seive(){
  rep(i,2,sqrt(N1)+1){
      if(isprime[i]){
        for(int j=i*i;j<N1;j+=i) isprime[j]=0;
        prime.pb(i);
      }
  }
  rep(i,sqrt(N1)+1,N1) if(isprime[i]) prime.pb(i);
}



struct dsu {
    vector<int> par, rank;
    dsu(int n): par(n+1), rank(n+1) {
        for (int i = 0; i <= n; i++) {
            par[i] = i;
            rank[i]= 1;
        }
    }
    int root(int a) {
        if (a == par[a]) return a;
        return par[a] = root(par[a]);
    }
    void merge(int a, int b) {
        a = root(a);
        b = root(b);
        if (a == b) return;
        if (rank[a] > rank[b]) swap(a, b);
        par[b] = a;
    }
    set<int> parent(int n){
        set<int> s;
        for(int i=1;i<=n;i++){
            s.insert(root(i));
        }
        return s;
    }
};

void solve(){
  int n;
  cin>>n;
  cout<<n/3<<endl;
  // bool ok=false;
  // int cnt=0;
  // while(n>=3){
  //   ok=true;
  //   cnt++;
  //   n-=3;
  // }
  // if(ok) cout<<cnt<<endl;
  // else cout<<0<<endl;
}

int main(){
    optimizeIO();
    int r=1;
    {solve();}
}


Measured memory_bytes: 7068
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=51;
const int INF=2147483647;
int n,minnum=INF,maxnum=-INF,minpos,maxpos;
int arr[MAXN];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		arr[i]=read();
		if(maxnum<arr[i]) {maxnum=arr[i];maxpos=i;}
		if(minnum>arr[i]) {minnum=arr[i];minpos=i;}
	}
	printf("%d\n",2*n-1);
	if(maxnum>=-minnum)
	{
		for(int i=1;i<=n;++i)
			printf("%d %d\n",maxpos,i);
		for(int i=2;i<=n;++i)
			printf("%d %d\n",i-1,i);
	}
	else
	{
		for(int i=1;i<=n;++i)
			printf("%d %d\n",minpos,i);
		for(int i=n;i>=2;--i)
			printf("%d %d\n",i,i-1);
	}
	return 0;
}

Measured memory_bytes: 384
N = int(input())
A = [int(a) for a in input().split()]
B = [0]
for a in A:
    B.append(B[-1]+a)

dp = [[0] * N for _ in range(N)]

for d in range(1, N):
    for l in range(N-d):
        r = l + d
        if d == 0:
            dp[l][r] = A[l]
            
        else:
            dp[l][r] = 10**20
            for m in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + B[r+1]-B[l])
    
print(dp[0][N-1])

Measured memory_bytes: 46940
#include<cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>

using namespace std;
int main(){
    long long n,k;
    cin>>n>>k;
    long long a[100001];
    for (int i=0;i<100001;i++){
        a[i]=0;
    }
    for (int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        a[x-1]+=y;
    }
    int ans;
    int i=0;
    while (i<100001){
        
        if (k<=a[i]) {
            ans=i+1;
            break;
        }
        else{
            k=k-a[i];
            i+=1;
        }
    }
    printf ("%d",ans);
    return 0;
}
  


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
const int Q = 10005;

using namespace std;

int main(){
    int N;
    int sum;
    cin >> N;
    int x,y,z;
    x = y = z = 1;
    vector<int> cnt(Q);

    for(int i = 1 ; i <= 105; i++){
        for(int j = 1 ; j <= 105; j++){
            for(int k = 1 ; k <= 105 ; k++){
                //cout << x << " " << y << " " << z << endl;
                sum = x*x + y*y + z*z +  x*y + y*z + z*x ;
                //cout << s << " "<< sum << " "<< endl;
                if(sum < Q){
                    cnt[sum]++ ;
                    z++;
                    sum = 0;
                }
            }
            z = 1 ;
            y++;
        }
        y = 1;
        x++;
    }
    
    for(int i = 1 ; i <= N ; i++){
        cout << cnt[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
using namespace std;
int main()
{
	int n, m, t, tot;
	cin >> n >> m;
	tot = 0;
	rep(i, m) {
		cin >> t;
		tot += t;
	}
	cout << max(-1, n - tot) << endl;
	return 0;
}

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

int main(){
	int n;
	cin>>n;
	while(n >= 0){
		if(n - 1000 > 0)
		n -= 1000;
		else{
			cout<<1000 - n<<endl;
			break;
		}
		
	}
}


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

int N, K;

int main() {
    int ans = 1e9;
    
    cin >> N >> K;
    vector<int> x(N);
    vector<int> negX, posX;
    negX.push_back(0);
    posX.push_back(0);
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            K--;
        } else if (x < 0) {
            negX.push_back(x);
        } else {
            posX.push_back(x);
        }
    }
    
//    posXからi個, negXからK -i個とる
    for (int i = 0; i <= K; i++) {
        if (negX.size() < K - i + 1 || posX.size() < i + 1) {
            continue;
        }
        
        int timeP = posX[i], timeN = - negX[negX.size() - K + i];
        int time = min(2 * timeP + timeN, 2 * timeN + timeP);
        ans = min(ans, time);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1404
from operator import itemgetter
N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort()
if N%2 == 1:
    mini = L[N//2][0]
    L.sort(reverse=True, key=itemgetter(1))
    maxi = L[N//2][1]
    ans = maxi-mini+1
else:
    mini = (L[N//2][0]+L[N//2-1][0])
    L.sort(reverse=True, key=itemgetter(1))
    maxi = (L[N//2][1]+L[N//2-1][1])
    ans = maxi-mini+1

print(ans)

Measured memory_bytes: 45624
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;




int main() {
	int n; cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	ll cur = 1, ans = 0; int pos = 0;
	while (true) {
		while (pos < n && a[pos] < cur) pos++;
		if (pos >= n) break;
		if (a[pos] == cur) cur++;
		else ans += (a[pos] - 1) / cur, a[pos] = 1;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define ld long double
#define MAX 100007
#define pb push_back
#define MOD 1000000007
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    string s;
    cin>>s;
    for(ll i=0;i<s.length();i++)
    {
    	if(s[i]=='?')
    		s[i]='D';
    }
    cout<<s;
    return 0;
}

Measured memory_bytes: 3768
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=998244353;
const LL LINF=1LL<<62;
const LL INF=1<<30;

int memo[31][31][4];
struct E {P ps;int cost;int k;};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main(){
    int w,h;
    while(cin >> w >> h){
        if(!w&&!h) break;
        int s[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> s[i][j];
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                for (int k = 0; k < 4; k++) {
                    memo[i][j][k]=INF;
                }
            }
        }
        int C[4];
        for (int i = 0; i < 4; i++) {
            cin >> C[i];
        }
        queue<E> q;   
        q.push({P(0,0),0,0});
        while(!q.empty()){
            E e=q.front();q.pop();
            P p=e.ps;
            int kk=e.k;
            int c=e.cost;
            if(memo[p.fs][p.sc][kk]<=e.cost) continue;
            memo[p.fs][p.sc][kk]=e.cost;
            for (int i = 0; i < 4; i++) {
                int nx=p.sc+dx[(i+kk)%4],ny=p.fs+dy[(i+kk)%4];
                int nc=c+(s[p.fs][p.sc]==i?0:C[i]);
                if(0<=nx&&nx<w&&0<=ny&&ny<h){
                    q.push({P(ny,nx),nc,(i+kk)%4});
                }
            }
        }
        int ans=INF;
        for (int i = 0; i < 4; i++) {
            ans=min(ans,memo[h-1][w-1][i]);
        }
        cout << ans << endl;
    }
    return 0;
}




Measured memory_bytes: 3632
#include<iostream>
#include<string>

using namespace std;

int main() {
	string O,E;
	cin >> O;
	cin >> E;

	if (O.length() == E.length()) {

		for (int i = 0; i < O.length(); i++) {
			cout << O[i] << E[i];
		}


	}else {
		
		for (int q = 0; q < E.length(); q++) {
			cout << O[q] << E[q];
		}
	    cout<<O.back();
	
	}
	




	
}

Measured memory_bytes: 256
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));

  $ans = array_fill(0, 10001, 0);
  for ($i=1; $i<100; $i++) {
    for ($j=1; $j<100; $j++) {
      for ($k=1; $k<100; $k++) {
        $p = $i*$i + $j*$j + $k*$k + $i*$j + $i*$k + $j*$k;
        if($p < 10001){
          $ans[$i*$i + $j*$j + $k*$k + $i*$j + $i*$k + $j*$k]++;
        }
      }
    }
  }

  for ($i=1; $i<=$n; $i++) {
    echo $ans[$i].PHP_EOL;
  }

Measured memory_bytes: 16252
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
using edge = pair<int, ll>;
using Graph = vector<vector<int>>; 
using WeightedGraph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main(){
char c; cin >> c;
string ans = "consonant";
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')ans = "vowel";
cout << ans << endl;
}


Measured memory_bytes: 256
S = int(input())
a = S // 100
b = S % 100
if (a == 0 and b == 0) or (12 < a and 12 < b) or (12 < a and b == 0) or (12 < b and a == 0):
  print("NA")
elif 0 < a < 13 and 0 < b < 13:
  print("AMBIGUOUS")
elif 0 < a < 13 and b >= 0:
  print("MMYY")
elif 0 < b < 13 and a >= 0:
  print("YYMM")

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

int main(){
    int len;
    string S;
    int K;
    char t;
    
    cin >> len;
    cin >> S;
    cin >> K;
    
    // get k-1 char
    t = S[K-1];
    
    for(int i = 0; i < len; i++){
        if(S[i] != t){
            S[i] = '*';
        }
    }
    
    cout << S << endl;
    return 0;
}


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

using namespace std;

struct node{
	int v;
	vector<node> l;
	vector<node> r;

	void out(){
		//cout << "out " << (int)v << " " << (int)l.size() << endl;
		cout << "(";
		if( !l.empty() ) l.back().out();
		cout << ")[" << v << "](";
		if( !r.empty() ) r.back().out();
		cout << ")";
	}
};

node parse(int &p, string &S){
	node ret;
	p++;
	if( S[p] != ')' ){
		ret.l.push_back( parse(p, S) );
		//while( S[p] != ')' ) p++;
	}
	p++;
	p++;
	int val=0;
	while( S[p] != ']' ){
		val = val * 10 + (S[p]-'0');
		p++;
	}
	ret.v = val;
	p++;
	p++;
	if( S[p] != ')' ){
		ret.r.push_back( parse(p, S) );
		//while( S[p] != ')' ) p++;
	}
	p++;
	return ret;
}

node merge(node &n1, node &n2){
	node ret;
	ret.v = n1.v + n2.v;
	if( !n1.l.empty() && !n2.l.empty() ){
		ret.l.push_back( merge(n1.l[0], n2.l[0]) );
	}
	if( !n1.r.empty() && !n2.r.empty() ){
		ret.r.push_back( merge(n1.r[0], n2.r[0]) );
	}
	return ret;
}

int main(){
	int N, M, T, cur=0, ans=0;
	string S1, S2;

	cin >> S1 >> S2;
	int p1=0, p2=0;
	node n1 = parse(p1, S1);
	node n2 = parse(p2, S2);

	//n1.out();
	//cout << endl;
	//n2.out();
	//cout << endl;

	merge( n1, n2 ).out();
	cout << endl;

	return 0;
}

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

using namespace std;

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

  vector<int> a(3);
  for (int i = 0; i < 3; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int sum = 0;
  int cost = a[0];
  for (int i = 1; i < 3; ++i) {
    sum += a[i] - cost;
    cost = a[i];
  }
  cout << sum << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#include <stack>
#include <fstream>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>

using namespace std;

constexpr int INF = 1000000000;/* 1e+9a */
constexpr int MODULO = 1000000007;

typedef int64_t ll;


ll sunuke(ll n){
    if(n < 10)
        return n;
    return sunuke(n/10) + n % 10;
}


ll sun(ll n){
    ll mini = n;
    double mins = n / sunuke(n);
    int d = 0;
    ll meslog = n + 1;
    while(meslog > 0){
        meslog /= 10;
        d++;
    }
    ll divid = 10;
    for (int i = 0; i <= d; ++i) {
        ll t = n / divid;
        t++;
        t *= divid;
        t--;
        ll sunt = sunuke(t);
        double fsn = double(t) / sunt;
        if(fsn <= mins){
            if(fsn < mins || t < mini){
                mini = t;
                mins = fsn;
            }
        }
        divid *= 10;
    }

    return mini;

}

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

    ll n;
    cin >> n;
    ll pren = 0;
    for (int i = 0; i < n; ++i) {
        pren = sun(pren+1);
        cout << pren << '\n';
    }

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <bitset>
#include <cassert>

using namespace std;

char a[309][309];

int f[309][309];
int cnt1[309][309];
int cnt2[309][309];

int main() {
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            cin >> a[i][j];
    long long ans = 0;
    for (int i = 0; i + 1 < w; ++i) {
        for (int i1 = 0; i1 <= h; ++i1)
            f[i1][0] = 0;
        for (int i2 = 0; i2 <= h; ++i2)
            f[0][i2] = 0;
        for (int d = 0; d <= h; ++d) {
            int i1 = 0, i2 = d;
            cnt1[d][0] = 0;
            int curh = 1;
            while (curh <= h - d) {
                cnt1[d][curh] = cnt1[d][curh - 1];
                if (a[i1][i] == a[i2][i + 1])
                    cnt1[d][curh]++;
                ++i1;
                ++i2;
                ++curh;
            }
        }
        for (int d = 0; d <= h; ++d) {
            int i1 = d, i2 = 0;
            cnt2[d][0] = 0;
            int curh = 1;
            while (curh <= h - d) {
                cnt2[d][curh] = cnt2[d][curh - 1];
                if (a[i1][i] == a[i2][i + 1])
                    cnt2[d][curh]++;
                ++i1;
                ++i2;
                ++curh;
            }
        }
        for (int i1 = 1; i1 <= h; ++i1) {
            for (int i2 = 1; i2 <= h; ++i2) {
                if (i1 <= i2) {
                    f[i1][i2] = cnt1[i2 - i1][i1];
                } else {
                    f[i1][i2] = cnt2[i1 - i2][i2];
                }
                f[i1][i2] += min(f[i1 - 1][i2], f[i1][i2 - 1]);
            }
        }
        //cout << f[h][h] << endl;
        ans += f[h][h];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {
	static class MaximumHeaps {
		public void mh (InputReader ir) {
			
			int h = ir.nextInt();
			Node[] node = new Node[h + 1];
			
			for (int i = 1; i <= h; i++) {
				node[i] = new Node ();
				node[i].key = ir.nextInt();
			}
			
			Heaps (node, h);
			BuildMaxHeap (node, h);
			
			StringBuilder sb = new StringBuilder ();
			
			for (int i = 1; i <= h; i++) sb.append(" ").append(node[i].key);
			
			System.out.println(sb);
			
			
		}
		
		static void Heaps (Node[] node, int n) {
			
			for (int i = 1; i <= n; i++) {
				if (i / 2 > 0) node[i].parent = node[i / 2].key;
				if ( i * 2  <= n) node[i].left = node[ i * 2].key;
				if ( i * 2 +1 <= n) node[i].right = node[ i * 2 + 1].key;
			}
			
		}
		
		
		static void MaxHeapify(Node[] node, int i, int n) {
			
			int l = i * 2;
			int r = i * 2 + 1;      
			int largest = i;
		        
			if (l <= n && node[l].key > node[i].key) largest = l;
			else largest = i;
			
			if (r <= n && node[r].key > node[largest].key) largest = r;    
		    
			if (largest != i) {
				int tmp = node[i].key;
				node[i].key = node[largest].key;
				node[largest].key = tmp;
				MaxHeapify(node, largest, n);
			}		
		}
		    
		
		static void BuildMaxHeap(Node[] node, int n) {
			for(int i = n / 2; i >= 1; i--) {
				MaxHeapify(node, i, n);	
			}    
		}
		
		
	}
	
	static class Node {
		Integer key;
		Integer parent;
		Integer left;
		Integer right;
		Node () {
			key = null;
			parent = null;
			left = null;
			right = null;
		}
	}
	
	static class InputReader {
		BufferedReader br;
		StringTokenizer st;
		
		public String nextString() {
			
			 while (!st.hasMoreTokens()) {
	                try {
	                    st = new StringTokenizer(br.readLine(), " ");
	                } catch (IOException e) {
	                    throw new InputMismatchException();
	                }
	            }
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(nextString());
		}
					
		public InputReader (InputStream inputStream) {
			br = new BufferedReader (new InputStreamReader (inputStream));
			st = new StringTokenizer ("");
		}
		
	}
	
	public static void main (String[] args) {
		InputStream inputStream = System.in;
		InputReader in = new InputReader (inputStream);
		MaximumHeaps obj = new MaximumHeaps ();
		obj.mh (in);
	}
	
	
}



Measured memory_bytes: 139776
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long
//#define lint long long

const int INF = 1e9;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで


using namespace std;
int r , d, x;

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


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
// import java.time.*;

public class Main {
    static StringBuilder sb;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sb = new StringBuilder();

        int n = sc.nextInt();

        List<Integer> a = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            a.add(Integer.parseInt(sc.next()));
        }

        int m = sc.nextInt();

        List<Integer> ans = new ArrayList<>();

        int index = 0;
        for (int i = 0; i < m; i++) {
            int tmp = Integer.parseInt(sc.next());
            while (index < a.size() && a.get(index) < tmp) {
                index++;
            }
            if (index == a.size()) break;
            if (a.get(index) == tmp) ans.add(tmp);
        }

        for (int i = 0; i < ans.size(); i++) {
            sb.append(ans.get(i)).append("\n");
        }

        PrintWriter out = new PrintWriter(System.out);
        out.print(sb);
        out.flush();
        
        sc.close();
    }
}



Measured memory_bytes: 110512
#include <stdio.h>

#define MAX 40

void solve(int*,int*,int);

int n, post[MAX], idx;

int main(){
  int pre[MAX], in[MAX], i;

  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d",pre+i);
  }
  for(i = 0 ; i < n ; i++){
    scanf("%d",in+i); 
  }

  solve(pre, in, n);

  for(i = 0 ; i < n ; i++){
    printf("%d%c",post[i],(i != n-1 ? ' ':'\n'));
  }

  return 0;
}

void solve(int pre[], int in[], int N){
  int i, p;

  for(i = 0 ; i < N ; i++){
    if(in[i] == pre[0]){
      p = i;
      break;
    }
  }

  if(p != 0){
    solve(pre+1, in, p);
  }
  if(p != N-1){
    solve(pre+p+1, in+p+1, N-p-1);
  }
  post[idx++] = pre[0]; 
}


Measured memory_bytes: 2144
import Control.Monad
import Control.Applicative

solve :: Int -> Int -> String
solve n x =
    "Case " ++ show n ++ ": " ++ show x

main =
    mapM_ putStrLn =<< (zipWith solve [1..]) . takeInputs . lines <$> getContents
    where
    takeInputs :: [String] -> [Int]
    takeInputs = takeWhile (/= 0) . map read 


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

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 998244353
#define inf 100000000000010
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
#define all(x) (x).begin(), (x).end()

typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pi;

bool prime(ll n)
{
    if(n<=1)return false;
    if(n<=3)return true;
    if(n%2==0||n%3==0)return false;
    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0||n%(i+2)==0)return false;
    }
    return true;
}

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1)r=(r*a)%m;
        b = b>>1;
        a=(a*a)%m;
    }
    return r%m;
}

struct CustomCompare
{
    bool operator()(const int& lhs, const int& rhs)
    {
        return lhs < rhs;
    }
};

bool comp(pair<ll, pi>a,pair<ll,pi>b)
{
    if(a.se.fi==b.se.fi)return a.se.se>b.se.se;
    return a.se.fi>b.se.fi;
}

ll builtin_popcount(ll x)
{
    ll cnt = 0;
    for(ll i=60;i>=0;i--)
    {
        if((1LL<<i)&x)cnt++;
    }
    return cnt;
}


int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
vi arr(5);
ll ans = 0;
rep(i,0,5)cin>>arr[i];
rep(i,0,5)
{
    if(arr[i]==0)ans = i;
}
cout<<ans+1<<endl;
return 0;
}
/*
50 25
39 99 70 24 49 13 86 43 88 74 45 92 72 71 90 32 19 76 84 46 63 15 87 1 39 58 17 65 99 43 83 29 64 67 100 14 17 100 81 26 45 40 95 94 86 2 89 57 52 91 45
1221 360 459 651 958 584 345 181 536 116 1310 403 669 1044 1281 711 222 280 1255 257 811 409 698 74 838
*/


Measured memory_bytes: 3608
n = int(input())
a = list(map(int,input().split()))
cnt2 = 0
cnt4 = 0

for i in range(n):
    if a[i] % 4 == 0:
        cnt4 += 1
    elif a[i] % 2 == 0:
        cnt2 += 1

if cnt2 % 2 == 1:
    if cnt2 > 2:
        cnt2 -= 1
    else:
        cnt2 = 0

if n - ((cnt4*3)-(cnt4-1))-cnt2 <= 0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 14224
use std::io;
use std::ops::Sub;
use std::cmp;
use std::iter;

const P: u64 = 1000000007;

fn main() {
    let (x, y) = read_input();
    println!("{}", solve(x, y));
}

fn read_input() -> (u64, u64) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).expect("input");
    let mut parsed = input
        .trim()
        .split_whitespace()
        .map(|n| n.parse().expect("invalid as number"));
    (parsed.next().expect("not enought ints"), parsed.next().expect("not enought ints"))

}


fn solve(n: u64, m: u64) -> u64 {
    match diff(n, m) {
        0 => n.mfac().mmul(&m.mfac()).mmul(&2),
        1 => n.mfac().mmul(&m.mfac()),
        _ => 0,
    }
}

// THIS TOTALLY SUCKS
fn diff<A: Sub + std::cmp::PartialOrd>(n: A, m: A) -> A::Output {
    if n > m { n - m } else { m - n }
}

trait ModMult {
    fn mmul(&self, other: &Self) -> Self;
    fn mfac(&self) -> Self;
}

impl ModMult for u64 {
    fn mmul(&self, other: &u64) -> u64 {
        (self * other) % P
    }
    fn mfac(&self) -> Self {
        // (*self..1).step_by(-1).fold(1, |acc, &n| acc.mmul(n))
        let mut acc: u64 = 1;
        for i in (1..*self + 1).rev() {
            acc = acc.mmul(&i);
        }
        acc
    }
}

Measured memory_bytes: 4352
fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let a: Vec<i8> = s.by_ref().take(9).map(|a| a.parse().unwrap()).collect();
	let n: usize = s.next().unwrap().parse().unwrap();
	let mut c = vec![false; 9];
	for _ in 0..n {
		let b: i8 = s.next().unwrap().parse().unwrap();
		for i in 0..9 {
			if a[i] == b {
				c[i] = true;
			}
		}
	}
	let mut ok = false;
	for i in 0..3 {
		ok |= c[i] && c[3 + i] && c[6 + i];
		ok |= c[i * 3] && c[i * 3 + 1] && c[i * 3 + 2];
	}
	ok |= (c[0] && c[4] && c[8]) || (c[2] && c[4] && c[6]);
	if ok {
		println!("Yes");
	} else {
		println!("No");
	}
}


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

using Vertex = int;
using Weight = long long;

struct Edge{
    Vertex from, to;
};

struct VW{
    Vertex v;
    Weight w;
};

struct Tree{
    int nV;
    Vertex root;
    vector<Edge> edges;
    vector<vector<Vertex>> adj;
    vector<Vertex> parent;
    vector<int> subtree_size;
    void add_edge(Vertex a, Vertex b){
        edges.push_back(Edge{a, b});
    }
    void build(Vertex _root = 0){
        root = _root;
        nV = 0;
        for (auto edge : edges) nV = max(nV, max(edge.from, edge.to));
        adj.resize(++nV);
        parent.assign(nV, 0);
        subtree_size.assign(nV, 0);
        for (auto edge : edges){
            adj[edge.from].push_back(edge.to);
            adj[edge.to].push_back(edge.from);
        }
        dfs(root);
    }
    int dfs(Vertex v){
        subtree_size[v] = 1;
        for (auto u : adj[v]) {
            if (subtree_size[u] == 0) {
                subtree_size[v] += dfs(u);
                parent[u] = v;
            }
        }
        return subtree_size[v];
    }
};

class Centroid{
    const Tree &t;
public:
    Centroid(const Tree &_t): t(_t){}
    vector<Vertex> find(){
        vector<Vertex> centroids;
        for (Vertex v = 0; v != t.nV; ++v) {
            bool is_centroid = true;
            for (auto u : t.adj[v]){
                if ((u == t.parent[v] ? t.nV - t.subtree_size[v] : t.subtree_size[u]) > t.nV/2) is_centroid = false;
            }
            if (is_centroid) centroids.push_back(v);
        }
        return centroids;
    }
};

long long calc_upper_bound(const Tree &t, const vector<vector<VW>> &costs){
    long long ret = 0;
    auto nV = t.nV;
    for (Vertex u = 0; u != nV; ++u){
        for (const auto &vw : costs[u]){
            if (vw.v == t.parent[u]){
                ret += vw.w * min(t.subtree_size[u], nV - t.subtree_size[u]);
            }else{
                ret += vw.w * min(t.subtree_size[vw.v], nV - t.subtree_size[vw.v]);
            }
        }
    }
    return ret;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<VW>> costs(N, vector<VW>());
    Tree tree;
    for (int m = 1; m != N; ++m){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        costs[--a].push_back(VW{--b, c});
        costs[b].push_back(VW{a, c});
        tree.add_edge(a, b);
    }
    tree.build();
    auto upper_bound = calc_upper_bound(tree, costs);
    Centroid cntr(tree);
    auto cntrs = cntr.find();
    if (cntrs.size() == 1){
        long long min_cost = 1e9;
        for (const auto &vw : costs[cntrs[0]]){
            min_cost = min(min_cost, vw.w);
        }
        cout << upper_bound - min_cost << endl;
    }else{
        for (const auto & vw : costs[cntrs[0]]){
            if (vw.v == cntrs[1]){
                cout << upper_bound - vw.w << endl;
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 18036
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    string s,t,ans="Yes"; cin>>s>>t;
    map<char,char> q;
    set<char> r;
    rep(i,s.size()){
        if(q.count(s[i])){
            if(q[s[i]]!=t[i]){
                ans="No";
                break;
            }
        }
        else{
            if(r.count(t[i])){
                ans="No";
                break;
            }
            else{
                r.insert(t[i]);
                q[s[i]]=t[i];
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 776
#include <iostream>

using namespace std;

void print(int H, int W) {
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cout << "#";
        }
        cout << endl;
    }
}

int main() {
    int H, W;
    while (cin >> H >> W) {
        if (H == 0 && W == 0) {
            break;
        }
        print(H, W);
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3096
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>
#include<iostream>
#include<iomanip>
using namespace std;

int main() {
	int N, P[200000], m, ans;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> P[i];
	}
	m = 10000000;
	ans = 0;
	for (int i = 0; i < N; i++) {
		if (m > P[i]) {
			ans++;
			m = P[i];
		}
	}
	cout << ans;
}

Measured memory_bytes: 1024
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    private static boolean debug = false;
    private static boolean elapsed = false;

    private static PrintWriter _out = new PrintWriter(System.out);
    private static PrintWriter _err = new PrintWriter(System.err);

    private static final int INF = Integer.MAX_VALUE / 2;

    private void solve(Scanner sc) {
        int H = sc.nextInt();
        int W = sc.nextInt();
        sc.nextLine();

        char[][] b = new char[H][];

        for (int i = 0; i < H; ++i) {
            b[i] = sc.nextLine().toCharArray();
        }

        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                if (b[i][j] == '.') {
                    int n = 0;
                    if (i > 0 && j > 0 && b[i - 1][j - 1] == '#') ++n;
                    if (i > 0 && b[i - 1][j] == '#') ++n;
                    if (i > 0 && j < W - 1 && b[i - 1][j + 1] == '#') ++n;
                    if (j > 0 && b[i][j - 1] == '#') ++n;
                    if (j < W - 1 && b[i][j + 1] == '#') ++n;
                    if (i < H - 1 && j > 0 && b[i + 1][j - 1] == '#') ++n;
                    if (i < H - 1 && b[i + 1][j] == '#') ++n;
                    if (i < H - 1 && j < W - 1 && b[i + 1][j + 1] == '#') ++n;
                    b[i][j] = (char)('0' + n);
                }
            }
        }
        for (int i = 0; i < H; ++i) {
            _out.println(new String(b[i]));
        }
    }
    private static BigInteger C(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        for (long i = r; i > 1; --i) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res;
    }
    private static BigInteger P(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();

        long G = System.currentTimeMillis();
        if (elapsed) {
            _err.println((G - S) + "ms");
        }
        _err.flush();
    }
}

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

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

Fa = 0 if A == 0 else (((A - 2) // 2 - 1) % 2 if (A - 1) % 2 == 1 else (A - 1) ^ ((A - 2) // 2 - 1) % 2)
Fb = ((B - 1) // 2 - 1) % 2 if B % 2 == 1 else B ^ ((B - 1) // 2 - 1) % 2

print(Fa ^ Fb)


Measured memory_bytes: 3060
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
?????§?????????
FX????????§????????°?????????????????¨????????????????????¨??§????????????????????????????????¨?????§????????????
????????°????????????100???????????? 1000???????????????????????????????????? 1?????? 108???????????£??????????£??????¨???
(108??? ?????? 100???) ???? 1000?????? == 8000??????????????????????????¨?????§????????????

???????????¨????????????????????? t ?????????????????? Rt (t=0,1,2,,,n???1)???
??\?????¨??????????????????????????§??????????????? Rj???Ri (????????????j>i ??¨??????) ????????§??????
?±??????????????????????
"""
import math

# ?????????
n = int(input().strip())
a = []
for i in range(n):
    a.append(int(input().strip()))

min = a[0]
cnt = -1000000000
for j in range(1,n):
    x = a[j] - min
    if cnt < x:
        cnt = x
#    print("cnt={0} min={1} Rj={2}".format(cnt,min,a[j]))
    if min > a[j]:
        min = a[j]
print(cnt)

Measured memory_bytes: 15616
a,b,m=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=min(A)+min(B)
for i in range(m):
    data=list(map(int,input().split()))
    ans=min(ans,A[data[0]-1]+B[data[1]-1]-data[2])

print(ans)



Measured memory_bytes: 18736