akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		static int num[40];
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (*num = 0; x; x /= 10) {
			num[++*num] = x % 10;
		}
		while (*num){
			putchar(num[*num] ^ '0');
			--*num;
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

const int N = 100005;

int n, m;
std::vector<std::pair<int, int>> E[N];
bool vis[N], visE[N];
std::vector<std::pair<int, int>> ans;

int dfs(int u) {
	vis[u] = 1;
	int s = 0;
	for (auto p : E[u]) {
		int v = p.first, id = p.second;
		if (!visE[id]) {
			visE[id] = 1;
			if (!vis[v]) {
				int t = dfs(v);
				if (t) {
					ans.push_back({v, u});
				} else {
					ans.push_back({u, v});
					s ^= 1;
				}
			} else {
				ans.push_back({u, v});
				s ^= 1;
			}
		}
	}
	return s;
}

int main() {
	read(n), read(m);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		read(u), read(v);
		E[u].push_back({v, i}), E[v].push_back({u, i});
	}
	if (dfs(1)) {
		print(-1);
	} else {
		for (auto v : ans) {
			print(v.first, ' '), print(v.second);
		}
	}
}


Measured memory_bytes: 21336
#include <stdio.h>
typedef unsigned long uint;

inline static uint gl(void){
    uint x = 0;
    for(;;){
        const uint c = getchar_unlocked() - 48;
        if(c < 10){
            x = x*10 + c;
        }else{
            break;
        }
    }
    return x;
}
#define H 200000
uint v[H];
int main(void){
    const uint h = gl();
    gl();
    const uint n = gl();
    for(uint i=0; i<H; i++){ v[i] = H; }
    for(uint i=0; i<n; i++){
        const uint x = gl()-1;
        const uint y = gl()-1;
        v[x] = y<v[x] ? y : v[x];
    }
    uint right = 0;
    for(uint x=1; x<h; x++){
        const auto b = v[x];
        const auto r = right+1;
        if(b<r){
            printf("%ld\n", x);
            return 0;
        }else if(b>r){
            right=r;
        }
    }
    printf("%ld\n", h);
    return 0;
}


Measured memory_bytes: 1664
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

N = iin()
h = iln()

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

dp[0] = 0

for i in range(N):
    if i+1 < N: dp[i+1] = min(dp[i+1], dp[i]+abs(h[i+1]-h[i]))
    if i+2 < N: dp[i+2] = min(dp[i+2], dp[i]+abs(h[i+2]-h[i]))
print(dp[N-1])


Measured memory_bytes: 80776
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

char mp[20+2][20+2];

int dirx[] = {1,0,-1,0};
int diry[] = {0,1,0,-1};

vector<vector<int> > done(22,vector<int>(22,0));

int bfs(int ix, int iy, int gx, int gy){
    int ans = 100000;
    queue<pair<int, int> > q;
    queue<int> qw;
    q.push(make_pair(ix,iy));
    qw.push(0);

    while(q.size() > 0){
        auto tmp = q.front();
        q.pop();
        int x = tmp.first;
        int y = tmp.second;

        int w = qw.front();
        qw.pop();

        if(done[x][y]==1) continue;

        done[x][y] = 1;
        if(x == gx && y == gy){
            ans = w;
            break;
        }

        for(int i = 0; i < 4; i++){
            if(mp[x+dirx[i]][y+diry[i]] == '.'){
                if(done[x+dirx[i]][y+diry[i]] == 0){
                    q.push(make_pair(x+dirx[i],y+diry[i]));
                    qw.push(w+1);
                }
            }
        }
    }
    return ans;
}

