akhauriyash/Code-Regression huggingface dataset:
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

vll as;

void solvee(ll n){
  vll dp(n+1, -1);
  dp[0] = 0;
  rep(i, n){
    if(i & 1){
      ll add = dp[i-1];
      if(i - 2 >= 0) chmax(add, dp[i-2]);
      dp[i+1] = add+ as[i];
    } else {
      dp[i+1] = as[i];
      if(i - 1 >= 0) dp[i+1] += dp[i-1];
    }
  }
  cout << max(dp[n], dp[n-1]) << endl;
}

void solveo(ll n){
  vvll dp(n, vll(3, -INF));

  dp[0][0] = as[0];
  dp[1][1] = as[1];
  dp[2][0] = as[0] + as[2];
  dp[2][2] = as[2];

  repLRE(i, 3, n-1){
    rep(j, 3){
      if(i - 2 >= 0 && dp[i-2][j] != -INF) chmax(dp[i][j], dp[i-2][j] + as[i]);
      if(j == 2){
        if(i - 4 >= 0 && dp[i-4][j-2] != -INF) chmax(dp[i][j], dp[i-4][j-2] + as[i]);
      }
      if(j >= 1){
        if(i - 3 >= 0 && dp[i-3][j-1] != -INF) chmax(dp[i][j], dp[i-3][j-1] + as[i]);
      }
    }
  }

  ll ans = dp[n-1][2];
  chmax(ans, dp[n-2][1]);
  chmax(ans, dp[n-3][0]);
  cout << ans << endl;
}

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n;
  cin >> n;

  as.resize(n);
  rep(i,n) cin >> as[i];
  if(n & 1){
    solveo(n);
  } else {
    solvee(n);
  }

  return 0;
}


