akhauriyash/Code-Regression huggingface dataset:
import numpy as np

N = int(input())
A = sorted(list(map(int, input().split())))

if len(A)%2 == 0:
    result = (2**(len(A)//2))%(10**9+7)
    a = np.arange(1, len(A), 2).tolist()
    a = sorted(a+a)
    if a == A:
        pass
    else:
        result = 0
else:
    result = 2**(len(A)//2)%(10**9+7)
    a = np.arange(2, len(A), 2).tolist()
    a = sorted([0]+a+a)
    if a == A:
        pass
    else:
        result = 0
print(result)

Measured memory_bytes: 23380
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		long N = scn.nextLong();
		long M = scn.nextLong();
		long ans = 0;
		if(2 * N > M) {
			ans = M/2;
		}else {
			ans +=N;
			M-=2*N;
			ans += M/4;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 21332
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while (!(line = br.readLine()).equals("0")) {
            String[] lines = br.readLine().split(" ");
            double[] list = new double[lines.length];
            int n = lines.length;
            double total = 0.0; //????¨????
            double average = 0.0; //?????????
            double var = 0.0; //?????£
            while (n-- > 0) {
                list[n] = Double.parseDouble(lines[n]);
                total+=list[n];
            }
            n=lines.length;
            average=total/n;
            for(int i=0;i<n;i++){
                var+=((list[i]-average)*(list[i]-average));
            }
            System.out.printf("%f\n",Math.sqrt(var/n));
        }
    }
}


Measured memory_bytes: 26464
import std.stdio;
import std.ascii;
import std.conv;
import std.string;
import std.algorithm;
import std.range;
import std.functional;
import std.math;
import core.bitop;
import std.numeric;

alias lread = () => readln.chomp.to!long;
alias aryread = () => readln.split.to!(long[]);

void main()
{
    auto nx = aryread();
    long N = nx[0];
    long X = nx[1];
    auto x = aryread().array;

    x.map!(a => abs(a - X))
        .reduce!((a, b) => gcd(a, b))
        .writeln;
}


Measured memory_bytes: 6068
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}
	
	public void solve() throws NumberFormatException, IOException {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(sc.readLine());
		String str = sc.readLine();
		int q = Integer.parseInt(sc.readLine());
		
		SegTree segTree = new SegTree(str);
		
		for(int i = 0; i < q; i++) {
			String[] queryArr = sc.readLine().split(" ");
			int queryNo = Integer.parseInt(queryArr[0]);
			if(queryNo == 1) {
				int pos = Integer.parseInt(queryArr[1]) - 1;
				char val = queryArr[2].charAt(0);
				segTree.update(val, pos);
			}else if(queryNo == 2){
				
				int left = Integer.parseInt(queryArr[1]) - 1;
				int right = Integer.parseInt(queryArr[2]);
				
				System.out.println(testBit(segTree.query(left, right, 0, 0, segTree.leafSize)));
			}
		}
		sc.close();
	}
	
	
	class SegTree{
		int nodeNum;
		int leafSize;
		int[] data;
		
		public SegTree(String str) {
			
			nodeNum = str.length();
			leafSize = 1;
			while(leafSize < nodeNum) {
				leafSize *= 2; 
			}
			
			data = new int[leafSize * 2 - 1];
			
			for(int i = 0; i < str.length(); i++) {
				update(str.charAt(i), i);
			}
		}
		
		public void update(char val, int pos) {
			
			int pointer = leafSize+pos-1;
			int beforeVal = data[pointer];
			int charInt = val - 97;
			int nowVal = (1 << charInt);
			
			if(beforeVal == nowVal) {
				return;
			}
			
			data[pointer] = nowVal;
			
			while(pointer > 0) {
				pointer = (pointer-1)/2;
				data[pointer] = data[pointer*2+1] | data[pointer*2+2];
			}
		}
		
		public int query(int a, int b, int k , int l, int r) {
			if(r <= a || b <= l) {
				return 0;
			}
			if(a <= l && r <= b) {
				return data[k];
			}
			
			int m = (l+r)/2;
			return (query(a,b, k*2+1, l,m) | query(a, b, k*2+2, m, r));
		}
	}
	
	public int testBit(int bit) {
		int ans = 0;
		for(int i = 0; i < 26; i++) {
			if(((bit>>i) & 1 ) == 1) {
				ans++;
			}
		}
		return ans;
	}

}


