akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

int n;
long long x[120000];
long long gcd(long long a,long long b)
{
    return (a%b)?gcd(b,a%b):b;
}
void init()
{

    cin>>n>>x[0];
    n++;
    for (int i=1; i<n; ++i)
        cin>>x[i];
    sort(x,x+n);
long long ans=abs(x[1]-x[0]);
    for (int i=1; i<n-1; ++i)
        ans=gcd(ans,x[i+1]-x[i]);
    cout<<ans<<endl;

}

void work()
{

}


int main()
{
    init();
    work();
    return 0;
}



Measured memory_bytes: 1024
#pragma warning (disable: 6031)
#pragma warning (disable: 26451)

#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <map>


//const int mod = 1000000007;
const int mod = 998244353;
int maximum(int a, int b) { return a < b ? b : a; }
int minimum(int a, int b) { return a > b ? b : a; }
using std::pair;
using std::vector;

class UnionFind {
	int n;
	int* par;
public:
	UnionFind(int N) : n(N), par(new int[N]) {
		for (int i = 0; i < n; i++) {
			par[i] = i;
		}
	}
	void unite(int a, int b) {
		par[root(b)] = root(a);
	}
	int root(int a) {
		if (par[a] == a)return a;
		return par[a] = root(par[a]);
	}
	bool isSame(int a, int b) {
		return root(a) == root(b);
	}
};


int main() {
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);
	auto fr = new vector<int>[N];
	auto bl = new vector<int>[N];
	UnionFind un(N);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--; b--;
		fr[a].push_back(b);
		fr[b].push_back(a);
		un.unite(a, b);
	}
	for (int i = 0; i < K; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--; b--;
		bl[a].push_back(b);
		bl[b].push_back(a);
	}
	auto cnt = new int[N] {};
	for (int i = 0; i < N; i++)cnt[un.root(i)]++;
	for (int i = 0; i < N; i++) {
		int res = cnt[un.root(i)] - 1;
		for (int j = 0; j < fr[i].size(); j++) {
			if (un.isSame(i, fr[i][j]))res--;
		}
		for (int j = 0; j < bl[i].size(); j++) {
			if (un.isSame(i, bl[i][j]))res--;
		}
		printf("%d ", res);
	}
	return 0;
}

Measured memory_bytes: 13048
#include <stdio.h>

