akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define Rep(n) for (ll _ = 0; _ < (ll)(n); _++)
#define fs first
#define sc second

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}
template <class S> void print(vector<S> &v){for(ll i=0; i<(ll)v.size(); i++){cerr << v[i] << ' ';}cerr << endl;}
template <class S> void print(vector<vector<S>> &v) {for (ll i = 0; i < (ll)v.size(); i++) {for (ll j = 0; j < (ll)v[i].size(); j++) {cerr << v[i][j] << ' ';}cerr << endl;}}

int main(){
	int n; cin >> n;
	vector<int> a(n+1), b(n+1,0);
	rep(i,n) cin >> a[i+1];
	int ans = 0;
	for(int i=n; i>0; i--){
		int t = 0;
		for(int j=i+i; j<=n; j+=i){
			//cerr << j << endl;
			if(b[j]){
				t = !t;
			}
		}
		cerr << t << a[i] << endl;
		if(t != a[i]){
			b[i] = 1;
			ans++;
		}
	}
	cout << ans << endl;
	print(b);
	rep(i,n){
		if(b[i+1]){
			cout << i+1 << ' ';
		}
	}
}

Measured memory_bytes: 4844
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


int main()
{
	ll n, m;
	cin >> n >> m;

	vector<ll> h(n);
	vector<ll> x(n);
	for (ll i = 0; i < n; i++)
	{
		cin >> h[i];
	}

	ll res = 0;
	for (ll i = 0; i < m; i++)
	{
		ll a, b;
		cin >> a >> b;

		a--;
		b--;
		
		x[a] = max(x[a], h[b]);
		x[b] = max(x[b], h[a]);
	}

	for (ll i = 0; i < n; i++)
	{
		if (h[i] > x[i])
		{
			res++;
		}
	}

	println(res);
}

Measured memory_bytes: 4844
nums = list(map(lambda x: int(x), input().split(" ")))
n = nums[0]
k = nums[1]
ps = list(map(lambda x: (int(x) + 1) / 2, input().split(" ")))
res = 0.0
su = 0.0
sums = [0] * n
for i, s in enumerate(ps):
    su = su + s
    sums[i] = su
for i in range(n - k + 1):
    if i == 0:
        res = sums[k - 1]
    else:
        res = max(res, sums[i + k - 1] - sums[i - 1] )
print(res)

Measured memory_bytes: 23524
import java.util.Scanner;

// 3
public class Main{

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

        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();

        String s = sc.next();

        int count = 0;
        int count_b = 0;
        for(int i = 0; i < N; i++) {
            char c = s.charAt(i);

            if(c == 'c') {
                System.out.println("No");
                continue;
            }

            if(c == 'a') {
                if(count < (A + B)) {
                    System.out.println("Yes");
                    ++count;
                    continue;
                }else {
                	System.out.println("No");
                    continue;
                }
            }

            if(c == 'b') {
                if(count < (A + B) && (count_b + 1) <= B) {
                    System.out.println("Yes");
                    ++count;
                    ++count_b;
                    continue;
                }else {
                	System.out.println("No");
                	continue;
                }
            }
        }
    }

}


Measured memory_bytes: 50288
#include <bits/stdc++.h>
using namespace std;
#define int long long

int N, U, A[100005], DC[100005], ft[100005];
pair<int, int> T[100005];

inline int ls(int x) { return x & -x; }

int qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r = max(r, ft[p]);
	return r;
}