Measured memory_bytes: 47152
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int e = pow(10, 9) + 7;
  long long ans = 1;
  for (long i = 1; i <= n; i++) {
    ans = (ans * i) % e;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int H,W,i,n,m,x,y;
    for(;;){
        scanf("%d %d",&H,&W);
        if(H==0 && W==0){
            break;
        } 
        for(n=1;n<=H;n++){
            y=n;
            for(x=1;x<=3000;x++){
                y=y%2;
            }
            if(y==0){
                for(m=1;m<=W;m++){
                    y=m;
                    for(x=1;x<=3000;x++){
                        y=y%2;
                    }
                    if(y==0){
                        printf("#");
                    }else{
                        printf(".");
                    }
                }
                printf("\n");
            }else{
                for(m=1;m<=W;m++){
                    y=m;
                    for(x=1;x<=3000;x++){
                        y=y%2;
                    }
                    if(y==0){
                        printf(".");
                    }else{
                        printf("#");
                    }
                }
                printf("\n");
            }
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 572
//#define _XCODE_DEBUG

#include <iostream>
#include <string>
#include <math.h>

#ifdef _XCODE_DEBUG
    #include <fstream>
#endif

using ll = long long;
const static ll kMod = pow(10,9)+7;

int main(int argc, const char * argv[]) {
    #ifdef _XCODE_DEBUG
        std::ifstream in("input.txt");
        std::cin.rdbuf(in.rdbuf());
    #endif
    
    ll N, K;
    ll ans = 0;
    std::cin >> N >> K;
    
    for(ll k = K; k<=(N+1); ++k) {
        ll max_val = N*(N+1)/2 - (N-k)*(N-k+1)/2;
        ll min_val = (k-1)*k/2;
        ans = (ans + (max_val - min_val + 1)) % kMod;
    }
    std::cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3192
k = int(input())
A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
ans = A[k-1]
print(ans)

Measured memory_bytes: 3060
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int ans = 0;
		
		for(int i=0; i<n; i++){
		    if(sc.nextInt()>=k){
		        ans++;
		    }
		}
		
      	System.out.println(ans);
    }
}

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

a.sort()
k = a[n-1]
r = a[0]
dis = abs(a[n-1]/2-a[0])
for i in range(n-1):
    if dis > abs(a[n-1]/2-a[i]):
        dis = abs(a[n-1]/2-a[i])
        r = a[i]
print(k,r)



Measured memory_bytes: 88704
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
using namespace std;


int main()
{
	int n,t,a,tmpI=0;
	double tmp, min = 100000000;
	cin >> n >> t >> a;
	vector<double>h;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		h.push_back(abs(a-(t-tmp*0.006)));
	}
	for (int i = 0; i < n; i++) {
		tmp = abs(h[i]);
		if (min > tmp)tmpI = i,min=h[i];
	}
	cout << tmpI+1 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn =  1e6 + 10;
#define ll long long
#define ios std::ios::sync_with_stdio(false)
const ll INF(0x3f3f3f3f3f3f3f3fll);
const int inf(0x3f3f3f3f);
#define int long long
#define pb(a) push_back(a)
#define debug(a) cout << "a : " << a << '\n'
#define mp(a , b) make_pair(a ,b)
const int mod = 1e9 + 7;
const double eps = 1e-6;
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}
int fa[maxn] , num[maxn];
int findroot(int x)
{
    if(fa[x] == x)return x;
    return fa[x] = findroot(fa[x]);
}
signed main()
{
    ios,cin.tie(0);
    int n , m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++) fa[i] = i;
    for(int i = 1 ; i <= m ; i ++){
        int x , y;
        cin >> x >> y;
        if(findroot(x) != findroot((y))){
            fa[findroot(x)] = fa[findroot(y)];
        }
    }
    for(int i = 1 ; i <= n ; i ++){
        num[findroot(i)] ++;
    }
    int maxx = 0;
    for(int i = 1 ; i <= n ; i ++) maxx = max(maxx , num[i]);
    cout << maxx << '\n';
    return 0;
}

/*
1
12
LLLLRRLRRRLL
*/


