akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

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

		while (input.hasNext()) {
			long A = input.nextLong();
			long B = input.nextLong();
			long gcdAB = gcd(A, B);

			int countPrimeFactor = 0;
			for (long i = 2; i * i <= gcdAB; ++i) {
				if (gcdAB % i == 0) {
					++countPrimeFactor;
					
					while (gcdAB % i == 0) {
						gcdAB /= i;
					}
				}
			}
			
			if (gcdAB != 1) {
				++countPrimeFactor;
			}
			
			System.out.println(countPrimeFactor + 1);
		}
	}

	private static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}


Measured memory_bytes: 27128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    string sr=s;
    reverse(sr.begin(),sr.end());
    int n=s.size();
    int x=(n-1)/2;
    int y=(n+3)/2;
    string q="";
    string t="";
    for(int i=0;i<x;i++)
        t=t+s[i];
    for(int i=y-1,j=0;i<n;i++,j++)
        q=q+s[i];
    string qr=q;
    string tr=t;
    reverse(tr.begin(),tr.end());
    reverse(qr.begin(),qr.end());
    if(s==sr&&t==tr&&q==qr)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;

}




Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author bcools
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] length = new int[n];
            for (int i = 0; i < n; ++i) {
                length[i] = in.nextInt();
            }

            Arrays.sort(length);

            int result = 0;
            for (int i = n - k; i < n; ++i) {
                result += length[i];
            }
            out.println(result);
        }

    }
}



Measured memory_bytes: 21844
#include<iostream>
     
    using namespace std;
     
    const int N = 1000;
    int n, ans, now[N + 1];
     
    bool idax(int dep)
    {
        if(dep > ans)
            return false;
        if((now[dep] << (ans - dep)) < n) // 剪枝
            return false;
        if(now[dep] == n)
            return true;
     
        for(int i=0; i<=dep; i++) {
            now[dep + 1] = now[dep] + now[i];
            if (idax(dep + 1))
                return true;
            now[dep + 1] = now[dep] - now[i];
            if (idax(dep + 1))
                return true;
        }
     
        return false;
    }
     
    int main()
    {
        now[0] = 1;
     
        while(cin>>n && n) {
            ans = 0;
            while(!idax(0))
                ans++;
            cout << ans << endl;
        }
     
        return 0;
    }


Measured memory_bytes: 3088
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

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

static const double eps = 10e-8;

int main(){

	int n;
	 
	while(~scanf("%d",&n)){
		if(n==0) break;

		vector<P> data;
		for(int i=0;i<n;i++){
			int c1,m1,s1,m2,s2,m3,s3,m4,s4;
			scanf("%d %d %d %d %d %d %d %d %d",&c1,&m1,&s1,&m2,&s2,&m3,&s3,&m4,&s4);
			int sum = 60*(m1+m2+m3+m4)+(s1+s2+s3+s4);
			data.push_back(P(sum,c1));
		}

		sort(data.begin(),data.end());

		printf("%d\n",data[0].second);
		printf("%d\n",data[1].second);
		printf("%d\n",data[data.size()-2].second);
	}
}

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


#print(h,n)
#print(a)

a.sort(reverse=True)

#print(a)
win = 0

for i in range(n) :
    h = h - a[i]
    if h <= 0 :
        win=1
        break

if win :
    print("Yes")
else :
    print("No")

Measured memory_bytes: 13964
#include <stdio.h>