Measured memory_bytes: 15588
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <list>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip> // setprecisionを使用するのに必要 cout << fixed << setprecision(15) << p でpを小数点以下15桁表示
using namespace std;
#define REPD(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) REPD(i, 0, n)
typedef long long ll;
#define fin(ans) cout << (ans) << '\n'
/*

*/
int main()
{
    string T;
    cin >> T;
    int l = T.length();
    int nump = 0;
    REP(i,l){
        if(T[i] == 'p') nump++;
    }
    fin(l/2-nump);
    return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <algorithm>

using namespace std;

const int p=1000000007;

long long f[200],f_[200];
long long m,n;
int h,i,s,t;

inline void dfs(int x,int y,long long u,long long v,long long su,long long sv)
{
	if (x==y-1)
	{
		s=(s+(m-u)/v)%p;
		s=(s+(n-u)/v)%p;
	}
	else
	{
		long long tu,tv,tw;
		for (int k=1;;k++)
		{
			tu=v,tv=k*v+u;
			tu=su+(k-1)*v*f_[y-x-2];
			tv=sv+(k-1)*v*f_[y-x-1];
			if ((tu>n) || (tv>m))
				break;
			dfs(x+1,y,v,k*v+u,tu,tv);
		}
	}
	return;
}

int main()
{
	f[0]=0,f[1]=1,f[2]=2;
	for (i=3;i<=100;i++)
		f[i]=f[i-1]+f[i-2];
	f_[0]=1,f_[1]=1;
	for (i=2;i<=100;i++)
		f_[i]=f_[i-1]+f_[i-2];
	scanf("%d",&t);
	for (h=1;h<=t;h++)
	{
		scanf("%lld%lld",&n,&m);
		if (n>m)
			swap(n,m);
		if ((n==1) && (m==1))
		{
			printf("%d %d\n",1,1);
			continue;
		}
		for (i=0;(f[i]<=n) && (f[i+1]<=m);i++);
		printf("%d ",i-1);
		if (i-1==1)
			printf("%lld\n",(m%p)*(n%p)%p);
		else
		{
			s=0;
			dfs(0,i-1,1,1,f[i-1],f[i]);
			printf("%d\n",s);
		}
	}
	return 0;
}

Measured memory_bytes: 3968
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define ull unsigned long long
#define REP(i, n) for(int i=0; i<n; i++)

int main(){
    int A,B,C;
    int X,Y;
    cin >> A >> B >> C >> X >> Y;
    int cost = 0;
    if(C*2 > A+B){
        cost = X*A + Y*B;
    }
    else{
        int p = min(X,Y);
        cost += C*2*p;
        if(p == X && C*2 < B) cost += 2*C * (Y-p);
        else if(p == Y && C*2 < A) cost += 2*C * (X-p);
        else cost += (X-p)*A + (Y-p)*B;
    }
    cout << cost << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

fun main(args:Array<String>){

    val cin = Scanner(System.`in`)
    var str = cin.nextLine()

    for(i in 0..str.length-1){
        if(str[i].isUpperCase()) print(str[i].toLowerCase())
	    if(str[i].isLowerCase()) print(str[i].toUpperCase())
	    if(str[i] < 'A' || str[i] > 'z') print(str[i])
    }
    println()
}



Measured memory_bytes: 26056
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using P = pair<int,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const ll INF = 1LL<<60;
const int ny[4] = {-1,1,0,0}, nx[4] = {0,0,-1,1};
int sy,sx,gy,gx;

int main(){
  string a,b; cin >> a >> b;
  int al = a.size();
  int bl = b.size();
  string ans = "EQUAL";
  if(al < bl) ans = "LESS";
  else if(al > bl) ans = "GREATER";
  else{
    for(int i = 0; i < al; i++){
      int an = a[i] - '0', bn = b[i] - '0';
      if(an == bn) continue;
      if(an < bn) ans = "LESS";
      else ans = "GREATER";
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
n,a,b=parse.(split(readline()))
M=10^9+7
function f(x)
  s=t=1
  for i=1:x
    t=t*i%M
    s=s*(n-i+1)%M
  end
  s*invmod(t,M)%M
end
println(mod(powermod(2,n,M)-1-f(a)-f(b),M))


Measured memory_bytes: 169948
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		String[] array = s.split(" ");
		int a = Integer.parseInt(array[0]);
		int b = Integer.parseInt(array[1]);
		int c = Integer.parseInt(array[2]);

		if (a == b && b == c) {
			System.out.println("1");
		} else if (a == b || b == c || c == a) {
			System.out.println("2");
		} else {
			System.out.println("3");

		}
	}
}


Measured memory_bytes: 19412
#include <bits/stdc++.h>
using namespace std;
typedef  long long   ll;
typedef  long double ld;
#define ceil(n, m) ((n / m) + ( n % m ? 1 : 0))
#define mod(n, m) (((n % m) + m) % m)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int n, x,t;
    cin >> n >>x >> t;
    cout << ceil(n,x) * t;

}

Measured memory_bytes: 3608
fun main(args: Array<String>) {
    val (x, y, z) = readLine()!!.split(" ").map { it.toInt() }
    var array = Array(x) { y - z }
    for (i in 0 until z) {
        array[readLine()!!.toInt() - 1] += 1
    }
    array.forEach {
        (if (it > 0) "Yes" else "No").let { a ->
            println(a)
        }
    }
}


Measured memory_bytes: 62780
#include <bits/stdc++.h>
using ll = long long;
using itn = int;
using namespace std;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main(){
    int n;
    int d[110]={0};
    cin >> n;
    for(int i=0; i<n; i++) cin >> d[i];

    set<int> values;
    for(int i=0; i<n; i++){
        values.insert(d[i]);
    }
    cout << values.size() << endl;

}


Measured memory_bytes: 256
using System;

namespace ABC055_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var nm = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            var n = nm[0];
            var m = nm[1];
            if (m == 1)
            {
                Console.WriteLine(0);
            }
            else if (2 * n >= m)
            {
                Console.WriteLine(m / 2);
            }
            else
            {
                var c = m - 2 * n;
                Console.WriteLine(n + c / 4);
            }
        }
    }
}


Measured memory_bytes: 11220
a, b, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
XYC = [list(map(int, input().split())) for _ in range(m)]

ans = min(A) + min(B)
for x, y, c in XYC:
  x -= 1
  y -= 1
  cand = A[x] + B[y] - c
  ans = min(ans, cand)
print(ans)

Measured memory_bytes: 82156
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

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

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        int N = scanner.nextInt();
        int[] n = new int[N];
        for (int i = 0; i < N; i++) {
            n[i] = scanner.nextInt();
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            int a = n[i];
            while (a % 2 == 0) {
                a = a / 2;
                ans ++;
            }
        }
        System.out.println(ans);
    }

    private class MyScanner {
        String[] s;int i;BufferedReader br;String reg = " ";
        MyScanner () { s = new String[0];i = 0;br = new BufferedReader(new InputStreamReader(System.in)); }
        public String next() {
            try {
                if (i < s.length) return s[i++]; String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0); i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}



Measured memory_bytes: 27092
import java.util.*;

public class Main{
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int ab = a + b;
        int bc = b + c;
        int ca = c + a;
        int min = Math.min(ab, bc);
        System.out.println(Math.min(min, ca));
    }
}