int main(void){
    int n,m,c;
    int i,j,sum,ans;
    ans = 0;
    scanf("%d %d %d",&n,&m,&c);
    sum = c;
    int b[m],a[n][m];
    for (i=0;i<m;i++){
        scanf("%d",&b[i]);
    }
    for (i=0;i<n;i++){
        for(j=0;j<m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for (i=0;i<n;i++){
        for(j=0;j<m;j++){
            sum += a[i][j]*b[j];
        }
        //printf("%d\n",sum);
        if (sum > 0){
            ans +=1;
            sum = c;
        }else{
            sum = c;
        }
    }
    printf("%d\n",ans);
    return 0;
}


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

int res(int x, int y, int z)
{
  return x * x + y * y + z * z + x * y + x * z + y * z;
}

int main()
{
  int n;
  cin >> n;
  int ans = 0;
  int x;
  for(int i = 1; i <= n; i++){
    ans = 0;
    for(int j = 1; j < 101; j++){
      for(int k = j; k < 101; k++){
        for(int l = k; l < 101; l++){
          x = res(j, k, l);
          if(x > i) break;
          if(x == i) {
            //cout << "OK " << j << " " << k << " " << l << endl;
            if(j != k && k != l && j != l){              
              ans += 6;
            }
            else if(j == k && k == l && j == l){
              ans++;
            }
            else{
              ans += 3;
            }
          }
        }
      }
    }
    cout << ans << endl;
  } 

  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using ll = long long;
const ll mod = 1000000007;
const ll infi = 1000000000000000;
const ll md = 998244353;
using namespace std;
using vl = vector<ll>;
using pll =  pair<ll,ll>;

void solve()
{   
    int h,a;
    cin>>h>>a;
    if(h%a==0)
        cout<<h/a;
    else cout<<h/a+1;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   
    solve();
    return 0;
}

Measured memory_bytes: 256
def solve():
  ar = raw_input().split(' ')
  N = int(ar[0])
  M = int(ar[1])
  counts = [0 for i in range(N)]
  for i in range(M):
    #print counts
    ar = raw_input().split(' ')
    a = int(ar[0])
    b = int(ar[1])
    counts[a-1] = counts[a-1] + 1
    counts[b-1] = counts[b-1] + 1
  #print counts
  print '\n'.join(str(c) for c in counts)

if __name__ == '__main__' :
  solve()

Measured memory_bytes: 2568
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int k,a,b;
int main()
{
	scanf("%d%d%d",&k,&a,&b);
	if (b/k-(a-1)/k>=1) printf("OK\n");else printf("NG\n");
return 0;
}

Measured memory_bytes: 3656
#include<iostream>
using namespace std;
int main(void){
  char a,b,c;
  cin >> a;
  if(a == 'a' || a == 'i' || a == 'u' || a == 'e' || a =='o'){ 
  cout << "vowel" <<endl;
  }else{
   cout << "consonant" <<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}

ll dp[3030][3030][4];
int main() {
    int h, w, n;
    cin >> h >> w >> n;
    auto v = make_vec<ll>(h, w);
    rep(i, n) {
        int y, x;
        cin >> y >> x;
        cin >> v[--y][--x];
    }
    dp[0][0][0] = 0;
    dp[0][0][1] = v[0][0];
    rep(i, h) rep(j, w) {
        if (i > 0) {
            rep(k, 4) chmax(dp[i][j][0], dp[i - 1][j][k]);
            rep(k, 4) chmax(dp[i][j][1], dp[i - 1][j][k] + v[i][j]);
        }
        if (j > 0) {
            rep(k, 4) chmax(dp[i][j][k], dp[i][j - 1][k]);
            rep(k, 3) chmax(dp[i][j][k + 1], dp[i][j - 1][k] + v[i][j]);
        }
        ll now = 0;
        rep(k, 4) chmax(now, dp[i][j][k]);
        // cout << now << endl;
    }
    ll ans = 0;
    rep(k, 4) chmax(ans, dp[h - 1][w - 1][k]);
    cout << ans << endl;
}

Measured memory_bytes: 357632
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int n,a,b,ans=0,c=0;
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		c = i%10 + i/10%10 + i/100%10 +i/1000%10 +i/10000%10;
		if(a<=c && c<=b){
				ans+=i;
		}
	}
	cout<<ans<<endl;
	
}

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

using namespace std;

const int MAX = 1e5;
int n;
int d[100005];
int num[100005];
int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> d[i];
        num[d[i]]++;
    }
    for(int i = 1; i <= MAX; ++i)
    {
        num[i] += num[i-1];
    }
    int ans = 0;
    for(int i = 1; i <= MAX; ++i)
    {
        if(num[i]==n/2)ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
import sys
input=sys.stdin.readline
from bisect import bisect_left 
from collections import deque

def count_edge(a,b):
    global edge,AB
    if a>b:
        a,b=b,a
    edge[bisect_left(AB,(a,b))]+=1

def main():
    global edge,AB
    N,M=map(int,input().split())
    data=[[] for i in range(N+1)]
    AB=[]
    edge=[0]*M
    count=[0]*(N+1)
    for i in range(M):
        A,B=map(int,input().split())
        if A>B:
            A,B=B,A
        AB.append((A,B))
        data[A].append(B)
        data[B].append(A)
        count[A]^=1
    AB.sort()

    if M%2==1:
        print(-1)
        sys.exit()

    parent=[0]*(N+1)
    que=[1]
    parent[1]=1
    lsls=deque([])
    while que:
        h=[]
        for u in que:
            for v in data[u]:
                if parent[v]==0:
                    parent[v]=u
                    h.append(v)
                    if count[v]%2==1:
                        lsls.appendleft(v)
        que=h

    for i in lsls:
        if count[i]==0:
            continue
        else:
            count[i]=0
            while True:
                j=parent[i]
                if i==j:
                    break
                count_edge(i,j)
                if count[j]==1:
                    count[j]=0
                    break
                i=j
            
    for i in range(M):
        if edge[i]%2==0:
            print(*AB[i])
        else:
            print(*AB[i][::-1])
    
if __name__=="__main__":
    main()

Measured memory_bytes: 85792
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
        	while(true) {
        		int n = sc.nextInt();
        		int m = sc.nextInt();
        		if(n==0 && m==0) break;
        		int [] score = new int[n+1];
        		for(int i=0;i<n;i++) {
        			score [i] = sc.nextInt();
        		}
        		score[n] = 0;
        		int [] sum = new int [(n+1)*(n+1)];
        		for(int i=0;i<n+1;i++) {
        			for(int j=0;j<n+1;j++) {
        	        	sum[(n+1)*i+j] = score[i]+score[j];
            		}
        		}
        		Arrays.sort(sum);
        		search:
        			for(int i=m;i>0;i--) {
        				for(int j=0;j<(n+1)*(n+1);j++) {
        					int low = 0;
            				int high = sum.length;
            				while(low<high) {
            					int mid = (low+high)/2;
            					if(sum[mid]==i-sum[j]) {
            						System.out.println(i);
            						break search;
            					}else if(sum[mid]>i-sum[j]) {
            						high = mid;
            					}else if(sum[mid]<i-sum[j]) {
            						low = mid+1;
            					}
            				}
        				}
        			}
        	}
        }
    }
}
    


Measured memory_bytes: 59284
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int i = 0;
    double ans = 0;
    for(i = 0; i < N; i++){
      ans += 1 / sc.nextDouble();
    }
    System.out.print(1 / ans);
  }
}

Measured memory_bytes: 23380
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
// int256_t num

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin, n;
    vector<int256_t> a(n);
    int zero = 0;
    REP(i, 0, n) {
        cin, a[i];
        zero += (a[i] == 0);
    }
    if (zero > 0) {
        print(0);
        return 0;
    }
    int256_t ans = 1;
    REP(i, 0, n) {
        ans *= a[i];
        if (ans > 1000000000000000000LL) {
            print(-1);
            return 0;
        }
    }
    print(ans);

    return 0;
}


Measured memory_bytes: 7988
#include <iostream>

