akhauriyash/Code-Regression huggingface dataset:
class DisjointSet:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y]+=1
     
    def findSet(self, x):
        if(x!=self.p[x]):
            self.p[x]=self.findSet(self.p[x])
        return self.p[x]

def main():
    n,q=list(map(int,input().split()))
    disjointSet = DisjointSet(n)
    for _ in range(q):
        cmds=list(input().split())
        if cmds[0] == '0':
            x,y=list(map(int,cmds[1:]))
            disjointSet.unite(x,y)
        elif cmds[0]=='1':
            x,y=list(map(int,cmds[1:]))
            if disjointSet.same(x,y) == True:
                print(1)
            else:
                print(0)
    
if __name__=='__main__':
    main()



Measured memory_bytes: 6040
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int H,W;
    std::cin >> H >> W ;
    std::vector<string> a(H) ;
    for (int i=0;i<H;i++) std::cin >> a.at(i);
    for (int i=0;i<W+2;i++) {
        std::cout << "#";
    }
    std::cout <<  std::endl;
    for(int i=0;i<H;i++) {
        std::cout << "#"+a.at(i)+"#" << std::endl;
    }
    for(int i=0;i<W+2;i++) std::cout << "#" ;
    return 0;

}


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

int H;
long A[500001];

void maxHeapify(int i) {
  int largest;
  int l = 2*i;
  int r = 2*i+1;

  if (l <= H && A[l] > A[i]) largest = l;
  else largest = i;

  if (r <= H && A[r] > A[largest]) largest = r;

  if (largest != i) {
    swap(A[i], A[largest]);
    maxHeapify(largest);
  }
}

void buildMaxHeap() {
  for (int i = H/2; i > 0; i--)
    maxHeapify(i);
}

int main() {
  cin >> H;
  for (int i = 1; i <= H; i++)
    cin >> A[i];

  buildMaxHeap();

  for (int i = 1; i <= H; i++)
    cout << ' ' << A[i];
  cout << endl;

  return 0;
}

Measured memory_bytes: 5064
//Structured Program I - Print a Frame
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String input;
		
		 while (!(input = in.readLine()).equals("0 0")) {

			 String[] HW = input.split(" ");

			 int H = Integer.parseInt(HW[0]);
			 int W = Integer.parseInt(HW[1]);

			 for(int i=0;i<H;i++){
				 for(int j=0;j<W;j++){
					 
					 if(i%2==j%2 ){
						 System.out.print("#");
					 }else{
						 System.out.print(".");						 
					 }
				 }
				 System.out.println();
			 }
			 System.out.println();
			 
		 }

	}
}

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

int main(){
	int data[101]={},num,max=0;
	while(cin>>num){
		//if(num==0) break;
		data[num]++;
	}
	rep(i,1,101){
		if(data[i]>max) max=data[i];
	}
	rep(i,0,101){
		if(data[i]==max) cout<<i<<endl;
	}
}

Measured memory_bytes: 1160
#include <iostream>
#include <stack>
#include <string>

using namespace std;
int main()
{
	string in_str;
	getline(cin, in_str);
	stack<int> in_stk;
	string tmp;
	int a, b;
	for (char ch : in_str)
	{
		switch (ch)
		{
		case '+':
			a = in_stk.top();
			in_stk.pop();
			b = in_stk.top();
			in_stk.pop();
			in_stk.push(a + b);
			continue;
		case '-':
			a = in_stk.top();
			in_stk.pop();
			b = in_stk.top();
			in_stk.pop();
			in_stk.push(b - a);
			continue;
		case '*':
			a = in_stk.top();
			in_stk.pop();
			b = in_stk.top();
			in_stk.pop();
			in_stk.push(a * b);
			continue;
		case ' ':
			if(tmp.length()!=0) in_stk.push(stoi(tmp));
			tmp.clear();
			continue;
		default:
			tmp += ch;
			continue;
		}
	}
	cout << in_stk.top() << endl;
	return 0;
}


Measured memory_bytes: 3212
#include<stdio.h>
#define MAX 100005
#define NIL -1
 struct Node{
  int p;
  int l;
  int r;
};
struct Node T[MAX];
int n,D[MAX];

void pri(int u){
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if(T[u].p==NIL)printf("root, ");
  else if(T[u].l==NIL)printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for(i=0,c=T[u].l;c!=NIL;i++,c=T[c].r){
    if(i)printf(", ");
printf("%d",c);
  }
printf("]\n");
}

void rec(int u,int p){
  D[u]=p;
  if(T[u].r != NIL)rec(T[u].r,p);
  if(T[u].l !=NIL)rec(T[u].l,p+1);
}

int main(){
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++)T[i].p=T[i].l=T[i].r=NIL;

  for(i=0;i<n;i++){
    scanf("%d%d",&v,&d);
    for(j=0;j<d;j++){
     scanf("%d",&c);
     if(j==0)T[v].l=c;
     else T[l].r=c;
     l=c;
     T[c].p=v;
    }
  }