int main(){
    int h, w;
    cin >> h >> w;
    for(int i = 0; i < h+2; i++){
        for(int j = 0; j < w+2; j++){
            if(i == 0 || j == 0 || i == h+1 || j == w+1){
                mp[i][j] = '#';
            } else {
                cin >> mp[i][j];
            }
        }
    }
    
    int ans = 0;
    for(int sx = 1; sx < h+1; sx++){
        for(int sy = 1; sy < w+1; sy++){
            for(int gx = 1; gx < h+1; gx++){
                for(int gy = 1; gy < w+1; gy++){
                    if(sx >= gx && sy >= gy) continue;
                    if(mp[sx][sy] == '#' || mp[gx][gy] == '#') continue;
                    for(int i = 0; i < 22; i++){
                        for(int j = 0; j < 22; j++){
                            done[i][j] = 0;
                        }
                    }
                    int tmp = bfs(sx,sy,gx,gy);
                    if(tmp == 100000) continue;
                    ans = max(ans, tmp);
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3628
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T, class U> inline bool chmax(T& a,U b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class U> inline bool chmin(T& a,U b) { if (a > b) { a = b; return 1; } return 0; }
const int MAX = 220000;

int main() {
    int h, w, d;
    cin >> h >> w >> d;
    vector<vector<int>> a(h, vector<int>(w));
    map<int, pair<int, int>> mp;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
            mp[a[i][j]] = make_pair(i, j);
        }
    }
    
    long long cost[MAX];
    fill(cost, cost + MAX, 0);
    for (int i = 1; i <= h*w; i++) {
        pair<int, int> a = mp[i], b = mp[i+d];
        int c = abs(a.first - b.first) + abs(a.second - b.second);
        cost[i+d] = cost[i] + c;
    }
    
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << cost[r] - cost[l] << "\n";
    }
    return 0;
}

Measured memory_bytes: 13824
/* ********************************* JAI SAI RAM ************************************* */
//kash E C SE pahle dekha hota 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
ll P=1000000007;
ll dp[301][301][2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll i,j,k,l,m,n,o,p,q,r,t,h1,m1,h2,m2;
    string s;
    cin>>s;
    for(i=0;i<s.length();i++)
    {
        if(s[i]=='?')
        s[i]='D';
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 3744
def rec(m,i,j)
  m[i][j]=0
  rec(m,i,j+1) if j<11 and m[i][j+1]==1
  rec(m,i,j-1) if j>0 and m[i][j-1]==1
  rec(m,i+1,j) if i<11 and m[i+1][j]==1
  rec(m,i-1,j) if i>0 and m[i-1][j]==1
  return m
end
loop do
  m,c=[],0
  12.times{m<<gets.split("").map(&:to_i)}
  12.times do |i|
    12.times do |j|
      if m[i][j]==1
        m=rec(m,i,j)
        c+=1
      end
    end
  end
  p c
  break if !gets
end

Measured memory_bytes: 8792
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	int N;
	scanf("%d", &N);

	ll dp[2][3];
	dp[0][0] = 0;
	dp[0][1] = -1e18;
	dp[0][2] = -1e18;
	dp[1][0] = -1e18;
	dp[1][1] = -1e18;
	dp[1][2] = -1e18;
	int x = 0;
	int y = 1;

	rep(i, N) {
		int a;
		scanf("%d", &a);

		chmax(dp[y][1], dp[x][0]);
		dp[x][0] = dp[x][0] + a;
		chmax(dp[y][2], dp[x][1]);
		dp[x][1] = dp[x][1] + a;
		dp[x][2] = dp[x][2] + a;

		swap(x, y);
	}

	if (N % 2) {
		printf("%lld\n", max(dp[y][2], dp[x][1]));
	}
	else {
		printf("%lld\n", max(dp[y][1], dp[x][0]));
	}

	Would you please return 0;
}

Measured memory_bytes: 1704
#include <bits/stdc++.h>
#define int long long
const int MAX=1e18;
typedef std::pair<int,int> P;
using namespace std;

signed main(){
  int N;
  cin>>N;
  std::vector<int> a(N-1),b(N-1),c(N-1);
  for(int i=0;i<N-1;i++)cin>>a[i]>>b[i]>>c[i];
  std::vector<queue<P>> way(N+1);
  for(int i=0;i<N-1;i++){
    way[a[i]].push(P(b[i],c[i]));
    way[b[i]].push(P(a[i],c[i]));
  }
  int Q,K;
  cin>>Q>>K;
  std::vector<int> d(N+1,MAX);
  d[K]=0;
  queue<int> que;
  que.push(K);
  while(que.size()){
    int p=que.front();
    que.pop();
    while(way[p].size()){
      P l=way[p].front();
      way[p].pop();
      if(d[l.first]==MAX){
        d[l.first]=d[p]+l.second;
        que.push(l.first);
      }
    }
  }
  std::vector<int> x(Q),y(Q);
  for(int i=0;i<Q;i++)cin>>x[i]>>y[i];
  for(int i=0;i<Q;i++){
    cout<<d[x[i]]+d[y[i]]<<endl;
  }
}


Measured memory_bytes: 74112
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0211
{
    public class Program

    {
        public static void Main(string[] args)
        {

            while (true)
            {
                int n = RInt();
                if (n == 0) break;

                long[] d = new long[n];
                long[] v = new long[n];

                long lcm = 1;
                long gcd = 0;
                for (int i = 0; i < n; i++)
                {
                    long[] items = RLongAr();
                    long g = Gcd(items[0], items[1]);
                    d[i] = items[0] / g;
                    v[i] = items[1] / g;
                    gcd = Gcd(gcd, v[i]);
                    lcm = Lcm(lcm, d[i]);                  
                }

                for (int i = 0; i < n; i++)
                {
                    Console.WriteLine(lcm / d[i] * v[i] / gcd);
                }

            }
        }

        /// <summary>
        ///最小公倍数
        /// </summary>
        public static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }

        /// <summary>
        ///最大公約数
        /// </summary>
        public static long Gcd(long a, long b)
        {
            if (a < b) return Gcd(b, a);  // 引数を入替えて自分を呼び出す
            if (b == 0) return a; //一方が0の場合は、もう片方の数自身がGCD

            long d = 0;
            do
            {
                d = a % b;
                a = b;
                b = d;
            } while (d != 0);
            return a;
        }

        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RStAr(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }

}



Measured memory_bytes: 17920
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int INF = 1000000000;
const long INF64 = 1000000000000000ll;
const int MOD = 1000000007;
int main(){
	int n,m;
	std::cin >> n;
	std::vector<int> t(n);
	rep(i,n)std::cin >> t[i];
	std::cin >> m;
	std::vector<int> p(m),x(m);
	rep(i,m)std::cin >> p[i]>>x[i];
	rep(i,m){
		int su=0;
		rep(j,n){
			if(j==p[i]-1)su+=x[i];
			else su+=t[j];
			
		}
		std::cout << su << std::endl;
	}
}


Measured memory_bytes: 256
# input
A = []
A_append = A.append
for i in range(3):
    An = list(map(int, input().split()))
    A_append(An)

N = int(input())

b = []
append = b.append
for i in range(N):
    bn = int(input())
    append(bn)

# check

marker = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

bingo_fl = False
for i in b:
    for n, An in enumerate(A):

        if i in An:
            m = An.index(i)

            marker[n][m] = 1

            break

if (
        [1, 1, 1] in [marker[i][:] for i in range(3)] or
        [1, 1, 1] in [[marker[0][i], marker[1][i], marker[2][i]] for i in range(3)] or
        [1, 1, 1] == [marker[0][0], marker[1][1], marker[2][2]] or
        [1, 1, 1] == [marker[0][2], marker[1][1], marker[2][0]]
):
    bingo_fl = True

if bingo_fl is True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    private int count;

    public Main() {
        this.count = 0;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = in.nextInt();
        }
        Main test = new Main();
        test.mergeSort(num, 0, n);

        for (int i = 0; i < n; i++) {
            System.out.print(num[i]);
            if (i != n - 1) {
                System.out.print(" ");
            } else {
                System.out.println();
            }
        }
        System.out.println(test.count);
    }

    public void merge(int[] num, int left, int mid, int right) {
        int n1 = mid - left;
        int n2 = right - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = num[left + i];
        }
        for (int i = 0; i < n2; i++) {
            R[i] = num[mid + i];
        }
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            count++;
            if (L[i] <= R[j]) {
                num[k++] = L[i++];
            } else {
                num[k++] = R[j++];
            }
        }
        while (i < n1) {
            count++;
            num[k++] = L[i++];
        }
        while (j < n2) {
            count++;
            num[k++] = R[j++];
        }
//        for (int k = left; k < right; k++) {
//            count ++;
//            if (L[i] <= R[j]) {
//                num[k] = L[i++];
//            } else {
//                num[k] = R[j++];
//            }
//        }

    }

    public void mergeSort(int[] num, int left, int right) {
        if (left + 1 < right) {
            int mid = (left + right) / 2;
            mergeSort(num, left, mid);
            mergeSort(num, mid, right);
            merge(num, left, mid, right);
        }
    }
}



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