void upd(int p, int v) {
	for (; p <= N; p += ls(p)) ft[p] = max(ft[p], v);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i], T[i] = make_pair(A[i], i);
	sort(T + 1, T + 1 + N);
	for (int i = 1, c = 1; i <= N; i++) {
		DC[T[i].second] = c;
		if (T[i].first ^ T[i + 1].first) c++;
	}
	for (int i = 1; i <= N; i++) {
		int R = qry(N - DC[i] + 1);
		U = max(U, R + 1);
		upd(N - DC[i] + 1, R + 1);
	}
	cout << U << '\n';
}


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

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

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

    long long ans = 0;
    for (int i = 1; i < n; i++) {
        long long tmp = 0;
        if ((n - 1) % i == 0) {
            for (int j = 0, k = n - 1; j < k; j += i, k -= i) {
                tmp += as[j] + as[k];
                ans = max(ans, tmp);
            }
        } else {
            for (int j = 0, k = n - 1; j < n && k > i; j += i, k -= i) {
                tmp += as[j] + as[k];
                ans = max(ans, tmp);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAX 1000100

int main(){
  int n, k, cs;
  
  cin >> cs;
  while(cs--){
    cin >> n >> k;
    
    int val[MAX], dis[MAX];
    
    for(int i = 0 ; i < n ; i++) cin >> val[i];
    for(int i = 0 ; i < n-1 ; i++) dis[i] = val[i+1]-val[i];
    
    int total = val[n-1] - val[0];
    
    sort(dis, dis+n-1);
    reverse(dis, dis+n-1);
    
    //cout << "total = " << total << endl;
    //for(int i = 0 ; i < n-1 ; i++) cout << dis[i] << ' ';
    //cout << endl;
    
    if(n <= k) cout << 0 << endl;
    else{
      for(int i = 0 ; i < k-1 ; i++) total -= dis[i];
      cout << total << endl;
    }
  }
  return 0;
}

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

int main()
{
	int n[10];
	for(int i = 0; i < 10; i++)
	{
		cin >> n[i];
	}
	
	int max = 0;
	
	for(int i = 0; i < 9; i++)
	{
		for(int j = i+1; j < 10; j++)
		{
			if(n[i] < n[j]) swap(n[i], n[j]);
		}
	}
	
	cout << n[0] << endl;
	cout << n[1] << endl;
	cout << n[2] << endl;
	
	return 0;
}

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

int main() {
	int h,w;
	cin >> h >> w;
	string s[h];
	for(int i = 0;i < h;i++){
		cin >> s[i];
	}
	for(int i = 0;i < h;i++){
		for(int j = 0;j < w;j++){
			char pos = s[i][j];
			if(pos == '#'){
				cout << '#';
				continue;
			}
			int counter = 0;
			for(int k = -1;k < 2;k++){
				int row = i + k;//探す対象の行
				if(row < 0 || h <= row)continue;
				if(0 <= (j - 1) && s[row][j - 1] == '#')counter++;//1つ左の列
				if(s[row][j] == '#')counter++;//同じ行
				if(0 <= (j + 1) && s[row][j + 1] == '#')counter++;//1つ左の列
			}
			//s[i][j] = counter;
			cout << counter;
		}
		cout <<  endl;
	}
	return 0;
}

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

# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define p(s) std::cout << s << endl;

int main()
{
    int n;cin >> n;
    string str;cin >> str;
    int ret=0;
    for(int i=1;i<=n-1;i++){
        string s=str.substr(0,i);
        string t=str.substr(i,n-i);

        int res=0;
        for(char c='a';c<='z';c++){
            if(s.find(c)!=string::npos&&t.find(c)!=string::npos) res++;
        }
        ret = max(ret,res);
    }
    p(ret)
}

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

int bb(const vector <int>& v, int busca) {

	int L = 0;
	int R = v.size()-1;
	int resp = -1;

	while(L <= R) {
		int mid = (L+R) / 2;

		if(v[mid] > busca) {
			L = mid + 1;
		} else {
			resp = v[mid];
			R = mid - 1;
		}
	}

	return resp;
}

int main() {
	int n,m;
	string s;

	cin >> n >> m >> s;

	n++;

	vector <int> menor(n, -1);
	menor[n-1] = 0;

	vector <int> validos;
	validos.push_back(n-1);

	for(int i = n-2; i >= 0; i--) {
		if(s[i] == '1') continue;
		int alcance = i+m;

		int busca = bb(validos, alcance);

		if(busca == -1) s[i] = '1';
		else {
			validos.push_back(i);
			menor[i] = menor[busca] + 1;
		}
	}

	// for(auto x: menor) {
	// 	cout << x << " ";
	// }
	// cout << endl;

	int resp = menor[0];

	if(resp == -1) {
		printf("%d\n",resp );
		return 0;
	}

	int index = 0;

	while(index != n-1) {

		for(int i = 1; i <= m; i++) {
			if(menor[index+i] != -1 and menor[index+i] <= resp-1) {
				printf("%d ", i);
				index += i;
				break;
			}
		}

		resp--;
	}

	printf("\n");

	return 0;
}

Measured memory_bytes: 1528
# coding: utf-8
# Your code here!
N=int(input())

l=[0]*2*10**5#ペアを作れるか診断
k=[0]*2*10**5#ansを記録

ans=1
pre=-1
for _ in range(N):
    c=int(input())-1
    if pre==c:
        continue
    l[c]+=1
    ans+=k[c]*min(l[c]-1,1)
    k[c]=ans
    pre=c
    """
    print(c+1)
    print(l[:5],k[:5])
    print(ans)
    """
print(ans%(10**9+7))


Measured memory_bytes: 22236
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <queue>
#include <stack>
#include <climits>

using namespace std;

typedef long long ll;
#define pb push_back

#define rep(i, n) for (int i=0;i<(n);++i)
#define rep2(i, s, n) for (int i=s;i<(n);++i)
#define rev(i, n) for (int i=(n);i>0;--i)
#define INF (1e9+1e9)

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

    auto cnt = 0;
    int j;
    rep(i,10) {
        auto c = count(n.begin(), n.end(), to_string(i)[0]);
        if (c >= cnt) j = i;
        cnt = max(cnt, (int)c);
    }
    string s = to_string(j);
    s.append(2,s[0]);
    if (cnt >= 3 && n.find(s) != string::npos ) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}

Measured memory_bytes: 256
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) {
#if DEBUG
        //MyDebugger.MakeTestCase("../TextFile2.txt"); return;
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var n = int.Parse(input.ReadLine());
        List<work> list = new List<work>(n);
        for(int i=0; i<n; i++) {
            var s = input.ReadLine().Split(' ');
            list.Add(new work {
                a = long.Parse(s[0]),
                b = long.Parse(s[1]),
            });
        }

        list.Sort((x1,x2)=>{
            var l = x1.b - x2.b;
            if (l > 0) return 1;
            if (l < 0) return -1;
            return 0;
        });

        long p = 0;
        for(int i=0; i<n; i++) {
            var w = list[i];
            p += w.a;
            if (p > w.b) return "No";
        }
        return "Yes";
    }

    class work
    {
        public long a;
        public long b;
    }
}