int main(void){
    int a, b, c, cnt;

    std::cin >> a >> b >> c;
    if(a == b && b == c) cnt = 1;
    else if(a == b && b != c) cnt = 2;
    else if(c == b && a != c) cnt = 2;
    else if(a == c && b != a) cnt = 2;
    else cnt = 3;

    std::cout << cnt << std::endl;
    return 0;
}


Measured memory_bytes: 256
import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
#import bisect
n,q=map(int,input().split())

node=[[] for _ in range(n)]
d=deque()
d.append(0)
for i in range(n-1):
    a,b = map(int,input().split())
    node[a-1].append(b-1)
    node[b-1].append(a-1)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
seen=[0]*n
seen[0]=1
while True:
    if not d:
        break
    i=d.pop()
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
            ans[j]+=ans[i]
print(*ans)

Measured memory_bytes: 94100
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;

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

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif
    int a, b, c, d;
    cin>>a>>b>>c>>d;
    if(c != a){
        cout<<1<<endl;
    }else{
        cout<<0<<endl;
    }
    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Measured memory_bytes: 892
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest.ABC_169
{
    class E
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);

            Method(args);

            Out.Flush();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            long[][] abs = new long[n][];
            for(int i = 0; i < n; i++)
            {
                abs[i] = ReadLongs();
                if (n % 2 == 0)
                {
                    abs[i][0] *= 2;
                    abs[i][1] *= 2;
                }
            }

            long left = 0;
            abs = abs.OrderBy(a => a[0]).ToArray();
            if (n % 2 == 0)
            {
                left = (abs[n / 2 - 1][0] + abs[n / 2][0]) / 2;
            }
            else
            {
                left = abs[n / 2][0];
            }

            long right = 0;
            abs = abs.OrderBy(a => a[1]).ToArray();
            if (n % 2 == 0)
            {
                right = (abs[n / 2 - 1][1] + abs[n / 2][1]) / 2;
            }
            else
            {
                right = abs[n / 2][1];
            }

            WriteLine(right - left + 1);
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 60372
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+87;
int d[N];
char s[N];
int main()
{
    int n,q;
    cin >> n >> (s+1) >> q;
    for (int i = 1; i <= n; ++i)
        d[i] = (s[i] == 'D') + d[i-1];
    while (q--) {
        int k;
        cin >> k;
        int l = 0, r = 1;
        ll ans = 0, cm = 0, sm = 0;
        for (; r <= n; ++r) {
            if (s[r] == 'M')
                ++cm, sm += d[r];
            if (s[r] == 'C')
                ans += sm - cm * d[l];
            if (r - l == k) {
                if (s[++l] == 'M')
                    --cm, sm -= d[l];
            }
        }
        cout << ans << '\n';
    }
}


Measured memory_bytes: 5120
import math

n = int(input())