Measured memory_bytes: 23636
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int p = sc.nextInt();
        char[] s = sc.next().toCharArray();
        long ans = 0;
        if(10 % p == 0){
            for(int i = n-1; i >= 0; i--){
                if((s[i] - '0') % p == 0){
                    ans += i+1;
                }
            }
        }else{
            int[] cum = new int[n+1];
            int pow = 1;
            for(int i = n-1; i >= 0; i--){
                int tmp = ((s[i] - '0') * pow) % p;
                cum[i] = (cum[i+1]+tmp) % p;
                pow *= 10;
                pow %= p;
            }
            int[] counter = new int[p];
            for(int i = n; i >= 0; i--){
                ans += counter[cum[i]];
                counter[cum[i]]++;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 28812
memo=dict()
t=int(input())
def f(x):
	if x in memo:
		return memo[x]
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3+1)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5+1)+C+D*(5-x%5))
	memo[x]=ret
	return ret
for _ in range(t):
	memo=dict()
	n,A,B,C,D=map(int,input().split())
	print(f(n))



Measured memory_bytes: 11020
# -*- coding: utf-8 -*-
# 入力
a, b, c = map(int, input().split())
k = int(input())

# 処理
# A,B,Cをリストに格納し、最大値のみ取り出す
nums = sorted([a, b, c])
num_max = nums[2]
nums_rest = nums[:2]
# 最大値をK回2倍したものと残りの数値を足し合わせる
ans = num_max * (2 ** k) + sum(nums_rest)

# 出力
print("{}".format(ans))


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count etc.
#include <cstdlib>	// require abs
#include <cstdio>	// require printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require sqrt ceil floor
#include <climits>	// require INT_MAX etc
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>	// require tolower, toupper
#include <stdint.h>	// require uint64_t
#include <fstream>	// require freopen

using namespace std;

const int M = 100000;

int main()
{
//	cut here before submit 
//	freopen ("testcase.traveler", "r", stdin );
	int n, m;

	while (cin >> n >> m && n && m ){
		vector <int> d (n, 0 );
		for (int i = 0; i < n - 1; ++i ){
			cin >> d[i];
		} // end for
		vector <int> a (m, 0 );
		for (int i = 0; i < m; ++i ){
			cin >> a[i];
		} // end for

		int res = 0;
		int curr = 0;
		for (int i = 0; i < m; ++i ){
//			int sign = (a[i] > 0 ? 1 : -1 );
//			int offset = (sign == 1 ? 0 : -1 );
			int sum = (a[i] > 0 ? accumulate (d.begin() + curr, d.begin() + curr + a[i], 0 ) : accumulate (d.begin() + curr + a[i], d.begin() + curr, 0 ) );
			res = (res + sum) % M;
			curr += a[i]; 
		} // end for
		cout << res << endl;	
	} // end loop
		
	return 0;
}

Measured memory_bytes: 1648
from collections import defaultdict
def main():
	N, K, L = map(int, input().split())
	road = [0]*K
	rail = [0]*L
	road_graph = [[i, 0] for i in range(N+1)]
	rail_graph = [[i, 0] for i in range(N+1)]

	def root(graph, i):
		parent = graph[i][0]
		if parent == i:
			return i
		return root(graph, parent)

	def is_same_tree(graph, i, j):
		return root(graph, i) == root(graph, j)

	def unite(graph, i, j):
		if is_same_tree(graph, i, j):
			return
		l = graph[root(graph, i)]
		r = graph[root(graph, j)]
		if l[1] < r[1]:
			l[0] = r[0]
			r[1] += 1
		else:
			r[0] = l[0]
			l[1] += 1

	ans_list = [""]*N

	for i in range(K):
		road[i] = list(map(int, input().split()))
		unite(road_graph, road[i][0], road[i][1])
	for i in range(L):
		rail[i] = list(map(int, input().split()))
		unite(rail_graph, rail[i][0], rail[i][1])

	ans_memo = defaultdict(int)
	road_memo = [0]*(N+1)
	rail_memo = [0]*(N+1)
	for i in range(1, N+1):
		road_root = root(road_graph, i)
		rail_root = root(rail_graph, i)
		road_memo[i] = road_root
		rail_memo[i] = rail_root
		ans_memo[(road_root, rail_root)] += 1

	for i in range(1, N+1):
		road_root = road_memo[i]
		rail_root = rail_memo[i]
		this_ans = str(ans_memo[road_root, rail_root])
		ans_list[i-1] = this_ans

	ans = " ".join(ans_list)
	print(ans)


if __name__ == '__main__':
	main()

Measured memory_bytes: 145312
//
// Created by Myabu on 2020/01/21.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <numeric>
#include <iomanip>

using namespace std;