int main(){
    int N;
    char S[101];

    scanf("%d%s", &N, S);

    if(N % 2 == 0){
        int i;

        for(i = 0; i < N / 2; i ++){
            if(S[i] != S[i + N / 2]){
                break;
            }
        }
        if(i == N / 2){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }else{
        printf("No\n");
    }
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <fstream>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define ll long long

int main() {
    //入力
    string n;
    cin >> n;
    //処理
    ll sum = 0;
    rep(i, n.size()) {
        sum += n[i] - '0';
    }

    //出力
    string ans;
    if (sum % 9 == 0) {
        ans = "Yes";
    }
    else {
        ans = "No";
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3720
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    int left = a+b;
    int right = c+d;
    if(left>right){
      System.out.println("Left");
    }else if(left<right){
      System.out.println("Right");
    }else{
      System.out.println("Balanced");
    }
  }
}


Measured memory_bytes: 23764
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <fstream>
#include <unordered_map>
#define MAX_INT ((1 << 31) - 1);

using namespace std;

ifstream fin("../data.txt");

int n, x, sum, ans, diff;
vector<int> v;

int main() {

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

  ans = MAX_INT;
  for (int i = -100; i <= 100; i++) {
    sum = 0;
    for (int j = 0; j < n; j++) {
      diff = v[j] - i;
      sum += diff*diff;
    }
    if (sum < ans) ans = sum;
  }

  cout << ans;
  return 0;
}


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


const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

int main(){
    int n;
    cin >> n;
    mint ans = 1;
    mint res1 = 1;
    mint res2 = 1;
    rep(i, n){
        ans *= 10;
        res1 *= 9;
        res2 *= 8;
    }
    ans -= res1 * 2 - res2;
    cout << ans.x << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 200005
using namespace std;
struct P{
	int x,y;
}b[N];
struct edge{
	int k,next;
}e[N<<1];
int mn[2][N<<2],n,a[N],tot,home[N],cnt=-1;
void add(int x,int y){
	if(!x||!y) return;
	cnt++;
	e[cnt].k=y;
	e[cnt].next=home[x];
	home[x]=cnt;
}
void build(int k,int l,int r){
	if(l==r){
		mn[l&1][k]=l;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	for(int i=0;i<2;i++){
		if(a[mn[i][k<<1]]>a[mn[i][k<<1|1]]) mn[i][k]=mn[i][k<<1|1];
		else mn[i][k]=mn[i][k<<1];
	}
}
int query(int k,int l,int r,int L,int R,int op){
	if(L<=l&&R>=r) return mn[op][k];
	int mid=l+r>>1,ans=0;
	if(L<=mid) ans=query(k<<1,l,mid,L,R,op);
	if(R>mid){
		int t=query(k<<1|1,mid+1,r,L,R,op);
		ans=a[ans]<a[t]?ans:t;
	}
	return ans;
}
int solve(int l,int r){
	if(l>r) return 0;
	int x=query(1,1,n,l,r,l&1);
	int y=query(1,1,n,x+1,r,!(x&1));
	int g=tot+1;
	b[++tot].x=a[x];b[tot].y=a[y];
	add(g,solve(l,x-1));
	add(g,solve(x+1,y-1));
	add(g,solve(y+1,r));
	return g;
}
int id[N];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	memset(home,-1,sizeof(home));
	scanf("%d",&n);
	a[0]=1e9;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	int rt=solve(1,n);
	for(int  i=1;i<=tot;i++) id[b[i].x]=i;
	q.push(b[rt].x);
	while(!q.empty()){
		int k=id[q.top()];q.pop();
		printf("%d %d ",b[k].x,b[k].y);
		for(int i=home[k];~i;i=e[i].next) q.push(b[e[i].k].x);
	}
	return 0;
}

Measured memory_bytes: 20224
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{

	public static void main (String[] args) {
		BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in));
		int omosa=0;
		int[] omori=new int[10];
		int[] o_uuum=new int[10];
		int p=1;
		String mj="";
		String iru="";
		for(int i=0; i<10; i++) {
			omori[i]=p;
			o_uuum[i]=0;
			p*=2;
		}
		try {
			while(true) {
				mj=bfr.readLine();
				omosa=Integer.parseInt(mj);
				for(int i=0; i<10; i++) {
					o_uuum[i]+=omosa%2;
					omosa=omosa>>1;
					if(o_uuum[i]==1) {
						iru=iru+""+omori[i]+" ";
					}
					else {}
				}
				System.out.println(iru.substring(0,iru.length()-1));
				for(int i=0; i<10; i++) {
					o_uuum[i]=0;
				}
				iru="";
			}
		}catch(IOException e) {
		}
		catch(NumberFormatException e) {
			System.exit(0);
		}
	}
}


Measured memory_bytes: 24208
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))

INF = 1001001001

# ---------------------------------------



n, k = inpl()
p = [0] + inpl()
c = [0] + inpl()

ans = - INF

for i in range(1, n + 1):
    cycle_cnt = 0
    cycle_sum = 0
    v = i

    while True:
        v = p[v]
        cycle_cnt += 1
        cycle_sum += c[v]
        if v == i: break
    
    cnt = 0
    path = 0

    while True:
        v = p[v]
        cnt += 1
        path += c[v]

        if cnt > k: break

        num = (k - cnt) // cycle_cnt
        score = path + max(0, cycle_sum) * num
        ans = max(ans, score)

        if v == i: break

print(ans)


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

using namespace std;