ans = 1000000
for i in range(1, int(math.sqrt(n)//1)+1):
    if n % i == 0:
        b = str(int(n/i))
        f = max(len(str(i)), len(b))
        if f < ans:
            ans = f

print(ans)


Measured memory_bytes: 3060
class Array
    def accum
        ac = Array.new(size + 1)
        ac[0] = 0
        (1..size).each do |i|
            ac[i] = ac[i-1] + self[i-1]
        end
        ac
    end
end

w, h = gets.split.map(&:to_i)
a = (1..h).map { gets.split.map(&:to_i) }
h_accum = a.map(&:accum)
v_accum = a.transpose.map(&:accum).transpose

best = (0..h).map { Array.new(w+1) }
h.downto(0) do |i|
    w.downto(0) do |j|
        if i == h && j == w
            best[i][j] = 0
        elsif i == h
            best[i][j] =   v_accum[i][j] + best[i][j+1]
        elsif j == w
            best[i][j] = - h_accum[i][j] + best[i+1][j]
        else
            candidates = [
                v_accum[i][j] + best[i][j+1],
              - h_accum[i][j] + best[i+1][j]
            ]
            best[i][j] = (i + j).even? ? candidates.max : candidates.min
        end
    end
end

p best[0][0].abs


Measured memory_bytes: 55172
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstring>
#include<bitset>

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <double, double> pdd;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const long double eps=1e-6;
const int mod=1e9+7;
const int maxn=3e6;
const int M=3e6+10;
const int N=2e5+10;

/*inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int gcd(int x,int y)
{
    return x?gcd(y%x,x):y;
}
ll qpow(ll a, ll b, ll MOD)
{
    ll ans = 1;
    while (b)
    {
        if (b&1) ans = (ans*a)%MOD;
        b>>=1;
        a = (a*a)%MOD;
    }
    return ans;
}

void dfs(int u)
{
    cnt++;
    vis[u]=true;
    for(auto v:g[u])
    {
        if(!vis[v]) dfs(v);
    }
}*/

int main()
{
    #ifdef local
       //  freopen("in.txt","r",stdin);
  //       freopen("out.txt","w",stdout);
    #endif // local
    IOS;
    ll n,m;cin>>n>>m;int ans=0;
    while(n<=m)
    {
        ans++;
        n=n*2;
    }
    cout<<ans<<endl;
    return 0;


}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

a.sort()

candi = a[-1]
middle = (candi - 1) / 2

tmp = float("inf")
ans = 0

for i in range(len(a) - 1):
    if tmp >= abs(a[i] - middle):
        tmp = abs(a[i] - middle)
        ans = i
print(candi, a[ans])

Measured memory_bytes: 14060
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <locale.h>
#include <vector>
#include <iomanip>
#include <cassert>
#include <list>
#include <unordered_map>
#include <cstring>

#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back

#define onlycin ios_base::sync_with_stdio(false); cin.tie(0)
#define mp make_pair
#define endl "\n"
#define rep(i,x,y) for(int i = x; i <= y; ++i)
#define repr(i,x,y) for(long long i = x; i >= y; --i)
#define y1 wearsdfasdf
#define fi first
#define se second

typedef long long ll;

const int N = (100000) + 322;
const int INF = (ll)(1e9) + 7;

using namespace std;

int n, cost[N], flag;

vector <int> v[N];

vector <int> lst;

int getC(int sum, int mx) {
  if (sum / 2 < mx) return sum - mx;
  return sum / 2;
}

bool check(int sum, int av) {
  return (sum / 2 <= av && av <= sum);
}

void dfs(int x, int p = -1) {
  int sum = 0, mx = 0;
  for(auto it : v[x]) {
    if (p == it) continue;
    dfs(it, x);
    sum += cost[it];
    mx = max(mx, cost[it]);
  }
  if (sz(v[x]) > 1) {
   // cout << x << ' ' << sum << ' ' << mx << ' ' << cost[x] << ' ' << getC(sum, mx) << endl;
    if (!check(sum, cost[x])) {flag = 1;}
    int C = sum - cost[x];
    if (C > getC(sum, mx)) flag = 1;
    cost[x] = cost[x] - C;
  }
}

int main () {
  ios_base::sync_with_stdio(false);
  cin >> n;
  rep(i, 1, n) cin >> cost[i];
  rep(i, 1, n - 1) {
    int x, y; cin >> x >> y;
    v[x].pb(y);
    v[y].pb(x);
  }
  int root = 1;
  rep(i, 1, n) {
    if (sz(v[i]) > 1) root = i;
  }
  if (n == 2) {
    if (cost[1] != cost[2]) {
      cout << "NO";
      return 0;
    }
    cout << "YES";
    return 0;
  }
  
  dfs(root);
  if (cost[root] != 0) {
    cout << "NO";
    return 0;
  }
  if (flag == 1) {
    cout << "NO";
    return 0;
  }
  cout << "YES";
  return 0;
}


Measured memory_bytes: 13312
#include<stdio.h>
int main(void)
{
	unsigned int count,i,j,a[4],b[4];
	count = 0;
	for(i=0;i<3;i++){
	scanf("%d %d", &a[i], &b[i] );
	}
	
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			if(a[i] == b[j]) count++;
		}
	}
	
	for(i=0;i<3;i++){
		for(j=i+1;j<3;j++){
			if(a[i] == a[j]) count++;
			if(b[i] == b[j]) count++;
		}
	}
	
	
	if(count ==3) printf("NO");
	else printf("YES");

	return(0);
}

Measured memory_bytes: 128
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    T = list(map(int, input().split()))
    m = int(input())

    for i in range(m):
        p, x = map(int, input().split())
        res = 0
        for j in range(n):
            if j == p - 1:
                res += x
            else:
                res += T[j]
        print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

void Main() {
  ll n,m;
  cin >> n >> m;
  ll a[n];
  rep(i,n) R a[i];
  sort(a,a+n);
  ll l=0,r=MAXL;
  while(l+1<r) {
    ll mm=(l+r)/2;
    ll cnt=0;
    rep(i,n) {
      ll k=lower_bound(a,a+i,mm-a[i])-a;
      cnt+=max(0LL,(i-k)*2+(a[i]*2>=mm));
    }
    if(cnt<m) r=mm;
    else l=mm;
  }
  ll d[n+1],ans=0;
  mem(d);
  rep(i,n) d[i+1]=d[i]+a[i];
  rep(i,n) {
    ll k=lower_bound(a,a+i,r-a[i])-a;
    ll c=max(0LL,(i-k)*2+(a[i]*2>=r));
    c=min(c,m);
    m-=c;
    if(c) ans+=a[i]*c+a[i];
    ans+=max(0LL,(d[i]-d[k])*2);
  }
  pr(ans+l*m);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 1792
// In the name of GOD
 
#include <bits/stdc++.h>
#define ll long long
#define pp pair <int, int>
using namespace std;
const ll N = 1e5 + 15, MOD =  998244353;

int n;
void compute(int id, unsigned long int S,  
            unsigned long int X, vector<int>& ans) 
{ 
    unsigned long int A = (S - X)/2; 
  
    int a = 0, b = 0; 
  
    // Traverse through all bits 
    for (int i=0; i<8*sizeof(S); i++) 
    { 
        unsigned long int Xi = (X & (1 << i)); 
        unsigned long int Ai = (A & (1 << i)); 
        if (Xi == 0 && Ai == 0) 
        { 
            // Let us leave bits as 0. 
        } 
        else if (Xi == 0 && Ai > 0) 
        { 
            a = ((1 << i) | a);  
            b = ((1 << i) | b);  
        } 
        else if (Xi > 0 && Ai == 0) 
        { 
            a = ((1 << i) | a);  
  
            // We leave i-th bit of b as 0. 
        } 
        else // (Xi == 1 && Ai == 1) 
        { 
            cout << "Not Possible"; 
            return; 
        } 
    } 
    ans[id] = a;
    ans[n - 1 - id] = b; 
} 

void solve() {
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll txor = a[0];
    for (int i = 1; i < n; i++) {
        txor ^= a[i];
    }
    // cout << txor << "\n";
    vector<ll> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = a[i] ^ txor;
    }
    for (int i : ans)   cout << i << " ";
}