Measured memory_bytes: 26916
#include<stdio.h>
	int main(void)
{
	int N;
	double count=0.0;
	scanf("%d", &N);
	double ary[N+1];for(int i=1;i<=N;i++){scanf("%lf", &ary[i]);}
	for(int i=1;i<=N;i++){count =count + 1/ary[i];}
	printf("%lf", 1/count);
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

//Score
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt()+sc.nextInt()+sc.nextInt()+sc.nextInt();
		int t = sc.nextInt()+sc.nextInt()+sc.nextInt()+sc.nextInt();
		System.out.println(Math.max(s, t));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
h, w = map(int, input().split())
A = ['']*h
for i in range(h):
    A[i] = input()

r = [False]*h
c = [False]*w
for i in range(h):
    for j in range(w):
        if A[i][j] == '#':
            r[i] = True
            c[j] = True

for i in range(h):
    if r[i]:
        for j in range(w):
            if c[j]:
                print(A[i][j], end='')
        print()

Measured memory_bytes: 4468
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;

const int mx = 2e5+5;
void amin(ll &u, ll v){u=min(u,v);}
void amax(ll &u, ll v){u=max(u,v);}

ll n, a, b, c, d;
unordered_map<ll,ll> m;

ll fun(ll x){
    if(x == 0) return 0;
    if(x == 1) return d;

    if(m.find(x) != m.end()) return m[x];

    ll res = LLONG_MAX, y;
    if(x < res/d) res = x*d;
    y = (x/2)*2; amin(res, (x-y)*d + a + fun(y/2));
    y = (x/3)*3; amin(res, (x-y)*d + b + fun(y/3));
    y = (x/5)*5; amin(res, (x-y)*d + c + fun(y/5));

    y = ((x+1)/2)*2; amin(res, (y-x)*d + a + fun(y/2));
    y = ((x+2)/3)*3; amin(res, (y-x)*d + b + fun(y/3));
    y = ((x+4)/5)*5; amin(res, (y-x)*d + c + fun(y/5));
    return m[x] = res;
}

void solve(){
    cin >> n >> a >> b >> c >> d;
    m.clear();
    m.reserve(mx<<2);
    cout << fun(n) << "\n";
}

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

    int tc; cin >> tc;
    while(tc--) solve();
    return 0;
}



Measured memory_bytes: 10076
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

int N;
vector<int> c(501, 0), s(501, 0), f(501, 0);