int main(void){
    int A,B;
    string S;
    cin>>A>>B>>S;

    bool flag = true;
    for (int i = 0; i < S.length(); ++i) {
        if(i<A){
            if(S[i] == '-'){
                flag = false;
                break;
            }
        }
        if(i==A){
            if(S[i] != '-'){
                flag = false;
                break;
            }
        }
        if(i>A){
            if(S[i] == '-'){
                flag = false;
                break;
            }
        }
    }

    if(flag){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;

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

int dy[] = { 0, 0, 1, -1, 0 };
int dx[] = { 1, -1, 0, 0, 0 };

int main(){
	ios::sync_with_stdio(false);

	int d, w, h;
	int n;
	int r[10000];

	double x1, x2, x3;

	while (1){
		cin >> d >> w >> h;

		if (d == 0 && w == 0 && h == 0){
			break;
		}

		cin >> n;

		x1 = sqrt(d*d + w*w)*0.5;
		x2 = sqrt(h*h + w*w)*0.5;
		x3 = sqrt(d*d + h*h)*0.5;


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

		for (int i = 0; i < n; i++){
			if (x1 < r[i] || x2 < r[i] || x3 < r[i]){
				printf("OK\n");
			}
			else{
				printf("NA\n");
			}
		}
	}

}

Measured memory_bytes: 3068
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int a,b;
  string ans;
  cin>>a>>b;
  if(0<a && a<=b){
    ans="Positive";
  }else if(a<=b && b<0){
    if((b-a+1)%2==0){
      ans="Positive";
    }else{
      ans="Negative";
    }
  }else{
    ans="Zero";
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3616
#include<iostream> 
#include<string>
#include<bits/stdc++.h>
using namespace std;
int main(){	
	int a,b;
	cin>>a>>b;
	int c[a];
	cin>>c[a];
	if(a==b){
		cout<<"1";
	}
	else{
		a=a-b;
		if(a%(b-1)==0){
			cout<<a/(b-1)+1;
		}
		else{
			cout<<a/(b-1)+2;
		}
	}
    return 0;
} 

Measured memory_bytes: 256
N,M = map(int,input().rstrip().split(" "))
K = [[]] * M
sw = [False] * N
count = 0
check = True
ans = 0

for i in range(M):
    K[i] = list(map(int,input().rstrip().split(" ")))
P = list(map(int,input().rstrip().split(" ")))


for i in range(2 ** N):
    check = True
    for i2 in range(N):
        sw[i2] = (i >> i2) & 1
    
    for i2 in range(M):
        counter = 0
        for i3 in range(K[i2][0]):
            if sw[K[i2][i3 + 1] - 1]:
                counter += 1
        if counter % 2 != P[i2]:
            check = False
            break
    if check: ans += 1
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
  
int main(){
int N;
cin >>N;
string s;
char a,b,c,d;
s = to_string(N);
a =s.at(0);
 b=s.at(1) ;
 c=s.at(2);
d=s.at(3);

if(a==b&&b==c){
cout << "Yes"<<endl;
}
else if(b==c&&c==d){
cout << "Yes"<<endl;
}
else{
cout << "No"<<endl;
}  
}

Measured memory_bytes: 256
fun main(args: Array<String>){
    val input = readLine()!!.split("/")
    val year = input[0].toInt()
    val month = input[1].toInt()
    val day = input[2].toInt()

    if(year <= 2018){
        println("Heisei")
    }
    else if(year == 2019 && month < 5){
        println("Heisei")
    }
    else{
        println("TBD")
    }
}

Measured memory_bytes: 37992
#include <stdio.h>

int main(void) {
  int i, j, k, n, a = 0, b = 0, c = 0;
  scanf("%d", &n);
  for(i = 0; i < n; ++i) {
    scanf("%d", &k);
    if(!(k % 4)) c++;
    else if(!(k % 2)) b++;
    else a++;
  }
  if(b) c--;
  if(a <= c + 1) printf("Yes");
  else printf("No");
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[105];
int n;

int fun(int x){
    int res=0;
    for(int i=0;i<n;i++){
        res+=(pow(a[i]-x,2));
    }
    return res;
}

int fun2(){
    int h=0;
    for(int i=0;i<n;i++)
        h+=a[i];
        float h2;
    if(h>=0)
        h2=(float)h/n+0.5;
    else
        h2=(float)h/n-0.5;
    h=h2;
    return h;
}

int main(){
    int res=2100000000;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    res=fun(fun2());
cout<<res<<endl;
return 0;
}


Measured memory_bytes: 256
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collection;


 
public class Main{
	
        static final Scanner sc=new Scanner(System.in);
        
        
        
        
        
        
        public static void main(String[]args){
                int[]a=new int[3];
                for(int i=0;i<3;i++){
                        a[i]=sc.nextInt();
                }
                Arrays.sort(a);
                System.out.println(Math.abs(a[1]-a[0])+Math.abs(a[2]-a[1]));
                
                
                


                
        }
        
        
        

		
	
}


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

int main(){
    int N;
    cin >> N;
    int goukei = 0;
    vector<int>W(N);
    for(int i = 0; i < N; i++) {
        cin >> W[i];
        goukei += W[i];
    }
    int ans = 1e7;
    for(int i = 0; i < N; i++) {
        int cnt = 0;
        for(int j = 0; j < i; j++) {
            cnt += W[j];
        }
        ans = min(ans,abs((goukei-cnt)-cnt));
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Dev 1000000007

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    int n,t,a;
    cin>>n>>t>>a;
    vector<double> h(n);
    rep(i,n){
        cin>>h[i];
    }
    int min_index=0;
    double min_diff=114514;
    rep(i,n){
        double temp=abs(a-(t-0.006*h[i]));
        if(temp<min_diff){
            min_index=i;
            min_diff=temp;
        }
    }
    cout<<min_index+1<<endl;
    return 0;
}


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

#define int long long

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

#define endl '\n'
#define all(v) v.begin(), v.end()

#define lcm(a, b)  ((a) * ((b) / __gcd((a), (b)) ))
#define print_(x)  cout << #x << " : " << x << endl;
#define dvec(vct)  for(auto i : vct) cout << i << " "; cout << endl;
#define darr(a, n) for(int i = 0; i < n;) cout << a[i++] <<' '; cout<< '\n';



int32_t main() { 
    ios_base::sync_with_stdio(0); 
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    int a[n];
    int sm = 0;
    for (int i = 0; i< n; i++) {
        cin >> a[i];
        sm += a[i];
    }
    sort(a, a + n, greater<int>());
    if (a[m-1] < (sm + 0.0) / (4 * m)) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
    }

}



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

const int mod=1e9+7;
long long ans,f[100006];

long long poww(int a,int b)
{
	long long ans=1,tmp=a;
	while(b) {if(b&1) ans=ans*tmp%mod;tmp=tmp*tmp%mod;b>>=1;}
	return ans;
}

int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
//	ans=poww(k,n);
	for(int i=k;i>=1;--i) {
		f[i]=poww((k/i),n);
		for(int j=2;i*j<=k;++j) {
			f[i]-=f[i*j];
			f[i]%=mod;
		}
		(f[i]+=mod)%=mod;
	}
	for(int i=1;i<=k;++i) {
		ans+=i*f[i]%mod;
		ans%=mod;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 4560
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

// Begin {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}} End

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int x; cin >> x;

    int c = x / 100;
    cout << (100 * c <= x && x <= 105 * c) << "\n";

    return 0;
}


Measured memory_bytes: 256
import re
 
N,Q = list(map(int,input().split()))
s = input()
lis=[0]
 
count = 0
for i in range(1,len(s)):
    if s[i-1] == 'A' and s[i] == 'C':
        count +=1
    lis.append(count)
for i in range(Q):
    l,r = list(map(int,input().split()))
    print(lis[r-1]-lis[l-1])


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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = int(1e5);
ll N, A[MAX_N], B[MAX_N], C[MAX_N];

void solve() {
    sort(A, A + N);
    sort(C, C + N);

    ll ans = 0;
    REP(i, N) {
        ll *up_b = upper_bound(A, A + N, B[i] - 1);
        ll *up_c = upper_bound(C, C + N, B[i]);
        ans += (up_b - A) * (C + N - up_c);
    }
    cout << ans << endl;
}

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];
    REP(i, N) cin >> C[i];
    solve();
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
int n, m;
string a[100], b[100];
bool check(int i, int j)
{
    if ((n - i) < m || (n - j) < m)
    {
        return false;
    }
    for (int ax = i, bx = 0; bx < m; ax++, bx++)
    {
        for (int ay = j, by = 0; by < m; ay++, by++)
        {
            if (a[ax][ay] != b[bx][by])
                return false;
        }
    }
    return true;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
    }
    if (m > n)
    {
        cout << "No" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] == b[0][0])
            {
                if (check(i, j))
                {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc107_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int n = int.Parse(input[0]);
            int i = int.Parse(input[1]);

            Console.WriteLine(n-i+1);
            Console.ReadLine();
        }
    }
}


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

int main() {

	int x[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int k;
	cin >> k;

	cout << x[k-1] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
static const int INF = 1000010000;
static const ll MOD = 1000000007;
 
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb push_back
#define mp make_pair
#define np next_permutation
#define pq priority_queue
 

//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};

int main(){
    int n, t;
    cin >> n >> t;
    int ans = 1001;
    REP(i, n){
        int c, nt;
        cin >> c >> nt;
        if(nt <= t) ans = min(ans, c);
    }
    if(ans == 1001){
        cout << "TLE" << endl;
    }else{
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
N=int(input())
H=list(map(int,input().split()))

c=0
cmax=0

for i in range(N-1):
    if H[i]>=H[i+1]:
        c+=1
        if cmax<c:
            cmax=c
    else:
        if cmax<c:
            cmax=c
        c=0

print(cmax)


Measured memory_bytes: 14224
#include <iostream>
#include <string>

using namespace std;

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

    int ans = 1000;
    for (int i = 2; i < s.size(); i++){
        int dist = abs(stoi(s.substr(i - 2, 3)) - 753);
        if (dist < ans) ans = dist;
    }

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

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

int main()
{
	ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	int n{0},k{0};
	cin>>n>>k;
	int a[k]={0};
	for(int i=0;i<k;++i)
	{
		cin>>a[i];
	}
	int max=INT_MIN;
	for(int i=1;i<k;++i)
	{
		if(a[i]-a[i-1]>max)
		max=a[i]-a[i-1];
	}
	if(n+a[0]-a[k-1]>max)
	max=n+a[0]-a[k-1];
	cout<<n-max<<"\n";
	return 0;
}

Measured memory_bytes: 1024
string=input()
kaibun=list(string)
n=int(len(kaibun))

if (kaibun==list(reversed(kaibun)))and(list(reversed(kaibun[:int((n-1)/2)]))==kaibun[:int((n-1)/2)]) and (list(reversed(kaibun[int((n+1)/2):]))==kaibun[int((n+1)/2):]):
    print("Yes")
else:
    print("No")




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

const double pi  = 2 * acos(0.0);
const double eps = 1e-8;

#define REP(i,a,b) for(int i=(a); i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<29)
#define INFLL (1L<<63)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int dx[8] = {0, 1, 0, -1, 1, -1, 1, -1};
int dy[8] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  unsigned a, b;
  cin >> a >> b;
  a -= 2; b -= 2;
  if (a == b) cout << "Draw" << endl;
  else if (a > b) cout << "Alice" << endl;
  else cout << "Bob" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((int)(x).size())

using namespace std;
typedef long long ll;

const long long MOD = 2019;

void solve(long long L, long long R){
  if (R - L >= 2019) {
    printf("0\n");
    return;
  }

  int ans = 2019 * 2019;

  for (int i = L; i < R; i++) {
    for (int j = i + 1; j <= R; j++) {
      ans = min(ans, ((i % 2019) * (j % 2019)) % 2019);
    }
  }

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

int main(){
  long long L;
  scanf("%lld",&L);
  long long R;
  scanf("%lld",&R);
  solve(L, R);
  return 0;
}


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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split(" ");
		double p;
		double p1[] = {Double.parseDouble(str[0]),Double.parseDouble(str[1])};
		double p2[] = {Double.parseDouble(str[2]),Double.parseDouble(str[3])};
		p =Math.sqrt(((p2[0]-p1[0])*(p2[0]-p1[0]))+((p2[1]-p1[1])*(p2[1]-p1[1])));
		System.out.println(p);

	}
}

Measured memory_bytes: 24552
#include "bits/stdc++.h"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const ll mod = 1e9+7;

int n,m,k;

int main()
{
    cin >> n >> m >> k;
    rep(y,n+1){
        rep(t,m+1){
            int val = (y*m)+(t*n)-(2*t*y);
            if(val == k){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
import math

t = int(input())
abcd = []
for i in range(t):
    abcd.append(list(map(int, input().split())))

for i in range(t):
    if abcd[i][0] < abcd[i][1]:
        print("No")
    elif abcd[i][1] > abcd[i][3]:
        print("No")
    elif abcd[i][3] % abcd[i][1] == 0:
        if abcd[i][0] % abcd[i][1] > abcd[i][2]:
            print("No")
        else:
            print("Yes")
    else:
        big, small = abcd[i][1], abcd[i][3]
        while big % small:
            big, small = small, big % small
        gcd = small
        if abcd[i][1] - gcd <= abcd[i][2]:
            print("Yes")
        else:
            print("No")

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n) ;i++)

using namespace std;
using p=pair<int,int>;
typedef long long ll;

int main() {
  ll n,a,b;
  cin >> n >> a >> b;
  if(a==0){
    cout << 0 << endl;
  }
  else{
    if(b==0){
      cout<< n << endl;
    }
    else{
      ll k=n/(a+b);
      ll o=n%(a+b);
      if(o<=a){
        cout<< k*a+o << endl;
      }
      else{
        cout << k*a+a << endl;
      }
    }
  }
  return 0;

}


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

struct Vertex{int f; int r;};
vector<Vertex> snm;

int get(int v){
	if (snm[v].f != v) snm[v].f = get(snm[v].f);
	return snm[v].f;
}

void unite(int u, int v){
	if (u==v) return;
	if (snm[u].r > snm[v].r) swap(u, v);
	snm[u].f = v;
	if (snm[u].r == snm[v].r) snm[v].r++;
}

signed main()
{
	#ifdef LOCAL
	    freopen("H_input.txt", "r", stdin);
	    //freopen("B_output.txt", "w", stdout);
	#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	int n, m, q;
   	cin >> n >> m >> q;
   	for (int i=0;i<n;++i) snm.push_back({i, 1});
   	vector<pair<int, int> > others;
   	for (int i=0; i < q; ++i){
   		int u, v, t;
   		cin >> u >> v >> t;
   		if (t==0){
   			unite(get(u), get(v));
   		}
   		else others.push_back({u, v});
   	}
   	for (int i=0;i<others.size();++i){
   		int u = others[i].first, v = others[i].second;
   		if (get(u) == get(v)){
   			cout << "No";
   			exit(0);
   		}
   	}
   	set<int> Q;
   	for (int i=0; i < n; ++i){
   		Q.insert(get(i));
   	}
   	if (Q.size() == 2 && others.size()){
   		cout << "No";
   		exit(0);
   	}
   	if (m==n-1 && others.size()){
   		cout << "No";
   		exit(0);
   	}
   	m -= (n-Q.size());
   	int L = Q.size()-1, R = Q.size()*(Q.size()-1)/2;
   	if (m >= L && m <= R){
   		cout << "Yes";
   	}
   	else cout << "No";
    return 0;
}

Measured memory_bytes: 8048
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

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

    int ans = 0;

    REP(i,s.size()) {
        if (i < s.size() / 2) {
            ans += s[i] == 'p' ? 0: 1;
        } else {
            ans += s[i] == 'p' ? -1: 0;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;

#define INF (1e16)

ll X, Y, Z, K;

int main() {
    cin >> X >> Y >> Z >> K;

    vi A(X), B(Y), C(Z);
    for (int i = 0; i < X; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < Y; i++) {
        cin >> B[i];
    }
    for (int i = 0; i < Z; i++) {
        cin >> C[i];
    }

    sort(A.begin(), A.end(), greater<ll>());
    sort(B.begin(), B.end(), greater<ll>());
    sort(C.begin(), C.end(), greater<ll>());

    vi ans(K * K, 0);
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y; j++) {
            for (int k = 0; k < Z; k++) {
                if ((i + 1) * (j + 1) * (k + 1) <= K)
                    ans.push_back(A[i] + B[j] + C[k]);
            }
        }
    }

    sort(ans.begin(), ans.end(), greater<ll>());

    for (int i = 0; i < K; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 142848
from math import ceil


def main():
    n, k = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    left = 0
    right = a[0]
    while right - left > 1:
        ki = k
        mid = left + (right - left) // 2
        for ai in a:
            if ki < 0:
                left = mid
                break
            if ai <= mid:
                right = mid
                break
            ki -= ceil(ai / mid) - 1
        else:
            if ki < 0:
                left = mid
            else:
                right = mid
    print(right)


if __name__ == '__main__':
    main()


Measured memory_bytes: 31076
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int A, B, C;
    cin >> A >> B >> C;
    cout << (A == B ? C : A == C ? B : A) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
struct Combination {
    vector<ll> kaijou;
    Combination() : kaijou(3001001, 1) {
        rep(i, 3001000) kaijou[i + 1] = (kaijou[i] * (i + 1)) % MOD;
    }
    ll modinv(ll a, ll m) {
        ll b = m, u = 1, v = 0;
        while (b) {
            ll t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        u %= m;
        if (u < 0) u += m;
        return u;
    }
    ll c(int x, int y) {
        if (x < y || y < 0) return 0;
        return kaijou[x] * modinv(kaijou[x - y] * kaijou[y], MOD) % MOD;
    }
    ll h(int x, int y) {
        return c(x + y - 1, y);
    }
    ll calc(int R, int C) {
        ll ret = 0;
        for (int k = 0; k <= C; k++) {
            ret += c(k + R + 1, k + 1);
            ret %= MOD;
        }
        return ret;
    }
};

int main() {
    Combination comb;
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    ll ans = 0;
    ans += comb.calc(r2, c2);
    ans %= MOD;
    ans += (MOD - comb.calc(r1 - 1, c2));
    ans %= MOD;
    ans += (MOD - comb.calc(r2, c1 - 1));
    ans %= MOD;
    ans += comb.calc(r1 - 1, c1 - 1);
    ans %= MOD;
    cout << ans << endl;
}


Measured memory_bytes: 23680
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using ull = unsigned long long;

typedef pair<ll, ll> P;
typedef pair<double, double >pd;
typedef pair<string, string> sP;
typedef pair<ll, P> PP;
typedef pair<P, P> PPP;

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 5e14;
const double eps = 1e-10;
const double PI = acos(-1);
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second


ll n, a[100010], rui[100010], m, ans;
map<ll, ll>mp;

int main() {
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		rui[i + 1] = rui[i] + a[i];
		rui[i + 1] %= m;
	}
	mp[0] = 1;
	for (int i = 1;i <= n;i++) {
		ans += mp[rui[i]];
		mp[rui[i]]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5760
#include <iostream>
#define ll long long
using namespace std;
int main(){
	ll n,k;
	cin>>n>>k;
	ll s=1;
	for(ll i=0;i<n-1;i++){
		s*=(k-1);
	}
	s=s*k;
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 25, M = 1e6 + 25, oo = 1e9+7, mxmsk = 1 << 16;
const long long OO = 1e18+25;
    
#define f first
#define s second

long long n, mn=OO;
char s[100];
int main() {
    cin >> n;
    for(int i=1; 1ll*i*i<=n; i++) 
        if(n % i == 0)
        {
            mn = min (mn, i + n/i);
        }
    printf("%lld",mn-2);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n), b(n);
	rep(i, n) cin >> a[i] >> b[i];
	ll ans = 0;
	ll prev_sum = 0;
	for (int i = n - 1; i >= 0; --i) {
		a[i] += prev_sum;
		if (a[i] % b[i] == 0) continue;
		a[i] %= b[i];
		ans += b[i] - a[i];
		prev_sum += b[i] - a[i];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1792
num = list(map(int,raw_input().split()))
point = num[0]
line = num[1]
total = 0
d = {}
for i in range (point):
    d[i+1] = []
for i in range(line):
    pair = list(map(int,raw_input().split()))
    d[pair[0]].append(pair[1])
    d[pair[1]].append(pair[0])
old_list = []
new_list = [[1]]
for i in range (point-1):
    old_list = new_list[:]
    new_list =[]
    for j in old_list:
        for k in d[j[-1]]:
            if k in j:
                pass
            else:
                j.append(k)
                new_list.append(j[:])
                j.pop()
print len (new_list)


Measured memory_bytes: 4484
#include <iostream>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
using ll = long long;

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

    map<ll, ll> mp;
    ll ans = 0LL;
    
    for(int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        mp[a]++;
        ans += a;
    }


    int q;
    cin >> q;

    for(int i = 0; i < q; i++) {
        int b, c;
        cin >> b >> c;
        mp[c] += mp[b];
        ans = ans + (c - b) * mp[b];
        
        mp.erase(b);

        // cout << "size: " << mp.size() << endl;
        
        cout << ans << endl;
    }

    return 0;
}

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

int main()
{
  int n;
  cin>>n;
  vector<float> v(n);
  for(float &i:v) cin>>i;
  sort(v.rbegin(),v.rend());
  n--;
  while(n--)
  {
    float k = v[v.size()-1]+v[v.size()-2];
    k/=2.0;
    v.pop_back();v.pop_back();
    v.push_back(k);
    sort(v.rbegin(),v.rend());
    
  }
  cout<<v.back()<<"\n";
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	string ss;
	cin >> ss;
	int64 pp = 0;
	for(int64 ii = 0;ii < ss.length();ii++)
	{
		if(ss[ii] == 'p')
		{
			pp++;
		}
	}
	pp = ss.length() / 2 - pp;
	cout << pp << endl;
	return 0;
}

Measured memory_bytes: 3728
import scala.io.{StdIn => in}

object Main extends App {
  val Array(a, b) = in.readLine.split(" ").map(_.toInt)
  val s = in.readLine

  val ans = if(s.filter(_!='-').size == a + b && s.charAt(a) == '-') "Yes" else "No"
  println(ans)
}

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

int main(){
    string s[3];
    for(int i=0; i<3; i++) cin>>s[i];

    int cur = 0;
    char ans;

    while(1){
        if(s[cur].size() == 0){
            ans = 'A' + cur;
            break;
        }
        char c = s[cur][0];
        s[cur].erase(0,1);
        int dif = 'a' - 'A';
        c -= dif;
        cur = c - 'A';
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <math.h>
#include <limits.h>

using namespace std;

int main() {
	int n, r;
	cin >> n >> r;
	int ans = n;
	int count = 0;
	while (ans > 0) {
		ans /= r;
		count++;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
//
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(size_t i = 0; i < (n); ++i)

int main()
{
    string S;
    cin >> S;
    if (S.compare("RRR") == 0)
    {
        cout << 3 << endl;
        return 0;
    }
    else if (S.substr(0, 2).compare("RR") == 0 || S.substr(1, 2).compare("RR") == 0)
    {
        cout << 2 << endl;
        return 0;
    }
    REP(i, S.size())
    {
        if (S[i] == 'R')
        {
            cout << 1 << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 3592