int main()  {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tt = 1;
    // cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    } 
}                                   

Measured memory_bytes: 6328
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
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; }

struct edge { int to; int cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int MOD = 1e9+7;
const double EPS = 1.0e-12;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

ll dp[110][100010];

int main(){
	int n,W;
	cin >> n >> W;
	vi w(n),v(n);
	rep(i,n) cin >> w[i] >> v[i];
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= W; j++){
			chmax(dp[i+1][j],dp[i][j]);
			if(j+w[i] <= W) chmax(dp[i+1][j+w[i]],dp[i][j]+v[i]);
		}
	}
	cout << dp[n][W] << endl;

	return 0;
}

Measured memory_bytes: 79360
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		int d = scan.nextInt();
		
		while(true) {
			c -= b;
			if(c <= 0) {
				System.out.println("Yes");
				break;
			}
			a -= d;
			if(a <= 0) {
				System.out.println("No");
				break;
			}
		}

	}

}


Measured memory_bytes: 35532
import sys
s = input()

for i in range(8):
    bit = bin(i)[2:].zfill(3)
    string = s[0]
    flag = int(s[0])

    for j,k in enumerate(bit):
        if k == '0':
            string += '+' + s[j+1]
            flag += int(s[j+1])
        else:
            string += '-' + s[j+1]
            flag -= int(s[j+1])

    if flag == 7:
        print(string + '=7')
        sys.exit()

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    deque<long long> b;
    bool flag;
    if(n%2==0){
        flag = true;
    }else{
        flag = false;
    }
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        if(flag == false){
            b.push_front(a[i]);
            flag = true;
        }else{
            b.push_back(a[i]);
            flag = false;
        }
    }
    for(int i=0;i<n;i++){
        cout << b[i] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n;
	cin>>n;
	ll odd=0,even=0;
for(ll i=1;i<=n;i++){
	if(i%2!=0){
		odd++;
	}
	else{
		even++;
	}
}
double t=double(odd)/double(n);
cout<<t;
	
	return 0;
}

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

int main() {
  long ans=0;
  string s;
  cin >> s;
  if(s[0]=='R') ans=1;
  if(s[1]=='R') ans=1;
  if(s[2]=='R') ans=1;
  if(s[0]==s[1]&&s[0]=='R') ans=2;
  if(s[1]==s[2]&&s[1]=='R') ans=2;
  if((s[1]==s[2]&&s[1]=='R')&&s[0]==s[1]) ans=3;
  cout << ans << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
    string s;
    cin>>s;
    int n=s.size();
    bool ans=true;
    for(int i=0;i<(n-1)/2;i++){
        if(s[i]!=s[n-1-i]) ans=false;
    }
    for(int i=0;i<=(n/2-1);i++){
        if(s[i]!=s[n/2-1-i]||s[i+(n+1)/2]!=s[n/2-1-i+(n+1)/2]) ans=false;
    }
    if(ans) cout<<"Yes";
    else cout<<"No";
}

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

int main(void)
{
	int N,M,C = 0;
	int A[100][100] = {0,0};
	int B[100] = {0};
	int i,j;
	int num = 0;
	int accept_num = 0;
	std::cin >> N >> M >>C;
	for(i=0;i<M;i++){
		std::cin >> B[i];
	}
	for(i=0;i<N;i++){
		num = 0;
		for(j=0;j<M;j++){
			std::cin >> A[i][j];
			num += B[j]*A[i][j];
		}
		if(num+C>0){
			accept_num++;
		}
	}

	std::cout << accept_num << std::endl;


	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
#define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/






int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cout.precision(10); cout << fixed;
#ifdef LOCAL
  freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
  int n; cin >> n;
  int ret = 0;
  for (int i = 1; i <= n; i++) {
    int val; cin >> val;
    if (i % 2 == 1 && val % 2 == 1) ret++;
  }
  cout << ret << '\n';






/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
  return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    bool ok = true;

    for (int i = 1; i < 4; ++i)
        if (s[i] == s[i - 1])
        {
            ok = false;
            break;
        }

    cout << (ok ? "Good" : "Bad") << '\n';

    return 0;
}


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

struct Card { char suit, value; };

void bubble(struct Card A[], int N) {
  for ( int i = 0; i < N; i++ )
    for ( int j = N - 1; j >= i + 1; j-- )
      if ( A[j].value < A[j - 1].value )
        swap(A[j], A[j - 1]);
}

