akhauriyash/Code-Regression huggingface dataset:
//School of Killifish
public class Main{

	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
	}
	
	void run(){
		Scanner sc = new Scanner();
		int INF = Integer.MAX_VALUE;
		int[][] min = new int[1000][1000];
		for(;;){
			int R = sc.nextInt(), C = sc.nextInt(), Q = sc.nextInt(), MIN = INF;
			if((R|C|Q)==0)break;
			int h = (int) Math.ceil(Math.sqrt(R)), w = (int) Math.ceil(Math.sqrt(C));
			for(int i=0;i<h;i++)for(int j=0;j<w;j++)min[i][j]=INF;
			int[][] a = new int[R][C];
			for(int i=0;i<R;i++)for(int j=0;j<C;j++){
				a[i][j] = sc.nextInt();
				int I = i/h, J = j/w;
				min[I][J] = Math.min(min[I][J], a[i][j]);
				MIN = Math.min(MIN, INF);
			}
			while(Q--!=0){
				int r1 = sc.nextInt(), c1 = sc.nextInt(), r2 = sc.nextInt(), c2 = sc.nextInt(), res = INF;
				for(int i=r1/h;i<=r2/h;i++){
					int y1 = Math.max(r1, i*h), y2 = Math.min(r2, i*h+h-1);
					for(int j=c1/w;j<=c2/w;j++){
						if(res <= min[i][j])continue;
						int x1 = Math.max(c1, j*w), x2 = Math.min(c2, j*w+w-1);
						if(y1==i*h && y2==(i+1)*h-1 && x1 == j*w && x2 == (j+1)*w-1)res = Math.min(res, min[i][j]);
						else{
							for(int y=y1;y<=y2;y++)for(int x=x1;x<=x2;x++)
								res = Math.min(res, a[y][x]);
						}
					}
				}
				System.out.println(res);
			}
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 38000
#include<bits/stdc++.h>
#define ll long long
#define res register int
#define N 550
using namespace std;
int n,m;
char b[N][N],r[N][N];

int main()
{
	scanf("%d%d",&n,&m);
	
	for(res i=1;i<=n;i+=2)
	  for(res j=1;j<=m;j++)
	    r[i][j]='#',b[i][j]='.';
	    
	for(res i=2;i<=n;i+=2)
	  for(res j=1;j<=m;j++)
	    r[i][j]='.',b[i][j]='#';    	
	
	for(res i=1;i<=n;i++)
	  for(res j=1;j<=m;j++)
	  {
	  	 char ch;
	  	 cin>>ch;
	  	 if(ch=='#')
	  	 {
	  	 	r[i][j]='#';
	  	 	b[i][j]='#';
		 }
	  }
	  	 
    for(res i=1;i<=n;i++)
	r[i][1]='#',b[i][1]='.',r[i][m]='.',b[i][m]='#';
	
	for(res i=1;i<=n;i++)
	{
	  for(res j=1;j<=m;j++)
	  printf("%c",r[i][j]);
	  printf("\n");
    }
	  printf("\n");
	for(res i=1;i<=n;i++)
	{
	  for(res j=1;j<=m;j++)
	  printf("%c",b[i][j]);
	  printf("\n");
    }
	
}


Measured memory_bytes: 1280
#coding: utf-8
#ABC043B

l=list(raw_input())

res=""
for i in xrange(len(l)):
 if l[i]=='0':
  res=res+'0'
 elif l[i]=='1':
  res=res+'1'
 elif l[i]=='B':
  res=res[:-1]
  
print res


Measured memory_bytes: 2568
N = int(input())
A = dict()
B = dict()
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
A_sort = sorted(A.items(), key=lambda x:x[1])
B_sort = sorted(B.items(), key=lambda x:x[1])

if N % 2 == 1:
    print(B_sort[(N+1)//2-1][1]-A_sort[(N+1)//2-1][1]+1)
else:
    B_min = B_sort[N//2-1][1]
    A_min = A_sort[N//2-1][1]
    A_max = A_sort[N//2][1]
    B_max = B_sort[N//2][1]
    print(-A_max+B_max-A_min+B_min+1)


Measured memory_bytes: 80348
#include <algorithm>
#include <bitset>
//#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
// namespace mp = boost::multiprecision;
using namespace std;
using ull = unsigned long long;
using ld = long double;
// using ll = boost::multiprecision::cpp_int;
using ll = long long;
#define FOR(i, N) for(ll i = 0; i < N; ++i)

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
// using int = ll;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
void swap(ll &a, ll &b) {
    ll tmp = a;
    a = b;
    b = tmp;
}
ll combi(ll n, ll k) {
    ll r = 1, rr = 1;
    for(ll i = 0; i < k; ++i) {
        r *= (n - i);
        rr *= (i + 1);
        // r %= 1000000007;
        // rr %= 1000000007;
    }
    r /= rr;
    // r %= 1000000007;
    return r;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> v(N);
    FOR(i, N) {
        cin >> v[i];
        ;
    }
    sort(v.begin(), v.end());

    double a=v[0];
    FOR(i, N-1) { ;
        a = (a + v[i + 1]) / 2;
        //cout << v[i] << endl;
    }
    cout << a << endl;
    return 0;
}


Measured memory_bytes: 256
function Main(input) {
  var ar = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51];
  console.log(ar[input-1]);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include<stdio.h>
int main(){
  int h,w;
  char s;
  s ='#';
  // while (1)
  // {
  //   scanf("%d",&h);
  //   scanf("%d",&w);
  //   if(w == 0 && h == 0 )break;
  //   for (int i = 0; i < h; i++)
  //   {
  //     for (int j = 0; j < w; j++)
  //     {
  //       printf("#");
  //     }
  //     printf("\n");
  //   }
  //   printf("\n");
  // }
  ///////////////////////////////////////////////////////////
    while (1)
  {
    scanf("%d",&h);
    scanf("%d",&w);
    if(w == 0 && h == 0 )break;
    for (int i = 0; i < h; i++)
    {
      for (int j = 0; j < w; j++)
      {
        if(j == 0 || j == w-1 || i == 0 || i == h-1 ) s = '#';
        else
        {
          s = '.';
        }
        
        printf("%c",s);
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

const string YES = "Yes";
const string NO = "No";

int main(){
    int n;
    cin >> n;
    vpii ab(n);
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        ab[i] = {b, a};
    }
    sort(all(ab));
    int t = 0;
    bool ans = true;
    for (auto w : ab) {
        if (w.first < t + w.second) ans = false;
        t += w.second;
    }
    cout << (ans?YES:NO) << endl;
    return 0;
}


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


int main() {
    int N; cin >> N;
    vector<int> V(N); for (int i = 0; i < N; i++) cin >> V[i];
    vector<int> C(N); for (int i = 0; i < N; i++) cin >> C[i];

    vector<int> diff(N);
    for (int i = 0; i < N; i++) diff[i] = V[i] - C[i];
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (diff[i] <= 0) continue;
        ans += diff[i];
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    s = S()
    aa = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)
        e[b].add(a)

    sa = []
    for i in range(n):
        if s[i] == '1':
            sa.append(i)

    if len(sa) <= 1:
        return 0

    m = {}
    def f(i,p):
        k = (i,p)
        if k in m:
            return m[k]

        t = 0
        if s[i] == '1':
            t = 1

        h = []
        tk = 0
        tc = 0
        for c in e[i]:
            if c == p:
                continue
            r = f(c,i)
            if r[0] < 1:
                continue
            tc += r[0]
            tk += r[0] + r[1]
            h.append([r[0]+r[1],r[2]])

        if p == -1:
            return h

        mk = 0
        mv = 0
        for u,v in h:
            if mk < u:
                mk = u
                mv = v
        if mk > tk - mk:
            kk = tk - mk
            mk -= kk
            kk += min(mv//2,mk)
            m[k] = (tc+t,tk,kk*2)
        else:
            m[k] = (tc+t,tk,tk//2*2)

        return m[k]

    r = inf

    for i in range(n):
        t = f(i,-1)
        tk = 0
        mk = 0
        for u,v in t:
            tk += u
        if tk % 2 == 1:
            continue

        ff = 1
        for u,v in t:
            kk = u-v
            nk = tk - u
            if kk > nk:
                ff = 0
        # print(i,ff,tk,mk,t)
        if ff == 0:
            continue
        if tk // 2 < mk:
            continue
        v = tk // 2
        if r > v:
            r = v

    if r == inf:
        return -1

    return r


print(main())



Measured memory_bytes: 111444
N,K=gets.split.map(&:to_i)
A=gets.split.map(&:to_i)

temp=0
posacc=A.map{|a| temp+=(a>0 ? a : 0)}
posacc.unshift(0)
temp=0
negacc=A.map{|a| temp+=(a<0 ? -a : 0)}
negacc.unshift(0)

mincost=Float::INFINITY
(N-K+1).times do |i|
  temp=posacc[i+K]-posacc[i]
  mincost=temp if temp<mincost
  temp=negacc[i+K]-negacc[i]
  mincost=temp if temp<mincost
end

puts posacc[N]-mincost

Measured memory_bytes: 11020
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, i;
    long long ans = 0;
    vector <int> v;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        int x;
        
        scanf("%d", &x);
        
        v.push_back(x);
    }
    
    sort(v.begin(), v.end());
    
    if (n % 2 == 0) {
        long long sum = 0;
        
        for (i = 0; i < n / 2; i++) sum -= v[i] * 2;
        sum += v[n / 2 - 1];
        
        for (i = n / 2; i < n; i++) sum += v[i] * 2;
        sum -= v[n / 2];
        
        ans = max(ans, sum);
    } else {
        {
            long long sum = 0;
            
            for (i = 0; i < n / 2; i++) sum -= v[i] * 2;
            
            for (i = n / 2; i < n; i++) sum += v[i] * 2;
            sum -= v[n / 2];
            sum -= v[n / 2 + 1];
            
            ans = max(ans, sum);
        }
        
        {
            long long sum = 0;
            
            for (i = 0; i <= n / 2; i++) sum -= v[i] * 2;
            sum += v[n / 2];
            sum += v[n / 2 - 1];
            
            for (i = n / 2 + 1; i < n; i++) sum += v[i] * 2;
            
            ans = max(ans, sum);
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}


Measured memory_bytes: 892
#include<iostream>
#include<queue>
#include<map>
#define LEN 100
#define BASE 25

using namespace std;

int maps[LEN][LEN];
int off[LEN][LEN];

int checker[4];
int ncheck[4];

map<int, int> points[LEN];

class State {
public:
	char where;
	int enemy;
	int budget;
	int check[4];
	State() {check[0]=0;check[1]=0;check[2]=0;check[3]=0;}
	State(char w, int e, int b ) {
		where = w;
		enemy = e;
		budget = b; 
		check[0] = ncheck[0];
		check[1] = ncheck[1];
		check[2] = ncheck[2];
		check[3] = ncheck[3];
	}
};


inline bool operator< ( const State& a, const State& b) {
	if( a.enemy == b.enemy )
		return a.budget < b.budget;
	return a.enemy < b.enemy;
}

inline bool operator> ( const State& a, const State& b) {
	if ( a.enemy == b.enemy )
		return a.budget > b.budget;
	return a.enemy > b.enemy;
}

priority_queue<State, vector<State>, greater<State> > status;

inline void copy ( State now ) {
	checker[0] = now.check[0];
	checker[1] = now.check[1];
	checker[2] = now.check[2];
	checker[3] = now.check[3];
}

inline void ncopy ( ) {
	ncheck[0] = checker[0];
	ncheck[1] = checker[1];
	ncheck[2] = checker[2];
	ncheck[3] = checker[3];
}

inline bool check ( int i ) {
	return 0 == ((1<<(i%25)) & checker[i/BASE]);
}

inline void add ( int i ) {
	ncheck[i/BASE] = ((1<<(i%25)) | checker[i/BASE]);
}

inline void insert ( int i, int e, int b ) {
	
	map<int,int>::iterator itr = points[i].find(e);
	if ( itr == points[i].end() ) {
		points[i][e] = b;
		status.push(State(i,e,b));
	} else if ( (*itr).second < b ) {
		(*itr).second = b;
		status.push(State(i,e,b));
	}
}

int main () {


	while ( true ) {
		int n,m,l;
		cin >> n >> m >> l;

		if ( n == 0 )
			break;

		for ( int i=0; i<n; i++ ) {
			for ( int j=0; j<n; j++ ) {
				maps[i][j] = -1;
				off[i][j] = 0;
			}
			points[i].clear();
		}

		for ( int i=0; i<m; i++ ) {
			int a,b,d,e;
			cin >> a >> b >> d >> e;

			maps[a-1][b-1] = maps[b-1][a-1] = d;
			off[a-1][b-1] = off[b-1][a-1] = e;
		}

		for ( int i=0; i<4; i++ ) {
			ncheck[i] = 0;
			checker[i] = 0;
		}

		priority_queue<State, vector<State>, greater<State> > empty;
		status = empty;

		ncheck[0] = 1;
		status.push(State(0,0,l));
		int count = 0;
		while(!status.empty()) {
			State now = status.top();
			status.pop();
			if ( now.where == n-1 ) {
				cout << now.enemy << endl;
				break;
			}

			copy(now);

			for ( int i=0; i<n; i++ ) {
				if ( maps[now.where][i] > 0 ) {
					if ( check( i ) ) {
						ncopy();
						add(i);
						int e, b;
						if ( off[now.where][i] == 0 ) {
							e = now.enemy;
							b = now.budget;
							insert(i,e,b);
						} else {
							if ( now.budget - maps[now.where][i] >= 0 ) {
								e = now.enemy;
								b = now.budget - maps[now.where][i];
								insert(i,e,b);
							}
							e = now.enemy + off[now.where][i];
							b = now.budget;
							insert(i,e,b);
						}
					}
				}
			}
		}
	}
}

		

Measured memory_bytes: 3740
#include <stdio.h>
#include <stdlib.h>

int chmin(int a, int b)
{
	if (a > b)
		return b;
	else
		return a;
}


int main(int argc, char const *argv[])
{
	int n;
	scanf("%d", &n);
	int dp[n];
	int h[n];
	for (int i = 0; i < n; ++i)
		dp[i] = 10000;

	for (int i = 0; i < n; ++i)
		scanf("%d", &h[i]);

	dp[0] = 0;
	for (int i = 1; i < n; ++i)
	{			//i - 1の高さから iに移るときのコスト		//i - 2の高さから 以下略
		if (i == 1)dp[1] = abs(h[1] - h[0]);
		else dp[i] = chmin(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
	}
	printf("%d\n", dp[n - 1]);
	return 0;
}


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

using namespace std;

void solve()
{
	vector<int> p(8);
	while(cin >> p[0])
	{
		for(int i = 1; i < 8; ++i)
		{
			cin >> p[i];
		}
		int c[8] = {4, 1, 4, 1, 2, 1, 2, 1};
		int max_people = 0;
		vector<int> list;
		for(int i = 0; i < 8; ++i)
		{
			int people = 0;
			for(int j = 0; j < 8; ++j)
			{
				if(p[j] >= c[(i + j) % 8])
				{
					people += c[(i + j) % 8];
				}
				else
				{
					people += p[j];
				}
			}
			if(max_people < people)
			{
				max_people = people;
			}
		}
		for(int i = 0; i < 8; ++i)
		{
			int people = 0;
			for(int j = 0; j < 8; ++j)
			{
				if(p[j] >= c[(i + j) % 8])
				{
					people += c[(i + j) % 8];
				}
				else
				{
					people += p[j];
				}
			}
			if(people == max_people)
			{
				int k = 10000000;
				int sum = 0;
				for(int j = 0; j < 8; ++j)
				{
					sum += k * c[(i + j) % 8];
					k /= 10;
				}
				list.push_back(sum);
			}
		}
		sort(list.begin(), list.end());
		int k = 10000000;
		for(int i = 0; i < 7; ++i)
		{
			cout << list[0] / k << " ";
			list[0] %= k;
			k /= 10;
		}
		cout << list[0] << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1216
#include <iostream>
using namespace std;
int mp[2][20010],n;

int solve(){
  int x=0,y=0,cost=0,f=1;
  while(x!=n+1) {
    if(f&&mp[0][x])f=0;
    if(f&&mp[1][x])f=0,cost++;

    if(mp[1][x])y=1,mp[1][x]=0;
    else if(mp[0][x])y=mp[0][x]=0;
    else x++;
    cost++;
  }
  if(y==1)cost++;
  return cost-1;
}

int main(){
  int q;
  cin>> q;
  while(q--){
    cin>>n;
    char a;
    for(int i=0;i<2;i++)
      for(int j=0;j<2*n;j++)cin>> a,mp[i][(j+1)/2] |= a/'Y';
    cout<<solve()<<endl;
  }
  return 0;
}

Measured memory_bytes: 1240
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> bool max_self(T & a, const T & b){ 
  return b > a ? a = b, true : false; 
}
template<class T> bool min_self(T & a, const T & b){ 
  return b < a ? a = b, true : false;    
}
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);


int main(){
  FAST_IO
  int N, M;
  LL total = 0;
  cin >> N >> M;
  vector<pair<int, int>> cost(N);
  for(auto &ele : cost){
    cin >> ele.F >> ele.S;
  }

  sort(ALL(cost));

  for(auto ele : cost){
    int buy = min(ele.S, M);
    total += (LL)buy * ele.F;
    M -= buy;
  }

  cout << total; 
  return 0;
}


Measured memory_bytes: 3960
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define lop(i, n) for(i=0; i<n; i++)

int main()
{
	int s[100], cnt;
	int n, k, i, j;
	scanf("%d %d", &n, &k);
	lop(i, n){ s[i]=1; }
	
	int d[100];
	cnt=n;
	
	lop(i, k){
		scanf("%d", &d[i]);
		lop(j, d[i]){
			int a;
			scanf("%d", &a);
			if(s[a]!=0){ s[a]=0; cnt--; }
		}
		
	}
	
	printf("%d", cnt);
	
return 0;
}

Measured memory_bytes: 1728
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)

	ans := ""
	for _, r := range s {
		if r == 'B' && ans != "" {
			ans = ans[0 : len(ans)-1]
		}
		if r == '0' || r == '1' {
			ans += string(r)
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>

const int MAXN = (int)1e5;

int r[MAXN], g[MAXN], c[MAXN];

int64_t calc_sum(int l, int r, int *a) {
  int64_t sum = 0;
  for (int i = l; i < r; ++i) sum += a[i];
  return sum;
}

int64_t solve(int get_r, int get_g, int r_num, int g_num, int c_num) {
  std::sort(r, r + r_num);
  std::sort(g, g + g_num);
  std::sort(c, c + c_num);

  int r_p = r_num - get_r;
  int g_p = g_num - get_g;
  int c_p = c_num - 1;
  int64_t sum = calc_sum(r_p, r_num, r) + calc_sum(g_p, g_num, g);

  while (c_p >= 0 && (r_p < r_num || g_p < g_num)) {
    bool is_r = true;
    int cur = r[r_p];
    if (r_p == r_num || (g_p < g_num && r[r_p] > g[g_p])) {
      is_r = false;
      cur = g[g_p];
    }
    if (cur >= c[c_p]) break;
    sum += c[c_p--] - cur;
    if (is_r) ++r_p;
    else ++g_p;
  }
  return sum;
}

int main() {
  int get_r, get_g, r_num, g_num, c_num;
  std::cin >> get_r >> get_g >> r_num >> g_num >> c_num;
  for (int i = 0; i < r_num; ++i) std::cin >> r[i];
  for (int i = 0; i < g_num; ++i) std::cin >> g[i];
  for (int i = 0; i < c_num; ++i) std::cin >> c[i];
  
  std::cout << solve(get_r, get_g, r_num, g_num, c_num) << std::endl;
  return 0;
}


Measured memory_bytes: 1408
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
T[] RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[][] RDA2(T = long)(size_t n, T[] fix = []) { auto r = new T[][](n); foreach (i; 0..n) { r[i] = readln.chomp.split.to!(T[]); foreach (j, e; fix) r[i][j] += e; } return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

//long mod = 10^^9 + 7;
long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto A = RDA;
	double ans = 0.0;
	foreach (i; 0..N)
	{
		ans += 1.0 / A[i];
	}

	writefln(FMT_F, 1.0 / ans);
	stdout.flush();
	debug readln();
}

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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = long long;

void solve() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '?') {
      s[i] = 'D';
    }
  }
  cout << s << endl;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);

  solve();
  return 0;
}


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

int main() {
  ll n, ans = 0;
  cin >> n;
  vector<ll> h(n);  rep(i, 0, n) cin >> h[i];
  
  while(accumulate(begin(h), end(h), 0) > 0) {
    rep(i, 0, n) {
      if(h[i] != 0) {
        ans++;
        rep(j, i, n) {
          if(h[j] > 0) {
            h[j]--;
            i++;
          }
          else break;
        }
      }
    }      
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
/*
* @Author: Samson
* @Date:   2018-06-11 11:31:19
* @Last Modified by:   Samson
* @Last Modified time: 2018-06-11 11:46:49
*/
//   @URL : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
#include<bits/stdc++.h>
#include<algorithm>
#include <cstdlib>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN = 1e3+10;

string a,b;
int f[MAXN][MAXN];

int solve()
{
	memset(f,0,sizeof f);
	int lena = a.size(),lenb = b.size();
	int maxv = 0;
	a = ' '+a,	b = ' '+b;
	for(int i = 1; i <= lena; ++i)
	{
		for(int j = 1; j <= lenb; ++j)
		{
			if(a[i] == b[j])
				f[i][j] = f[i-1][j-1]+1;
			else
				f[i][j] = max(f[i-1][j],f[i][j-1]);
			if(f[i][j] > maxv)	maxv = f[i][j];
		}
	}
	return maxv;
}
int main(void)
{
	ios::sync_with_stdio(false); 
	//cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>a>>b;
		cout<<solve()<<'\n';
	}
	return 0;
}



Measured memory_bytes: 7204
#include <iostream>
#include <algorithm>
#include <vector>
#define NMAX 105
#define WMAX 10005
#define DIAGONAL 1
#define TOP 0

using namespace std;

struct Item
{
	int value,weight;
};

int N,W;
Item items[NMAX+1];
int C[NMAX+1][WMAX+1],G[NMAX+1][WMAX+1];

void compute(int &maxValue, vector<int> &selection)
{
    //????????§?°?w???0?????????????????°i???0??¶?????????????????????0?????????C???w=0???i=0????????????????´??????¨??¨????§???????0.
	for(int w=0;w<=W;w++)
	{
		C[0][w]=0;
		// G[0][w]=DIAGONAL;//????????????
	}
	
	for(int i=1;i<=N;i++)
		C[i][0]=0;
	
	for(int i=1;i<=N;i++)
	{
		for(int w=1;w<=W;w++)
		{
			C[i][w]=C[i-1][w];
			G[i][w]=TOP;
			if(items[i].weight>w)
				continue;
			if(items[i].value+C[i-1][w-items[i].weight]>C[i-1][w])
			{
				C[i][w]=items[i].value+C[i-1][w-items[i].weight];
				G[i][w]=DIAGONAL;
			}
		}
	}
	maxValue=C[N][W];
	selection.clear();
	for(int i=N,w=W;i>=1;i--)
	{
		if(G[i][w]==DIAGONAL)
		{
			selection.push_back(items[i].value);
			w-=items[i].weight;
		}
	}
	reverse(selection.begin(), selection.end());
}

void input()
{
	cin>>N>>W;
	for(int i=1;i<=N;i++)
		cin>>items[i].value>>items[i].weight;
}

int main()
{
	int maxValue;
	vector<int> selection;
	input();
	compute(maxValue,selection);
	
	cout<<maxValue<<endl;
	
	/*cout<<endl;
	for(int n=0;n<=N;n++)
	{
		for(int m=0;m<=W;m++)
		cout<<G[n][m]<<" ";
		cout<<endl;
	}*/
	/*cout<<"??????????????????????????????";
	for(int i=0;i<selection.size();i++)cout<<selection[i]<<" ";*/
}

Measured memory_bytes: 11000
#include <stdio.h>
#include <math.h>
int main(){

  double a,l,x,hon,yoko;

  while(scanf("%lf %lf %lf",&a,&l,&x) != EOF){

  hon=sqrt(l*l-a*a/4)*a/2;

  yoko=sqrt((l*l+2*l*x+x*x)/4-l*l/4)*l;

  printf("%f\n",hon+yoko);
  
  }

  return 0;

}

Measured memory_bytes: 2556
N = gets.to_i
A = gets.split.map(&:to_i)
Amax = A.max
D = Array.new(Amax + 1,&:itself)
(2 .. Integer.sqrt(Amax)).each do |i|
  next if D[i] < i
  s = i
  while s < D.size
    D[s] = i if D[s] == s
    s += i
  end
end
pairs = Array.new(Amax + 1, 0)
A.each do |a|
  while a > 1
    m = D[a]
    pairs[m] += 1
    while a % m == 0
      a /= m
    end
  end
end
if pairs.max <= 1 
  puts 'pairwise coprime'
elsif A.inject(&:gcd) == 1
  puts 'setwise coprime'
else
  puts 'not coprime'
end


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

using namespace std;

typedef long long int lli;

int main() {
    int n, k;

    cin >> n >> k;

    long double ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int cont = 1, num = i;
        while (num < k) {
            num *= 2;
            cont *= 2;
        }
        ans += 1/(long double)n * 1/(long double)cont;
    }
    
    cout << std::fixed << std::setprecision(10) << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int N, A[100001] = {},min = 1000000001,amarimin = 1000000001,ans=0;
	bool flag = false;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
		if (A[i] < min)min = A[i];
	}
	for (int i = 0; i < N; i++)
	{
		if (amarimin > A[i] % min && A[i] % min != 0) {
			amarimin = A[i] % min;
			flag = true;
		}
	}
	while (min % amarimin != 0 && flag == true)
	{
		int tmp = amarimin;
		amarimin = min % amarimin;
		min = tmp;
	}
	if (amarimin <= min)ans = amarimin;
	else ans = min;
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int a[5],cnt;
int main()
{
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);

    if(a[1]==a[2])
    {
        cnt=0;
        while((a[0]+2)<=a[1])
        {
            a[0]+=2;
            cnt++;
        }
        if(a[0]!=a[1])
        {
            cnt+=2;
        }
    }
        else
    {
        while((a[1]+2)<=a[2])
        {
            cnt++;
            a[1]+=2;
        }
        if(a[1]<a[2])
        {
            cnt++;
            a[0]++;
            a[1]++;
        }
        while((a[0]+2)<=a[1])
        {
            a[0]+=2;
            cnt++;
        }
        if(a[0]!=a[1])
        {
            cnt+=2;
        }
    }
    cout<<cnt<<'\n';
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long ans = 0;

    for (int n = 1; n <= N; n++) {
      int a = n % 3;
      int b = n % 5;
      if (a != 0 && b != 0) {
        ans = ans + n;
      }
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 35728
// AOJ 0539: Pizza
// 2017.9.1 bal4u@uu
// 2017.11.14

#include <stdio.h>
#include <stdlib.h>

#define MIN(a,b) ((a)<=(b)?(a):(b))

int p[100003]; int n;

int cmp(int *a, int *b) { return *a - *b; }

int bsrch(int x)
{
	int m, l = 0, r = n;
    while (l < r) {
        m = (l + r) >> 1;
//		if (p[m] == x) return 0;
		if (p[m] < x) l = m + 1; else r = m;
    }
	return MIN(x-p[l-1], p[l]-x); 
}

char buf[15], *bp;
int getint()
{
	int n = 0;
	while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf);
	return n;
}

int main()
{
	int d, m, i, ans;

	while (fgets(bp=buf, 15, stdin) && *buf != '0') {
		d = getint();
		fgets(bp=buf, 15, stdin), n = getint();
		fgets(bp=buf, 15, stdin), m = getint();

		p[0] = 0, p[n] = d;
		for (i = 1; i < n; i++) fgets(bp=buf, 15, stdin), p[i] = getint();
		n++; qsort(p, n, sizeof(int), cmp);

		ans = 0; while (m--) {
			fgets(bp=buf, 15, stdin);
			ans += bsrch(getint());
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 2512
#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
  int N;
  cin >> N;

  int ret = 0;
  for (int i = 1; i <= N; ++i) {
    int c = 0;
    for (int j = 1; j <= i; j += 2) {
      if (i % j == 0)
        ++c;
    }
    if (c == 8)
      ++ret;
  }

  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>

struct Node {
	int key;
	Node *prev, *next;
};

Node *nil;

void init() {
	nil = (Node *)malloc(sizeof(Node));
	nil->next = nil;
	nil->prev = nil;
}

void insert(int key){
	Node *x = (Node *)malloc(sizeof(Node));
	x->key = key;
	x->next = nil->next;
	nil->next->prev = x;
	nil->next = x;
	x->prev = nil;
}

Node* listSearch(int key){
	Node *cur = nil->next;
	while(cur != nil && cur->key != key){
		cur = cur->next;
	}
	return cur;
}
void deleteNode(Node *t){
	if(t == nil) return;
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t);
}

void deleteFirst(){
	deleteNode(nil->next);
}

void delateLast(){
	deleteNode(nil->prev);
}

void deleteKey(int key){
	deleteNode(listSearch(key));
}

void printList() {
	Node *cur = nil->next;
	int isf = 0;
	while(1){
		if(cur == nil) break;
		if (isf++ > 0) printf(" ");
		printf("%d", cur->key);
		cur = cur->next; 
	}
	printf("\n");
}

int main(){
	int key, n, i;
	int size = 0;
	char com[20];
	int np = 0, nd = 0;
	scanf("%d", &n);
	init();
	for(i = 0; i < n; i++){
		scanf("%s", com);
		if(com[0] == 'i'){scanf("%d", &key);insert(key); np++; size++; }
		else if(com[0] == 'd'){
			if(strlen(com) > 6){
				if(com[6] == 'F') deleteFirst();
				else if(com[6] == 'L') delateLast();
			} else {
				scanf("%d", &key);
				deleteKey(key); nd++;
			}
			size--;
		}
	}

	printList();
}






Measured memory_bytes: 33820
n = gets.to_i
ps = gets.split.map(&:to_i)
r = 0
(1..(n-1)/2).each do |d|
  s = 0
  d.step(n-2, d).each do |i|
    j = n - i - 1
    break if (j == i || j == i - d || j <= d)
    s += ps[i] + ps[j]
    r = s if (s > r)
  end
end
puts(r)


Measured memory_bytes: 14596
import bisect
n = int(input())
seq = [int(input()) for i in range(n)]

LIS = []
for number in seq:
    index = bisect.bisect_left(LIS, number)
    if index >= len(LIS):
       LIS.append(number)
    else:
        LIS[index] = number
print(len(LIS))



Measured memory_bytes: 10344
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int MOD=1e9+7;
ll a[N],sum[N];
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    string s;
    cin >>s;
    sort(s.begin(),s.end());
    if(s=="abc")    cout <<"Yes"<<endl;
    else    cout<<"No"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <queue>
#include <set>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
 
#define ll long long
#define uint unsigned int
#define ull unsigned ll
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define speedhack() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define do(x) for(int i = 1; i <= x; i++){ solve(); }
#define sz(x) (int)x.size()
#define pii pair < int, int >
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
const ll MAXN = 1e18;
const ll SIZE = 5e4+2; //are u sure?
const ll mod = 1e9+7;

bool check(ll x){
	if(x < 2) return false;
	for(ll i = 2; i * i < x; i++){
		if(x % i == 0) return false;
	}return true;
}

void solve(){
	int n; cin >> n;
	for(ll i = n; i < MAXN; i++){
		if(check(i)){
			cout << i << endl;
			return;
		}
	}
}


int main(){
	speedhack()
	// int it; cin >> it;
	int it = 1;
	do(it);
	return 0;
}

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

using namespace std;

int main(){
  string s;
  int k;
  cin >> k >> s;
  
  if(s.length() <= k){
    cout << s << endl;
  } else {
    cout << s.substr(0, k) << "..." << endl;
  }
  return 0;
}

Measured memory_bytes: 3624
N, M = map(int, input().split())
broken = set()
for _ in range(M):
  broken.add(int(input()))

dp = [0 for _ in range(N+1)]
dp[0] = 1
if 1 not in broken:
  dp[1] = 1

for i in range(2,N+1):
  if i not in broken:
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
    
print(dp[-1])

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

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

using namespace std;

int bfs(vector<string>& t, int c,int h, int w) {
  int si = 0, sj = 0;
  int ti = 0, tj = 0;
  REP(i,h)REP(j,w){
    if(t[i][j] == c + '0'){
      si = i;
      sj = j;
    }
    if(t[i][j] == c + '1'){
      ti = i;
      tj = j;
    }
  }
  vector<vector<int>> vis(h,vector<int>(w,1000000000));
  vis[si][sj] = 0;
  queue<pair<int,int>> q;
  q.push(make_pair(si,sj));
  while(!q.empty()) {
    auto p = q.front();
    q.pop();
    int i = p.first;
    int j = p.second;
    int di[4] = {1,0,-1,0};
    int dj[4] = {0,1,0,-1};
    REP(k,4){
      int ni=i+di[k];
      int nj=j+dj[k];
      if(ni<0||nj<0||ni>=h||nj>=w) continue;
      if(t[ni][nj] == 'X') continue;
      if(vis[ni][nj] > vis[i][j] + 1) {
        vis[ni][nj] = vis[i][j] + 1;
        q.push(make_pair(ni,nj));
      }
    }
  }
  return vis[ti][tj];
}

int main() {
  int h,w,n;
  cin >> h >> w >> n;
  vector<string> t(h);
  REP(i,h) cin >> t[i];
  int sum = 0;
  REP(i,h)REP(j,w)
    if(t[i][j] == 'S')
      t[i][j] = '0';
  REP(i,n) {
    sum += bfs(t,i,h,w);
  }
  cout << sum << endl;
  return 0;
}

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

using namespace std;
typedef long long ll;

ll n, w, dp[100+9][100000+9], m[100+9], v[100+9];


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>w;
    for(int i=1; i<=n; i++) cin>>m[i]>>v[i];
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<m[i]; j++) dp[i][j]=dp[i-1][j];
        for(int j=w; j>=m[i]; j--)
            dp[i][j]=max(dp[i-1][j], dp[i-1][j-m[i]]+v[i]);

    }
    cout<<dp[n][w]<<endl;
    return 0;
}


Measured memory_bytes: 79360
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
#define acc(v) accumulate(v.begin(), v.end(), 0)
#define cinv(n,v) rep(i,n) cin >> v[i]
using namespace std;
const int INF = 1e9;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vchar;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
int x_pos[4] = {1,0,-1,0}, y_pos[4] = {0,1,0,-1};
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

char upper(char c){
	return c-0x20;
}

char lower(char c){
	return c+0x20;
}

void unique_vector(vector<int>& v){
	sort(all(v));
	v.erase(unique(all(v)), v.end());
}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

//ユークリッドの互除法
//最大公約数
ll gcd(ll x, ll y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}

//最小公倍数
ll lcm(ll x, ll y){
	ll g = gcd(x,y);
	return x/g*y;
}

ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

int main() {
	string s;
	cin >> s;
	rep(i, s.length())
	{
		if (i % 2 == 0)
		{
			//奇数
			if (s[i] == 'L')
			{
				cout << "No" << endl;
				return 0;
			}
		}else{
			if(s[i]=='R'){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
}


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


int main(){
  ll n;
  while(cin>>n,n){
    vector<ll> e,o;
    for(ll i=0,x;i<n*(n+1)/2;i++){
      cin>>x;
      if(x%2)o.push_back(x);
      else e.push_back(x);
    }
    sort(e.begin(),e.end());
    sort(o.begin(),o.end());
    ll x=e[0],y=e[1],z=o[0];
    ll tp=__gcd(x,z);
    x/=tp,z/=tp,y/=z;
    ll an=sqrt(x*y+0.1);
    cout<<an<<endl;
    for(ll i=0;i<e.size();i++){
      if(i)cout<<' ';
      cout<<e[i]/an;
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3304
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>

template<class T>
struct ICAdd {
  std::vector<T> val;
  std::vector<int> l;
  std::vector<int> r;
  std::vector<int> uf;
  std::vector<int> uf2;

  ICAdd(int n) : l(n, -1), r(n, -1), val(n), uf(n, -1), uf2(n) {
    for (int i = 0; i < n; i++) {
      uf2[i] = i;
    }
  }

  int find(int u) {
    if (uf[u] < 0) return u;
    return uf[u] = find(uf[u]);
  }

  void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (-uf[u] < -uf[v]) std::swap(u, v);
    uf[u] += uf[v];
    uf[v] = u;
    val.push_back(T());
    l.push_back(uf2[u]);
    r.push_back(uf2[v]);
    uf2[u] = l.size() - 1;
  }

  void add(int u, T x) {
    val[uf2[find(u)]] += x;
  }

  int size(int u) {
    return -uf[find(u)];
  }

  void dfs(int u, T x) {
    if (u == -1) return;
    val[u] += x;
    dfs(l[u], val[u]);
    dfs(r[u], val[u]);
  }

  void build() {
    std::vector<bool> used(l.size());
    for (int i = l.size() - 1; i >= 0; i--) {
      if (l[i] != -1) used[l[i]] = true;
      if (r[i] != -1) used[r[i]] = true;
      if (!used[i]) {
        dfs(i, T());
      }
    }
  }
};

int main() {
  using namespace std;

  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
 
  vector<tuple<int, int, int>> es;
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    es.emplace_back(w, u, v);
  }
 
  sort(es.begin(), es.end());
  reverse(es.begin(), es.end());
 
  ICAdd<long long> ic(n);
  for (auto e : es) {
    int w, u, v;
    tie(w, u, v) = e;
    long long x = ic.size(u);
    long long y = ic.size(v);
    ic.add(u, y*w);
    ic.add(v, x*w);
    ic.merge(u, v);
  }
 
  ic.build();
 
  for (int i = 0; i < n; i++) {
    cout << ic.val[i] << endl;
  }
}


Measured memory_bytes: 8676
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m,q = LI()
    require = [LI() for _ in range(q)]
    itr = itertools.combinations_with_replacement(list(range(1,n+2)),m-1)     
    ans = 0
    for i in itr:
        lst = [0 for _ in range(n+2)]
        lst[0] = 1
        cnt = 0
        for j in i:
            lst[j] += 1
        lst = list(itertools.accumulate(lst))
        for re in require:
            if lst[re[1]]-lst[re[0]]==re[2]:
                cnt += re[3]
        ans = max(cnt,ans)
    print(ans)

main()

Measured memory_bytes: 10120
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに実装したソースコード
 */
public class Main {

	private static final long MOD = 1_000_000_007L;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int h = scanner.nextInt(), w = scanner.nextInt(), a = scanner.nextInt(), b = scanner.nextInt();
			// 階乗の配列
			long[] frac = new long[h + w - 1];
			frac[0] = 1;
			IntStream.range(1, frac.length).forEach(i -> frac[i] = frac[i - 1] * i % MOD);
			// 階乗^-1の配列
			long[] reverseFrac = new long[h + w - 1];
			reverseFrac[h + w - 2] = powMod(frac[h + w - 2], MOD - 2);
			for (int i = reverseFrac.length - 2; i >= 0; i--) {
				reverseFrac[i] = reverseFrac[i + 1] * (i + 1) % MOD;
			}
			long answer = 0L;
			for (int i = b; i < w; i++) {
				answer += frac[h - a - 1 + i] * reverseFrac[h - a - 1] % MOD * reverseFrac[i] % MOD
						* frac[a + w - 2 - i] % MOD * reverseFrac[a - 1] % MOD * reverseFrac[w - 1 - i] % MOD;
				answer %= MOD;
			}
			System.out.println(answer);
		}
	}

	/**
	 * @param n
	 * @param m
	 * @return n^m mod MOD
	 */
	private static long powMod(long n, long m) {
		long result = 1L;
		while (m > 0) {
			if (1 == (m & 1)) {
				result = result * n % MOD;
			}
			n = n * n % MOD;
			m >>= 1;
		}
		return result;
	}
}


Measured memory_bytes: 39748
#define _GLIBCXX_DEBUG //GCC環境での[]デバッグ
#include <bits/stdc++.h> //全ての標準ライブラリ
#define rep(i,n) for(int i = 0;i < n;i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
using namespace std;
using ll = long long;
int sumVector (const std::vector<int>& v){ //int配列計算
    int sum = 0;
    rep(i, v.size()) sum += v.at(i);
    return sum; 
}
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k,a,temp,cnt=0;
    cin >> n >> k;
    std::map<int, int> m;
    rep(i,k){
        cin >> a;
        rep(j,a){
            cin >> temp;
            temp --;
            m[temp] = 1;
        }
    }
    rep(i,n){
        if(m[i] == 0) cnt++;
    }
    cout << cnt;
    
}

Measured memory_bytes: 3684
#include <iostream>
using namespace std;
 
int main() {
	int W,H,x,y,r;
	cin >> W >> H >> x >> y >> r;
	if(W>=(x+r) && H>=(y+r) && (x+r)>0 && (y+r)>0){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3100
#include<stdio.h>

int main(){
  int i, j, minj, N, temp, count = 0, flag = 0, k;
  int A[100];

  scanf("%d", &N);

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

  for(i = 0; i < N; i++){
    flag=0;
    minj = i;
    for(j = i; j < N; j++){
      if(A[j] < A[minj]){
	flag=1;
	minj = j;
      }
    }
    if(flag==1){
      count++;
    }
    temp = A[i];
    A[i] = A[minj];
    A[minj] = temp;



  }

  for(i = 0; i < N; i++){
    if(i == N-1){
      printf("%d\n", A[i]);
      break;
    }
    printf("%d ",A[i]);
  }

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

  



Measured memory_bytes: 2104
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;

void main() {
    while(true) {
        int n = readln.chomp.to!int;
        if (n==0) break;
        long[] p = readln.split.to!(long[]);
        long[] j = readln.split.to!(long[]);

        int[] ary = (n-1).iota.array;
        sort!((a,b)=>a[1]>b[1])(zip(ary, j.dup));
        long num = n*p.sum;
        foreach(i; 0..ary.length) {
            long[] _p = p[0..ary[i]] ~ (p[ary[i]]+j[ary[i]]+p[ary[i]+1]) ~ (ary[i]+2<p.length ? p[ary[i]+2..$]:[]);
            long[] _j = j[0..ary[i]] ~ j[ary[i]+1..$];
            long _num = _p.length*_p.sum;
            if (_num > num) {
                p = _p;
                j = _j;
                num = _num;
                ary = ary.map!(a=>a>ary[i]?a-1:a).array;
            } else {
                break;
            }
        }
        num.writeln;
    }
}
int[] subtract(int[] a, int[] b) {
    string num = (a.to!(string[]).reduce!((a,b)=>a~b).to!int - b.to!(string[]).reduce!((a,b)=>a~b).to!int).to!string;
    while(num.length<4) {
        num = "0"~num;
    }
    return num.to!(char[]).map!(a=>(a-'0').to!int).array;
}

Measured memory_bytes: 15616
#include "bits/stdc++.h"

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

string fie[30]={};
int w,h;
int c;
bool visited[30][30];

void dfs(int y,int x){
    visited[y][x]=true;
    c++;
    int dx[]={1,0,-1,0};
    int dy[]={0,1,0,-1};
    rep(i,4){
        if(0<=x+dx[i] && x+dx[i]<w  &&  0<=y+dy[i] && y+dy[i]<h  &&  fie[y+dy[i]][x+dx[i]]=='.'  &&  visited[y+dy[i]][x+dx[i]]==false){
            dfs(y+dy[i],x+dx[i]);
        }
    }
}


int main(){
    while(cin>>w>>h){
        c=0;
        if(w==0 && h==0)break;
        rep(i,30)rep(j,30)visited[i][j]=false;
        int sy,sx;
        rep(i,h){
            cin>>fie[i];
        }
        rep(i,h)rep(j,w){
            if(fie[i][j]=='@') sy=i,sx=j;
        }
        
        dfs(sy,sx);
             
        cout<<c<<endl;
    }
}

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

using namespace std;

int main(){
  long long n, a[200009];
  cin >> n;
  for(int i=0;i<n;i++)cin >> a[i];
  sort(a, a+n);
  long long ans=a[n-1];
  int cnt=0;
  if(n==2){
    cout << ans << endl;
    return 0;
  }
  for(int i=n-2;i>=0;i--){
    ans += a[i];
    cnt++;
    if(cnt==n-2)break;
    ans += a[i];
    cnt++;
    if(cnt==n-2)break;
  }
  cout << ans << endl;
}



Measured memory_bytes: 5200
#include<stdio.h>
 
int main(){
  
 unsigned long long int a,ans;
 double b;
 
  (void) scanf("%llu %lf",&a,&b);
 // printf("%llu %lf\n",a,b);
 
  ans=a*(b*100);
  ans=ans/100;
   
 printf("%llu",ans);
  
 return 0; 
}

Measured memory_bytes: 2140
# 三角形を作れる場合
# A+B > C
N = int(input())
L = [int(i) for i in input().split()]
counter = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i]+L[j] > L[k] and L[i]+L[k] > L[j] and L[j] + L[k] > L[i]:
                if L[i] != L[j] and L[i] != L[k] and L[j] != L[k]:
                    counter += 1
print(counter)

Measured memory_bytes: 68268
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;

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

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
#グローバル変数
pn_list = [2,3]

def next_pn(pn):
    npn = pn + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list:
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list.append(npn)
    return npn

# 整数の入力
n = int(input())
s = input()
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)

# a を素因数分解する
lcm = int(1)
for i in pn_list:
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(n):
            if a[j] % i == 0:
                a[j] = a[j] // i
                wareta = 1
        if wareta == 1:
            lcm = lcm * i
pn_lcm = []
for i in a:
    if i > 1:
        if i not in pn_lcm:
            pn_lcm.append(i)
            lcm = lcm * i

min_bsum = int(0)
for i in aa:
    min_bsum = min_bsum + lcm // i

print(min_bsum % (10**9+7))


Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
// 型エイリアス
using pii = pair<int, int>;
using tisb = tuple<int, string, bool>;
using vi = vector<int>;
using vii = vector<vi>;

int top, S[1000];

void push(int x){
  ++top;
  S[top] = x;
}

int pop(){
  --top;
  return S[top+1];
}

int main(){
  int x, y;
  top = 0;
  char s[100];

  while(cin >> s){
    if(s[0] == '+'){
      x = pop();
      y = pop();
      push(x+y);
    }else if(s[0] == '-'){
      x = pop();
      y = pop();
      push(y-x);
    }else if(s[0] == '*'){
      x = pop();
      y = pop();
      push(x*y);
    }else{
      x = atoi(s);
      push(x);
    }
  }

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

  return 0;
}


Measured memory_bytes: 3236