int main() {
	int n; cin >> n;
	vector<int> a(n);
   	for(int i = 0; i < n; i++) cin >> a[i];
	
	int rst = 0;
	bool f = true;
	while(f) {
		for(int i = 0; i < n; i++) {
			if(a[i] % 2 == 0) {
				a[i] /= 2;
			} else {
				f = false;
				rst--;
				break;
			}
		}
		rst++;
	}

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <string.h>

using namespace std;
typedef pair<int, int> P;


void solve()
{
	int N, M, C;
	cin >> N >> M >> C;
	vector<int> B(M);
	for (int i = 0; i < M; ++i)
	{
		cin >> B[i];
	}
	int ans = 0;
	for (int i = 0; i < N; ++i)
	{
		vector<int> A(M);
		for (int j = 0; j < M; ++j)
		{
			cin >> A[j];
		}
		int sum = 0;
		for (int j = 0; j < M; ++j)
		{
			sum += A[j] * B[j];
		}
		sum += C;
		if (sum > 0)
		{
			++ans;
		}
	}
	cout << ans << endl;
}

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

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	long long n,s,a;
	int i;
	scanf("%d",&n);
	s=0;
	for(i=1;i<=32000;i++){
		a=i*i;
		if(a<=n){
			if(a>s){
				s=a;
			}
		}
	}
	printf("%d\n",s);
    return 0;
}

Measured memory_bytes: 128
N=int(input())
a= list(map(int, input().split()))
s=[0]*N
s[0]=a[0]
for i in range(1,N):
    s[i]=s[i-1]+a[i]
#print(s)
kake=0
ans=0
sum=0
anskai=0
for i in range(N):
    kake=s[N-1]-s[i]
    ans=a[i]*kake
    sum+=ans
anskai=sum%(10**9+7)
print(anskai)

Measured memory_bytes: 31612
# print("Input n")
n = int(input())

# print("Input the heights of the n stones")
a = [int(x) for x in input().split()]

# So that dp[n-1] will give the answer
dp = [0 for i in range(n)]

dp[0] = 0                  # The starting stone
dp[1] = abs(a[1] - a[0])   # Only one possibility
for i in range(2,len(dp)):
    # One hop from the previous one
    possibilityone = dp[i-1] + abs(a[i]-a[i-1])
    # A double hop from the one two before
    possibilitytwo = dp[i-2] + abs(a[i]-a[i-2])
    dp[i] = min(possibilityone, possibilitytwo)


print(dp[n-1])


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

double pow_list[20] = {1.};