void selection(struct Card A[], int N) {
  for ( int i = 0; i < N; i++ ) {
    int minj = i;
    for ( int j = i; j < N; j++ )
      if ( A[j].value < A[minj].value ) minj = j;
    Card t = A[i]; A[i] = A[minj]; A[minj] = t;
  }
}

void print(struct Card A[], int N) {
  for ( int i = 0; i < N; i++ ) {
    if ( i > 0 ) cout << " ";
    cout << A[i].suit << A[i].value;
  }
  cout << endl;
}

// バブルソートと選択ソートの結果を比較
bool isStable(struct Card C1[], struct Card C2[], int N) {
  for ( int i  = 0; i < N; i++ )
    if ( C1[i].suit != C2[i].suit ) return false;
  return true;
}

int main() {
  Card C1[100], C2[100];
  int N;
  char ch;

  cin >> N;
  for ( int i = 0; i < N; i++ )
    cin >> C1[i].suit >> C1[i].value;

  for ( int i = 0; i < N; i++ ) C2[i] = C1[i];

  bubble(C1, N);
  selection(C2, N);

  print(C1, N);
  cout << "Stable" << endl;
  print(C2, N);
  if ( isStable(C1, C2, N) )
    cout << "Stable" << endl;
  else
    cout << "Not stable" << endl;

  return 0;
}


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

const long long mod=1e9+7;
int n;
long long k, ans=0;

vector<vector<long long>>mult(vector<vector<long long>>a, vector<vector<long long>>b){
	vector<vector<long long>>ret(n,vector<long long>(n,0));
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			for (int k=0;k<n;k++){
				ret[i][j]+=a[i][k]*b[k][j];
				ret[i][j]%=mod;
			}
		}
	}
	return ret;
}

vector<vector<long long>>modpow(vector<vector<long long>>x, long long y){
	vector<vector<long long>>ret(n,vector<long long>(n,0));
	for (int i=0;i<n;i++) ret[i][i]=1;
	while (y>0){
		if (y&1) ret=mult(ret,x);
		x=mult(x,x);
		y>>=1;
	}
	return ret;
}

int main(){
	cin >> n >> k;
	vector<vector<long long>>adjl(n,vector<long long>(n));
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			cin >> adjl[i][j];
		}
	}
	adjl=modpow(adjl,k);
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			ans+=adjl[i][j];
			ans%=mod;
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 384
import java.util.*;

public class Main {

	private static Scanner sc;

	public static void main(String[] args) {
	sc = new Scanner(System.in);
	int a = 1 ;
	int n =1;
	while(a!=0){
	    a =sc.nextInt();
	    if(a!=0){
		System.out.println("Case "+n+": "+a);
		n=n+1;
	    }
		
		
   	}
	


}
	
}
    	

Measured memory_bytes: 32992
#include <math.h>
#include <bits/stdc++.h>
#include <deque>
#include<vector>
#define ll long long
#define l long double
#define pi 3.14159265358979323846
#define mod 1000000007
#define vali 1000000000000000000
using namespace std;
int main()
{
    ll x,n;
    cin>>x>>n;
    unordered_set<int>q;
    for(int i=0;i<n;i++)
    {
        ll a;
        cin>>a;
        q.insert(a);
    }
    ll ind=0,ind1=0;
    for(int i=x;i<=101;i++)
    {
        if(q.find(i)==q.end())
        {
            ind=i;
            break;
        }
    }
    for(int i=x;i>=1;i--)
    {
        if(q.find(i)==q.end())
        {
            ind1=i;
            break;
        }
    }
    if(n==0)
    cout<<x<<endl;
    else if(x-ind1<=ind-x)
    cout<<ind1<<endl;
    else if(x-ind1>ind-x)
    cout<<ind<<endl;
}

Measured memory_bytes: 3608
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
 x,y=map(int,input().split())
 a.append(x)
 b.append(y)
d=min(b)-max(a)+1
if d<=0:
  print(0)
else:
  print(d)

Measured memory_bytes: 10996
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int color[100005];
    long long sum[100005];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&color[i]);
        sort(color+1,color+n+1);
    sum[1]=color[1];
    for(int i=2;i<=n;i++)
        sum[i]=sum[i-1]+color[i];
        int ans=1;
        for(int i=n-1;i>=1;i--)
            if(2*sum[i]>=color[i+1])
            ans++;
            else
                break;
            printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 1408
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024*1024), bufio.MaxScanTokenSize)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

var M map[string]bool

func main() {
	N := nextInt()
	m := map[byte]int{
		'M': 0,
		'A': 1,
		'R': 2,
		'C': 3,
		'H': 4,
	}
	c := make([]int, 5)
	for i := 0; i < N; i++ {
		s := next()
		if v, ok := m[s[0]]; ok {
			c[v]++
		}
	}
	ans := 0
	for i := 0; i < 3; i++ {
		for j := i + 1; j < 4; j++ {
			for k := j + 1; k < 5; k++ {
				ans += c[i] * c[j] * c[k]
			}
		}
	}
	fmt.Println(ans)
}


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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		
		int sum = 0;
		
		for(int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
			sum += a[i];
		}
		
		Arrays.sort(a);
		
		int ave1 = 0;
		int ave2 = 0;
		if(sum % N == 0) {
			ave1 = sum / N;
		} else {
			ave1 = sum / N + 1;
			ave2 = sum / N;
		}
		
		int min1 = 0;
		int min2 = 0;
		
		for(int i = 0; i < N; i++) {
			min1 += (ave1 - a[i]) * (ave1 - a[i]);
		}
		
		int min = 0;
		
		if(sum % N != 0) {
			for(int i = 0; i < N; i++) {
				min2 += (ave2 - a[i]) * (ave2 - a[i]);
			}
			min = Math.min(min1, min2);
		}
		
		if(sum % N == 0) {
			min = min1;
		}
		System.out.println(min);
	}
}