for(i=0;i<n;i++){
  if(T[i].p==NIL)r=i;
}
rec(r,0);
for(i=0;i<n;i++)pri(i);
return 0;
}



Measured memory_bytes: 6428
while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:break
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, i):
            for k in range(1, j):
                if i + j + k == x:
                    ans += 1
    print(ans)


Measured memory_bytes: 5596
n=int(input())
s=input()

cnt=0
for i in range(1000):
    num=str(i).zfill(3)
    x=s.find(num[0])
    y=s.find(num[1],x+1)
    z=s.find(num[2],y+1)
    if x!=-1 and y!=-1 and z!=-1:
        cnt +=1

print(cnt)

Measured memory_bytes: 38508
#include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<sstream>
#include<fstream>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
/*freopen{"input.txt","r",stdin};
freopen{"output.txt","w",stdout};*/
#define mp make_pair
#define pb push_back
const int INF=1000*1000*1000;
const int maxn=2e5; 
typedef long long ll;
typedef long double ld;
typedef pair<int,int>PII;
//priority_queue <int,vector<int>,greater<int> > q1;  //从小到大 
//priority_queue <int,vector<int>,less<int> >q2;  //从大到小 

//set multiset vector queue priority_queue map multimap pair string structure 

//枚举 思维 贪心 搜索 模拟 预处理 二分 排序 
map<ll,ll>m;
int main(){
	//ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		ll x;
		cin>>x;
		m[x]++;
	}
	vector<ll>v;
	for(auto it=m.begin();it!=m.end();it++){
		if(it->second>=2){
			for(int i=0;i<it->second/2;i++)
			v.pb(it->first);
		}
	}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	ll area=1;
	if(v.size()>=2)
	area=v[0]*v[1];
	else
	area=0;
	cout<<area;
	return 0;
}