int main()
{
  int N, K;
  cin >> N >> K;
  
  for (int i = 1; i < 20; i++) {
    pow_list[i] = pow_list[i-1]* 0.5;
  }
  
  double ans = 0;
  for (int i = 1; i <= N; i++) {
    int point = i;
    int loop = 0;
    while (point < K) {
      point *= 2;
      loop++;
    }
    ans += pow_list[loop];
  }
  ans *= (1./N);
  cout << setprecision(20) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int N,C[50],V[50],i,MAX=0;
	scanf("%d",&N);
	for(i=0;i<N;i++)
		scanf("%d",&V[i]);
	for(i=0;i<N;i++)
		scanf("%d",&C[i]);
	for(i=0;i<N;i++)
	{
		if(V[i]>C[i])
			MAX+=V[i]-C[i];
	}
	printf("%d",MAX);
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <limits.h>
#include <bitset>
#include <math.h>
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
const int MOD = 10007;
const int INF = LLONG_MAX/3;
const int MAX = 710000;

/*-----Library-----*/

struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
    vector<int> sizeuf; //要素数
    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n); rank.resize(n); sizeuf.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            rank[i] = 0;
            sizeuf[i]=1;
        }
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        sizeuf[x]+=sizeuf[y];
        return true;
    }

    int size(int x){
        return sizeuf[root(x)];
    }
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}

long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}

long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*-----Library-----*/
signed main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]+n<='Z')cout<<(char)(s[i]+n);
        else cout<<(char)('A'+(n-('Z'-s[i]))-1);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

signed main(){
    
   int a, b, c; cin >> a >> b >> c;
   int rest = a - b;
   cout << max(0LL, c - rest) << endl;   
    return 0;
}


Measured memory_bytes: 256
#if 1

#include <bits/stdc++.h>
using namespace std;
int r,d,c;

int main()
{
    cin >> r >> d >> c;
    for(int i = 2001;i <= 2010;i++)
    {
        cout << r*c-d << '\n';
        c = r*c-d;
    }
}

#endif // 1++


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int M, D;