Measured memory_bytes: 21972
#include <stdio.h>

int main(){

  int select[100];
  int n,i,j,minj,count=0,c;

  scanf("%d",&n);

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

  for(i=0; i < n; i++){
    minj=i;
    for(j=i; j < n; j++){
      if(select[j] < select[minj]){
	minj=j;
      }
    }
      c=select[minj];
      select[minj]=select[i];
      select[i]=c;

      if(i!=minj)
	count++;
    }
for(i=0; i < n; i++){
  printf("%d",select[i]);
  if(i==n-1)
    printf("\n");
  else 
    printf(" ");
 }

 printf("%d\n",count);


return 0;

}

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

long long int prefix[500];
int a[500];

long long int sum(int i, int j)
{
  auto sub = i ? prefix[i-1] : 0;
  return prefix[j] - sub;
}


long long int f(int i, int j, vector<vector<long long>>& dp)
{
  auto S = sum(i,j);
  if (i == j)
    return a[i];
  auto& res = dp[i][j];
  if (res != numeric_limits<long long>::max())
    return res;
  for (int k = i; k < j; ++k)
  {
    res = min(res, S + f(i, k, dp) + f(k+1, j, dp));
  }
  return res;
}


int main()
{
  int n, k;
  cin >> n ;
  vector<int> a(n);
  vector<vector<long long>> dp(n, vector<long long>(n,numeric_limits<long long>::max()));
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  prefix[0] = a[0];
  for (int i = 1; i < n; ++i)
    prefix[i] = (prefix[i-1] + a[i]);
  for (int i = 0; i < n; ++i)
    dp[i][i] = 0;

  for(int len = 2; len <= n; ++len)
  {
    for (int i = 0; i < n; ++i)
    {
      int j = i + len - 1;
      if (j >= n)
        break;
      auto S = sum(i,j);
      for (int k = i; k < j; ++k) {
        dp[i][j] = min(dp[i][j], S + dp[i][k] + dp[k+1][j]);
      }
    }
  }


  cout << dp[0][n-1] <<'\n';


  return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
#define REP(i,n) for(ll i=0;i<n;++i)
 
vector<string> split(string base, char spl){
  vector<string> result;
  string::size_type pos = 0;
  string::size_type bef = 0;
  base += spl;
  while( (pos = base.find_first_of(spl,bef)) != string::npos ){
    result.push_back(base.substr(bef,pos-bef));
    bef = pos+1;
  }
  return result;
}
 
int toint(string s){
  return atoi(s.c_str());
}
 
// year : 2013 ~ 2413
// month : 12
// day : 31
// size : 401*366 = 146766
int maya_to_ad[150000];
// size : 2413*12*31 = 897636
int ad_to_maya[900000];
 
bool is_uruu(int y){
  return (y%4==0 && (y%100!=0 || y%400==0));
}
 
int daylist[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
 
#define AD 146097
#define MAYA 1872000

void calc(){
  int y = 2012;
  int m = 12;
  int d = 21;
  REP(i,150000){
    int id = ((y*12)+(m-1))*31+(d-1);
    maya_to_ad[i] = id;
    ad_to_maya[id] = i;
    ++d;
    if(d > daylist[m-1]){
      if(m==2 && is_uruu(y) && d==29){
        // do nothing
      }else if(m==12){
        // next year
        ++y;
        m=1;
        d=1;
      }else{
        // next month
        ++m;
        d=1;
      }
    }
    if(y==2414)break;
  }
}
 
int main(){
  // mae shori
  // 400 years
  calc();
  // input
  while(true){
    string s;
    cin>>s;
    if(s=="#")break;
    vector<string> input = split(s,'.');
    if(input.size()==3){
      // year.month.day
      int year = toint(input[0]);
      int month = toint(input[1]);
      int day = toint(input[2]);
      int yeardown = (year-2013)/400;
      year -= yeardown * 400;
      int id = ((year*12)+(month-1))*31+(day-1);
      // over flow
      ll maya = ad_to_maya[id];
      maya += (ll)yeardown * (ll)AD;
      maya %= MAYA;
      int ki = maya%20; maya/=20;
      int w = maya%18;  maya/=18;
      int t = maya%20;  maya/=20;
      int ka = maya%20; maya/=20;
      int b = maya;
      printf("%d.%d.%d.%d.%d\n",b,ka,t,w,ki);
    }else{
      // b.ka.t.w.ki
      int b = toint(input[0]);
      int ka = toint(input[1]);
      int t = toint(input[2]);
      int w = toint(input[3]);
      int ki = toint(input[4]);
      int id = ((((b*20)+ka)*20+t)*18+w)*20+ki;
      int yearadd = id/AD;
      id %= AD;
      int ad = maya_to_ad[id];
      int day = 1+ad%31;    ad/=31;
      int month = 1+ad%12;  ad/=12;
      int year = ad + yearadd*400;
      printf("%d.%d.%d\n",year,month,day);
    }
  }
  return 0;
}

Measured memory_bytes: 3260
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define N 100005
using namespace std;

inline void cmax(int &x, int &y, int z) {
    if (y < z) swap(y, z);
    if (x < y) swap(x, y);
    if (y < z) swap(y, z);
}

int n, rt, deg[N], c[N], ers[N], f[N], res;
int tot, fir[N], nxt[N << 1], to[N << 1];
queue<int> q;

inline void addE(int u, int v) {
    nxt[++tot] = fir[u], fir[u] = tot, to[tot] = v;
}

void dfs(int u, int p = 0) {
    int fi = 0, se = 0;
    for (int i = fir[u], v; i; i = nxt[i]) {
        v = to[i];
        if (v == p || ers[v]) continue;
        dfs(v, u);
        cmax(fi, se, f[v]);
    }
    res = max(res, se + (f[u] = fi + (c[u] ^ (deg[u] & 1) ^ 1)));
}

int main() {
#ifdef isLOCAL
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif

    cin >> n;
    for (int i = 1, u, v; i < n; ++i)
        scanf("%d%d", &u, &v),
        addE(u, v), addE(v, u),
        deg[u]++, deg[v]++;

    int numw = 0;
    for (int i = 1; i <= n; ++i) {
        char ch = getchar();
        while (ch != 'W' && ch != 'B')
            ch = getchar();
        c[i] = (ch == 'B');
        numw += !c[i];
        if (deg[i] == 1 && c[i]) q.push(i);
    }

    if (numw <= 1) return cout << numw << endl, 0;

    int dlt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ers[u] = 1, ++dlt;
        for (int i = fir[u], v; i; i = nxt[i]) {
            v = to[i];
            if (ers[v]) continue;
            if ((--deg[v]) == 1 && c[v])
                q.push(v);
        }
    }

    for (rt = 1; rt <= n && ers[rt]; ++rt);

    int ans = (n - 1 - dlt) * 2;

    for (int i = 1; i <= n; ++i)
        if (!ers[i]) ans += (deg[i] & 1) ^ c[i] ^ 1;

//    cout << ans << endl;

    dfs(rt);

//    cout << res << endl;

    cout << ans - res * 2 << endl;

    return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;
  
const int INF = 1e9 + 10;

int main() {
  int n, W;
  cin >> n >> W;
  vector<int> w(n), v(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> v[i];
  }
  
  vector<int> vs[4];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 4; j++) {
      if (w[i] == w[0] + j) {
        vs[j].push_back(v[i]);
        break;
      }
    }
  }

  for (int i = 0; i < 4; i++) {
    vs[i].push_back(INF);
    sort(vs[i].begin(), vs[i].end(), greater<int>());
    vs[i][0] = 0;
    for (int j = 1; j < vs[i].size(); j++) {
      vs[i][j] += vs[i][j - 1];
    }
  }

  int ans = 0;
  for (int i = 0; i < vs[0].size(); i++) {
    if (w[0] * i > W) {
      break;
    }
    for (int j = 0; j < vs[1].size(); j++) {
      if ((w[0] * i + (w[0] + 1) * j) > W) {
        break;
      }
      for (int k = 0; k < vs[2].size(); k++) {
        if ((w[0] * i + (w[0] + 1) * j + (w[0] + 2) * k) > W) {
          break;
        }
        for (int l = 0; l < vs[3].size(); l++) {
          if ((w[0] * i + (w[0] + 1) * j + (w[0] + 2) * k + (w[0] + 3) * l)> W) {
            break;
          }
          ans = max(ans, vs[0][i] + vs[1][j] + vs[2][k] + vs[3][l]);
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <regex>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
using ll = long long;
using VL=vector<ll>;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
const long long INF =  999999999;

ll N;

int main(){
  cin>>N;
  ll ans=0,div=10;
  if(N%2==1){
    cout<<0<<endl;
  }else{
    while(div<=N){
      ans+=N/div;
      div*=5;
    }
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String argv[]) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int D = sc.nextInt();
        int x = sc.nextInt();
        for(int i=0;i<10;i++){
            x = r*x - D;
            System.out.println(x);
        }
    }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long double arr[3009],n;
long double dp[3009][3009];
long double finds(ll head=0,ll tail=0,ll index=0)
{
    if(index==n)
    {
        if(head>tail)
            {return 1;}
        else
            {return 0;}
    }
    if(dp[head][tail]!=-1)
        {return dp[head][tail];}
    long double p1=1,p2=1;
    p1*=finds(head+1,tail,index+1)*arr[index];
    long double temp=(1-arr[index]);
    p2*=finds(head,tail+1,index+1)*temp;
    return dp[head][tail]=(p1+p2);
}
int main()
{
    ll i,j,k,l,m;
    cin>>n;
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            dp[i][j]=-1;
    for(i=0;i<n;i++)
        cin>>arr[i];
    cout<<fixed<<setprecision(12)<<finds();

}


Measured memory_bytes: 141824