int main(void) {
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    for(int i=0; i<N; i++) {
        cin >> h.at(i);
    }
    sort(h.begin(), h.end());
    int ans = INT32_MAX;
    for(int i=0; i<N-K+1; i++) {
        ans = min(ans, h.at(i+K-1) - h.at(i));
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 25;
const ll INFL = 1223372036854775807;
const ll mod = 1000000007;



int main() {

	int a, b, c;
	cin >> a >> b >> c;

	cout << min(c, b / a) << endl;



	return 0;
}

Measured memory_bytes: 256
import sys
def II(): return int(sys.stdin.readline())

def get_is_prime_tuple(n):  # including n
    isPrime = [True for _ in range(n+1)]
    isPrime[0] = False
    isPrime[1] = False
    for j in range(4, n+1, 2): isPrime[j] = False  # multiples of 2

    for i in range(3, int(n**0.5)+1):
        if not isPrime[i]: continue
        for j in range(i*i, n+1, i+i):  # j = (i*i, (i+2)*i, ..., m*i <= n)
            isPrime[j] = False
    return tuple(isPrime)

def main(): 
    isPrime = get_is_prime_tuple(55555)
    N = II()
    ans = []
    for i in range(2,55556):
        if isPrime[i] and i%5 == 1:
            ans.append(i)
            N -= 1
        if N == 0:
            break
    print(' '.join(map(str, ans)))
    
main()

Measured memory_bytes: 3992
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include <functional>
#include <array>
#include <cmath>
#include <set>
#include <iomanip>

using namespace std;


int N, X;
int m[100]{};

int main(){
	
	cin >> N >> X;
	for (int i = 0; i < N; ++i) {
		cin >> m[i];
		X -= m[i];
	}

	int ans = N;
	int minm = *(min_element(m, m + N));

	ans += X / minm;

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 384
#!/usr/bin/env python3
import sys


def solve(S: str):
    print('ABC' if S == 'ARC' else 'ARC')
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


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

int main(){

  int a,b,c[110][110],d[110],e[110]={0};
  
  cin >> a >> b;
  
  for(int i=0;i<b;i++){

  cin >> d[i];
    
   
    for(int j=0;j<d[i];j++)
    cin >> c[d[i]][j];
    
    for(int k=0;k<d[i];k++){
      e[c[d[i]][k]]++;
    }
    
  }
  int ans = 0;
  for(int i=1;i<=a;i++){
    if(e[i] > 0){
      ans++;
    }
  }
  
  cout << a-ans << endl;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 

int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}

/*int ncr(int n,int r){

    int ret = (fact[n-r]*fact[r])%mod;
    ret = inverse(ret);
    ret *= fact[n];
    ret %= mod;
    return ret;
}*/



signed main()
{
    showoff;
    int s,x2,y3;
    cin >> s;
    x2 = sqrt(s)+5,y3 = x2;
    x2 = min(x2,(int) 1000000000);
    y3 = x2;
    int diff = x2*y3-s;
    while(diff > (int) 1000000000){
        x2--;
        y3--;
        diff = x2*y3-s;
    }
    cout << 0 << " " << 0 << " " << x2 << " " << diff << " " << 1 << " " << y3;
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...   

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

struct Point{
	bool operator<(const struct Point &arg) const{
			return x < arg.x;
	};
	double x,y;
};

double a,b,c,d;

double calc(double x){
	return ((c-a)*x)/(b-d)+(b+d)/2-(c-a)*(a+c)/(2.0*(b-d));
}


double dist(double x,double y){
	double ans1 = sqrt((x-a)*(x-a)+(y-b)*(y-b));
	double ans2 = sqrt((x-c)*(x-c)+(y-d)*(y-d));

	if(fabs(1.0-ans1) < fabs(1.0-ans2)){
		return ans1;
	}else{
		return ans2;
	}
}

int main(){

	int N,maximum,count;
	Point points[300];
	double left,right,m,tmp_x,tmp_y,tmp_dist;

	bool FLG;

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		maximum = 1;

		for(int loop = 0; loop < N; loop++){
			scanf("%lf %lf",&points[loop].x,&points[loop].y);
		}

		sort(points,points+N);

		for(int i = 0; i <= N-2; i++){
			for(int k = i+1; k <= N-1; k++){

				a = points[i].x;
				b = points[i].y;
				c = points[k].x;
				d = points[k].y;

				left = 0.0;
				right = (a+c)/2.0;
				m = (left+right)/2.0;

				FLG = false;

				while(left <= right){
					tmp_y = calc(m);
					tmp_dist = dist(m,tmp_y);

					if(fabs(tmp_dist-1.0) < EPS){
						FLG = true;
						tmp_x = m;
						break;
					}else if(tmp_dist > 1.0){
						left = m + EPS;
					}else{
						right = m - EPS;
					}
					m = (left+right)/2.0;
				}

				if(FLG){
					count = 0;
					for(int p = 0; p < N; p++){
						if(sqrt((tmp_x-points[p].x)*(tmp_x-points[p].x)+(tmp_y-points[p].y)*(tmp_y-points[p].y)) < 1.0){
							count++;
						}else if(fabs(sqrt((tmp_x-points[p].x)*(tmp_x-points[p].x)+(tmp_y-points[p].y)*(tmp_y-points[p].y))-1.0) <= EPS){
							count++;
						}
					}
					maximum = max(maximum,count);
				}

				left = (a+c)/2.0;
				right = 10.0;
				m = (left+right)/2.0;
				FLG = false;

				while(left <= right){
					tmp_y = calc(m);
					tmp_dist = dist(m,tmp_y);

					if(fabs(tmp_dist-1.0) < EPS){
						FLG = true;
						tmp_x = m;
						break;
					}else if(tmp_dist > 1.0){
						right = m - EPS;
					}else{
						left = m + EPS;
					}
					m = (left+right)/2.0;
				}

				if(FLG){
					count = 0;
					for(int p = 0; p < N; p++){
						if(sqrt((tmp_x-points[p].x)*(tmp_x-points[p].x)+(tmp_y-points[p].y)*(tmp_y-points[p].y)) < 1.0){
							count++;
						}else if(fabs(sqrt((tmp_x-points[p].x)*(tmp_x-points[p].x)+(tmp_y-points[p].y)*(tmp_y-points[p].y))-1.0) <= EPS){
							count++;
						}
					}
					maximum = max(maximum,count);
				}

			}
		}

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

	return 0;
}

Measured memory_bytes: 2568
N = int(input())
P = list(map(int,input().split()))

D = [0]*N

for i in range(N):
    D[P[i]-1] = i

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

    #you can use this function when the BIT has only non-negative values.
    def lower_bound(self, w):
        if w<=0:
            return 0
        x = 0
        k = self.N0
        while k>0:
            if x+k<=self.N:
                if self.bit[x+k-1]<w:
                    w-=self.bit[x+k-1]
                    x+=k
            k//=2
        return x

bit = BIT([0]*N)

def calc_num(x,l1,l2,h1,h2):
    A = (l1-l2)*(h1-x)
    B = (h2-h1)*(x-l1)
    return A+B

ans = 0

for i in range(N):
    j = N-i-1
    bit.add(D[j],1)
    s = bit.sum(D[j])
    if s==i+1:
        h1=h2=N
    elif s==i:
        h2=N
        h1 = bit.lower_bound(s+1)
    else:
        h1 = bit.lower_bound(s+1)
        h2 = bit.lower_bound(s+2)
    if s==1:
        l1=l2=-1
    elif s==2:
        l1 = bit.lower_bound(s-1)
        l2 = -1
    else:
        l1 = bit.lower_bound(s-1)
        l2 = bit.lower_bound(s-2)

    #print(D[j],l1,l2,h1,h2)
    #print(calc_num(D[j],l1,l2,h1,h2))
    ans += calc_num(D[j],l1,l2,h1,h2)*(j+1)

print(ans)

Measured memory_bytes: 58988
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;


    void calc()
    {
        cin = new Scanner();
        int[] NMXY = cin.ArrayInt(4,0);
        int[] x = cin.ArrayInt(NMXY[0],0);
        int[] y= cin.ArrayInt(NMXY[1],0);
        Array.Sort(x);
        Array.Sort(y);
        if(x[NMXY[0]-1]>=y[0])Console.WriteLine("War");
        else if(y[0]<=NMXY[2]||x[NMXY[0]-1]>=NMXY[3])Console.WriteLine("War");
        else Console.WriteLine("No War");
    }


}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 11092
use std::cmp::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        h: [i32 ; n],
    }
    let mut dp = vec![0; n];

    dp[1] = (h[0] - h[1]).abs();
    for i in 2..n {
        let one = (h[i] - h[i - 1]).abs() + dp[i - 1];
        let two = (h[i] - h[i - 2]).abs() + dp[i - 2];
        dp[i] = min(one, two);
    }

    println!("{}", dp[n - 1]);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define FOR(i,n) for(int i=0;i<(n);i++)
#define cinv(v,n) FOR(i,n){cin>>(v)[i];}
#define nvec(type,v,n) vector<type> v(n);cinv(v,n);
#define pb push_back
#define mp make_pair

int main() {
  int x,a;
  cin>>x>>a;
  if(x<a){
    cout<<0;
  }else{
    cout<<10;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		//
		int a = sc.nextInt();
		int b = sc.nextInt();

		int [] haco = {(a)+(b), (a)-(b), (a)*(b)};

		int max = 0;

		if(haco[0] > haco[1]) {
			max = haco[0];
		}else {
			max = haco[1];
		}

		if(max < haco[2]) {
			max = haco[2];
		}

		System.out.println(max);
	}
}

Measured memory_bytes: 23380
#include<iostream>   //AA06(17 / 05/ 20)

using namespace std;

int main()
{
    int k, i;

    string S;

    cin >> k >> S;

    if(S.length() > k){

        for(i = 0; i < k; ++i) {

            cout << S[i];

        }

        cout << "..." << endl;

    }

    else {
        cout << S << endl;
    }



    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define Phuong_ ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
#define mp make_pair

/// easy access -------------
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<int,int> pii;
///-------------------------

int main()
{
    Phuong_; /// <3
    ll n,k;
    cin >> n >> k;
    ll sum=0;
    ll mod=1e9+7;
    for(ll i=k; i<=n+1; ++i)
        sum=(sum+ (n-i+1)*i +1)%mod;
    cout << sum;
    return 0;
}



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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef pair<ll, ll> P;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = 10000000000;
/****** define constant end ********/


/****** define variable start ******/
ll h, a;
/******* define variable end *******/

ll solve(){
    cin >> h >> a;
    if(h % a == 0){
        cout << h / a << endl;
    }else{
        cout << h / a + 1 << endl;
    }
    return 0;
}
int main(){
    //clock_t start = clock();
    cout << std::fixed << std::setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll end_solve = solve();
    /*
    clock_t end = clock();
    const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
    printf("time %lf[ms]\n", time);
    */
    return (int)end_solve;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<algorithm>
#include<bitset>
using namespace std;

int main(void)
{
	int N;
	cin >> N;

	const string head = "MARCH";
	vector<long long> cnt(head.size(), 0);
	for(int i=0; i<N; i++){
		string name;
		cin >> name;

		auto it = find(head.begin(), head.end(), name[0]);
		if(it != head.end())
			cnt[it-head.begin()]++;
	}

	long long ret = 0;
	for(int i=(1<<5)-1; i>0; i--){
		bitset<5> bit(i);
		if(bit.count() != 3)
			continue;

		long long n = 1;
		for(int j=0; j<5; j++){
			if(bit[j] == 0)
				continue;

			n *= cnt[j];
		}

		ret += n;
	}

	cout << ret << endl;

	return 0;
}


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

int main() {
  int N;
  cin >> N;
  string S[N];
  for(int i=0;i<N;i++){
    cin >> S[i];
    int N1 = S[i].size();
    char A[N1];
    for(int j=0;j<N1;j++){
      A[j] = S[i][j];
    }
    sort(A, A+N1);
    S[i] = "";
    for(int k=0;k<N1;k++){
      S[i] += A[k];
    }
  }
  sort(S, S+N);
  int64_t A[1000000];
  A[0] = 0;
  A[1] = 1;
  for(int i=2;i<1000000;i++){
    A[i] = A[i-1] + i;
  }
  int64_t ans = 0;
  int Z[N] = {};
  Z[0] = 0;
  for(int i=1;i<N;i++){
    if(S[i] == S[i-1]) {
      Z[i] = Z[i-1] + 1;
    }
    else {
      Z[i] = 0;
      ans += A[Z[i-1]];
    }
  }
  if(Z[N-1] != 0) ans += A[Z[N-1]];
  cout << ans << endl;
}

Measured memory_bytes: 15488
n, m = [int(i) for i in input().split()]

if abs(n-m) > 1:
    print(0)
    exit()
count = 1
for i in range(1, n + 1):  # n!
    count *= i
    count %= (10**9 + 7)
for i in range(1, m + 1):  # n!
    count *= i
    count %= (10 ** 9 + 7)
if n == m:
    count *= 2
print(int(count % (10**9 + 7)))

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

using namespace std;

typedef long long int ll;

ll M = 1e9+7;
ll power(ll a , ll n)
{
    unsigned long long int result=1,x=a;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x = (x * x)%M;
        n=n/2;
    }
    return result;
}
int main()
{
    ll n,k;
    cin >> n >> k;
    ll ans = 0;
    ll dp[k+1];   
    for(ll i=k; i>=1 ; i--)
    {
        ll ka = k/i;
        ll p = power(ka,n);
        for(ll j=2*i ; j<=k ; j=j+i)
            p = (p - dp[j] + M)%M;
        dp[i] = p;
        ans = (ans + i*p)%M;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 4320
import sys
input = sys.stdin.readline

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

ans = 0
for i in range(N):
    if not ans:
        ans = min(abs(A[i - 1] - A[i]), abs(A[i] + (K - A[i + 1])))
    else:
        d = min(abs(K + A[i - 1] - A[i]), abs(A[i] + (K - A[i + 1]))) if i != N - \
            1 else min(abs(A[0] - A[i]), abs(A[i] + (K - A[0])))
        ans = min(ans, d)

print(ans)


Measured memory_bytes: 25880
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll>> PP;

const ll MOD = 1e9 + 7;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fr first
#define sc second


int main() {
	ll n, a[300010], sum = 0, ma[300010] = { 0 }, ans = 0, s = 0;
	cin >> n;
	for (int i = 0;i < 3 * n;i++)cin >> a[i];
	if (n == 1) {
		cout << max(a[0] - a[1], max(a[0] - a[2], a[1] - a[2])) << endl;
		return 0;
	}

	priority_queue<ll>p;
	for (int i = 3 * n - 1;i > 2 * n - 1;i--) {
		s += a[i];
		p.push(a[i]);
	}
	ma[2 * n] = s;
	for (int i = 2 * n - 1;i > n - 1;i--) {
		s += a[i];
		p.push(a[i]);
		ll b = p.top();p.pop();
		s -= b;
		ma[i] = s;
	}

	priority_queue<ll, vector<ll>, greater<ll>>pq;
	for (int i = 0;i < n;i++) {
		sum += a[i];
		pq.push(a[i]);
	}
	ans = sum - ma[n];
	for (int i = n;i < 2 * n;i++) {
		sum += a[i];
		pq.push(a[i]);
		ll b = pq.top(); pq.pop();
		sum -= b;
		ans = max(ans, sum - ma[i + 1]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 7284
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;
using TextReader = System.IO.TextReader;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var N = consoleReader.Int;
            var a = consoleReader.Split.Int.Select((x, i) => x - i - 1).OrderBy(i => i).ToArray();
            var b = a[(a.Length - 1) / 2];

            long s = 0;
            foreach (var item in a)
                s += Math.Abs(item - b);

            return s;
        }


        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program(new ConsoleReader(Console.In)).Calc()); static string AllLines<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

#pragma warning disable
    public class ConsoleReader
    {
        private string[] line = Array.Empty<string>();
        private int linePosition;
        private TextReader textReader;
        public ConsoleReader(TextReader tr) { textReader = tr; }
        public int Int => int.Parse(String);
        public long Long => long.Parse(String);
        public double Double => double.Parse(String);
        public string String
        {
            get
            {
                if (linePosition >= line.Length)
                {
                    linePosition = 0;
                    line = textReader.ReadLine().Split();
                }
                return line[linePosition++];
            }
        }
        public class SplitLine
        {
            private string[] splited;
            public SplitLine(ConsoleReader cr) { splited = cr.textReader.ReadLine().Split(); }
            public int[] Int => String.Select(x => int.Parse(x)).ToArray();
            public long[] Long => String.Select(x => long.Parse(x)).ToArray();
            public double[] Double => String.Select(x => double.Parse(x)).ToArray();
            public string[] String => splited;
        }
        public SplitLine Split => new SplitLine(this);
        public class RepeatReader
        {
            ConsoleReader cr; int count;
            public RepeatReader(ConsoleReader cr, int count) { this.cr = cr; this.count = count; }
            public IEnumerable<T> Select<T>(Func<ConsoleReader, T> func) { for (int i = 0; i < count; i++) yield return func(cr); }
            public IEnumerable<string> String { get { for (int i = 0; i < count; i++) yield return cr.String; } }
            public IEnumerable<int> Int { get { for (int i = 0; i < count; i++) yield return cr.Int; } }
            public IEnumerable<double> Double { get { for (int i = 0; i < count; i++) yield return cr.Double; } }
        }
        public RepeatReader Repeat(int count) => new RepeatReader(this, count);
    }
}

Measured memory_bytes: 35656
O = list(input())
E = list(input())
password = []
if len(O) - len(E) == 0:
    for i in range(len(O)):
        password.append(O[i])
        password.append(E[i])
elif len(O) - len(E) == 1:
    for i in range(len(E)):
        password.append(O[i])
        password.append(E[i])
    password.append(O[len(O)-1])
password = "".join(password)

print(password)


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

int main() {
	int x, y;
	while (true) {
		cin >> x >> y;
		if ((x | y) != 0) {
			if (x < y) {
				cout << x << " " << y << endl;
			} else {
				cout << y << " " << x << endl;
			}
		} else {
			break;
		}
	}
	return 0;
}

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

bool check[1000005];

int main(){
  int s;
  cin>>s;
  check[s]=true;
  int a1=s,a2;
  int ans=2;
  while(1){
    if(a1&1) a2=3*a1+1;
    else a2=a1/2;
    if(check[a2]==true){
      cout<<ans<<endl;
      return 0;
    }
    check[a2]=true;
    a1=a2;
    ans++;
  }
  return 0;
}

Measured memory_bytes: 256
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
t = ins()
oa = ord('a')
ls = len(s)
nxt = [[-1]*26 for i in range(ls)]
nx = [-1]*26
for i in range(2*ls-1,-1,-1):
    c = ord(s[i%ls])-oa
    for j in range(26):
        if i<ls and nx[j]>=0:
            nxt[i][j] = nx[j]-i
    nx[c] = i
if DBG:
    for i in range(ls):
        #printn(f"{i} ")
        print(nxt[i])

prevpos = nxt[ls-1][ord(t[0])-oa]-1
if prevpos<0:
    print(-1)
    exit()
for i in range(1,len(t)):
    c = ord(t[i])-oa
    nx = nxt[prevpos%ls][c]
    if nx<0:
        print(-1)
        exit()
    prevpos += nx
    #ddprint(f"i {i} pp {prevpos} c {c} ti {t[i]}")
print(prevpos+1)


Measured memory_bytes: 72284
from collections import deque
n,k = map(int,input().split())
l = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
rl = [0 for i in range(n+1)]
nl = [0 for i in range(n+1)]
ans = 0
nl[0] = -1
d = deque()
d.append([1,0])
rl2 = [0 for i in range(n+1)]
rl2[0] = 1
while len(d):
    [now,p] = d.popleft()
    #print(rl,nl,now,p)
    rl[now] = k - nl[p] - 1
    nl[p] += 1
    rl2[now] = 1
    if now != 1:
        nl[now] += 1
    for i in l[now]:
        if rl2[i] == 0:
            d.append([i,now])
ans = 1
mod = 10**9+7
#print(l,rl,nl)
for i in range(1,n+1):
    ans *= rl[i]
    ans %= mod
if ans > 0:
    print(ans)
else:
    print(0)

Measured memory_bytes: 76032
//#pragma optimization_level 3

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <chrono>
#include <ctime>
#include <queue>
#include <math.h>
#include <deque>
#include <stack>
#include <iomanip>
#include <assert.h>
#include <stdio.h>
#include <cstring>
#include <random>

using namespace std;

#define int long long
#define ld long double
#define ull unsigned long long
//#define endl '\n'
#define try tr
#define pii pair<int, int>
#define ti tuple <int, int, int>
#define vi vector <int>
#define vpi vector <pii>
#define umap unordered_map
#define uset unordered_set
#define left left11
#define right right11
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define sqr(a) ((a) * (a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define X first
#define Y second

ld TL = 1.0;
bool is_tl = 0;
int CALLS = 0;

inline bool IS() {
    if (++CALLS == 1000) {
        CALLS = 0;
        is_tl |= clock() > (TL - 0.1) * CLOCKS_PER_SEC;
    }
    return is_tl;
}

template<typename T1, typename T2>
inline void amin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void amax(T1 &a, T2 b) { if (a < b) a = b; }

template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << p.first << ' ' << p.second << endl;
    return os;
}

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
    for (auto &u : v) os << u << ' ';
    os << endl;
    return os;
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 7, NS = 2e3 + 7, lg = 19, sq = 550, inf = 1e18 + 7, SM = 1e2 + 7;
const ld eps = 1e-9;
int hash_mod[4] = {1000000007, 998244353, 1000000009, 999999937}, mod = hash_mod[rnd() % 4];
int hash_pows[4] = {179, 239, 1007, 2003}, P = hash_pows[rnd() % 4];
vi v[N];
int n, p, ans = 0, k;
int dfs(int x, int pr, int d) {
    int mx = d;
    for (auto u : v[x]) {
        amax(mx, dfs(u, x, d + 1));
    }
    if(x && ((mx - d > k - 1) || (pr && mx - d == k - 1))) {
        ans++;
        return d - 1;
    }
    else
        return mx;
}
void solve() {
    cin >> n >> k;
    cin >> p;
    p--;
    if(p)
        ans++;
    for (int i = 1; i < n; i++) {
        cin >> p;
        p--;
        v[p].pb(i);
    }
    dfs(0, -1,0);
    cout << ans;
}

signed main() {
    fast
    solve();

}


Measured memory_bytes: 19240
#include"bits/stdc++.h"
using namespace std;

#define MAX 10000
#define INF (1 << 29 )

class DisjointSet {
public:
	vector<int> rank, p;

	DisjointSet() {}
	DisjointSet(int size) {
		rank.resize(size, 0);
		p.resize(size, 0);
		for (int i = 0; i < size; i++) makeSet(i);
	}

	void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}

	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}

	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}

	void link(int x, int y) {
		if (rank[x] > rank[y]) {
			p[y] = x;
		}
		else {
			p[x] = y;
			if (rank[x] == rank[y]) {
				rank[y]++;
			}
		}
	}

	int findSet(int x) {
		if (x != p[x]) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
};

class Edge {
public:
	int source, target, cost;
	Edge(int source = 0, int target = 0, int cost = 0) :
		source(source), target(target), cost(cost) {}
	bool operator < (const Edge& e) const {
		return cost < e.cost;
	}
};

int kruskal(int N, vector<Edge> edges) {
	int totalCost = 0;
	sort(edges.begin(), edges.end());
	DisjointSet dset = DisjointSet(N + 1);

	int source, target;
	for (int i = 0; i < edges.size(); i++) {
		Edge e = edges[i];
		if (!dset.same(e.source, e.target)) {
			totalCost += e.cost;
			dset.unite(e.source, e.target);
		}
	}
	return totalCost;
}

int main(void)
{
	int N, M, cost;
	int source, target;

	cin >> N >> M;

	vector<Edge> edges;
	for (int i = 0; i < M; i++) {
		cin >> source >> target >> cost;
		edges.push_back(Edge(source, target, cost));
	}

	cout << kruskal(N, edges) << endl;

	return 0;
}


Measured memory_bytes: 5428
import math

def segfunc(x,y):
  return math.gcd(x,y)

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


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

Tree = SegmentTree(A, segfunc, 0)
ans = 0
for i in range(N):
  Tree.update(i,0)
  ans = max(ans,Tree.sum(0,N))
  Tree.update(i,A[i])
print(ans)

Measured memory_bytes: 88156
#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);

    string S;
    cin >> S;
    ll N = S.length();
    cout << S;

    if (S[N - 1] == 's')
        cout << "es" << endl;
    else
        cout << "s" << endl;
    return 0;
}

Measured memory_bytes: 3656
n, k = map(int, input().split())
k = min(n - 1, k)

mod = 10 ** 9 + 7
fact = [1] * (n + 1)
ifact = [1] * (n + 1)

for i in range(n):
    fact[i + 1] = fact[i] * (i + 1) % mod
    ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


ans = 0
for i in range(k + 1):
    ans += comb(n, i) * comb(n - 1, n - i - 1) % mod
    ans %= mod
print(ans)


Measured memory_bytes: 79552
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;


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


void solve(){
	ll a,v;
	cin >> a >> v;
	ll b,w;
	cin >> b >> w;
	ll t;
	cin >> t;
	ll dist = abs(a-b);
	if(v<=w){
		cout << "NO" << endl;return;
	}
	ll speed = abs(v-w);
	if(ceil(dist*1.0/speed*1.0)<=t){
		cout << "YES" << endl;return;
	}
	cout << "NO" << endl;

}

int main(){
	fast;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	// int t;cin >> t;while(t--)
		solve();
}


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

#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

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

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



int main(){
    int N;
    string S;
    cin >> N >> S;

    int ans = 0;
    for(int i = 0; i< N ;){
        while(S[i] == S[i+1] && i+1 < N){
            i++;
        }
        ans +=1;
        i++ ;
    }
    cout << ans << endl;

}


Measured memory_bytes: 3764
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil

int main() {
    long int N;
    std::cin >> N;
    
    long int num = N;
    for (int i=0; i<3; ++i) {
        if (num%10 == 7) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
        num /= 10;
    }
    std::cout << "No" << std::endl;
    return 0;
    
}


Measured memory_bytes: 3104
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>

int main(){

  long long int A, B;
  scanf("%lld%lld", &A, &B);

  std::cout << 6 - A - B << std::endl;

  return 0;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, ans = 0;
  string S;
  cin >> n  >> S;
  for (int i=0;i<10;i++){
    for (int j=0;j<10;j++){
      for (int k=0;k<10;k++){
        int cnt=0,iflag=0,jflag=0;
        while (true){
          if (cnt >= n) break;
          if (iflag == 0 && S[cnt] == '0'+i){
            iflag = 1;
            cnt += 1;
            continue;
          }
          if (iflag == 1 && jflag == 0 && S[cnt] == '0'+j){
            jflag = 1;
            cnt += 1;
            continue;
          }
          if (jflag == 1 && S[cnt] == '0'+k){
            ans ++;
            break;
          }
          cnt ++;
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3692
n,t,s=map(int,raw_input().split())
ab=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(t+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(1,t+1):
        if j<ab[i][1] or j-ab[i][1]<s<j:
            dp[i+1][j]=dp[i][j]
            continue
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i][1]]+ab[i][0])
print(max(dp[n]))

Measured memory_bytes: 220672