Measured memory_bytes: 11472
/*
    JAI JAGANNATH!
*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int lli;
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<lli,lli>
#define vi              vector<lli>
#define mii             map<lli,lli>
#define pqb             priority_queue<lli>
#define pqs             priority_queue<lli,vi,greater<lli> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            lli x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<lli, null_type, less<lli>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

void ss()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

}
void solve() {
	char x;
	cin >> x;
	if (x >= 'A' && x <= 'Z') {
		cout << 'A'  << endl;
	} else {
		cout << 'a' << endl;
	}
}
int main()
{
	ss();
	solve();
	return 0;
}

Measured memory_bytes: 3620
S = list(input())
flags = [False,False,False]
if S.pop(0) == "A":
    flags[0] = True
if flags[0] == True: 
    if S[1:len(S)-1].count("C") == 1:
        flags[1] = True
        del S[1+S[1:len(S)-1].index("C")]
if flags[1] == True:
    if "".join(S) == "".join(S).lower():
        flags[2] = True
if False in flags:
    print("WA")
else:
    print("AC")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define N 1000005
#define ll long long 
using namespace std;
inline ll read(){
	ll ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
ll n,s,ans,x[N],p[N];
int main(){
	n=read(),s=read();
	for(ll i=1;i<=n;++i)x[i]=read(),p[i]=read();
	ll l=1,r=n;
	while(l<=r){
		if(x[l]>=s){ans+=x[r]-s;break;}
		if(x[r]<=s){ans+=s-x[l];break;}
		ans+=x[r]-x[l];
		if(p[l]>=p[r])while(p[l]>=p[r]&&l<r)p[l]+=p[r--];
		else while(p[l]<p[r]&&l<r)p[r]+=p[l++];
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
 
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define Rep(i,n0,n) for(ll i=n0;i<n;i++)
#define Com(i,j,n) for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++)
const int INF =100100100;
const long long  MOD = (long long )1e9+7;
const double EPS = 1e-9;
typedef long long ll;
#define pb push_back 
#define mp make_pair

ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll g = a;
    x = 1;
    y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

ll gyaku(ll a) {
  ll x, y;
  if (extgcd(a, MOD, x, y) == 1) return (x + MOD) % MOD;
  else                         return 0; // unsolvable
}

ll bikkuri(ll a){
	if(a==1 || a== 0) return 1;
	else return ((a * bikkuri(a-1))%MOD);
}


signed main (){	
	ll NN,MM;
	ll upper = (long long)2e+5;
	cin >> NN >> MM;
	ll arr[upper+10];
	vector <ll> primes;

	rep(i,upper+10){
		arr[i] = 1;
	}
	Rep(i,2,sqrt(upper)+10){
		if(arr[i]){
			for(int j=0;i*(j+2)<upper;j++){
				arr[i*(j+2)]=0;
			}
		}
	}
	Rep(i,2,upper){
		if(arr[i]) {
			primes.pb(i);
		}
	}
	ll primec = primes.size();
	ll count = 0;
	ll cc = 0;
	vector <ll> kkkk;
	ll mt = MM;

	while(count != primec){
		cc = 0;
		while(mt%primes[count]==0){
			mt = mt/primes[count];
			cc ++;
		}
		if(cc!=0)kkkk.pb(cc);
		count ++;
	}
	if (mt != 1) kkkk.pb(1);
	ll ans = 1;
	ll LLLL = kkkk.size();
	
	for(ll i = 0;i<LLLL;i++){
		ans = (((ans * bikkuri(kkkk[i]+NN-1)%MOD)%MOD * gyaku(bikkuri(kkkk[i]))%MOD)%MOD * gyaku(bikkuri(NN-1))% MOD)%MOD;
		ans = ans%MOD;
	}
	cout << ans%MOD << endl;


	return 0;
}


Measured memory_bytes: 3580
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<math.h>

using namespace std;

int main(){
  int N, ans = 0, i = 1;
  cin >> N;
  while( i <= N ){
	ans = i;
	i *= 2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
package main

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

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	} 
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	s := scanString()

	if s[2] == s[3] && s[4] == s[5] {
		fmt.Fprintln(wr, "Yes")
	} else {
		fmt.Fprintln(wr, "No")
	}
}


Measured memory_bytes: 640
N, Q = map(int, input().strip().split())

A = []
D = {}
for l in range(N):
    n, t = input().strip().split()
    A.append([n, int(t)])

T = 0
while A:
    l = A.pop(0)
    if l[1] > Q:
        l[1] -= Q
        T += Q
        A.append(l)
    else:
        T += l[1]
        print(l[0], T)

Measured memory_bytes: 15932
#include <iostream>
#include <queue>
using namespace std;
struct node 
{
    int xx;
    int brojac;
};
vector<vector<pair<int,pair<int,int> > > > v;
bool const operator<(const node&x,const node&y)
{
    if(x.brojac!=y.brojac)
        return x.brojac>y.brojac;
    else
        return x.xx>y.xx;
}

int main()
{
    int n,m;
    cin>>n>>m;
    vector<pair<int,pair<int,int> > > vec;
    v.insert(v.begin(),n+1,vec);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        v[a].push_back(make_pair(b,make_pair(c,i)));
        v[b].push_back(make_pair(a,make_pair(c,i)));
    }
    vector<bool> visited(m+1,0);
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			vector<int> dist(101,1e9);
vector<pair<int,int > > pat(101,make_pair(-2,-1));
			priority_queue<node> qi;
			node g;
			g.xx=i;
			g.brojac=0;
			dist[i]=0;
			pat[i]=make_pair(-1,-1);
			qi.push(g);
			while(!qi.empty())
			{
				int topi=qi.top().xx;
				int tops=qi.top().brojac;
				qi.pop();
				for(int i=0;i<v[topi].size();i++)
				{
					if(tops+v[topi][i].second.first<dist[v[topi][i].first])
					{
						pat[v[topi][i].first]=make_pair(topi,v[topi][i].second.second);
						dist[v[topi][i].first]=tops+v[topi][i].second.first;
						g.xx=v[topi][i].first;
						g.brojac=tops+v[topi][i].second.first;
						qi.push(g);
                
					}
				}
			}

			
				int y=j;
				while(y!=-1)
				{
					if(pat[y].second!=-1)
					visited[pat[y].second]=true;
					y=pat[y].first;
				}
			
		}
	}
    
    int brojac1=0;
    for(int i=0;i<m;i++)
    {
       if(!visited[i])
       brojac1++;
    }
    cout<<brojac1<<endl;
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define COUT(x) cout << (x) << endl
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

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


int main() {
    string s;
    cin >> s;
    bool check = false;
    if(s[0] == s[1] && s[2] == s[3] && s[0] != s[2]) check = true;
    else if(s[0] == s[3] && s[1] == s[2] && s[0] != s[1]) check = true;
    else if(s[0] == s[2] && s[1] == s[3] && s[0] != s[1]) check = true;
    
    COUT(check ? "Yes" : "No");
        
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vp;
typedef map<ll, ll> mll;
typedef map<string, ll> mstrll;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define indent() cout << '\n'
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
const ll N = 200005;
const ll M = 100005;
ll n, m, x, y, z, w, h, ans, cnt, mx, mn;
string s, t, alphabet = "abcdefghijklmnopqrstuvwxyz";
ll a[N] = {}, b[N] = {}, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
vll v;
//vll dx = {-1, 0, 1, -1, 1, -1, 0, 1}, dy = {-1, -1, -1, 0, 0, 1, 1, 1};

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n){
        rep(i, n){
            cin >> a[i];
        }
        ans = INF;
        rep(i, -100, 101){
            cnt = 0;
            rep(j, n){
                cnt += pow(abs(i - a[j]), 2);
            }
            mins(ans, cnt);
        }
        print(ans);
    }
}


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

int x,n,a;
map<int,int> m;

int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>x;
		m[x]++;
	}
	
	for (auto i=m.begin();i!=m.end();i++){
		//cout<<i->first<<' '<<i->second<<endl;
		if (i->first != i->second){
			if (i->second > i->first)
				a += (i->second - i->first);
			else 
				a += i->second;
		}
	}
	
	cout<<a<<endl;
	return 0;
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

void dfs(const vector<vector<int64_t>>& adjs, const vector<int64_t>& a,
         vector<vector<int64_t>>& t, vector<int64_t>& ans, int64_t v,
         int64_t p) {
    auto idx = lower_bound(t.begin() + 1, t.end(), a[v],
                           [&](const vector<int64_t>& tt, int64_t aa) {
                               return tt.back() < aa;
                           }) -
               t.begin();
    if (idx == t.size()) {
        t.push_back(vector{a[v]});
    } else {
        t[idx].push_back(a[v]);
    }

    ans[v] = t.size() - 1;

    for (auto u : adjs[v]) {
        if (u == p) {
            continue;
        }

        dfs(adjs, a, t, ans, u, v);
    }

    t[idx].pop_back();
    if (t.back().empty()) {
        t.pop_back();
    }
}

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

    vector<int64_t> a(n);
    for (auto&& aa : a) {
        cin >> aa;
    }

    vector<vector<int64_t>> adjs(n);
    for (auto _ : irange(0L, n - 1)) {
        int64_t v, u;
        cin >> v >> u;
        --v;
        --u;
        adjs[v].push_back(u);
        adjs[u].push_back(v);
    }

    vector<vector<int64_t>> t(1);
    vector<int64_t> ans(n);
    dfs(adjs, a, t, ans, 0, -1);

    for (auto aa : ans) {
        cout << aa << "\n";
    }
}

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

const int MOD = (int)1e9+7;

int main(){
	int N,M;
	cin >> N >> M;
	vector<pair<int,int>> AB(N);
	for(int i=0;i<N;i++)	cin >> AB.at(i).first >> AB.at(i).second;
	
	sort(AB.begin(),AB.end());
	//for(int i=0;i<N;i++)	cout << AB.at(i).first << "," << AB.at(i).second << endl;
	long long ans=0;
	int now=0;
	priority_queue<int> pq;
	for(int i=1;i<=M;i++){
		while(1){
			if(now==N)	break;
			if(AB.at(now).first==i){
				pq.push(AB.at(now).second);
				now++;
			}
			else	break;
		}
		if(!pq.empty()){
			ans+=pq.top();
			pq.pop();
		}
	}
	cout << ans << endl;
	
	return 0;
}


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

int main(){
  int N,M,C,i,j,count = 0,c = 0;
  int a[20][20];
  int b[20];
  cin >> N >> M >> C;
  for( i = 0; i < M; i++ ){
    cin >> b[i];
  }

  for( i = 0; i < N; i++ ){
    c = 0;
    for( j = 0; j < M; j++ ){
      cin >> a[i][j];
      c += a[i][j] * b[j];
    }
    c = c + C;
    if( c > 0 )
    {
      count++;
    }
  }

  cout << count << endl;
}


Measured memory_bytes: 256
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
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

for i in range(len(ascii_lowercase)):
	S = re.sub(ascii_lowercase[i] + "+", ascii_lowercase[i], S)

print(len(S))

Measured memory_bytes: 92376
#include <bits/stdc++.h>
#define MOD (long long)(1E9+7)
#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;

int main(){
	int n, t=0;
	cin >> n;
	vector<long> x(n);
	rep(i, n){
		cin >> x[i];
	}
  	sort(x.begin(), x.end());
  	rep(i, n-1){
		t += x[i];
    }
	cout << (t>x[n-1] ? "Yes": "No") << endl;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = Integer.parseInt(sc.next());
    	int[] a = new int[n];
    	int min = Integer.MAX_VALUE;
    	for(int i=0; i<n; i++) {
    	    a[i] = Integer.parseInt(sc.next());
    	    int count = 0;
    	    while(a[i] % 2 == 0) {
    	        a[i] /= 2;
    	        count++;
    	    }
    	    if(min > count) min = count;
    	}
    	System.out.println(min);
    }
}

Measured memory_bytes: 22608
import sys
N, D, A = map(int, sys.stdin.readline().split())
XH = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

XH = sorted(XH)

for i in range(N):
    XH[i][1] = (XH[i][1] + A - 1) // A

adjust = [0 for _ in range(N + 1)]

def findi(v):
    ng = 0
    ok = N
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if XH[mid][0] > v: ok = mid
        else: ng = mid
    return ok

ans = 0
done = 0

for i in range(N):
    done -= adjust[i]
    XH[i][1] -= done
    if XH[i][1] < 0: continue

    ans += XH[i][1]
    index = findi(XH[i][0] + D * 2)
    done += XH[i][1]
    adjust[index] += XH[i][1]

print(ans)


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

int main() {
  int a, b;
  cin >> a >> b;

  string s = to_string(a);
  string t = to_string(b);

  string r = s + t;
  int c = stoi(r);

  double sq = sqrt(c);

  if(sq == floor(sq)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include "iostream"
using namespace std;
int main()
{
	int n , b, f, r, v, manshon[4][3][10] = {};
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> b >> f >> r >> v;
		manshon[b - 1][f - 1][r - 1] += v;
	}
	for (int i = 0; i < 4;i++)
	{
		for(int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 10; k++)
			{
				cout << " " << manshon[i][j][k];
			}
			cout << endl;
		}
		if (i != 3)
		{
			for (int l = 0; l < 20; l++)
			{
				cout << "#";
			}
			cout << endl;
		}
	}
}


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

int main()
{
	int n;

	cin >> n;
	vector<int> a(n);

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

	do {
		for (int i = 0; i < n - 1; i++)
			cout << a[i] << " ";
		cout << a[n - 1] << endl;
	} while (next_permutation(a.begin(), a.end()));

	return 0;
}


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

using namespace std;

const int N = (int)1e5 + 7;

int dp[N][3];
int n;
int a[N][3];

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 0; i < 3; i++) {
		dp[1][i] = a[1][i];
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j == k) continue;
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i][j]);
			}
		}
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2]));
}


Measured memory_bytes: 2560
N,M = map(int,input().split(" "))
L = 1
R = N
for i in range(M):
    l,r = map(int,input().split(" "))
    L = max(L,l)
    R = min(R,r)

if L <= R:
    print(R-L+1)
else:
    print(0)

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  double ans = 0.0, a;
  for (int i = 0; i < n; i++) {
    cin >> a;
    ans += 1.0/a;
  }
  ans = 1.0/ans;
  cout << fixed << setprecision(16);
  cout << ans << '\n';
}

Measured memory_bytes: 256
#include<iostream>

using namespace::std;
#define int long long int

int cnt[200005];

int32_t main(){
	int n,sum=0;
	cin>>n;
	for(int i=0,t;i<n;i++)
		cin>>t,cnt[t]++,sum+=t;
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		sum-=(l-r)*cnt[l];
		cnt[r]+=cnt[l];
		cnt[l]=0;
		cout<<sum<<'\n';
	}
}

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<bool> can(n,false);
    vector<int> num(n,1);
    can[0] = true;
    rep(i,m) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        if(can[x]) can[y] = true;
        if(can[x] && num[x] == 1) can[x] = false;
        num[x]--; num[y]++;
    }
    int ans = 0;
    rep(i,n) if(can[i]) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a / b * x;
    return d;
}

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

long long modinv(long long a, long long m) {
    long long x, y;
    extGCD(a, m, x, y);
    return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}

void comdiv(map<int, s64>& x, s64 y)
{
    map<int, s64> vy;
    for (int i = 2; i * i <= y; ++i)
    {
        while (y % i == 0)
        {
            vy[i]++;
            y /= i;
        }
    }
    vy[y]++;

    for (auto my : vy)
    {
        x[my.first] = MAX(x[my.first], vy[my.first]);
    }
}

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

    s64 N;
    vs64 a;
    vs64 ainv;
    cin >> N;
    a.resize(N);
    ainv.resize(N);
    map<int, s64> com;
    com[1] = 0;
    rep (i, N)
    {
        cin >> a[i];
        comdiv(com, a[i]);
        ainv[i] = modinv(a[i], MOD);
    }

    s64 g = 1;
    for (auto mcom : com)
    {
        while (mcom.second > 0)
        {
            g *= mcom.first;
            g %= MOD;
            mcom.second--;
        }
    }

    s64 ans = 0;
    rep (i, N)
    {
        ans += (g * ainv[i]) % MOD;
        ans %= MOD;
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    public static long ReadInt()
    {
        return long.Parse(Console.ReadLine());
    }

    public static long[] ReadInts()
    {
        return Console.ReadLine().Split().Select(long.Parse).ToArray();
    }

    public static void Main()
    {
        var input = ReadInts();
        var r = input[0];
        var D = input[1];
        var X = input[2];
        for(int i = 0; i < 10; i++)
        {
            var y = r * X - D;
            X = y;
            Console.WriteLine(y);
              }
    }
}

Measured memory_bytes: 11348
#include<iostream>
#include<queue>
#include<cctype>
#include<map>

using namespace std;

struct S{
  int y,x,t,b;
};

int main(){
  for(int W,H;cin>>W>>H,W;){
    char g[30][31];
    map<char,int> m;
    queue<S> que;
    for(int i=0;i<H;i++){
      cin>>g[i];
      for(int j=0;j<W;j++){
	if(g[i][j]=='@'){
	  que.push({i,j,0,0});
	}else if(islower(g[i][j])){
	  if(!m.count(g[i][j])){
	    int s=m.size();
	    m[g[i][j]]=s;
	  }
	}
      }
    }
    bool p[30][30][1<<8]={};
    while(!que.empty()){
      S cs=que.front();
      if(g[cs.y][cs.x]=='<')break;
      que.pop();
      if(p[cs.y][cs.x][cs.b]++)continue;
      for(int i=0;i<4;i++){
	int ny=cs.y+(~i&i-1);
	int nx=cs.x+(i?2-i:0);
	char c=g[cs.y][cs.x];
	if(c!='#'&&!(isupper(c)&&(!m.count(tolower(c))||!(cs.b>>m[tolower(c)]&1)))){
	  int nb=cs.b;
	  if(islower(c)){
	    nb^=1<<m[c];
	  }
	  que.push({ny,nx,cs.t+1,nb});
	}
      }
    }
    cout<<(que.empty()?-1:que.front().t)<<endl;
  }
}

Measured memory_bytes: 1952
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    s,t=input().split()
    print(t+s)
main()

Measured memory_bytes: 3060
#include <iostream>

using namespace std;
int main() {
  int A, B;
  cin >> A >> B;

  int card[] = {13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

  if (card[A-1] == card[B-1]) {
    cout << "Draw" << endl;
  }
  else if (card[A-1] > card[B-1]) {
    cout << "Alice" << endl;
  }
  else {
    cout << "Bob" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int x;
cin>>x;
int ans=1-x;
cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3620
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String str="";
		int c_t=0,c_y=0,c_o=0;
		int wa=0;
		int sets=0;
		while(true) {
			c_t=sc.nextInt();
			c_y=sc.nextInt();
			c_o=sc.nextInt();
			wa=c_t+c_y+c_o;

			int min=Math.min(c_t, Math.min(c_y, c_o));
			int max=Math.max(c_t, Math.max(c_y, c_o));
			int nak=wa-min-max;
			int hki=min*min+nak*nak;
			hki=hki/4;
			//System.out.println(hki);
			if(c_t*c_y*c_o==0) {
				System.exit(0);
			}
			sets=sc.nextInt();
			int[] ookisa=new int[sets];
			for(int i=0; i<sets; i++) {
				ookisa[i]=sc.nextInt();
				if(hki<ookisa[i]*ookisa[i]) {
					System.out.println("OK");
				}
				else {
					System.out.println("NA");
				}
			}
		}
	}
}


Measured memory_bytes: 25848
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		int sqrt = (int) Math.sqrt(N);
		long min = 0;
		for (long i = 1; i <= sqrt; i++) {
			if (N%i == 0) {
				min = (i+N/i-2);
			}
		}
		System.out.println(min);
	}
}

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

int main(){
  int N, K;
  scanf("%d %d", &N, &K);
  double P = 0;                                     //確率
  if(N >= K)
    P += 1.0*(N-K+1)/N;                  //サイコロを振った時点で終了する確率

  for(int i = 1; i <= min(N,K); i++){
    int j = 0;
    while(i << j < K)
      j++;
    if(j == 0)
      break;
    P += 1.0 / N / (1 << j);
  }

  printf("%.10f\n", P);
  return 0;
}

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

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

	cin>> a >> b >> c;
	int sum= a+b+c;

	if (sum >= 22)
	{
		cout << "bust";
		return 0;
	}
	cout << "win";
	return 0;
}

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

using namespace std;

int main()
{
	string s;
	getline(cin, s);

	for (int i = 0; i < s.size(); ++i)
	{
		if (isspace(s[i]));
		else if (isupper(s[i]))
			s[i] = tolower(s[i]);

		else if (islower(s[i]))
			s[i] = toupper(s[i]);

		cout << s[i];
	}

	cout << endl;

	return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <queue>
#include <sstream>
#include <set>

typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
int guki (int a){
    if(a%2==0) return 0;
    else return 1;
}
int gcd(int a, int b){
    if(a%b==0){
        return b;
    }else{
        return (gcd(b,a%b));
    }
}
int lcm(int a, int b){
    int x = gcd(a,b);
    return (a*b/x);
}












const int limit = 51;
int n,m;
bool vec[limit][limit];
bool vis[limit];

void DFS(int x){
    if(vis[x]) return;

    vis[x] = true;

    REP(i,n){
        if(vec[i][x]){
            DFS(i);
        }
    }
}
using namespace std;
int main(){
    string s;
    cin >> s;
    int cnt =0;

    map<char,int > mp;

    REP(i,4){
        mp[s[i]]++;
    }

    for(auto x:mp){
        if(x.second == 2) cnt ++;
    }

    if(cnt == 2){
        cout << "Yes" <<endl;
    }else{
        cout << "No" <<endl;
    }
}

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

const int MAX_N = 1e5 + 1;
const int INF = 1e9 + 10;

int A[MAX_N];

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    bool finish = false;
    while (!finish) {
        int now_min = INF, idx;
        for (int i = 0; i < N; i++) {
            if (A[i] == 0) continue;
            if (now_min > A[i]) {
                now_min = A[i];
                idx = i;
            }
        }
        for (int i = 0; i < N; i++) {
            if (i == idx) continue;
            A[i] = A[i] % now_min;
        }
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (A[i] > 0) cnt++;
        }
        if (cnt == 1) finish = true;
    }
    for (int i = 0; i < N; i++) {
        if (A[i] > 0) {
            cout << A[i] << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
struct qwe
{
	int t,x,y;
}a[N];
bool cmp(const qwe &a,const qwe &b)
{
	return a.t<b.t;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);
	a[++n].t=0,a[n].x=0,a[n].y=0;
	sort(a+1,a+1+n,cmp);
	for(int i=2;i<=n;i++)
	{
		int now=abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y),t=a[i].t-a[i-1].t;
		if(now>t)
		{
			puts("No");
			return 0;
		}
		if((t-now)%2==1)
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = (1e+9) + 7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	while (y) {
		int r = x % y; x = y; y = r;
	}
	return x;
}
int main() {
	int a, b, c; cin >> a >> b >> c;
	int d = gcd(a, b);
	if (c%d == 0)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

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

signed main() {
  int n, k;
  cin >> n >> k;
  vector<int> p(n), c(n);
  for (int &i : p) {
    cin >> i;
    i--;
  }
  for (int &i : c) cin >> i;
  ll ans = -1001001001;
  for (int i = 0; i < n; i++) {
    int now = i;
    vector<ll> vs;
    ll res = 0;
    while (1) {
      now = p[now];
      res += c[now];
      vs.push_back(res);
      if (now == i) break;
    }
    int sz = vs.size();
    for (int j = 0; j < min(sz, k); j++) {
      ans = max(ans, vs[j] + ((k - j - 1) / sz) * max(0ll, res));
    }
  }
  cout << ans << endl;
  return 0;
}

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

const int64_t MOD = 998244353;

//Segment Tree改
int INF = -1e9;
int64_t n = 1;

vector<int64_t> value; // ノードの値を持つ配列

void update(int64_t i, int64_t x, int64_t n) { //nは上にあるn(0-indexのはず)
  // i 番目の葉の値を x に変える
  i += n - 1; 
  value[i] = x;
  while (i > 0) {
    i = (i - 1) / 2;
    value[i] = max(value[i * 2 + 1],value[i * 2 + 2]);
  }
}

int64_t query(int64_t a, int64_t b, int64_t k, int64_t l, int64_t r) { //a,b,0,0,n
  if (r <= a || b <= l) return INF; 
  if (a <= l && r <= b)
    return value[k];
  else {
    int64_t c1 = query(a, b, 2 * k + 1, l, (l + r) / 2);
    int64_t c2 = query(a, b, 2 * k + 2, (l + r) / 2, r); 
    return max(c1, c2);
  }
}

void init(int64_t N){
  while(n < N){
    n *=2 ;
  }
  value = vector<int64_t>(2*n - 1, INF);
}

int64_t access(int64_t x, int64_t n){
  return value[x+n-1];
}

int main(){
  int N;
  cin >> N;
  vector<vector<int>> vec(N,vector<int>(2));
  for(int i=0; i<N; i++){
    for(int j=0; j<2; j++){
      cin >> vec[i][j];
    }
  }
  sort(vec.begin(),vec.end());
  
  vector<int> dist(N);
  for(int i=0; i<N; i++){
    dist[i] = vec[i][0];
  }
  
  //Segにはiを動かした時に最大どこまで動くかを記録する
  init(N);
  
  vector<vector<int>> ans(N+1,vector<int>(2));
  //0は存在しない、1は存在する
  ans[N-1][0] = 1;
  ans[N-1][1] = 1;
  ans[N][0] = 1;
  
  for(int i=0; i<N; i++){
    update(i,i,n);
  }
  
  vector<int>::iterator pos;
  int idx;
  
  for(int i=N-2; i>=0; i--){
    int x = vec[i][0];
    int y = vec[i][1];
    pos = lower_bound(dist.begin(),dist.end(),x+y);
    idx = distance(dist.begin(),pos);
    int q = query(i,idx,0,0,n);
    //cout << i << " " << idx << " " << q << endl;
    update(i,access(q,n),n);
    //cout << query(i,idx,0,0,n) << endl;
    ans[i][0] = ans[q+1][0] + ans[q+1][1];
    ans[i][0] %= MOD;
    ans[i][1] = ans[i+1][0] + ans[i+1][1];
    ans[i][1] %= MOD;
  }
  cout << (ans[0][0] + ans[0][1]) %MOD << endl;
}


Measured memory_bytes: 29916
#include <iostream>

using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)

int main(){
long long N, K, x1, x2, ans;
    cin >> N >> K;
    if (N >= K){
        x1 = N % K;
        x2 = abs(x1-K);
        ans = min(x1, x2);
    }
    else if (N<K){
        x1 = N;
        x2 = abs(x1-K);
        ans = min(x1, x2);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
namespace Collections
{
	class program
	{
		static void Main(string[] args)
		{
			// 入力
			//string[] input = Console.ReadLine().Split(' '); // N, a
			int N = Int32.Parse(Console.ReadLine());

			int[] input = new int[N];
			int max = 0, num = 0; // N個の数字の中での最大値とその個数
			for(int i=0; i<N; i++)
			{
				int a = Int32.Parse(Console.ReadLine());
				input[i] = a;
				if(max < a)
				{
					max = a;
					num = 1;
				}
				else if(max == a)
				{
					num++;
				}
			}

			// num >= 2の場合は全て最大値を出力すればOK
			if(num >= 2)
			{
				for(int i=0; i<N; i++)
				{
					Console.WriteLine(max + "");
				}
			}
			else
			{
				for(int i=0; i<N; i++)
				{
					if(input[i] == max)
					{
						// maxより小さい中での最大値を探す
						int nextMax = 0;
						for(int j=0; j<N; j++)
						{
							if(i==j)
								continue;

							if(nextMax < input[j])
								nextMax = input[j];
						}
						Console.WriteLine(nextMax + "");
					}
					else
					{
						Console.WriteLine(max + "");
					}
				}
			}
    }
	}
}


Measured memory_bytes: 17096
N = int(input())

div = [0 for _ in range(10**7+5)];

for i in range(1,10**7+1):
    j = 1
    while i * j <= N:
        div[i * j] += 1
        j += 1

ans = 0

for i in range(1,N+1):
    ans += div[i] * i
print(ans)


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

//関数
long ab(long x){
    return max(x,0-x);
}
//main関数
int main() {
    
    
    //入力
    long N;
    int K;
    cin>>N>>K;
    vector<long> h(N);
    for(int i=0;i<N;i++){
        cin>>h.at(i);
    }
    
    //計算
    vector<long> dp(N,0);
    for(int i=1;i<N;i++){
       // cout<<i<<"はじめ";
        long m=1000000000;
        for(int j=max(i-K,0);j<i;j++){
            m=min(m,dp.at(j)+ab(h.at(j)-h.at(i)));
           // cout<<dp.at(j)+ab(h.at(j)-h.at(i))<<" ";
        }
      //  cout<<i<<"終わり"<<endl;
       // cout<<m;
        dp.at(i)=m;
    }
    for(int i=0;i<N;i++){
     //  cout<<dp.at(i)<<" ";
    }
   // cout<<endl;
    
    //出力
    cout<<dp.at(N-1)<<endl;
}


Measured memory_bytes: 1792
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1175&lang=ja
// 解答AC
// 国内予選2011D
// And Then. How Many Are There?

/*
Problem.
位置と半径、色が指定された円盤が配置されていて、
同色でそれぞれ上に重なる円盤のないペアを排除していく。
最大でいくつの円盤を排除可能か？

Point.
依存関係を表すテーブル on[N] : i番目のitemより先に削除が必要な要素のbitが立っている。
bool dp[1<<N]: dp[now] が探索済みかどうかT/F
bit全探索を行い、dfs(int now)中で
!(now & on[i]) を満たすi、同様にjを求め、
dfs(now & ~(1<<i) & ~(1<<j)) が実行可能になる。
*/


