akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cctype>
const int N=200050;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
inline int rdc(){
	char c=getchar();
	while(!isupper(c))c=getchar();
	if(c=='L')return 0;
	else if(c=='R')return 1;
	else if(c=='U')return 2;
	else if(c=='D')return 3;
}
int s[N],t[N],h,w,n;
inline bool check(int x,int y,int d){
	int i,tx,ty;
	for(i=0;i<n;++i){
		if(s[i]==d){
			x+=dx[d];y+=dy[d];
			if(!x||x>h||!y||y>w)return 1;
		}
		if(t[i]==(d^1)){
			tx=x+dx[d^1];ty=y+dy[d^1];
			if(tx&&tx<=h&&ty&&ty<=w){x=tx;y=ty;}
		}
	}
	return 0;
}
int main(){
	int x,y,i,l=1,r,m,s1,s2;
	scanf("%d%d%d%d%d",&h,&w,&n,&x,&y);
	for(i=0;i<n;++i)s[i]=rdc();
	for(i=0;i<n;++i)t[i]=rdc();
	r=w;s1=0;
	while(l<=r){
		m=l+r>>1;
		if(check(1,m,0)){s1=m;l=m+1;}
		else r=m-1;
	}
	l=1;r=w;s2=w+1;
	while(l<=r){
		m=l+r>>1;
		if(check(1,m,1)){s2=m;r=m-1;}
		else l=m+1;
	}
	if(y<=s1||y>=s2){
		puts("NO");
		return 0;
	}
	l=1;r=h;s1=0;
	while(l<=r){
		m=l+r>>1;
		if(check(m,1,2)){s1=m;l=m+1;}
		else r=m-1;
	}
	l=1;r=h;s2=h+1;
	while(l<=r){
		m=l+r>>1;
		if(check(m,1,3)){s2=m;r=m-1;}
		else l=m+1;
	}
	if(x<=s1||x>=s2){
		puts("NO");
		return 0;
	}
	puts("YES");
	return 0;
}

Measured memory_bytes: 1792
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    lis = list(map(int, input().split()))
    lis.sort(reverse=True)
    count = 0

    for i in range(len(lis)-1):
        count += abs(lis[i] - lis[i+1])
    print(count)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9560
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int N=3e3+5;
ll a[N],dp[N][N];
int main()
{
	int n,i,j,L,R;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(L=n;L>=1;L--)
	{
		for(R=L;R<=n;R++)
		{
			dp[L][R]=max(a[L]-dp[L+1][R],a[R]-dp[L][R-1]);
		}
	}
	printf("%lld\n",dp[1][n]);
	return 0;
}

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

long long N,D;

int main(){
	cin>>N>>D;
	long long maxim=D*D,total=0;
	for(int i=0; i<N; i++){
		long long p,q;
		cin>>p>>q;
		if(maxim>=p*p+q*q){
			total++;
		}
	}
	cout<<total<<'\n';
}

Measured memory_bytes: 3632
#define REP(i, t, n)  for (int i = t; i < n; i++)
#define ALL(n)        (n).begin(),(n).end()
#include <limits.h>
#include <stdio.h>
#include <cmath>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <functional>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef bool               BOOL;
typedef short              WORD;
typedef unsigned short     U_WORD;
typedef long               DWORD;
typedef unsigned long      U_DWORD;
typedef long long          QWORD;
typedef unsigned long long U_QWORD;

#define INF (100000)
#define N_MAX (20)

DWORD N;
DWORD adwInputP[N_MAX];

void solve_main()
{
	DWORD dwAns = 0;

	cin >> N;
	REP(i, 0, N) {
		cin >> adwInputP[i];
	}

	REP(i, 1, (N - 1)) {
		priority_queue<DWORD> que;
		for (int j = i - 1; j <= i + 1; j++) {
			que.push(adwInputP[j]);
		}
		que.pop();
		if (que.top() == adwInputP[i]) {
			dwAns++;
		}
	}
	cout << dwAns << endl;
}