int main(void){
    
    scanf("%d", &N);
    for(int i = 0; i < N; ++i) scanf("%d %d %d", &c[i], &s[i], &f[i]);
    
    for(int i = 0; i < N - 1; ++i){
        int cnt = c[i] + s[i];
        for(int j = i + 1; j < N - 1; ++j){
            if(cnt <= s[j]) cnt += c[j] + (s[j] - cnt);
            else cnt += c[j] + ((cnt % f[j] == 0) ? 0 : f[j] - cnt % f[j]);
        }
        printf("%d\n", cnt);
    }
    printf("0\n");
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
#define pll pair<ll,ll>
#define pii pair<int32_t,int32_t>
#define loop(i,n) for(int64_t i=0; i<n; i++)
#define loop1(i,a,b) for(int64_t i=a; i<=b; i++)
#define rloop(i,n) for(int64_t i=n-1; i>=0; i--) 
#define rloop1(i,a,b) for(int64_t i=a; i>=b; i--) 
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define print(val) cout << #val << ": " << val << "\n";
#define print_c(a) cout<<#a<<": ";for(auto it=begin(a);it!=end(a);it++)cout<<*it<<" ";cout<<"\n";
#define fill(c,v) fill(begin(c),end(c),v);
template <typename T> T flip(T val) {reverse(begin(val),end(val)); return val;}

int main() {
  fast_io
  ll t=1; 
  while(t--) {
    ll n; cin >> n;
    map<string,ll> mp;
    mp["AC"] = 0;
    mp["WE"] = 0;
    mp["TLE"] = 0;
    mp["RE"] = 0;
    loop(i,n) {
      string str; cin >> str;
      mp[str]++;
    }
    cout << "AC x " << mp["AC"] << "\n";
    cout << "WA x " << mp["WA"] << "\n";
    cout << "TLE x " << mp["TLE"] << "\n";
    cout << "RE x " << mp["RE"] << "\n";
  }
}

Measured memory_bytes: 3664
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c_ = [[0 for _ in range(C)] for _ in range(3)]
for i in range(N):
  ci =list(map(int, input().split()))
  for j in range(N):
    cij = ci[j]
    c_[(i+j)%3][cij-1] += 1

cost = [[0 for _ in range(C)] for _ in range(3)]
for i in range(3):
  for j in range(C):
    for k in range(C):
      cost[i][k] += D[j][k] * c_[i][j]
      
ans = 1000*500*500
for i in range(C):
  if ans < cost[0][i]:
    continue
  for j in range(C):
    if i is j:
      continue
    if ans < (cost[0][i]+cost[1][j]):
      continue
    for k in range(C):
      if i is k or j is k:
      	continue
      ans = min(ans, cost[0][i]+cost[1][j]+cost[2][k])
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
inline int rnd(int x){
	return rand()%x;
}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
double solve(int n,double d,double x){
	if(n==0)return 0;
	double jb=d+(2*n-1)*x;
	double l=d*(2*n-1)/2/n+(d+d+x+d+x+x)/2/n,r=(jb+jb-x+jb-x-x)/2/n+jb*(2*n-1)/2/n;
	//cout<<n<<" "<<l<<" "<<r<<endl;
	return solve(n-1,l,(r-l)/(2*n-3))+(d+jb)/2;
}
int main(){
	int n=read(),d=read(),x=read();
	printf("%.9lf\n",solve(n,d,x));
}

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

int main(){
	int a,b;
	char op;
	while(1){
		cin >> a >> op >> b;
		if(op == '?')break;
		switch(op){
			case '+':
				a +=b;
				cout << a <<"\n";
				break;
			case '-':
				a -=b;
				cout << a <<"\n";
				break;
			case '/':
				a /=b;
				cout << a <<"\n";
				break;
			case '*':
				a *=b;
				cout << a <<"\n";
				break;
		}
	}
	return 0;
	

}

Measured memory_bytes: 1160
import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()

ans=0
for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    ans+=bisect.bisect_left(L,a+b)-j-1
print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

void solve(string s){

	int l = s.length();
	set<string> train;
	string one, re_one, two, re_two;

	train.insert(s);
	for(int i=1; i<l; i++){
		one = s.substr(0,i);
		re_one = one; reverse(re_one.begin(),re_one.end());
		two = s.substr(i,l-i);
		re_two = two; reverse(re_two.begin(),re_two.end());

		train.insert(one + re_two);
		train.insert(two + one);
		train.insert(re_two + one);

		train.insert(re_one + two);
		train.insert(re_one + re_two);
		train.insert(two + re_one);
		train.insert(re_two + re_one);
		
	}
	cout << train.size() << endl;
}

int main()
{
	int m;
	string s;

	cin >> m;

	for(int i=0; i<m; i++){
		cin >> s;
		solve(s);
	}

	return 0;
}

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

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

  if(n%10==7 || (n/10)%10==7 || (n/100)%10==7) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

  return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

typedef pair<int, int> pp;
typedef pair<pp, string> ppp;

int main()
{
    int sec = 0, n;
    while(cin >> n && n)
    {
        if(sec) cout << endl;
        vector<ppp> res;
        string t;
        int win, lose, even;
        REP(n)
        {
            cin >> t >> win >> lose >> even;
            res.push_back(ppp(pp(-(win * 3 + even * 1), i), t));
        }
        sort(all(res));
        REP(n) cout <<  res[i].second << "," <<-res[i].first.first << endl;
        sec = 1;
    }

    return 0;
}

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

#define debug(x) cerr << #x << " = " << x << endl

const int N_MAX = 100003;
long long a[N_MAX];
std::vector<int> g[N_MAX];

bool ans = 1;
long long dfs(int x, int fa) {
  if (g[x].size() == 1 && fa != 0) {
    return a[x];
  }
  long long val = g[x].size() > 1 ? 2 * a[x] : a[x];
  long long sum = 0, mx = 0;
  for (int y : g[x])
    if (y != fa) {
      long long temp = dfs(y, x);
      sum += temp;
      mx = max(temp, mx);
    }
  if (mx > a[x] || sum * 2 < val)
    ans = 0;
  if (fa == 0) {
    if (sum != val)
      ans = 0;
    return 0;
  }
  else {
    if (sum > val)
      ans = 0;
    return val - sum;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i];
  for (int i = 1; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y), g[y].push_back(x);
  }
  
  dfs(1, 0);
  printf(ans ? "YES\n" : "NO\n");
  return 0;
}


Measured memory_bytes: 13184
N = int( input())
A = [0]*N
B = [0]*N
S = [(0,0)]*N
for i in range(N):
    a, b = map( int, input().split())
    A[i] = a
    B[i] = b
    S[i] = (-a-b,i)
S.sort()
ansa = 0
ansb = 0
for i in range(N):
    _, j = S[i]
    if i%2 == 0:
        ansa += A[j]
    else:
        ansb += B[j]
print( ansa-ansb)


Measured memory_bytes: 24880
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, x, y, W;
ll dp[101][100001];
vector <pair <int, int> > a;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> W;
    for(int i = 0 ; i < n && cin >> x >> y ; i++)
        a.push_back(make_pair(x, y));
    dp[0][0] = 0;
    dp[0][a[0].second] = a[0].first;
    for(int i = 1 ; i < n ; i++){
        for(int j = 0 ; j <= 100000 ; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= a[i].second){
                if(dp[i - 1][j - a[i].second] != -1){
                    if(dp[i][j] == -1 || dp[i - 1][j - a[i].second] + a[i].first < dp[i][j])
                        dp[i][j] = dp[i - 1][j - a[i].second] + a[i].first;
                }
            }
        }
    }
    for(int i = 100000 ; i >= 0 ; i--)
        if(dp[n - 1][i] != -1 && dp[n - 1][i] <= W)
            finish(i);
}


Measured memory_bytes: 79232
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
const ll inf = 1001001001;