#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pii = pair<int, int>;
using ppi = pair<pii, int>;

struct saucer{
  double x, y, r;
  int c;
  saucer(double ix, double iy, double ir, int ic): x(ix), y(iy), r(ir), c(ic){}
};

int n;
int ans;
vector<saucer> v;
vector<int> on;
vector<bool> dp(1<<4);
void dfs(int now){
  if(dp[now]) return;
  dp[now] = true;
  int unused = 0;
  for(int i = 0; i < n; i++) if(now >> i & 1) unused++; //未削除itemのカウント
  ans = max(n-unused, ans);
  for(int i = 0; i < n; i++){
    if(!(now>>i & 1) || now & on[i]) continue; //依存itemは全て除去済みである必要がある。
    for(int j = i+1; j < n; j++){
      if(!(now>>j & 1) || now & on[j]) continue;
      if(v[i].c == v[j].c){
        dfs((now & ~(1 << i)) & ~(1 << j));
      }
    }
  }
}


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  while(cin >> n && n){
    ans = 0;
    v = vector<saucer>();
    on = vi(24, 0);
    dp = vector<bool>(1<<n, false);
    double x, y, r; int c;
    for(int i = 0; i < n; i++){
      cin >> x >> y >> r >> c;
      v.push_back({x, y, r, c});
    }
    for(int i = 0; i < n; i++){
      for(int j = 0; j < i; j++){
        if(pow((v[i].x-v[j].x), 2.0) + pow((v[i].y-v[j].y), 2.0) < pow(v[i].r+v[j].r, 2.0)){
          on[i] |= (1 << j);
        }
      }
    }
    dfs((1<<n)-1);
    cout << ans << endl;
  }

  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}