int main()
{
#ifdef FOR_IDE
	ifstream in("input.txt");
	cin.rdbuf(in.rdbuf());
#endif

	solve_main();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int a, b; cin>>a>>b;
    for (double i = 1; i <= 2000; ++i) {
        int A = floor(i*0.08);
        int B = floor(i*0.10);
        if (A==a&&B==b) {
            cout << (int)i << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    return 0;
}

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

int main() {
	int i,N,m,d,s;
	d=10;
	cin >> N;
	for (int k=0; k<N; k++) {
		cin >> m;
		while (m>9) {
			i += 1;
			while (m % d != m) {
				int lower = m%d;
				int upper = (m-lower)/d;
				int mlp = lower * upper;
				if(s < mlp) s = mlp;
				d *= 10;
			}
			m = s;
			d=10;
			s=0;
		}
		cout << i << endl;
		i=0;
	}
}

Measured memory_bytes: 1160
n = int(input())
*arr, = map(int, input().split())
modulo = 10 ** 9 + 7
p = arr.copy()
p.append(0)
for i in range(len(p) - 2, -1, -1):
    p[i] = (p[i] + p[i + 1]) % modulo

ans = 0
for i in range(n):
    ans += arr[i] * p[i + 1]
    ans %= modulo
print(ans)





Measured memory_bytes: 104668
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
	string yan;
	cin >> yan;
	string a, b;
	for (int i = yan.size() - 2; i >= 0; i--) {
		a = yan.substr(0, i);
		b = yan.substr(0, i / 2);
		if (b + b == a) {
			cout << a.size() << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long int lli;
const lli mod = 1e9+7;
const lli inf = 1e18;
typedef pair<int ,int> pii;
typedef pair<lli, lli> pll;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int allxor = 0;
    for(int i=0; i<n; i++){
        allxor ^= a[i];
    }
    for(int i=0; i<n-1; i++){
        cout << (allxor^a[i]) << " ";
    }
    cout << (allxor^a[n-1]) << endl;
    return 0;
}


Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    char c;
    cin>>c;
    if(islower(c)) cout<<"a";
    else cout<<"A";
    return 0;
}

Measured memory_bytes: 3616
n=int(input())
a=list(map(int,input().split()))
b=[i**2 for i in a]
#sum_=sum(b)-2*p*sum(a)+n*p**2
c=sum(a)
def tai(p):
    return n*p**2-2*p*c
d=[]
for i in range(min(a)-2,max(a)+2):
    d.append(tai(i+1))
print(min(d)+sum(b))

Measured memory_bytes: 3064
/**
*   @Author : MeGaCrazy
*   @InitTime : Sat Jan 05 02:35:59 2019
*   @Idea :
*
*
*
*
*
*  Happy Solving :)
**/
#include <bits/stdc++.h>
using namespace std;
int main(){
#ifndef ONLINE_JUDGE
   //freopen("in","r",stdin);
   //freopen("out","w",stdout);
#endif
  int n,m;
  cin>>n>>m;
  if(abs(n-m)>1){
   	cout<<"0"<<endl;
   	return 0;
  }
  long long a=1;
  long long b=1;
  for(int i=2;i<=n;i++){
  	a=(a*i)%(int)(1e9+7);
  }
  for(int i=2;i<=m;i++){
  	b=(b*i)%(int)(1e9+7);
  }
  if(a!=b){
  	cout<<(a*b)%(int)(1e9+7)<<endl;
  }else{
  	cout<<(a*b*2)%(int)(1e9+7)<<endl;
  }



}

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

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  int count = 0;
  for(int i = min(A,B); i > 0; i--) {
    if(A%i == 0 && B%i == 0) {
      count++;
    }
    if(count == K) {
      cout << i << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
import java.util.Scanner;

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

        while(true) {
            String num = sc.next();
            int[] x;
            x = new int[1000];
            int length = num.length();
            int sum = 0;

            for (int i = 0; i < length; i++)
                x[i] = num.charAt(i) - '0';

            for (int i = 0; i < length; i++)
                sum += x[i];

            if (sum == 0) {
                break;
            } else {
                System.out.println(sum);
            }
        }
    }
}



Measured memory_bytes: 26716
#include <stdio.h>
int main(){
  int i,j,N,flag,change;
  int A[100];
  scanf("%d",&N);
  for(i=0;i < N;i++){
    scanf("%d",&A[i]);
  }

 
  flag=0;
  for(i=0; i < N-1; i++){
    for( j=N-1; j > i ; j--){
      if(A[j] < A[j-1]){
	change = A[j];
	A[j]=A[j-1];
	A[j-1]=change;
	flag++;
      }
      
    }
  }

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



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

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

int main() {
  int n;
  ll k,r,s,p,answer=0;
  cin>>n>>k>>r>>s>>p;
  string t;
  cin>>t;
  vector<vector<int>> vec(k,vector<int>(3));
  for(int i=k;i<n;i++){
    if(t.at(i)==t.at(i-k)){
      t.at(i)='x';
    }
  }
  for(int i=0;i<n;i++){
    if(t.at(i)=='r'){
      answer+=p;
    }
    if(t.at(i)=='s'){
      answer+=r;
    }
    if(t.at(i)=='p'){
      answer+=s;
    }
  }
  cout<<answer<<endl;
}

Measured memory_bytes: 5120
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { 
 
	public static void main(String[] args) { 
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		long[] pref = new long[N];
		long[] suff = new long[N];
		long[] arr = new long[N];
		for (int i = 0; i < N; i++) {
			arr[i] = input.nextLong();
		}
		pref[0]=arr[0]; //Prefix and suffix sums using a dp approach
		suff[N-1]=arr[N-1];
		for (int i = 1; i < N; i++) {
			long prev = pref[i-1];
			long cur = arr[i];
			pref[i]=GCD(prev,cur);
		}
		for (int i = N-2; i >=0; i--) {
			long prev = suff[i+1];
			long cur = arr[i];
			suff[i]=GCD(prev,cur);
		}
		long ans = pref[N-1]; //Assuming max GCD is GCD of entire tuple to begin with
		ans=Math.max(ans, suff[1]);//Excluding first number
		ans=Math.max(ans, pref[N-2]);//Excluding last number
		for (int cur = 1; cur < N-1; cur++) {
			int prefIndex = cur-1;
			int suffIndex = cur+1;
			long L = pref[prefIndex];
			long R = suff[suffIndex];
			ans=Math.max(ans, GCD(L,R)); //Excluding intermediate elements
		}
		System.out.println(ans);
	}
	public static long GCD(long a, long b) { //Euclidean GCD
		if (a==0||b==0) return Math.max(a, b);
		return GCD(Math.max(a, b)%Math.min(a, b),Math.min(a, b));
	}
}

Measured memory_bytes: 62732
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<int>G[1<<17];
pair<int,bool>dfs(int u,int p)
{
	int now=0,cnt=0;
	bool flag,tmp=false;
	for(int v:G[u])
	{
		if(v!=p)
		{
			pair<int,bool>p=dfs(v,u);
			now+=p.first;
			cnt++;
			flag=p.second;
			tmp|=p.second;
		}
	}
	return cnt==0?make_pair(1,true):cnt==1?make_pair(now,flag):make_pair(now-tmp,false);
}
main()
{
	cin>>N;
	for(int i=1;i<N;i++)
	{
		int a,b;cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	bool flag=true;
	for(int i=0;i<N;i++)flag&=G[i].size()<=2;
	if(flag)
	{
		cout<<1<<endl;
		return 0;
	}
	int r=0;
	while(G[r].size()<=2)r++;
	int ans=0;
	flag=false;
	for(int v:G[r])
	{
		pair<int,bool>p=dfs(v,r);
		ans+=p.first;
		flag|=p.second;
	}
	cout<<ans-flag<<endl;
}

Measured memory_bytes: 10624
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int qty = sc.nextInt();

		int price[] = new int[qty];
		int maxPrice = 0;
		int maxindex = 0;
		int sum = 0;
		for(int i = 0; i < qty; i ++) {
			price[i] = sc.nextInt();
			if(price[i] > maxPrice) {
				maxPrice = price[i];
				maxindex = i;
			}
			sum += price[i];
		}
		sum -= price[maxindex] / 2;

		System.out.println(sum);
	}
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

int main(){
    int n; cin>>n;
    map<long long,int> mp; vector<long long> v(n);
    rep(i,n){
        cin>>v[i];
        mp[v[i]]++;
    }
    sort(all(v)); v.erase(unique(v.begin(),v.end()),v.end()); reverse(all(v));
    long long t[35]; t[0]=1;
    for(long long i=1;i<35;i++) t[i]=t[i-1]*2;
    reverse(t,t+35);
    long long ans=0;
    for(auto i:v){
        rep(jj,35){
            long long j=t[jj];
            if(j-i>0){
                long long tmp;
                if(j-i==i) tmp=mp[i]/2;
                else tmp=min(mp[i],mp[j-i]);
                // cout<<i<<" "<<j<<" "<<tmp<<endl;
                ans+=tmp;
                mp[i]-=tmp;
                mp[j-i]-=tmp;
            }else{
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 95232
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int> h;
	int temp=0;
	int ans=0;
	for(int i=0;i<n;i++)
	{
		int k;
		cin>>k;
		if(k>=max(temp,k))
		{
			temp=k;
			ans++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define REPR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m, n) for(int i = m-1; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))
#define FILL2D(A,c) fill(A[0], A[0] +sizeof(A)/sizeof(**A),c)
#define FILL3D(A,c) fill(A[0][0], A[0][0] +sizeof(A)/sizeof(***A),c)
using namespace std;
typedef long long ll;
int main(){
    int a,b,ans;
    ans=-1;
    cin>>a>>b;
    for(int i=1;i<1010;i++){
    if(i*2/25==a&&i/10==b){
        ans=i;
        break;
    }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
pair<int,int> s[100010];

bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first < b.first;
}


int main(){

    int n;
    long long k;
    long long sum = 0;

    cin >> n >> k;
    int a,b;
    for(int i=0;i<n;i++){
        cin >> a >> b;
        s[i].first = a;
        s[i].second = b;
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++){
        sum += (long long)s[i].second;
        if(sum >= k){
            cout << s[i].first << endl;
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 1024
object Main {
  import java.util.Scanner

  def readStrings(n: Int)(implicit sc: Scanner): Array[String] = Array.fill(n) { sc.next() }
  def readInts(n: Int)(implicit sc: Scanner): Array[Int] = Array.fill(n) { sc.nextInt() }
  def readLongs(n: Int)(implicit sc: Scanner): Array[Long] = Array.fill(n) { sc.nextLong() }
  def readLineStrings(implicit sc: Scanner): Array[String] = sc.nextLine().split(' ')
  def readLineInts(implicit sc: Scanner): Array[Int] = readLineStrings.map(_.toInt)
  def readLineLongs(implicit sc: Scanner): Array[Long] = readLineStrings.map(_.toLong)

  def main(args: Array[String]): Unit = solve(new Scanner(System.in))

  def solve(implicit sc: Scanner): Unit = {
    val Array(a, b) = readInts(2)
    val ans = if ((a % 2 == 0) || (b % 2 == 0)) "No" else "Yes"
    println(ans)
  }
}


Measured memory_bytes: 25784
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if max(a[i], a[j], a[k]) * 2 < sum([a[i], a[j], a[k]]):
                if a[i] != a[j] and a[i] != a[k] and a[j] != a[k]:
                    cnt += 1
print(cnt)


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

char S[] = "CODEFESTIVAL2016";
char T[17];

int main() {
    scanf("%s", T);
    int res = 0;
    for (int i = 0; i < 16; i++)
        if (S[i] != T[i]) res++;
    printf("%d\n", res);
    return 0;
}

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

int main(){
	int N, D, X;
	cin >> N >> D >> X;
	int A[N];
	rep(i,N) cin >> A[i];

	rep(i,N)rep(j,101) {
			int d = j*A[i]+1;
			if (d>D) break;
			X++;
	}
	cout << X << endl;

	return 0;
}


Measured memory_bytes: 3564
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    int m;
    cin >> m;
    vector<string> t(m);
    for (int i = 0; i < m; i++) {
        cin >> t[i];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int score = 0;
        for (int j = 0; j < n; j++) {
            if (s[i] == s[j]) {
                score++;
            }
        }
        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) {
                score--;
            }
        }
        ans = max(ans, score);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define lim 200005
#define mod 1000000007
#define nfs_mw ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

bool Q;
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const {
		return Q ? p < o.p : k < o.k;
	}
};

//Line equation is k*x + m
//works for maximum, negate values for minimum
struct LineContainer : multiset<Line> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
		return l.k * x + l.m;
	}
	void min_add(ll k, ll m) {
		add(-k, -m);
	}
	ll min_query(ll x) {
		return -query(x);
	}
};



int main()
{
    nfs_mw;
    int i,j,n; ll c, h, dp[lim] = {};
    cin>>n>>c;
    LineContainer idk;
    dp[0] = 0; cin>>h;
    idk.min_add(-2*h, dp[0] + h*h + c);
    for(i=1; i<n; i++){
    	cin>>h;
    	dp[i] = idk.min_query(h) + h*h;
    	idk.min_add(-2*h, dp[i] + h*h + c);
    }
    cout<<dp[n-1];
}

Measured memory_bytes: 14336
def solve(N, M, K, S, P):
    ret = 0
    for i in range(pow(2, N)):
        turned_on_switches = []
        for j in range(N):
            if i >> j & 1:
                turned_on_switches.append(j)
        for k in range(M):
            kth_turned_on_lights_num = 0
            for s in S[k]:
                kth_turned_on_lights_num += 1 if s - 1 in turned_on_switches else 0
            if kth_turned_on_lights_num % 2 != P[k]:
                break
        else:
            ret += 1
    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        tmp = list(map(int, input().split()))
        K.append(tmp[0])
        S.append(tmp[1:])
    P = list(map(int, input().split()))
    solve(N, M, K, S, P)

Measured memory_bytes: 42992
#include <bits/stdc++.h>
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define INF 1e9
using namespace std;
typedef long long ll;

signed main() {
  // std::ifstream in ("input.txt"); std::cin.rdbuf(in.rdbuf());
  int a, b;
  cin >> a >> b;

  if ((a + b) % 2 == 1){
    cout << "IMPOSSIBLE" << endl;
  } else {
    cout << (a + b) / 2 << endl;
  }
}



Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#include <bits/stdc++.h>
//~ #include <atcoder/all>
using namespace std;
using ll = long long;
//~ using P = pair<int, int>;

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;
}
//~ int A = (1<<2) | (1<<3) | (1<<5) | (1<<7);
//~ for (int bit=A; ; bit=(bit-1)&A){
//~ if (!bit) break;
//~ }
int next_combination(int sub)
{
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}
//~ int n=5;
//~ int k=3; // nCkの組み合わせ、ただしk=0には対応してない
//~ int bit=(1<<k)-1; // 1000 -> 0111
//~ for(; bit < (1<<n); bit=nex_combination(bit){
//~ }
bool isPrime(int a)
{
    if (a == 2)
        return true;
    if (a <= 1 || a % 2 == 0)
        return false;

    for (int i = 3; i * i <= a; i += 2)
    {
        if (a % i == 0)
            return false;
    }
    return true;
}
//~ vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};
vector<int> a;
// index が条件を満たすかどうか
bool isOK(int index, int key)
{
    if (a[index] >= key)
        return true;
    else
        return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key)
{
    int ng = -1;            //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1)
    {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//~ int v[100100];
//~ int INF = 1 << 30;
//~ vector<vector<int>> dp(310, vector<int>(310));
//~ ll dp[110][100100];
//~ vector<int> dp(100100, 0));

//~ int seen[110];
//~ int ans[110][2];
//~ ll MOD = 1e9 + 7;

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

    vector<int> a(n);

    rep(i, n) cin >> a[i];

    sort(a.rbegin(), a.rend());

    int alice = 0;
    int bob = 1;
    vector<int> sum(2);
    rep(i, n)
    {
        sum[i % 2] += a[i];
    }

    cout << sum[alice] - sum[bob] << endl;

    return 0;
}


Measured memory_bytes: 3680
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>
#include <iomanip>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define Imax 2147483647
#define ll long long
#define asort(a) sort(a.begin(),a.end());

using namespace::std;

int jo(ll int jxo, ll int jyo){//累乗
	ll int jhogeo = 1;
	rep(jinto,0,jyo) jhogeo=jhogeo*jxo;
	return jhogeo;
}
char tobig(char toxbig){//char大文字化
  return (toxbig-0x20);
}
char tolow(char toxlow){//char小文字化
  return (toxlow+0x20);
}
int ctoi(char cctoi){//char->int
  if('0' <= cctoi && cctoi <= '9') return (cctoi-'0');
  return -1;
}
int gcd(int gcad, int gcbd) {//最大公約数
  if(gcad < gcbd) return gcd(gcbd, gcad);
  int gcrd;
  while ((gcrd=gcad%gcbd)) {
    gcad = gcbd;
    gcbd = gcrd;
  }
  return gcbd;
}
int lcm(int lcam, int lcbm){//最小公倍数
 return (lcam*lcbm)/gcd(lcam,lcbm);
}


int main(){
  int n,m,c;
  cin>>n>>m>>c;
  vector<int> b(m);
  vector<vector<int>> a(n, vector<int>(m));
  rep(i,0,m) cin>>b[i];
  rep(i,0,n){
    rep(j,0,m){
      cin>>a[i][j];
    }
  }
  int hoge;
  int count=0;
  rep(i,0,n){
    hoge=0;
    rep(j,0,m) hoge=hoge+a[i][j]*b[j];
    hoge+=c;
    if(hoge>0) count++;
  }
  cout<<count;
   
  
}
// int *p = new int[N];

//  vector<int> 変数名(要素数);
//  sort(変数名.begin(),変数名.end());//昇順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<long long> s(n);
	for(int i=0;i<n;i++)
	cin>>s[i];
	sort(s.rbegin(),s.rend());
	long long ans=0;
	if(n%2==0)
	{
		int t=n/2;
		for(int i=0;i<t;i++)ans+=s[i];
		for(int i=0;i<t-1;i++) ans+=s[i+1];
	}
	else
	{
		int t=n/2;
		for(int i=0;i<t;i++)ans+=s[i];
		for(int i=0;i<t;i++) ans+=s[i+1];
	}
	cout<<ans;
	return 0;
} 

Measured memory_bytes: 4840
#!/usr/bin/env python
# -*- coding: utf-8 -*-

dp = [0 for i in range(31)]
dp[1] = 1
dp[2] = 1
dp[3] = 1

for i in range(1,31):
    for j in range(1,4):
        if i-j > 0:
            dp[i] += dp[i-j]

while True:
    N = int(raw_input())
    if N == 0:
        break
    print(int(dp[N]/10//365)+1)
    

Measured memory_bytes: 4220
import java.util.Scanner;

public class Main {
    static Scanner stdIn = new Scanner(System.in);
    public static void main(String[] args){
        int n = stdIn.nextInt();
        int[] d1 = new int[n];
        int[] d2 = new int[n];
        for(int i=0; i<n; i++){
            d1[i] = stdIn.nextInt();
            d2[i] = stdIn.nextInt();
        }

        for(int i=0; i<n-2; i++){
            if((d1[i] == d2[i]) && (d1[i+1] == d2[i+1]) && (d1[i+2] == d2[i+2])){
                System.out.println("Yes");
                return;
            }
        }

        System.out.println("No");
    }
}

Measured memory_bytes: 35988
N = int(input())
a = list(map(int, input().split(' ')))

even = [i for i in a if i % 2 == 0 and i % 4 != 0]
odd = [i for i in a if i % 2 != 0]
by4 = [i for i in a if i % 4 == 0]
if len(odd) <= len(by4):
    print('Yes')
elif len(odd) - len(by4) == 1:
    if len(even) == 0:
        print('Yes')
    else: print('No')
else:
    print('No')

Measured memory_bytes: 14252
n, m, x = map(int, input().split())
a = list(map(int, input().split()))

l = list(range(n))[:x]
r = list(range(n))[x+1:]
lcost = 0
rcost = 0

for i in range(len(l)):
    if l[i] in a:
        lcost += 1

for i in range(len(r)):
    if r[i] in a:
        rcost += 1

print(min(lcost, rcost))



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

using ll = long long;
const int AMAX = 100000;
ll cnt[AMAX + 1];
 
int main(void) {
 int N;
 ll K;
 cin >> N >> K;

 for (int i = 0; i < N; ++i) {
 int A, B;
 cin >> A >> B;
 cnt[A] += B;
 }

 for (int ans = 1; ans <= AMAX; ++ans){
 if (K <= cnt[ans]) {
 cout << ans << endl;
 break;
 }
 K -= cnt[ans];
 }

 return 0;
 }

Measured memory_bytes: 1024
// D - Bouquet
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N,A,B;
ll MOD = 1000000007;

// a^n mod m を計算する(二分累乗法:O(logn))
ll modpow(ll a, ll n, ll m) {
	ll res = 1;
	while(n > 0){
		if(n & 1) res = res * a % m;
		a = a * a % m;
		n >>= 1;
	}
	return res;
}

// nCr mod m
ll nCr(ll n, ll r, ll m){
	ll a = 1, b = 1;
	for(ll i=0; i<r; ++i){
		a = a * (n-i) % m;
		b = b * (r-i) % m;
	}
	return a * modpow(b, m-2, m) % m;
}

ll solve(){
	ll sum_nCr = modpow(2, N, MOD) - 1;
	ll nca = nCr(N, A, MOD);
	ll ncb = nCr(N, B, MOD);
	ll ans = (sum_nCr - (nca + ncb)%MOD)%MOD;
	if(ans < 0L) ans += MOD;
	return ans;
}

int main(){
	cin>>N>>A>>B;
	cout<< solve() <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

vector<int> Eratosthenes(ll n) {
  vector<int> res(n + 1, 1);
  res[0] = res[1] = 0;
  for (ll i = 2; i * i <= n; i++)
    if (res[i]) {
      for (ll j = 2; i * j <= n; j++) res[i * j] = 0;
    }
  return res;
}

int main() {
  const ll M = 1e5;
  vector<int> isPrime = Eratosthenes(M + 1);
  vector<ll> cnt(M + 1, 0);
  FOR(i, 1, M + 1) {
    if (i % 2 == 0) {
      cnt[i] = cnt[i - 1];
      continue;
    }
    if (isPrime[i] && isPrime[(i + 1) / 2]) {
      cnt[i] = cnt[i - 1] + 1;
    } else {
      cnt[i] = cnt[i - 1];
    }
  }

  ll q;
  cin >> q;
  while (q--) {
    ll l, r;
    cin >> l >> r;
    cout << cnt[r] - cnt[l - 1] << endl;
  }
}

Measured memory_bytes: 1792
n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]

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

# bfs
milestone = [0] * (n+1)
q = []
q.append(1)
while len(q) != 0:
    for i in graph[q[0]]:
        if milestone[i] == 0:
            milestone[i] = q[0]
            q.append(i)
    q.pop(0)

print("Yes")
for i in range(2, n+1):
    print(milestone[i])

Measured memory_bytes: 33808
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

ll n;
vector<pair<ll, ll>> ab;

void solve() {
    // sort from bigger.
    sort(ab.begin(), ab.end(),
         [](pair<ll, ll> a, pair<ll, ll> b) { return a.first + a.second > b.first + b.second; });
    ll ans = 0;
    rep(i, n) {
        if (i % 2 == 0) ans += ab[i].first;
        else ans -= ab[i].second;
    }
    cout << ans << endl;
}

int main() {
    cin >> n;
    rep(i, n) {
        ll a, b;
        cin >> a >> b;
        ab.emplace_back(make_pair(a, b));
    }
    solve();
    return 0;
}

Measured memory_bytes: 2420
X, Y = map(int, input().split())
ans = 0
if X == 1 and Y == 1:
    ans = 1000000
else:
    if X == 1:
        ans += 300000
    elif X == 2:
        ans += 200000
    elif X == 3:
        ans += 100000
    if Y == 1:
        ans += 300000
    elif Y == 2:
        ans += 200000
    elif Y ==3:
        ans += 100000
print(ans)

Measured memory_bytes: 38384
import sys
import numpy as np
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    np.set_printoptions(threshold=20)
    A, B, C = map(int, input().rstrip().split())
    K = int(input())
    # A < B < C
    while A >= B:
        B *= 2
        K -= 1
    while B >= C:
        C *= 2
        K -= 1
    if K >= 0:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 27208
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define divceil(A, B) ((A + (B - 1)) / B)
#define MODN 998244353
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr

using namespace std;

int main(){

    int x;
    cin >> x;

    vector<bool> dp(100001, false);

    dp[0] = true;

    for(int i = 1; i <= x; i++){

        if(i - 100 >= 0 && dp[i - 100]){
            dp[i] = true;
        }else if(i - 101 >= 0 && dp[i - 101]){
            dp[i] = true;
        }else if(i - 102 >= 0 && dp[i - 102]){
            dp[i] = true;
        }else if(i - 103 >= 0 && dp[i - 103]){
            dp[i] = true;
        }else if(i - 104 >= 0 && dp[i - 104]){
            dp[i] = true;
        }else if(i - 105 >= 0 && dp[i - 105]){
            dp[i] = true;
        }
    }

    if(dp[x]){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T &a){int t = 0;for(auto itr :a){if(t++)cout << " "; cout << itr;} cout <<endl; }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    //    std::ios_base::sync_with_stdio(false);
    //    cin.tie(NULL);
    int n; cin >> n;
    map<int,int>mp;
    rep(i,n){
        int num; cin >> num;
        mp[num]++;
    }
    int odd  = 0, even = 0;
    for(auto e : mp){
        if(e.second % 2)++odd;
        even += e.second - 1;
    }
    cout << mp.size() - (even % 2 != 0) << endl;
}




Measured memory_bytes: 6528
include Math
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

def printd(str)
  print str if $debugFlag
end

# input
arr = []
lc = 0
nn = 0
dd = 0
while l = $stdin.gets do
  if lc == 0
    tmp = l.chomp.split(" ").map(&:to_i)
    nn = tmp[0]
    dd = tmp[1]
  else
    arr << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

# input check

# body
if $debugFlag
  p nn
  p dd
  p arr
end

cnt = 0
for i in 0..nn-2
  for j in i+1..nn-1

    sum = 0
    for k in 0..dd-1
      sum += (arr[i][k] - arr[j][k])*(arr[i][k] - arr[j][k])
    end
    sqrtSum = sqrt(sum)
    pd sqrtSum
    if sqrtSum.ceil == sqrtSum.floor
      cnt += 1
    end
    
  end
end


puts cnt


Measured memory_bytes: 1788
import math
N,H = input().split()
n = int(N)
h = int(H)
da = 0
db = [0] * n
for i in range(n):
    a,b = tuple(map(int,input().split()))
    da = max(a,da)
    db[i] = b
db.sort()      
#　その都度最大値を持ってくる
#　持ってきたのが2番目の要素なら消す、1番目の要素なら維持する
total = 0 
i = 0
while total < h:
    if db[-1] >= da:
        total += db.pop()
        if len(db) == 0:
            i += math.ceil((h - total)/da) + 1
            break
    else:
        i += math.ceil((h - total)/da) 
        break
    i += 1
print(str(i))

Measured memory_bytes: 7592
from collections import Counter
from itertools import accumulate

# from copy import deepcopy

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)

# for k in range(1, n + 1):
#     cx = deepcopy(c)

#     count = 0

#     while k <= len(cx):
#         # print(cx)
#         mc = cx.most_common()
#         for key, _ in mc[:k]:
#             cx[key] -= 1
#             if cx[key] < 1:
#                 del cx[key]
#         count += 1

#     print(count)

cv = Counter(c.values())
max_take = max(cv.keys())

lx = list(accumulate(cv[i] for i in range(max_take + 1)))
rx = list(accumulate(cv[i] * i for i in range(max_take + 1)))
ax = [rx[i] + (lx[-1] - lx[i]) * i for i in range(max_take + 1)]


def bisec(l0, r0, predicate):
    l, r = l0, r0

    while abs(l - r) > 1:
        mid = (l + r) // 2
        if predicate(mid):
            r = mid
        else:
            l = mid

    return r


for k in range(1, n + 1):
    print(bisec(n + 1, 0, lambda x: x * k <= ax[min(x, max_take)]))


Measured memory_bytes: 122296
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int siz=2e5;
const long inf=1e9;
int calc(int x){
	int res = 0;
	while(x > 0){
		int k = 0;
		rep(i,0,20)if(x & (1<<i)) k++;
		x %= k;
		res++;
	}return res;
}
long modpow(long x,int n,long p){
	int i = 0; long res = 1;
	while(n >= (1<<i)){
		if(n & (1<<i)) (res *= x) %= p;
		i++;
		x = (x * x) % p;
	}return res;
}
int main(){
	int N; string s; cin>>N>>s;
	int cnt = 0; int A = 0, B = 0;
	rep(i,0,N) cnt += s[i] - '0';
    rep(i,0,N){
        if(cnt > 1) ((A *= 2) += s[i] - '0') %= (cnt - 1);
        ((B *= 2) += s[i] - '0') %= (cnt + 1);
    }
    int t;
	rep(i,0,N){
        if(cnt == 1 && s[i] == '1'){ cout<<0<<endl; continue; }
		if(s[i] == '1'){
            t = (A - modpow(2, N - i - 1, cnt - 1)) % (cnt - 1);
            (t += cnt - 1) %= (cnt - 1);
        }else{
            t = (B + modpow(2, N - i - 1, cnt + 1)) % (cnt + 1);
            (t += cnt + 1) %= (cnt + 1);
        }cout<<calc(t) + 1<<endl;
	}
}

Measured memory_bytes: 3756
import java.util.Scanner;

public class Main {
	long count = 0;

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

	private void run() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] num = new int[n];
		for (int i = 0; i < n; i++) {
			num[i] = scanner.nextInt();
		}
		mergeSort(num, 0, n);
		System.out.println(count);
	}

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

	}

	private void merge(int[] num, int left, int mid, int right) {
		int n1 = mid - left;
		int n2 = right - mid;
		int[] L = new int[n1 + 1];
		int[] R = new int[n2 + 1];
		for (int i = 0; i < n1; i++) {
			L[i] = num[left + i];
		}
		for (int i = 0; i < n2; i++) {
			R[i] = num[mid + i];
		}
		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;

		int l = 0;
		int r = 0;
		for (int k = left; k < right; k++) {
			if (L[l] < R[r]) {
				num[k] = L[l++];
				count += r;
			} else {
				num[k] = R[r++];
			}
		}

	}
}

Measured memory_bytes: 96724
#include <stdio.h>

	int main(void){

	int a,b,c,temp;
	
	scanf("%d" "%d" "%d", &a, &b, &c);
	
	if(b > c){
			temp = b;
			b = c;
			c = temp;
	}
	if(a > b){
			temp = a;
			a = b;
			b = temp;
	}
	if(b > c){
			temp = b;
			b = c;
			c = temp;
	}
	printf("%d %d %d\n", a, b, c);
	return 0;
	}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mm multimap<ll,ll>
#define mp make_pair
#define pii pair<ll,ll>

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
ll n,w;
cin>>n>>w;
ll arr[n][2];
ll dp[n+1][w+1];
memset(dp,0,sizeof(dp));

for(ll i=1;i<=n;i++)
cin>>arr[i][0]>>arr[i][1];
for(ll i=1;i<=n;i++)
{
    for(ll j=1;j<=w;j++)
    {
        if(j-arr[i][0]>=0)
        dp[i][j]=max(dp[i-1][j-arr[i][0]]+arr[i][1],dp[i-1][j]);
        else
        dp[i][j]=dp[i-1][j];
    }
}
cout<<dp[n][w];


}

Measured memory_bytes: 79232
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))


int main(void)
{
long N, index;
long A, B[200000];
memset(&B, 0, sizeof(long)*200000);

  scanf("%ld", &N);
  for (index = 1; index < N; ++index) {
    scanf("%ld", &A);
    B[A-1]++;
  }
  for (index = 0; index < N; ++index) {
    printf("%ld\n", B[index]);
  }
  
  return 0;
}


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	int l = ri();
	int end = l + n - 1;
	int eat;
	if (l < 0 && end > 0) eat = 0;
	else if (l < 0) eat = end;
	else eat = l;
	std::cout << (l + end) * n / 2 - eat << std::endl;
	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem B

if __name__ == '__main__':
    odd_th_password = input()
    even_th_password = input()
    original_password = ''

    for i in range(max(len(odd_th_password), len(even_th_password))):
        if i < len(odd_th_password):
            original_password += ''.join(odd_th_password[i])
        if i < len(even_th_password):
            original_password += ''.join(even_th_password[i])

    print(original_password)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>

int main(){
  int N; cin >> N;
  int a[N]; rep(i,N) cin >> a[i];
  int tot = 0;
  rep(i,N) tot ^= a[i];
  rep(i,N){
    cout << (a[i]^tot) << endl;
  }
  
  
  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 4308
#include <stdio.h>

int main(){
  int N;
  long long int M=1000LL,K=0LL;
  long long int A[100];
  scanf("%d",&N);
  for(int i=1;i<=N;i++)
    scanf("%lld",A+i);
  A[N+1]=0LL;
  for(int i=1;i<=N;i++){
    M+=A[i]*K;
    K=0LL;
    if(A[i]<=A[i+1]){
      K=M/A[i];
      M-=A[i]*K;
    }
  }
  printf("%lld\n",M);
  return 0;
}

Measured memory_bytes: 1632
import java.util.Scanner;
import java.util.Set;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] forecasts = sc.nextLine().toCharArray();
        char[] facts = sc.nextLine().toCharArray();
        int cnt = 0;
        for(int i=0;i<3;i++){
            if(forecasts[i]==facts[i]){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 21460
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

int main(){

    int n;
    cin >> n;

    vector<string> some_strings(n);
    int m;
    cin >> m;
    
    REP(i,n){cin >> some_strings[i];}

    std::sort(some_strings.begin(), some_strings.end() );

    for(const auto& e : some_strings){
        cout << e;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import math
n, m = [int (x) for x in input().split()]
cnt = 0
for x in range(n):
    a, b = [int(x) for x in input().split()]
    ans = math.sqrt((a*a)+(b*b))
    #print(ans)

    if ans <= m:
        cnt = cnt + 1
print(cnt)

Measured memory_bytes: 9120
#include<stdio.h>
int linearSearch(int A[],int i,int key);
int main(){
  int i,n,o,A[10001],key,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&o);
  for(i=0;i<o;i++){
    scanf("%d",&key);
    if(linearSearch(A,n,key)!=-1){
      sum++;
    }
  }
  printf("%d\n",sum);
  return 0;
}
int linearSearch(int A[],int n,int key){
  int i=0;
  A[n]=key;
  while(A[i]!=key){
    i++;
  }
  if(i==n){
    return -1;
  }
  return i;
}
  



Measured memory_bytes: 2104
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>


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

using namespace std;
typedef long long ll;

int main(){
  string str;
  cin >> str;
  reverse(str.begin(), str.end());

  vector<string> candidates = {"dream", "dreamer", "erase", "eraser"};
  rep(i, candidates.size()){
    reverse(candidates[i].begin(), candidates[i].end());
  }

  int idx = 0;
  int goal_idx = str.size();

  while(1){
    if(idx == goal_idx){
      cout << "YES" << endl;
      return 0;
    }

    bool matched = false;
    for(string candidate: candidates){
      if(str.substr(idx, candidate.size()) == candidate){
        matched = true;
        idx += candidate.length();
        break;
      }
    }

    if(!matched){
      cout << "NO" << endl;
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> p(n);
 for (int i = 0; i < n; i++){
   cin >> p.at(i);
 }
  int ans = 0;
  for (int i = 0; i < n-2; i++){
    if (p.at(i) < p.at(i+1) & p.at(i+1) < p.at(i+2) | p.at(i) > p.at(i+1) & p.at(i+1) > p.at(i+2)){
      ans++;
    }
    else continue;
  }
  cout << ans << endl;
}

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

/*struct mint {
    ll x; // typedef long long ll;
    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 { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }*/

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

    int ans = 1000;
    rep(i, s.size() - 2) {
        int num = (s[i] - 48) * 100 + (s[i + 1] - 48) * 10 + (s[i + 2] - 48);
        ans = min(ans, abs(num - 753));
    }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	ll N; cin >> N;
	ll ans = 1100000000000;
	for (ll i = 1;i < sqrt(N) + 1;++i) {
		if (N % i == 0) {
			ll a = N / i;
			ans = min(ans, a + i - 2);
		}
	}
		cout << ans << "\n";
	return 0;
}

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

int main() {
	int n, k;
	cin >> n >> k;
	int cnt = 0;
	rep(i, n) {
		int h; cin >> h;
		if (h >= k) cnt++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int n,k;
  cin >> n >> k;
  int h[n];
  REP(i,n) cin >> h[i];
  sort(h,h+n);
  int ans = 1e9;
  for(int i = 0; i+k-1 < n; i++){
	ans = min(ans, h[i+k-1]-h[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 640