int main() {
	cin >> M >> D;
	int ans = 0;
	for (int i = 1; i <= M; i++) {
		for (int d = 22; d <= D; d++) {
			int d1 = (d % 10);
			int d10 = (d - d1)/10;
			if (d1 >= 2 && d10 >= 2 && d1*d10 == i) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n,k;
    cin >> n >> k;
    int vis[n+1]={0};
    for(int i=0;i<k;i++){
    	int d;
    	cin >> d;
    	for(int j=0;j<d;j++){
    		int x;
    		cin >> x;
    		vis[x]=1;
    	}
    }
    int ans=0;
    for(int i=1;i<=n;i++){
    	if(!vis[i])ans++;
    }
    cout << ans;
}

Measured memory_bytes: 3644
#include<stdio.h>

int main(void){
  char a,b,c,d;

  scanf("%c%c%c%c",&a,&b,&c,&d);

  if((a==b)&&(c==d)){
    if(a!=c){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }
  else if((a==c)&&(b==d)){
    if(a!=b){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }
  else if((a==d)&&(b==c)){
    if(a!=b){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }
  else {
    printf("No\n");
  }

  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <limits.h>

static long long diff(long long A, long long B, long long C);

int main(int argc, char *argv[])
{
	long long H, W, i, j, k, d, min = LLONG_MAX;
	scanf("%lld %lld", &H, &W);

	/* 試すパターンは4 */
	if ( W%3 == 0 || H%3 == 0 ){
		printf("0\n");
		return 0;
	}

	/* 縦分割 */
	if ( W>3 ){
		if ( min > H ){
			min = H;
		}
	}
	/* 横分割 */
	if ( H>3 ){
		if ( min > W ){
			min = W;
		}
	}
	for ( i = 1; i < W; i++ ){
		j = H/2;
		k = H%2==0?j:j+1;
		d = diff(i*H, j*(W-i), k*(W-i));
		if ( min > d ){
			min = d;
		}
	}
	for ( i = 1; i < H; i++ ){
		j = W/2;
		k = W%2==0?j:j+1;
		d = diff(i*W, j*(H-i), k*(H-i));
		if ( min > d ){
			min = d;
		}
	}
	printf("%lld\n", min);

	return 0;
}

static long long diff(long long A, long long B, long long C)
{
	long long max, min;
	if ( A >= B && A >= C ){
		max = A;
	} else if ( B >= A && B >= C ){
		max = B;
	} else {
		max = C;
	}
	if ( A <= B && A <= C ){
		min = A;
	} else if ( B <= A && B <= C ){
		min = B;
	} else {
		min = C;
	}
	return max - min;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(){
  int N,S=0;
  scanf("%d",&N);
  int V[30],C[30];
  for(int i=1;i<=N;i++)
    scanf("%d",V+i);
  for(int i=1;i<=N;i++){
    scanf("%d",C+i);
    C[i]=V[i]-C[i];
    if(C[i]>0) S+=C[i];
  }
  printf("%d\n",S);
  return 0;
}

Measured memory_bytes: 1712
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
	Scanner scan = new Scanner(System.in);
	int n = Integer.parseInt(scan.nextLine());
	int cnt = 0;
        for (int i = 0; i < n; i++) {
	    int a = Integer.parseInt(scan.nextLine());
	    if (isPrime(a)) {
		cnt++;
	    }
	}
	System.out.println(cnt);
    }
    public static boolean isPrime(int a){
	if (a == 2) {
	    return true;
	}
	if (a % 2 == 0) {
	    return false;
	}
	for (int i = 3; i <= Math.sqrt(a); i++) {
	    if (a % i == 0) {
		return false;
	    }
	}
	return true;
    }
}

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

const int N = 100000;

int n, p;
int pre[N+1];

int find(int x)
{
    while (x != pre[x])
        x = pre[x];
    return x;
}

int main(void)
{
    while (scanf("%d%d", &n, &p) != EOF) {
        if (!n && !p) break;
        pre[1] = 1;
        for (int i = 2; i <= n; i ++)
            scanf("%d", &pre[i]);
        long long sum = 0;
        for (int i = 1; i <= p; i ++) {
            char s[2];
            int x;
            scanf("%s%d", s, &x);
            if (s[0] == 'M')
                pre[x] = x;
            else
                sum += find(x);
        }
        printf("%lld\n", sum);
    }

    return 0;
}

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

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

  int n, x;
  cin >> n >> x;

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

  sort(a, a+n);
  int cnt = 0;

  for (int i = 0; i < n; ++i) {
    if (x - a[i] < 0) break;
    else x -= a[i];

    ++cnt;
  }

  if (cnt == n) {
    if (x > 0) cout << n-1 << '\n';
    else cout << n << '\n';
  } else cout << cnt << '\n';

  return (0);
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  int n;
  cin >> n;
  vector<int> a(n);
  REP(i, n) cin >> a[i];
  sort(ALLr(a));
  int ans = 0;
  REP(i, n){
    if(i%2 == 0) ans += a[i];
    else ans -= a[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main() {
	int N,i,j,ans=0,H[100000],count=0;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &H[i]);
	}
	for (i = 0; i < N-1; i++) {
		count += 1;
			if (H[i] < H[i+1]) {
				if (ans < count-1) 
					ans = count-1;
					count = 0;
			}
			if (i == N - 2)
			{
				if (H[i - 1] >= H[i]) {
					if (ans < count)
						ans = count;
				}
			}
		}
	printf("%d", ans);
	return 0;
}






Measured memory_bytes: 512
'use strict'

let S;

function myShift(i){
    let c=S[i];
    let count=0;
    let l = S.length;
    while(c===S[i] && i<l){
        count++;
        i++;
    }
    return count;
}

function Main(input) {
    let temp = input.trim().split('\n');
    let N = parseInt(temp[0].split(' ')[0]);
    let K = parseInt(temp[0].split(' ')[1]);
    S = temp[1];
    
    //console.log(N,K,S);
    let i=0;
    let count;
    let que=[];
    let sum=0;
    let max=0;
    let obj = {};

    if(N<=K){
        console.log(N);
        return;
    }

    //先頭が'1'だったらqueにいれておく。合計も足しておく
    if(S[0]==='1'){
        count = myShift(0);
        que.push({type:'1',count:count});
        sum += count;
        i += count;
        max = count;
        //console.log('start1:',count);
    }


    //足せるところまで0と次の1を足す。
    while(i<N){
        if(S[i]==='0'){
            K--;
            if(K<0){
                obj = que.shift();
                sum -= obj.count;
                K++;
                if(obj.type==='1'){
                    obj = que.shift();
                    sum -= obj.count;
                }
            }
        }
        //次を足す
        count = myShift(i);
        que.push({type:S[i],count:count});
        sum += count;
        i += count;
        max = Math.max(sum,max);
        //console.log('[',S[i-count],']','count:',count,' sum:',sum,' i:',i,' K:',K,' max:',max,' que:',que);
    }        

    console.log(max);

}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 16960
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

/*#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;*/

int n;
ll a[2010];
pll p[2010];

ll dp[2010][2010];
bool memo[2010][2010];
ll f(int x, int y)
{
    if(x == y) return p[n].F * abs(p[n].S - x);
    if(memo[x][y]) return dp[x][y];
    ll ans = 0;
    ll pos = p[n - (y - x)].S;
    ll val = p[n - (y - x)].F;
    ans = max(ans, val * abs(pos - x) + f(x+1, y));
    ans = max(ans, val * abs(pos - y) + f(x, y-1));
    memo[x][y] = 1;
    dp[x][y] = ans;
    return ans;
}

int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    cin >> n;
    Forn(i, n)
    {
        cin >> a[i];
        p[i] = mp(a[i], i);
    }
    sort(p+1, p+1+n, greater<pll>());
    cout << f(1, n) << endl;
}


Measured memory_bytes: 30372
//Zory-2020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define Debug printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define debug(x) cerr<<#x<<'='<<x<<endl
#define mem(x,val) memset(x,val,sizeof x)
namespace mine
{
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T>inline bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
    template<typename T>inline bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
    bool IN(ll x,ll l,ll r){return l<=x and x<=r;}

    const int INF=0x3f3f3f3f;
    const int MOD=1e9+7;
    int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
    ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e5+10;

    set<int> a;typedef set<int>::iterator IT;
    int n,b[N],ban[N],deg[N];
    bool dfs(int lst)
    {
        if(!sz(a)) return 1;
        // fo(i,1,n-sz(a)) write1(b[i]);puts("");
        for(IT it=a.begin();it!=a.end();)
        {
            int nxt=*it;if(nxt==ban[lst]) {++it;continue;}
            b[n-sz(a)+1]=nxt;a.erase(nxt);deg[ban[nxt]]--;
            if((sz(a)-1!=deg[ban[nxt]] or !a.count(ban[nxt])) and dfs(nxt)) return 1;
            it=a.upper_bound(nxt);a.insert(nxt);deg[ban[nxt]]++;
        }return 0;
    }
    void main()
	{
        n=qread();fo(i,1,n) a.insert(i),deg[ban[i]=qread()]++;
        if(!dfs(0)) puts("-1"); else fo(i,1,n) write1(b[i]);
	}
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 12928
N = int(input())
W = list(map(int, input().split()))

WSum = sum(W)

min = 99999
partSum = 0

for i in range(N) :
    partSum += W[i]
    if abs(2*partSum - WSum) < min :
        min = abs(2*partSum - WSum)

print(min)


Measured memory_bytes: 3060
#include<stdio.h>
int main(){
    int n,a,b;
    scanf("%d",&n);
    if(n==1){
        printf("Hello World\n");
    }
    if(n==2){
        scanf("%d %d",&a,&b);
        printf("%d\n",a+b);
    }
    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main(void){
	char s[101] = {'\0'};
	scanf("%s", s);
	int i = 0;
	while(1){
		printf("x");
		if(s[i+1] == '\0'){
			break;
		}
		i++;
	}
	printf("\n");
	return 0;
}


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

int main(){
	vector<int> x;
	for(int i=2;i<=1000000;i*=2)x.push_back(i);

	int n;	cin>>n;
	int ans=2;
	for(int a:x){
		if(n>=a)ans=a;
	}

	cout<<ans<<endl;




	return 0;
}



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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, A;
  cin >> N >> A;
  cout << N * N - A << endl;
  return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
//No change above here

const ll maxi = 2 * 1e5 + 5;
ll mod = 5;
double pi = 3.141592653589793238;

//function for power
ll power(ll x, ll n) {
	ll res = 1;
	x %= mod;
	while (n) {
		if (n & 1)
			res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}

ll sum_digits(ll n)
{
	ll ret = 0;
	while (n)
	{
		ret += n % 10;
		n /= 10;
	}
	return ret;
}

ll gcd(ll a, ll b)
{
	if (a == 0)
		return b;
	else
		return gcd(b % a, a);
}

ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}

ll max_subarray(vector<int>& v)
{
	if (v.empty())
		return 0;
	ll glob = v[0], loc = v[0];
	for (int i = 1; i < v.size(); ++i)
	{
		loc = max(v[i] + 0LL, loc + v[i]);
		glob = max(loc, glob);
	}
	return glob;
}

long long num_digits(long long x)
{
	long long ans = 0;
	while (x)
	{
		++ans;
		x /= 10;
	}
	return ans == 0 ? 1 : ans;
}

vector<int> topological_sort(vector<vector<int>>& graph, int n, vector<int>& indegree)
{
	vector<int> ans;
	stack<int> s;
	for (int i = 0; i < n; ++i)
		if (indegree[i] == 0)
			s.push(i);
	while (!s.empty())
	{
		int x = s.top();
		s.pop();
		ans.push_back(x);
		for (auto& adj : graph[x])
			if (--indegree[adj] == 0)
				s.push(adj);
	}
	return ans;
}

ll dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

ll p, q;
bool valid(ll i, ll j) { return i >= 1 && i <= p && j >= 1 && j <= q; }


//declare needed things here

int main()
{
	IOS;
	ll n;
	cin >> n;
	vector<ll> v(n);
	ll ans = 0, max_ele = 0;
	cin >> v[0];
	max_ele = v[0];
	for (int i = 1; i < n; ++i)
	{
		cin >> v[i];
		if (v[i] < max_ele)
		{
			ans += max_ele - v[i];
		}
		max_ele = max(max_ele, v[i]);
	}
	cout << ans << endl;
	return 0;
}


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

using namespace std;

inline void quit(){ exit(0); }

typedef long long ll;

ll mpow(ll _x, ll _y, ll _mod){
    if(_y==0) return 1;
    if(_y==1) return _x%_mod;
    if(_y&1) return (mpow(_x, _y-1, _mod)*_x)%_mod;
    ll _tmp = mpow(_x, _y>>1, _mod);
    return (_tmp*_tmp)%_mod;
}

int n;
int k;
int arr[1<<18];
multiset<int, greater<int> > st;
vector<int> v;
multiset<int, greater<int> >::iterator it;
vector<int> tv;

int main(){
    scanf("%d", &n);
    k=1<<n;
    for(int i=0; i<k; i++){
        scanf("%d", &arr[i]);
    }

    sort(arr, arr+k);
    reverse(arr, arr+k);

    for(int i=1; i<k; i++) st.insert(arr[i]);
    v.push_back(arr[0]);
    for(int d=0; d<n; d++){
        for(auto &j: v){
            it = st.lower_bound(j-1);
            if(it == st.end()){
                printf("No");
                quit();
            }
            tv.push_back(*it);
            st.erase(it);
        }
        for(auto &j: tv) v.push_back(j);
        tv.clear();
    }
    printf("Yes");
}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    ll ans = 0;
    int pre = a[0];
    for (int i = 1; i < n; i++) {
        if (pre > a[i]) {
            ans += pre - a[i];
            a[i] = pre;
        }
        pre = a[i];
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 4040
n = int(input())
x = input()
t = int(x, 2)
c = x.count('1')
a = t % -~c
b = 0 if c < 2 else t % ~-c
for i in range(n):
    if int(x[i]):
        if c < 2:
            print(0)
            continue
        else:
            t = (b-pow(2, n-i-1, c-1)) % ~-c
    else:
        t = (a+pow(2, n-i-1, c+1)) % -~c
    z = 1
    while t:
        d = bin(t).count('1')
        t %= d
        z += 1
    print(z)

Measured memory_bytes: 9472
#include <iostream>

int main()
{
    int D;
    std::cin >> D;
    std::cout << "Christmas";
    if (D < 25) std::cout << " Eve";
    if (D < 24) std::cout << " Eve";
    if (D < 23) std::cout << " Eve";
    std::cout << std::endl;
}


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

#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 2e5+25;
int n,m,u,v,cnt,head[maxn],a[maxn],c[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
inline void add(int u,int v){
    e[++cnt] = (edge){v,head[u]};
    head[u] = cnt;
}
inline int getid(int x){
    return upper_bound(c+1,c+m,x) - c - 1;
}
int dp[maxn],val[maxn],tr[maxn<<2];
void query(int l,int r,int L,int R,int x,int &Max){
    if(l > R || r < L) return ;
    if(l >= L && r <= R){
        Max = max(Max,tr[x]);
        return;
    }
    int mid = (l+r) >> 1;
    query(l,mid,L,R,x<<1,Max);
    query(mid+1,r,L,R,x<<1|1,Max);
}
void updata(int l,int r,int L,int R,int x,int v){
    if(l > R || r < L) return ;
    if(l >= L && r <= R){
        tr[x] = v;
        return;
    }
    int mid = (l+r) >> 1;
    updata(l,mid,L,R,x<<1,v);
    updata(mid+1,r,L,R,x<<1|1,v);
    tr[x] = max(tr[x<<1],tr[x<<1|1]);
}
void dfs(int x,int fa){
    int id = getid(a[x]), Max = 0;
    query(1,m,id,id,1,val[x]);
    query(1,m,1,id-1,1,Max);
    dp[x] = max(dp[fa],Max+1);
    updata(1,m,id,id,1,Max+1);
    for(int i = head[x];i > 0;i=e[i].nxt){
        int v = e[i].to; if(v==fa) continue;
        dfs(v,x);
    }
    updata(1,m,id,id,1,val[x]);
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n; ++i){
        scanf("%d",a+i);
        c[i] = a[i];
    }
    for(int i = 1;i < n; ++i){
        scanf("%d %d",&u,&v);
        add(u,v); add(v,u);
    }
    sort(c+1,c+n+1);
    m = unique(c+1,c+n+1) - c;
    dfs(1,0);
    for(int i = 1;i <= n; ++i) printf("%d\n",dp[i]);
    return 0;
}

Measured memory_bytes: 25032
h,w= map(int,input().split())
l = list()
m = 0
for i in range(h):
  c = input()
  if "#" in c:
    b = [ w for w in range(len(c)) if c[w] == "#" ]
    l.append(b)
    if m < max(b) : m = max(b)
p = list()
for i in range(m) :
  for j in l:
    if i in j: break
  else:
    p.append(i)
for j in range(len(l)):
  for e in range(len(l[j])):
    cnt = 0
    for q in p:
      if l[j][e] > q : cnt += 1
    l[j][e]  = l[j][e]  - cnt
m = 0
for i in l:
  if m < max(i) : m = max(i)
for i in l:
  t = ""
  for j in range(m+1):
    if j in i : t = t + "#"
    else: t = t + "."
  print(t)

Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MOD = 1e9+7;
using ll = long long;
using vi = vector<int>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(x) x.begin(), x.end();
int main() {
  int a,ans=0,MAX=0;
  cin >> a;
  int b[a];
  rep(i,a){
    cin >> b[i];
    if(b[i]>=MAX){
      MAX = b[i];
      ans++;
    }
  }
  cout << ans;
}

Measured memory_bytes: 3620
n = int(input())
testimonies = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        x -= 1
        testimonies[i].append((x, y))

to_bit = [1 << i for i in range(n)]
from_bit = {1 << i: i for i in range(n)}
ans = 0
for check in range(1 << n):
    b = check
    flag = True
    while b:
        bit = b & -b
        i = from_bit[bit]
        for x, y in testimonies[i]:
            if (check >> x) & 1 != y:
                flag = False
                break
        if not flag:
            break
        b ^= bit

    if flag:
        ans = max(ans, bin(check).count('1'))

print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
#define N 100
int main() {
	int n, m, i, j, k, l, a;
	int m1[N][N], m2[N];
	
	scanf ( "%d", &n );
	for ( i = 0; i < n; i++ ) {
		scanf ( "%d %d", &m2[i], &m );
	}
	m2[n] = m;
	
	
	for ( i = 1; i < n + 1;  i++ ) {
		m1[i][i] = 0;
	}
	
	for ( l = 2; l < n + 1; l++ ) {
		for ( i = 1; i < n - l + 2; i++ ) {
			j = i + l - 1;
			m1[i][j] = 10000000;
			for ( k = i; k <= j - 1; k++ ) {
				a = ( m1[i][k] + m1[k + 1][j] + m2[i - 1] * m2[k] * m2[j] );
				if (m1[i][j] > a ) {
					m1[i][j] = a;
				}
			}
		}
	}
	
	printf ( "%d\n", m1[1][n] );
	return 0;
}


Measured memory_bytes: 2100
import copy

sx, sy, tx, ty = map(int, input().split())
p = [sx, sy]
g = []
b = []

for _ in range(1,tx - sx):
    g.append('R')
    b.append('L')
for _ in range(1,ty - sy):
    g.append('U')
    b.append('D')

b.reverse()

g1 = g
g1.insert(0,'R')
g1.append('U')
g2 = copy.deepcopy(g1)
g2.insert(0,'R')
g2.insert(0,'D')
g2.append('U')
g2.append('L')
b1 = b
b1.insert(0,'L')
b1.append('D')
b2 = copy.deepcopy(b1)
b2.insert(0,'L')
b2.insert(0,'U')
b2.append('D')
b2.append('R')

ans = []
ans.extend(g1)
ans.extend(b1)
ans.extend(g2)
ans.extend(b2)
ans = ''.join(ans)
print(ans)

Measured memory_bytes: 3700
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
AA = inpl()
BB = inpl()
CC = inpl()

ans = sum(BB)
for i in range(N-1):
    if AA[i+1] == AA[i]+1:
        ans += CC[AA[i]-1]

print(ans)


Measured memory_bytes: 4328
#include <bits/stdc++.h>
#include<cmath>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Graph vector<vector<int>>
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = (1LL << 60LL);

int main(){
    int N,R;
    cin>>N>>R;
    int naibu;
    if(N<10){
        naibu=R+100*(10-N);
    }
    else{
        naibu=R;
    }
    cout<<naibu;
}


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

using namespace std;

int n;
vector<int> v;

void swap(int &a, int &b){
	int tmp = a;
	a = b;
	b = tmp;
}

int SelectionSort(){
	if(n == 1) return 0;
	int cnt = 0, minv;
	int num;
	for(int i=0;i < n;++i){
		minv = 100;
		for(int j=i+1;j < n;++j){
			if(v[j] < minv){
				num = j;
				minv = v[j];
			}
		}
		if(v[i] > v[num]){
			swap(v[i], v[num]);
			cnt++;
		}
	}
	return cnt;
}

int main(){
	cin >> n;
	int vin;
	for(int i=0; i<n; ++i){
		cin >> vin;
		v.push_back(vin);
	}

	int ans = SelectionSort();
	for(int k=0;k < n;++k){
		cout << v[k];
		if(k != n-1) cout << " ";
	}
	cout <<endl;
	cout << ans << endl;

	return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll X[5];
    REP(i, 5) {
        cin >> X[i];
    }
    REP(i, 5) {
        if (X[i] == 0) {
            cout << i + 1 << endl;
            break;
        }
    }
    return 0;
}

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

int main() {
    int N;cin >> N;
    ll A[N] = {};ll B[N] = {};ll C[N] = {};ll D[N] = {};
    for (int i = 0;i < N;i++){
        cin >> A[i];
        B[A[i] - 1]++;
    }
    ll sum = 0;
    for (int i = 0;i < N;i++){
        ll n = B[i];
        if (n >= 2) {
            C[i] = n * (n - 1) / 2;
            sum += C[i];
            if (n == 2) D[i] = 0;
            else D[i] = (n - 1) * (n - 2) / 2;
        }
        else{
            C[i] = 0;
            D[i] = 0;
        }
    }
    for (int i = 0;i < N;i++){
        cout << sum - C[A[i] - 1] + D[A[i] - 1] << endl;
    }
}

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

int main()
{

    int N;
    cin >> N;

    vector<int> D(N);

    for (int i = 0; i < N; ++i){
        cin >> D[i];
    }
    sort(D.begin(), D.end());

    int ans = 0;
    if (N % 2 != 0)
    {
        cout << ans << endl;
    }else{
        ans = D[N / 2] - D[N / 2 - 1];
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(){
	string str;
	cin>>str;
	int len=str.length();
	int num=len/2;
	int count=0;
	for(int i=0;i<len;i++){
		if(str[i]=='p'){
			count++;
		}
	}
	cout<<num-count<<endl; 
	return 0;
}

Measured memory_bytes: 512