Measured memory_bytes: 7196
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

int main() {
  int N; double T, A; cin >> N >> T >> A;
  double H[N]; rep(i,N) cin >> H[i];

  int result = 1;
  rep(i, N) {
    if (abs((T-H[result-1]*0.006)-A) > abs((T-H[i]*0.006)-A)) result = i+1;
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<set>
#include<math.h>
#include<iomanip>

using namespace std;

int main(void)
{
    int n,k;
    cin>>n>>k;
    
    if(n<k){
        double pro=0;
        for(int i=1;i<=n;i++){
            int count=1;
            long int num=i*2;
            
            while(num<k){
                num*=2;
                count++;
            }
            pro+=(double)1/(n*pow(2,count));
        }
        cout<<fixed<<setprecision(10)<<pro<<endl;
        
    }
    
    else{
        double pro=(double)(n-k+1)/n;
        for(int i=1;i<k;i++){
            int count=1;
            long int num=i*2;
            
            while(num<k){
                num*=2;
                count++;
            }
            pro+=(double)1/(n*pow(2,count));
        }
        cout<<fixed<<setprecision(12)<<pro<<endl;
    }
}


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

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBUG = true;

int main(){

    map<ll, ll> m;

    ll n;
    cin >> n;
    for(int i = 0; i < n; i++){
        ll tmp;
        cin >> tmp;
        m[tmp]++;
    }

    int Q;
    cin >> Q;
    vector<ll> ans(Q);
    ll tmp = 0;
    for(auto it = m.begin(); it != m.end(); it++){
        tmp += (it->first) * (it->second);
    }

    for(int q = 0; q < Q; q++){
        ll b, c;
        cin >> b >> c;
        ll add , minus;
        minus = b * m[b];
        add = c * m[b];
        m[c] += m[b];
        m[b] = 0;
        tmp += add;
        tmp -= minus;
        ans[q] = tmp;
    }

    for(int q = 0; q < Q; q++){
        cout << ans[q] << endl;
    }


    return 0;
}

Measured memory_bytes: 10004
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))

n,d = map(int, input().split())

if (n%(2*d+1) == 0):
    print( n // (2*d+1))
else:
    print( n // (2*d+1) + 1)


Measured memory_bytes: 9108