Measured memory_bytes: 6528
#include <iostream>
using namespace std;
int main(){
	
	long long d[4001];
	long long ans;
	int n;
	
	for(int i=0;i<=4000;i++)d[i]=0;
	for(int i=0;i<=1000;i++)for(int j=0;j<=1000;j++)d[i+j]++;
	
	while(cin>>n){
		ans=0;
		for(int i=0;i<=n;i++)ans+=(d[i]*d[n-i]);
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 1188
from collections import Counter
n, m = list(map(int, input().split()))
ll = []
x = 0
y = 10 ** 5

for i in range(m):
    l, r = list(map(int, input().split()))
    x, y = max(x, l), min(y, r)

s = (y - x) + 1
if s < 0:
    s = 0
print(s)


Measured memory_bytes: 3444
n=int(input())
a=list(map(int,input().split()))
cnt=0
ans=0
m=10**9+1
for i in a:
    if i<0: cnt+=1
    ans+=abs(i)
    if abs(i)<m: m=abs(i)
if cnt%2==0:
    print(ans)
else:
    print(ans-m*2)

Measured memory_bytes: 20056
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxnn=1e6+7;
const int mod=1e9+7;
const ll inf=1e18+7;
ll sum[maxnn];
void init()
{
    sum[1]=1ll;
    for(ll i=2;i<=100000;i++)
    {
        sum[i]=sum[i-1]*i;
        sum[i]%=mod;
    }
}
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans%mod;
}
ll ny(ll a,ll b)
{
    return a*ksm(b,mod-2)%mod;
}
ll c(ll n,ll m)
{
    if(n<m) return 0;
    if(m==0||n==m) return 1ll;
    return ny(sum[n],sum[n-m]*sum[m]%mod);
}
ll MOD(ll x)
{
    return (x+mod)%mod;
}
int main()
{
    ll n,k;
    init();
    scanf("%lld %lld",&n,&k);
    for(ll i=1ll;i<=k;i++)
    {
        //printf("%lld %lld\n",c(n-k+1,min(i,n-k+1)),c(k-1,min(i,n-k+1)-1));
        printf("%lld\n",MOD(c(n-k+1,i)*c(k-1,i-1)));
    }
    return 0;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			final int M = sc.nextInt();
			
			boolean[] acs = new boolean[N];
			int[] was = new int[N];
			for(int i = 0; i < M; i++) {
				final int p = sc.nextInt() - 1;
				final String status = sc.next();
				
				if(status.equals("AC")) {
					acs[p] = true;
				}else if(!acs[p]){
					was[p] += 1;
				}
			}
			
			int ac_count = 0;
			for(final boolean ac : acs) { ac_count += ac ? 1: 0; }
			
			int wa_count = 0;
			for(int i = 0; i < N; i++) { wa_count += acs[i] ? was[i] : 0; }
			
			System.out.println(ac_count + " " + wa_count);
			
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 40796
#include <iostream>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;
const int INF = 1001001001;

void solve(long long N){
    int mini = INF;
    if (N == 2) mini = min(mini, 2);
    if (N == 3) mini = min(mini, 3);
    for (int i = 2; i <= N - 2; i++) {
        string strA = to_string(i);
        string strB = to_string(N - i);
        int sum = 0;
        REP(j, strA.size())
            sum += strA[j] - '0';
        REP(j, strB.size())
            sum += strB[j] - '0';
        mini = min(mini, sum);
    }
    cout << mini << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
int main()
{
    string a ;
    cin >> a ;
    if(a[0] + a[1] + a[2] == 294 || a[0] + a[1] + a[2] == 198)
    cout << "Yes" ;
    else
    cout << "No" ;
    
    return 0 ;
}


Measured memory_bytes: 256
#import <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
typedef long long INT;
int main(){
    INT N;
    scanf("%lld",&N);
    INT A[100002] = {0};
    INT max=0;
    for(INT i=0;i<N;i++){
        INT a;
        scanf("%lld",&a);
        max=MAX(max,a);
        if (a>0) A[a-1]++;
        A[a]++;
        A[a+1]++;
    }
    INT result = 0;
    for(INT i=0;i<=max;i++){
        result = MAX(result,A[i]);
    }
    printf("%lld", result);
}


Measured memory_bytes: 7888
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	int dp[100100];
	dp[0] = 0;
	for( int i = 1; i <= n; ++i ) dp[i] = INF;
	for( int i = 1; i <= n; ++i ){
		for( int j = 1; j <= n; j *= 6 ){
			if( i < j ) break;
			dp[i] = min(dp[i], dp[i-j]+1);
		}
		for( int j = 9; j <= n; j *= 9 ){
			if( i < j ) break;
			dp[i] = min(dp[i], dp[i-j]+1);
		}
	}
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 640
#include<cmath>
#include<iostream>
#include<bitset>

#define MAX 10001

using namespace std;

bitset<MAX> b1;

void ComputePrimes(){
	b1.set();

	b1.reset(1);
	for(int i = 4; i <= 10000; ++i){
		for(int j = 2; j <= sqrt((double)i); ++j){
			if( i % j == 0 ){
				b1.reset( i );
				break;
			}
		}
	}
}

int main()
{
	ComputePrimes();

	while( true )
	{
		int N, P = 0;
		
		cin >> N;

		if( cin.eof() )
			break;

		for(int i = 1; i <= N; ++i){
			if( b1[N - i + 1] == true && b1[ i ] == true )
				++P;
		}

		cout << P << '\n';
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,m;
	cin>>n>>m;
	long long maxn=1;
	if(n==1){
		cout<<m<<endl;
		return 0;
	}
	double ff=m,fff=n;
	double f=pow(ff,1.0/fff);
	
	//cout<<f<<endl;
	for(long long i=f+1;i>=2;i--){
		long long sum=1;
		for(long long j=0;j<n;j++){
			sum*=i;
			if(sum>m)
				break;
			}
		if(m%sum==0){
			maxn=i;
			break;
		}
	}
	cout<<maxn<<endl;
}

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

namespace ABC
{
    class ProgramA
    {
        static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(" ");
            var a = int.Parse(inputs[0]);
            var b = int.Parse(inputs[1]);
            var result = 0;

            if (a > b)
            {
                result = a - 1;
            }
            else
            {
                result = a;
            }

            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 27308
//
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
//
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 mut $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")
    };
}

// solution 
use std::collections::HashSet;
#[allow(unused_mut)]
#[allow(non_snake_case)]
fn main() {
    input!{
        N: usize,
        S: [chars; N],
    }

    let mut counts = [0_usize; 5];

    for s in S.iter() {
        match s[0] {
            'M' => counts[0] += 1,
            'A' => counts[1] += 1,
            'R' => counts[2] += 1,
            'C' => counts[3] += 1,
            'H' => counts[4] += 1,
             _  => (),
        }
    }
    let mut sum = 0_usize;
    for first in 0..3 {
        for second in first+1..4 {
            for third in second+1..5 {
                sum += counts[first] * counts[second] * counts[third];
            }
        }
    }

    println!("{}", sum);
}


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

int main()
{
    int n, k;
    cin >> n >> k;
    if((n + 1) / 2 >= k) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=2000005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

ll nPk(ll n,ll k){
	return nCk(n,k)*F[k]%mod;
}

int n;
string s;

int main(){
	cin>>n>>s;
	int t=0;
	for(auto i:s) if(i=='R') t++;
	int res=t;
	for(int i=0;i<t;i++) if(s[i]=='R') res--;
	cout<<res<<endl;
}

Measured memory_bytes: 3744
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

// conversion
//------------------------------------------
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T> inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

// math
//-------------------------------------------
template <class T> inline T sqr(T x) { return x * x; }

// typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

// container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c)                                                             \
  for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

// clear memory
#define CLR(a) memset((a), 0, sizeof(a))

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                                               \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"                       \
       << " " << __FILE__ << endl;

void solve(long long N, std::vector<long long> W) {
  long long sum=0;
  REP(i, N){
    sum += W[i];
  }
  vector<long long> ans(N);
  ans[0]=W[0];
  for(int i=1; i<N; i++){
    ans[i] += ans[i-1]+W[i];
  }

  REP(i, N){
    ans[i] = abs(ans[i]*2 - sum);
  }
  SORT(ans);
  cout<<ans[0]<<endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> W(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &W[i]);
  }
  solve(N, std::move(W));
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N; 
int A[5][15] = {0};
for (int i = 0; i < N; i++){
char c; 
int m;
cin >> c >> m; 
if(c == 'S') A[1][m] = 1; 
if(c == 'H') A[2][m] = 1; 
if(c == 'C') A[3][m] = 1; 
if(c == 'D') A[4][m] = 1; 
}

for (int j = 1; j <= 13; j++){
if(A[1][j] == 0)
 cout << "S " << j << endl;  
}
for (int j = 1; j <= 13; j++){
if(A[2][j] == 0)
 cout << "H " << j << endl;  
}
for (int j = 1; j <= 13; j++){
if(A[3][j] == 0)
 cout << "C " << j << endl;  
}
for (int j = 1; j <= 13; j++){
if(A[4][j] == 0)
 cout << "D " << j << endl;  
}
}


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

int main() {
    int N;
    int A[100005], B[100005];
    int cnt = 0;
    cin >> N;
    for ( int i = 0; i < N; i++ ) { cin >> A[i]; B[i] = A[i]; }
    sort(B, B + N);
    for ( int i = 0; i < N; i++ ) cnt += (i + lower_bound(B, B + N, A[i]) - B) % 2;
    cout << cnt / 2 << endl;
    return ( 0 );
}

Measured memory_bytes: 1024
#coding=utf-8
from itertools import combinations
from collections import Counter

def solve(n, gc):
    #filtered_ss = list(filter(lambda x: x in "MARCH", ss))

    #gc = Counter(filtered_ss)
    if len(gc) < 3:
        return 0

    ans = 0
    for permutation in combinations("MARCH", 3):
        ans += (gc[permutation[0]] * gc[permutation[1]] * gc[permutation[2]])

    return ans

def main():
    n = int(input())
    gc = {'M': 0, 'A': 0, 'R': 0, 'C': 0, 'H': 0}
    for _ in range(n):
        x = input()[0]
        if x in "MARCH":
            gc[x] += 1
    print(solve(n, gc))

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
import Control.Monad
import Data.List
import Data.Bits
import Debug.Trace
import Data.Maybe
import qualified Data.ByteString.Char8 as C
import Data.Vector.Unboxed (Vector, (!))
import qualified Data.Vector.Unboxed as U
import Data.Vector.Unboxed.Mutable (unsafeRead, unsafeWrite)
import qualified Data.Vector.Unboxed.Mutable as UM

main :: IO ()
main = do
  [s] <-  readInts
  --let result = vectest input
  --print result
  print $ solve s

solve :: Int -> Int
solve s = result ! 0
  where
    result = U.create $ do
      v <- UM.replicate 1000001 0
      unsafeWrite v s 1
      loop v s 1
      return v
      where
        f n = if even n then (n `div` 2) else (3 * n + 1)
        loop v a i = do
          let nexta = f a
          let nexti = i + 1
          x <- unsafeRead v nexta
          if x == 0
            then do
              unsafeWrite v nexta nexti
              loop v nexta nexti
            else do
              unsafeWrite v 0 nexti
              return ()

vectest :: Vector Int -> Vector Int
vectest input = U.create $ do
  v <- UM.replicate 1000 0
  forM_ [0 .. 999] (\i -> do
    let e = input ! i
    unsafeWrite v i e
    )
  return v

-- 以下ライブラリ

readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

readNInts :: Int -> IO [[Int]]
readNInts = flip replicateM readInts

getNLns :: Int -> IO [String]
getNLns = flip replicateM getLine

toTup2 :: [[a]] -> [(a, a)]
toTup2 = map (\ys -> case ys of y : z : zs -> (y, z))

encIdx2 :: Int -> (Int, Int) -> Int
encIdx2 mx (y, x) = y * mx + x

decIdx2 :: Int -> Int -> (Int, Int)
decIdx2 mx idx = (idx `div` mx, idx `mod` mx)

encIdx3 :: (Int, Int) -> (Int, Int, Int) -> Int
encIdx3 (my, mx) (z, y, x) = z * my * mx + y * mx + x

decIdx3 :: (Int, Int) -> Int -> (Int, Int, Int)
decIdx3 (my, mx) idx = (z, y, x)
  where
    basez = my * mx
    z = idx `div` basez
    y = (idx `mod` basez) `div` mx
    x = idx `mod` mx

while :: Monad m => m Bool -> m () -> m ()
while cond body = do
  b <- cond
  when b $ do
    body
    while cond body

Measured memory_bytes: 8700
n, m, c = map(int,input().split())
b = list(map(int,input().split()))
ans = 0
for i in range(n):
    kar = 0
    a = list(map(int,input().split()))
    for j in range(m):
        kar += a[j]*b[j]
    if kar + c > 0:
        ans += 1
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
ll dp[101][100001];
int main(){
	int N,W;
	int value[100],weight[100];
	scan(N);scan(W);
	rep(i,N){
		scan(weight[i]);scan(value[i]);
	}
	rep(w,W+1){
		dp[0][w]=0;
	}
	rep(i,N){
		rep(w,W+1){
			if(w>=weight[i]) dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w]);
			else dp[i+1][w]=dp[i][w];
		}
	}
	prin(dp[N][W]);
	return 0;
}


Measured memory_bytes: 79104
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n = int(input())
#n,a = [int(i) for i in readline().split()]
n = int(input())
p = [int(i)-1 for i in readline().split()]+[10**8]

ans = 0
num = 0
for i,c in enumerate(p):
    if i==c:
        num += 1
    else:
        ans += (num+1)//2
        num = 0
    

print(ans)


Measured memory_bytes: 13876
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for (int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
#define f first
#define s second
#define pb push_back

int n, A[55], numneg, numpos;
pi neg, pos;
bool ok = true;
vector<pi> ans;

int main() {
	cin >> n;
	FOR(i, 1, n) {
		cin >> A[i];
		if (i != 1 and A[i] < A[i-1]) ok = false;
		if (A[i] < 0) neg = min(neg, pi(A[i], i));
		else if (A[i] > 0) pos = max(pos, pi(A[i], i));
	}
	if (ok) {cout << 0; return 0;}
	if (pos.f > -neg.f) {
		FOR(i, 1, n) {
			if (A[i] < 0) {
				int t = (int) ceil((double)-A[i]/(double)pos.f);
				FOR(j, 1, t) ans.pb(pi(pos.s, i));
				A[i] += t * pos.f;
			}
		}
		FOR(i, 1, n-1) {
			A[i+1] += A[i];
			ans.pb(pi(i, i+1));
		} 
	} else {
		DEC(i, n, 1) {
			if (A[i] > 0) {
				int t = (int) ceil((double)A[i]/(double)-neg.f);
				FOR(j, 1, t) ans.pb(pi(neg.s, i));
				A[i] += t * neg.f;
			}
		}
		DEC(i, n, 2) {
			A[i-1] += A[i];
			ans.pb(pi(i, i-1));
		}
	}
	cout << ans.size() << "\n";
	for(auto it:ans) cout << it.f << " " << it.s << "\n";
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/practice2/tasks/practice2_f
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)
const int MOD = 998244353;

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (auto &x : A)
        cin >> x;
    for (auto &x : B)
        cin >> x;
    auto p = convolution<MOD>(A, B);
    for (auto &x : p) {
        cout << x << " ";
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 27280
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
double a,b,x;
double p1,ans1,p2,ans2,ans;
int main()
{
	scanf("%lf%lf%lf",&a,&b,&x);
	p1=x*2.0/a/a-b;
	p2=x*2.0/a/b;
	ans1=atan((b-p1)/a)*180.0/atan(1.0)/4.0;
	ans2=90.0-atan(p2/b)*180.0/atan(1.0)/4.0;
	if(2.0*x>=a*a*b)
		ans=ans1;
	else
		ans=ans2;
	printf("%lf",ans);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,x) memset(a,x,sizeof(a))
#define SZ(x) ((int)(x).size())
#define lson rt<<1
#define rson rt<<1|1
#define pb push_back
#define fi first
#define se second
#define what_is(x) cerr<<#x<<" "<<x<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
template <typename T>
inline void _read(T& x){
    cin>>x;
}
void R(){}
template <typename T,typename... U>
void R(T&head,U&... tail){
    _read(head);
    R(tail...);
}

template <typename T>
inline void _write(const T& x){
    cout<<x<<' ';
}
void W(){cout<<endl;}
template <typename T,typename... U>
void W(const T&head,const U&... tail){
    _write(head);
    W(tail...);
}

void go();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    go();
    return 0;
}
/****************ackun*********************/
void go(){
    string s;
    R(s);
    if(s=="A")W("T");
    else if(s=="T")W("A");
    else if(s=="C")W("G");
    else W("C");
}


Measured memory_bytes: 256
package main

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

var stdin = bufio.NewScanner(os.Stdin)

func main() {
	stdin.Split(bufio.ScanWords)
	N := nextInt()
	S := nextStr()
	sum := 0
	Rs := make([]int, 0, N)
	Gs := make([]int, 0, N)
	Bs := make([]int, 0, N)
	for i, c := range S {
		if c == 'R' {
			Rs = append(Rs, i)
		}
		if c == 'G' {
			Gs = append(Gs, i)
		}
		if c == 'B' {
			Bs = append(Bs, i)
		}
	}

	runes := []rune(S)
	for _, r := range Rs {
		for _, g := range Gs {
			var bindex int
			// right
			if r > g {
				bindex = 2*r - g
			} else {
				bindex = 2*g - r
			}
			if bindex < N && runes[bindex] == 'B' {
				sum++
			}
			// left
			if r > g {
				bindex = 2*g - r
			} else {
				bindex = 2*r - g
			}
			if bindex >= 0 && runes[bindex] == 'B' {
				sum++
			}
			// mid
			if (r+g)%2 == 0 && runes[(r+g)/2] == 'B' {
				sum++
			}
		}
	}

	// for i := 0; i < N-2; i++ {
	// 	for j := i + 1; j < N-1; j++ {
	// 		if S[i] == S[j] {
	// 			continue
	// 		}
	// 		for k := j + 1; k < N; k++ {
	// 			if j-i != k-j && S[i] != S[k] && S[j] != S[k] {
	// 				sum++
	// 			}
	// 		}
	// 	}
	// }
	fmt.Println(len(Rs)*len(Gs)*len(Bs) - sum)
}

func nextInt() int {
	stdin.Scan()
	i, err := strconv.Atoi(stdin.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func nextStr() string {
	stdin.Scan()
	i := stdin.Text()
	// if err != nil {
	// 	panic(err)
	// }
	return i
}


Measured memory_bytes: 1836
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

H,W,A,B = map(int,readline().split())

import numpy as np
grid = np.zeros((H,W),np.int8)
grid[:,:A]^=1
grid[:B]^=1

print('\n'.join(''.join(row) for row in grid.astype(str)))

Measured memory_bytes: 45684
K = int(input())
N = 50
A = [i for i in range(N)]
q, r = divmod(K, N)
for i in range(N): A[i] += q
for i in range(r):
    for j in range(N):
        if j == i: A[j] += N
        else: A[j] -= 1
print(N)
print(*A)

Measured memory_bytes: 38512
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()

ll P[100010][2];
void init(ll N){
    for (ll i=1; i<=N; ++i) {
        P[i][0] = i;
        P[i][1] = 1;
    }
}

ll root(ll a){
    if (P[a][0] == a) return a;
    return (P[a][0] = root(P[a][0]));
}

bool is_same_set(ll a, ll b){
    return root(a) == root(b);
}

ll size(ll a){
    return P[root(a)][1];
}

void unite(ll a, ll b){
    ll temp = size(a) + size(b);
    if (!is_same_set(a,b)) {
        P[root(a)][0] = root(b);
        P[root(a)][1] = temp;
    }
    else P[root(a)][0] = root(b);
}

int main() {
    ll N,M; scanf("%lld%lld",&N,&M);
    ll A[M],B[M];
    ll ans[M];
    ans[M-1] = N*(N-1)/2;
    rep(i,M) scanf("%lld%lld",&A[i],&B[i]);
    init(N);
    rep(i,M){
        if (!is_same_set(A[M-i-1],B[M-i-1])){
            ans[M-i-2] = ans[M-i-1] - size(A[M-i-1])*size(B[M-i-1]);
            unite(A[M-i-1],B[M-i-1]);
        }
        else {
            ans[M-i-2] = ans[M-i-1];
            unite(A[M-i-1],B[M-i-1]);
        }
    }
    rep(i,M){
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 5248
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        if(Math.abs(a - b) >= 2){
            System.out.println("Alice");
        }else{
            System.out.println("Brown");
        }
    }
}


class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

// https://atcoder.jp/contests/dp/submissions/10212135
void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  // dp[i][j] : 最後の値が j
  // これまで選んだ数全部を持たないとダメ

  // i 番目の数より大きいのが j 個残ってるような場合の数
  vector<vector<int> > dp(n + 1, vector<int>(n));
  dp[0] = vector<int>(n, 1);
  // dp[0][0] : 0 番目 n-1

  rep3(i, 1, n) {
    vector<int> acc(n + 1);
    rep(j, n) {
      if (s[i - 1] == '<') {
        (acc[0] += dp[i - 1][j]) %= mod;
        (acc[j] += mod - dp[i - 1][j]) %= mod;
      } else {
        int tmp = n - i - j; // ai より小さいのの個数
        (acc[j] += dp[i - 1][j]) %= mod;
        (acc[j + tmp] += mod - dp[i - 1][j]) %= mod;
      }
    }
    rep3(j, 1, n) (acc[j] += acc[j - 1]) %= mod;
    rep(j, n) add(dp[i][j], acc[j]);
  }

  cout << dp[n - 1][0] << endl;
  // rep(i, n) cout << dp[i] << endl;
}


Measured memory_bytes: 35584
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cmath>
#define ll long long

using namespace std;

long long MOD = 1000000007;

int main(){
    ll a,b,c;
    cin >> a >> b >> c;
    if(c-a-b<0){
        cout << "No" << endl;
        return 0;
    }
    if(4*a*b<(c-a-b)*(c-a-b)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let n = get!(i32);
    let a = get!(i32);
    println!("{}", n.pow(2) - a);
}

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

int main() {
	cin.sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int k[110], p[110];
	for (int i = 0; i < n; i++) {
		cin >> k[i] >> p[i];
	}
	for (int i = 0; i < n; i++) {
		int ans = k[i] % p[i];
		if (ans == 0) {
			ans = p[i];
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 3192
class Problem
  attr_accessor *(?a..?z).to_a.map(&:to_sym)
  def initialize
    @a,@b,@c = gets.to_s.split.map{ |v| v.to_i }  
    @k = gets.to_s.to_i
  end

  def solve
    cnt = 0
    while a >= b
      @b *= 2
      cnt += 1
    end
    while b >= c
      @c *= 2
      cnt += 1
    end
    cnt <= k
  end

  def show(ans)
    puts ans ? "Yes" : "No"
  end
end

Problem.new.instance_eval do
  show(solve)
end

Measured memory_bytes: 14372
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<functional>
#include<queue>
#include<stack>
#include<set>
using namespace std;

int main(){
	int a,b,c;
	while(cin>>a>>b>>c){
	int x=0,z=0;//x?????¨??????????????????z??????????????????20????¶???????????????????
		for(int i=1;i<=10;i++){
			if(i==a||i==b||i==c)continue;
			if(a+b+i<=20)z++;
			x++;
		}
		double p=(double)z/(double)x;
		//cout<<p<<" "<<x<<" "<<z<<endl;
		if(p>=0.5)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}

}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long hxtype;
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const int N=100001;
int a[N],c[N];
inline bool cmp(int a,int b){return a>b;}
int main(){
	int n,m,v,p,i,l,r,d,s,t;ll T;
	scanf("%d%d%d%d",&n,&m,&v,&p);
	v=n-v;l=(s=p)+1;r=n;
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	while(l<=r){
		d=(l+r)>>1;t=v;T=0ll;
		for(i=p;i!=d;++i){
			if(t){--t;T-=m;}
			T+=a[i]-a[d];
			if(T>0ll)break;
		}
//		printf("d=%d i=%d\n",d,i);
		if(i==d)l=(s=d)+1;else r=d-1;
	}
	printf("%d",s);
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int dp[1401][1401]={},m,h,w,f;
#define r(i,n) for(int i=0;i<n;i++)
main(){
cin>>h>>w;m=0;
r(i,h)r(j,w){cin>>f;if(!f)dp[i+1][j+1]=min(dp[i][j],min(dp[i+1][j],dp[i][j+1]))+1,m=max(m,dp[i+1][j+1]);}
cout<<m*m<<endl;
}


Measured memory_bytes: 9640
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define SZ(x) ((int)(x).size())

typedef long long ll;

int const N = 1e4 + 5;

struct point {
	ll x, y;
}p[N];

int n;

ll abs(ll x) {
	if(x < 0) return -x;
	return x;
}

bool check() {
	if(n == 1) 
		return 1;
	for(int i = 2; i <= n; ++i)
		if(abs(p[i].x + p[i].y) % 2 != abs(p[1].x + p[1].y) % 2)
			return 0;
	return 1;
}


std::vector<ll> sec;
std::vector<char> ans[N];

int main() {
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(0);
	std::cin >> n;
	for(int i = 1; i <= n; ++i)
		std::cin >> p[i].x >> p[i].y;

	if(::check() == 0) {
		puts("-1");
		return 0;
	}

	for(ll i = 1, bit2 = 1; i <= 34 && bit2 <= ll(2e9); ++i) {
		sec.push_back(bit2);
		bit2 <<= 1;
	}

	if(abs(p[1].x + p[1].y) % 2 == 0) 
		sec.push_back(1);

	for(int i = 1; i <= n; ++i) {
		ans[i].clear();
		for(int j = SZ(sec) - 1; j >= 0; --j) {
			ll const& bit2 = sec[j];
			if(abs(p[i].x) > abs(p[i].y)) {
				if(p[i].x < 0) {
					p[i].x += bit2;
					ans[i].push_back('L');
				}
				else {
					p[i].x -= bit2;
					ans[i].push_back('R');
				}
			} else {
				if(p[i].y < 0) {
					p[i].y += bit2;
					ans[i].push_back('D');
				} 
				else {
					p[i].y -= bit2;
					ans[i].push_back('U');
				}
			}
		}
	}

	std::cout << SZ(sec) << '\n';
	for(auto& x : sec)
		std::cout << x << ' ';
	std::cout << '\n';
	for(int i = 1; i <= n; ++i) {
		for(int j = SZ(ans[i]) - 1; j >= 0; --j)
			std::cout << ans[i][j];
		std::cout << '\n';
	}
	auto chkAns = [] (auto& a, auto& se) -> void {
		point now;
		now.x = now.y = 0;
		int _p = SZ(a) - 1;
		for(auto& d : se) {
			if(a[_p] == 'R') 
				now.x += d;
			if(a[_p] == 'L')
				now.x -= d;
			if(a[_p] == 'U')
				now.y += d;
			if(a[_p] == 'D')
				now.y -= d;
			--_p;
		}
		std::cout << now.x << ' ' << now.y << '\n';
	};
	// std::cout << n << '\n';
	// for(int i = 1; i <= n; ++i)
	//     chkAns(ans[i], sec);
	return 0;
}


Measured memory_bytes: 640
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
#include <bits/stdc++.h>
using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 3
#endif

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cout_precision cout.setf(ios::fixed); cout.precision(15);
using ll = int64_t; using ull = uint64_t; using ld = long double;

// -----------------------------------------------------------------------------

const int N = 1e5 + 5, Q = 1e5 + 5;
int n, m;
vector<int> g[N];
tuple<int, int, int> op[Q];
int color[N], last[N];

void dfs(int u, int d, int c) {
    if (!color[u]) color[u] = c;
    if (last[u] >= d) return;
    last[u] = d;
    for (auto &v : g[u]) {
        dfs(v, d - 1, c);
    }
}

int main() {
    fast_io;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int q; cin >> q;
    for (int i = 0; i < q; ++i) {
        int v, d, c;
        cin >> v >> d >> c;
        op[i] = make_tuple(v, d, c);
    }
    for (int i = q - 1; i >= 0; --i) {
        int v, d, c;
        tie(v, d, c) = op[i];
        dfs(v, d, c);
    }
    for (int i = 1; i <= n; ++i) {
        cout << color[i] << '\n';
    }
}


Measured memory_bytes: 8440
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;

using namespace std;

int main()
{
  ull N, T;
  cin >> N >> T;
  vector<ull> cs(N);
  vector<ull> ts(N);

  for (auto i = 0; i < N; i++) {
    cin >> cs[i] >> ts[i];
  }
  ull tle = 1001;
  ull res = tle;

  for (auto i =0; i < N; i++) {
    if (ts[i] <= T) {
      res = min(res, cs[i]);
    }
  }

  if (res == tle) cout << "TLE" << endl;
  else cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
#define NIL -1

struct Node{int parent,left,right;};

vector<Node> T(MAX);
int n;
vector<int> D(MAX),H(MAX);

void setDepth(int u,int d){
    if(u == NIL) return;
    D.at(u) = d;
    setDepth(T.at(u).left,d+1);
    setDepth(T.at(u).right,d+1);
}

int setHeight(int u){
    int h1 = 0, h2 = 0;
    if(T.at(u).left != NIL){
        h1 = setHeight(T.at(u).left) + 1;
    }
    if(T.at(u).right != NIL){
        h2 = setHeight(T.at(u).right) + 1;
    }
    return H.at(u) = max(h1,h2);
}

int getSibling(int u){
    if(T.at(u).parent == NIL) return NIL;
    if(T.at(T.at(u).parent).left != u && T.at(T.at(u).parent).left != NIL) return T.at(T.at(u).parent).left;
    if(T.at(T.at(u).parent).right != u && T.at(T.at(u).parent).right != NIL) return T.at(T.at(u).parent).right;
    return NIL;
}

void print(int u){
    cout << "node " << u << ": ";
    cout << "parent = " << T.at(u).parent << ", ";
    cout << "sibling = " << getSibling(u) << ", ";
    int deg = 0;
    if(T.at(u).left != NIL) deg++;
    if(T.at(u).right != NIL) deg++;
    cout << "degree = " << deg << ", ";
    cout << "depth = " << D.at(u) << ", ";
    cout << "height = " << H.at(u) << ", ";

    if(T.at(u).parent == NIL){
        cout << "root" << endl;
    }else if(T.at(u).left == NIL && T.at(u).right == NIL){
        cout << "leaf" << endl;
    }else{
        cout << "internal node" << endl;
    }
}

int main(){
    int v,l,r,root = 0;
    cin >> n;

    for(int i = 0; i < n; i++) T.at(i).parent = NIL;

    for(int i = 0; i < n; i++){
        cin >> v >> l >> r;
        T.at(v).left = l;
        T.at(v).right = r;
        if(l != NIL) T.at(l).parent = v;
        if(r != NIL) T.at(r).parent = v;
    }

    for(int i = 0; i < n; i++) if(T.at(i).parent == NIL) root = i;

    setDepth(root,0);
    setHeight(root);

    for(int i = 0; i < n; i++) print(i);

    return 0;
}




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

int main() {
	char ca,cb,cc,cd;
	cin >> ca >> cb >> cc >> cd;
	int a = ca - '0',b = cb - '0',
	    c = cc - '0',d = cd - '0';
	string ans="111111111";
	int p1,p2,p3;
	for(int i=0;i<2;i++)
	{
		char o1 = '-';
		p1 = a - b;
		if(i>0)
		{
			o1 = '+';
			p1 = a+b;
		}
		for(int j=0;j<2;j++)
		{
			char o2 = '-';
			p2 = p1 - c;
			if(j>0)
			{
				o2 = '+';
				p2 = p1 + c;
			}
			for(int k=0;k<2;k++)
			{
				char o3='-';
				p3 = p2 - d;
				if(k>0)
				{
					o3='+';
					p3 = p2 + d;
				}
				if(p3 == 7)
				{
					ans.at(0)=ca;
					ans.at(1)=o1;
					ans.at(2)=cb;
					ans.at(3)=o2;
					ans.at(4)=cc;
					ans.at(5)=o3;
					ans.at(6)=cd;
					ans.at(7)='=';
					ans.at(8)='7';
				}
			}
		}
	}
    cout << ans << endl;
}


Measured memory_bytes: 256