int main() {
  int n;
  cin >> n;
  vl a(n);
  int numNegative = 0;
  ll sum = 0;
  ll a_min = inf;
  rep(i,n){
    cin >> a[i];
    if(a[i] < 0) numNegative++;
    sum += abs(a[i]);
    mins(a_min,abs(a[i]));
  }
  if(numNegative % 2 == 1){
    sum-=2*a_min;
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<long long>
#define INF 1e18
 
ll modInverse(ll a, ll m);
ll gcd(ll a, ll b);
ll power(ll x, unsigned ll y, unsigned ll m);
ll logint(ll x,ll y);
 
 
ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
 
ll power(ll x, unsigned ll y, unsigned ll m)
{
    if (y == 0)
        return 1;
    ll p = power(x, y/2, m) % m;
    p = (p * p) % m;
 
    return (y%2 == 0)? p : (x * p) % m;
}
 
ll modInverse(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
 
    if (m == 1)
      return 0;
 
    while (a > 1)
    {
        // q is quotient
        ll q = a / m;
        ll t = m;
 
        // m is remainder now, process same as
        // Euclid's algo
        m = a % m, a = t;
        t = y;
 
        // Update y and x
        y = x - q * y;
        x = t;
    }
 
    // Make x positive
    if (x < 0)
       x += m0;
 
    return x;
}
 
void pairsort(ll a[],ll b[], ll n)
{
    pair<ll, ll> pairt[n];
 
    // Storing the respective array
    // elements in pairs.
    for (ll i = 0; i < n; i++)
    {
        pairt[i].first = a[i];
        pairt[i].second = b[i];
    }
 
    // Sorting the pair array.
    sort(pairt, pairt + n);
 
    // Modifying original arrays
    for (ll i = 0; i < n; i++)
    {
        a[i] = pairt[i].first;
        b[i] = pairt[i].second;
    }
}
 
ll logint(ll x,ll y)
{
    ll ans=0;
    ll a=1;
    for(ll i=0;i<x;i++)
    {
        if(x<=a)
        {
            return ans;
        }
        ans++;
        a*=y;
    }
    return -1;
}
/*
ll v[500001], size[500001];
vector<ll>ve(0);
ll fin(ll x){
    //using path compression optimization
    if(x == v[x]){
        return x;
    }
    return v[x] = fin(v[x]);
}
void uni(ll x, ll y){
    x = fin(x);
    y = fin(y);
    if(x == y){
        return ;
    }
    //Using Union by size method, to reduce long chains
    if(size[x] < size[y]){
	size[x]+= size[y];
    	v[y] = x;}
    else{
	size[y]+=size[x];
	v[x]=y;
	}
}
*/
ll dp[101][100001];
int main()
{
   // ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
 
    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */
    ll n, w;
    cin>>n>>w;
    memset(dp, 0, sizeof(dp));
    vector<pair<ll,ll> > p(0);
    REP(i, 0, n){
        ll x, y;
        cin>>x>>y;
        p.pb(mp(x, y));
    }
    sort(p.begin(), p.end());
    REP(i, 0, n){
        REP(j, 1, w+1){
            if(p[i].ff > j){dp[i+1][j] = dp[i][j];}
            else{
                dp[i+1][j] = max(dp[i][j-p[i].ff]+p[i].ss, dp[i][j]);
            }
        }
    }
    cout<<dp[n][w];
}

Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
long long n,a[305],s;
int main()
{
	cin>>n;
	for(int i=0;i<n*2;i++)
	{
		cin>>a[i];
	}
	sort(a,a+2*n);
	for(int i=0;i<n*2;i+=2)
	{
		s+=a[i];
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s;
int cnt;
int main()
{
	cin>>s;
	for(int i=0;i<s.size()-1;i++)
	{
		if(s[i]!=s[i+1])
		{
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

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

int main() {
  int a,b,c,k;
  cin >> a >> b >> c >> k;
  int ans;
  if(a >= k) ans = k;
  else if(a + b >= k) ans = a;
  else ans = a - (k - a - b);
  cout << ans << endl;
}

Measured memory_bytes: 3616
with open(0) as f:
    N, *xy = map(int, f.read().split())

from collections import namedtuple
v = namedtuple('v',['coordinate','num'])
#最小全域木に使われる辺は高々座標(xまたはy)が隣接する頂点間のものである
#したがって、x座標・y座標それぞれでソートして辺を求める
X = sorted([v(x,i) for x,i in zip(xy[::2], range(N))])
Y = sorted([v(y,i) for y,i in zip(xy[1::2], range(N))])

diffiter = lambda X:zip(X[:len(X)-1], X[1:]) #Xの1階階差差分のイテレータを返す関数
cost = lambda u,v:abs(u.coordinate - v.coordinate)
from itertools import chain
Edge = sorted([(cost(u,v), u.num, v.num) for u,v in chain(diffiter(X),diffiter(Y))])

root = namedtuple('root',['num', 'rank']) #(num_of_root, rank_of_root)
Root = [root(i,0) for i in range(N)]

def fr(i): #findRoot
    if i == Root[i].num:
        return Root[i]
    Root[i] = fr(Root[i].num)
    return Root[i]


def unionT(i, j): #unionTree
    p, q = fr(i), fr(j)
    if p.rank < q.rank:
        Root[p.num] = q
    elif p.rank > q.rank:
        Root[q.num] = p
    elif p.rank == q.rank:
        r, s = min(p, q), max(p, q)
        Root[r.num] = Root[s.num] = root(r.num, r.rank+1)
    

ans = 0
#最小全域木の大きさ算出(環状にならないように辺を小さい順に足してゆく)
for w, i, j in Edge:
    if fr(i).num == fr(j).num: #既に連結済み
        continue
    else:
        unionT(i,j)
        ans += w
print(ans)

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

int main(void){
    string s;
    cin>>s;
    if(s[2]==s[3]&&s[4]==s[5]){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
import collections
n = int(input())
A = list(map(int,input().split()))
Cou = collections.Counter(A)
Ite = list(Cou.items());Ite.sort()
ans = 0
for i in range(len(Ite)):
    num = Ite[i][0];cou = Ite[i][1]
    if i > 0 and Ite[i-1][0] == num-1:
        cou += Ite[i-1][1]
    if i < len(Ite)-1 and Ite[i+1][0] == num+1:
        cou += Ite[i+1][1]
    ans = max(ans,cou)
print(ans)

Measured memory_bytes: 16096
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
vector<ll> nums(64);
const int mod = 1000000007;
int main()
{
    int n;cin >> n;
    ll a[n+1];
    rep(i,n)cin >> a[i];
    
    rep(j,64)rep(i,n){
        if(a[i]>>j&1)nums[j]++;
    }
    ll ans = 0;
    ll keta = 1;
    rep(i,64){
        ll res = nums[i]*(n-nums[i]);
        res %= mod;
        res = (res*keta)%mod;
        keta *= 2;
        keta%= mod;

        ans = (ans+res)%mod;
    }
    
    cout << ans << endl;

    


 
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 2e5 + 7;
const ll Inf = 2e14 + 7;
int n;
int a[maxx];
ll sumk[maxx];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sumk[i] = sumk[i - 1] + a[i];
	}
	ll ans = Inf;
	for(int i = 1; i < n; i++) {
		ll tmp = sumk[n] - sumk[i];
		ll dd = abs(sumk[i] - tmp);
		ans = min(ans, dd);
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(ll)(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
ll combi(ll n,ll m) {
  ll ans=1;
  rFOR(i,n,n-m){
    ans*=i;
  }
  FOR(i,1,m+1){
    ans/=i;
  }
  return ans;
}
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll n,k;
  	ci(n>>k);
  vll A(100000);
  FOR(i,0,n){
    ll a,b;
    	ci(a>>b);
    A[a-1]+=b;
  }
  FOR(i,0,100000){
    k-=A[i];
    if(k<=0){
      co(i+1)
        break;
    }
  }
}


Measured memory_bytes: 1024
#include<stdio.h>
#define M 100000
#define IN 300000

typedef struct{
  int g,bac;
    int co;
}B;

int n,b[M];
B A[600000];

void Troo(int x);
int main(){
  int i,j;
  int a,k,cut=0;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    b[i]=IN;
  }
 
  for(i=0;i<n;i++){
    scanf("%d %d",&a,&k);
    for(j=0;j<k;j++){
      A[cut].bac=a;
       scanf("%d %d",&A[cut].g,&A[cut].co);
       cut++;
    }
  }
  Troo(cut);
  return 0;
}
void Troo(int x){
  int i;
  int f=0;
  b[0]=0;
  
  while(f !=1){
    f=1;
    for(i=0;i<x;i++){
      
      if(A[i].co+b[A[i].bac]<b[A[i].g]){
        b[A[i].g]=A[i].co+ b[A[i].bac];
        f= 0;
      }
      
    }
  }
  
  for(i=0;i<n;i++){
    printf("%d %d\n",i,b[i]);
  }

}


Measured memory_bytes: 7640
#include <stdio.h>
 int main( void ){
     int s;
     scanf("%d",&s);
     int h=s/3600;
     int m=(s-h*3600)/60;
     int x=s-(3600*h+60*m);
     printf("%d:%d:%d\n",h,m,x);
    return 0;
    }

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define fr(i,a,b) for(int i=a;i<b;i++)
#define ll long long 
#define vec vector<ll int>
#define pb push_back
using namespace std;

int main() 
{
  ll int n1,n2,n3,n4,sum{0};
  cin>>n1>>n2>>n3>>n4;
  n1=min(n1,n4); n4=n4-n1;
  sum+=n1;
  n2=min(n2,n4); n4=n4-n2;
  n3=min(n3,n4); 
  sum-=n3;
  cout<<sum;
  
   
    
}


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

int main()
{
   set<int>s;
   int n,d;
   cin>>n;
   for(int i=0;i<n;i++)
   {
       cin>>d;
       s.insert(d);
   }
   cout<<s.size();
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        Arrays.sort(a);
        long l = -1000000000000000001L;
        long r = 1000000000000000001L;
        while (l + 1 < r) {
            long m = (l + r) / 2;
            if (ok(a, m, k)) {
                l = m;
            } else {
                r = m;
            }
        }
        System.out.println(l);
    }

    // x 未満の数が k 以下
    private static boolean ok(long[] a, long x, long k) {
        long count = 0;
        for (int i = 0; i < a.length; i++) {
            int l = -1, r = a.length;
            if (a[i] < 0) {
                while (l + 1 < r) {
                    int m = (l + r) / 2;
                    if (a[m] * a[i] < x) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                count += (a.length - r);
            } else {
                while (l + 1 < r) {
                    int m = (l + r) / 2;
                    if (a[m] * a[i] < x) {
                        l = m;
                    } else {
                        r = m;
                    }
                }
                count += r;
            }
            if (a[i] * a[i] < x)
                count--;
        }
        count /= 2;
        return count < k;
    }
}


Measured memory_bytes: 88160
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B = MAP()
print((A+B)//2 if (A+B)/2 % 1 == 0 else "IMPOSSIBLE")

Measured memory_bytes: 5156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

int main(){
  string a,b,c;
  cin >> a >> b >> c;
  if(a[a.size()-1]==b[0] && b[b.size()-1]==c[0]) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;

}


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

int main()
{
    int a, b, k;
    cin >> a >> b >> k;
    int i = (a > b ? a : b);
    while(1){
        if(a%i == 0 && b%i == 0){
            k--;
            if(k == 0) break;
        }
        i--;
    }
    
    cout << i << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=45,NN=405, inf=1e17;
ll a[N],b[N],c[N],dp[N][NN+10][NN+10];
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,ma,mb;cin>>n>>ma>>mb;
    for(ll i=0;i<n;i++)cin>>a[i]>>b[i]>>c[i];
    for(ll i=0;i<=n;i++)for(ll ca=0;ca<NN+10;ca++)for(ll cb=0;cb<NN+10;cb++)dp[i][ca][cb]=inf;
    dp[0][0][0]=0;
    for(ll i=0;i<n;i++){
        for(ll ca=0;ca<NN;ca++){
            for(ll cb=0;cb<NN;cb++){
                if(dp[i][ca][cb]==inf)continue;
                dp[i+1][ca][cb]=min(dp[i+1][ca][cb],dp[i][ca][cb]);
                dp[i+1][ca+a[i]][cb+b[i]]=min(dp[i+1][ca+a[i]][cb+b[i]] , dp[i][ca][cb] + c[i]);
            }
        }
    }

    ll ans=inf;
    for(ll ca=1;ca<NN;ca++)for(ll cb=1;cb<NN;cb++)if(ca*mb==cb*ma)ans=min(ans,dp[n][ca][cb]);
    if(ans==inf)ans=-1;
    cout<<ans;
}


Measured memory_bytes: 55552
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;
char S[200000], tmp[200000];
int main()
{
	scanf("%s", S);
	int count = 1;
	int i = 1, j = 1;
	tmp[0] = S[0];
	while (S[i] != '\0') {
		tmp[j] = S[i];
		count++;
		if (tmp[j] == 'T' && tmp[j - 1] == 'S') {
			tmp[j] == 0; tmp[j - 1] = 0;
			count -= 2;
			j -= 2;
		}
		i++; j++;
	}
	printf("%d", count);
	return 0;
}

Measured memory_bytes: 512
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;// (int)3e18;
const int maxn = 500100;


int ans[maxn];
int main(){
        _
        string s; cin >> s;
        int n = sz(s);

        for(int i = 0; i<n; i++){
            if(s[i]=='<'){
                ans[i+1] = max(ans[i+1], ans[i]+1);
            }
        }

        for(int i = n-1; i>=0; i--){
            if(s[i]=='>'){
                ans[i] = max(ans[i], ans[i+1]+1);
            }
        }

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




return 0;
}



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

typedef pair<int,int> ii;
typedef pair<int, ii> II;
const int N = 200005;

int n, a[N], p[N];
ii pmin[2][N][18];
int lg[N];
priority_queue < II, vector<II>, greater<II> > seg;
bool del[N];

ii get(ii a[][18], int l, int r) {
	int k = lg[r - l + 1];
	return min(a[l][k], a[r - (1 << k) + 1][k]);
}

void add(int l, int r) {
	if (l >= r) return;
	int val = get(pmin[l % 2], l / 2, (r - 1) / 2).first;
	seg.push(II(val, ii(l, r)));
}

void solve(int l, int r, int pos) {
	// to the right: [pos + 1, r]
	int newr = get(pmin[r % 2], (pos + 1) / 2, r / 2).second;
	printf("%d %d ", a[pos], a[newr]);
	del[pos] = del[newr] = true;

	add(l, pos - 1);
	add(pos + 1, newr - 1);
	add(newr + 1, r);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", a + i), p[a[i]] = i;

	// prepare
	for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;

	for (int i = 0; i < n; ++i) {
		pmin[i % 2][i / 2][0] = make_pair(a[i], i);
	}

	for (int j = 1; j <= 17; ++j) {
		for (int i = 0; i + (1 << j) - 1 < n / 2; ++i) {
			for (int parity = 0; parity <= 1; ++parity) {
				pmin[parity][i][j] = min(pmin[parity][i][j - 1], pmin[parity][i + (1 << j - 1)][j - 1]);
			}
		}
	}

	// solve
	add(0, n - 1);

	while(!seg.empty()) {
		II top = seg.top(); seg.pop();
		int l = top.second.first, r = top.second.second, pos = p[top.first];
		solve(l, r, pos);
	}
}

Measured memory_bytes: 38392
#include <bits/stdc++.h>
using namespace std;
int NumRev(int num)
{
    int ret=0;
    while(num)
    {
        ret=ret*10+num%10;
        num/=10;    
    }
    return ret;
}
int main()
{
	int a,b,i,count=0;
	scanf("%d %d",&a,&b);
	for(i=a;i<=b;i++)
	{
		if(NumRev(i)==i)
		{
			count++;
		}
	}
	printf("%d",count);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
    public class Main{
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            while(true){
                int H = sc.nextInt();
                int W = sc.nextInt();
                if(H == 0 && W == 0){
                    break;
                }else{
                for(int h=1;h<=H;h++){
                    if(h%2==0){
                    for(int w=1;w<=W;w++){
                        if(w%2==0){
                            System.out.printf("#");
                        }else{
                            System.out.printf(".");
                        }
                    }
                    }else{
                        for(int w=1;w<=W;w++){
                            if(w%2==0){
                                System.out.printf(".");
                            }else{
                                System.out.printf("#");
                        
                            }   
                        }   
                }   
                        System.out.printf("\n"); 
                }
                    System.out.printf("\n");
            }
            
            }
            sc.close();
        
        }
    }
        
    


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

int main(){
  ll n, x, d;
  cin >> n >> x >> d;
  if(d == 0) {
    if(x == 0) cout << 1 << endl;
    else cout << n+1 << endl;
    return 0;
  }
  if(d < 0) {
    x = -x;
    d = -d;
  }
  map<ll,vector<P>> mp;
  for(ll k = 0; k <= n; k++) {
    ll l = k*x + d*k*(k-1)/2;
    ll r = l + (n*k-k*k)*d;
    ll m = (l % d + d) % d;
    l = (l-m)/d; r = (r-m)/d;
    mp[m].push_back(P(l,r));
  }
  ll ans = 0;
  for(auto p : mp) {
    sort(p.second.begin(),p.second.end());
    ll s = -INF;
    for(auto k : p.second) {
      if(k.second > s) {
        if(k.first <= s) ans += k.second - s;
        else ans += k.second - k.first + 1;
        s = k.second; 
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 22144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h,w;cin >> h >> w;
	vector<vector<int>> a(h,vector<int>(w)),b(h,vector<int>(w));
	rep(i,h) rep(j,w) cin >> a[i][j];
	rep(i,h) rep(j,w) cin >> b[i][j];
	vector<vector<bitset<15000>>> dp(h + 1, vector<bitset<15000>>(w + 1));
	dp[0][1].set(7500);
	dp[1][0].set(7500);
	rep(i,h){
		rep(j,w){
			int t = abs(a[i][j] - b[i][j]);
			dp[i + 1][j + 1] |= (dp[i + 1][j] << t) | (dp[i + 1][j] >> t) | (dp[i][j + 1] << t) | (dp[i][j + 1] >> t);
		}
	}
	int ans = 15000;
	rep(i,15000){
		if(dp[h][w][i]) ans = min(ans, abs(7500 - i));
	}
	cout << ans << endl;
}


Measured memory_bytes: 12800
h, n = map(int, input().split())

ab = []
for i in range(n):
  a, b = map(int, input().split())
  ab.append([a, b])

h_map = [-1 for _ in range(h+1)]

h_map[h] = 0
for i in range(h):
  i_map = h - i
  if h_map[i_map] == -1:
    continue
  
  for a, b in ab:
    if (i_map - a) <= 0:
      if h_map[0] != -1:
        h_map[0] = min(h_map[0], h_map[i_map]+b)
      else:
        h_map[0] = h_map[i_map] + b
    else:
      if h_map[i_map - a] != -1:
        h_map[i_map - a] = min(h_map[i_map - a], h_map[i_map]+b)
      else:
        h_map[i_map - a] = h_map[i_map]+b

print(h_map[0])

Measured memory_bytes: 43180
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int h=sc.nextInt();
			int w=sc.nextInt();
			if(h==0 && w==0) {
				break;
			}
			for(int j=0;j<w;j++) {
				System.out.print("#");
			}
			System.out.println();
			for(int i=0; i<h-2;i++) {
				System.out.print("#");
				for(int k=0;k<w-2;k++) {
					System.out.print(".");
				}
				System.out.print("#");
				System.out.println();
			}
			for(int j=0;j<w;j++) {
				System.out.print("#");
			}
			System.out.println();
			System.out.println();
		}
	}
}


Measured memory_bytes: 32692
import scala.collection.mutable.ArrayBuffer
import scala.io.StdIn.{readInt, readLine}

object Main extends App {
  val pushBack     = 0
  val randomAccess = 1
  val popBack      = 2

  val n     = readInt()
  val lines = Iterator.fill(n)(readLine())

  val orders = lines.map { _.split(" ").map { _.toInt } }
  var xs     = Vector[Int]()
  orders.foreach {
    case Array(`pushBack`, x)     => xs = xs :+ x
    case Array(`randomAccess`, x) => println(xs(x))
    case Array(`popBack`)         => xs = xs.init
  }
}



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


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

	int vn, g, en;
	while (cin >> vn >> g >> en , vn) {
		int v[4], e[51], a[51];
		double dp[51][5010][2] = {0};
		for (int i = 0; i < vn; i++) {
			cin >> v[i];
		}

		memset(e, 0, sizeof e);
		for (int i = 0; i < en; i++) {
			int n;
			cin >> n;
			cin >> e[n] >> a[n];
		}

		memset(dp, 0, sizeof dp);
		dp[0][0][0] = 1.0;

		for (int i = 0; i < g; i++) {
			for (int j = 0; j <= 5000; j++) {
				for (int skip = 0; skip <= 1; skip++) {
					if (dp[i][j][skip] == 0) continue;

					int nj = j;
					if (skip == 0) {
						if (e[i] == 1) {
							int ni = min(i + a[i], g);
							dp[ni][j][1] += dp[i][j][0];
							continue;
						}
						if (e[i] == 2) nj = j + a[i];
						if (e[i] == 3) nj = max(0, j - a[i]);
					}

					for (int k = 0; k < vn; k++) {
						int ni = min(i + v[k], g);
						dp[ni][nj][0] += dp[i][j][skip] / vn;
					}
				}
			}
		}

		double ans = 0;
		for (int j = 0; j <= 5000; j++) {
			for (int s = 0; s < 2; s++) {
				ans += j * dp[g][j][s];
			}
		}
		cout << int(ans) << endl;
	}
}

Measured memory_bytes: 5196