akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define TIME ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
    const ll N = 2e5 + 7;
ll n , k , a[N] , cnt;
int main(){
    TIME
    cin >> n >> k;
    for(int i = 1; i <= n ; i ++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= max(0ll , n - k); i ++){
        cnt += a[i];
    }
    cout << cnt;
}
///...


Measured memory_bytes: 1792
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<complex>
#include<stack>
#include<cmath>

using namespace std;

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


int main(){
	
	int a,b,c,d,e;
	while(scanf("%d,%d,%d,%d,%d",&a,&b,&c,&d,&e)!=EOF){
		typedef map<int,int> mii;
		
		mii m;
		m[a]++;
		m[b]++;
		m[c]++;
		m[d]++;
		m[e]++;
		
		typedef pair<int,int> pii;
		vector<pii> dat;
		mii::iterator it = m.begin();
		while(it!=m.end()){
			dat.push_back(pii(-it->second,it->first));
			it++;
		}
		sort(dat.begin(),dat.end());
		rep(i,dat.size())dat[i].first*=-1;
		
		
		bool flg[8]={false};
		flg[1]=true;
		if(dat[0].first==2){
			flg[2]=true;
		}
		if(dat[0].first==2 && dat[1].first==2){
			flg[3]=true;
		}
		if(dat[0].first==3){
			flg[4]=true;
		}
		
		if(dat.size()==5){
			int st = 0;
			if(dat[0].second==1 && dat[4].second==13)st=1;
			bool ok=true;
			reps(i,st,dat.size()-1){
				if(dat[i].second+1!=dat[i+1].second)ok=false;
			}
			flg[5]=ok;
		}
		
		if(dat[0].first==3 && dat[1].first==2){
			flg[6]=true;
		}
		if(dat[0].first==4){
			flg[7]=true;
		}
		
		//rep(i,dat.size())printf("%d-%d ",dat[i].first,dat[i].second);puts("");
		
		string yaku[8]={
			"null",
			"null",
			"one pair",
			"two pair",
			"three card",
			"straight",
			"full house",
			"four card"
		};
		
		for(int i=7;i>=1;i--){
			if(flg[i]){
				cout<<yaku[i]<<endl;
				break;
			}
		}
		
	}
}

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

int main(){
    int H,N,i,sum=0;
    cin >> H >> N;
    int A[N];
    for(i=0;i<N;i++){
        cin >> A[i];
        sum = sum + A[i];
    }

    if(sum >= H) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
int W,H,x,y,r;

scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);

if (H>=y+r&&W>=x+r&&x-r>=0&&y-r>=0)
{
printf("Yes\n");
}else{
printf("No\n");
}

return 0;
}

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

int main() {

  string S;
  cin >> S;

  while(true){
    S = S.substr(0, S.size()-1);
    if(S.size() % 2 == 1){
      continue;
    }
     else if(S.substr(0, S.size()/2) == S.substr(S.size()/2, S.size())){
        cout << S.size() << endl;
       	return 0;
    }
  }
}


Measured memory_bytes: 256
using namespace std;
#include<bits/stdc++.h>
#define st first
#define nd second
#define FORE(i,a,b) for(int i=(a),b_=(b);i<=b_;++i)
#define FORD(i,a,b) for(int i=(a),b_=(b);i>=b_;--i)
#define TR(c, it) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)

const int MAXN = 2e5 + 1 ;
long long f[MAXN] ;
vector <int> g[MAXN];
int n, m;
void dfs (int u, int parent){
    TR(g[u], it){
        int v = *it;
        if(v == parent) continue;
        f[v] += f[u] ;
        dfs(v , u);
    }
}

int main()
{
#define TASK "NAME"
    // freopen(TASK".inp","r",stdin);
    // freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m ;
    for (int i = 1; i <= n; ++i) f[i] = 0;
    for (int i = 1; i < n ; ++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= m; ++i){
        int u, p ;
        cin >> u >> p;
        f[u] += p;
    }
    dfs(1, -1);
    for (int i = 1; i <= n; ++i) cout << f[i] << " ";


    return 0;
}


Measured memory_bytes: 24320
n = int(input())
xy=[list(map(int,input().split())) for i in range(n)]
from collections import defaultdict
x_d = defaultdict(list)
y_d = defaultdict(list)
for i in range(n):
    x,y = xy[i]
    x_d[x].append(i)
    y_d[y].append(i)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
uf = UnionFind(n)
for k in x_d.keys():
    if len(x_d[k])==1:
        continue
    last=x_d[k][0]
    for itm in x_d[k]:
        uf.union(last, itm)
        last=itm

for k in y_d.keys():
    if len(y_d[k])==1:
        continue
    last=y_d[k][0]
    for itm in y_d[k]:
        uf.union(last, itm)
        last=itm
ans=0
for root in uf.roots():
    mems = uf.members(root)
    xset=set()
    yset=set()
    for m in mems:
        x,y=xy[m]
        xset.add(x)
        yset.add(y)
    points = len(xset)*len(yset)
    points -= len(mems)
    ans+=points
print(ans)

Measured memory_bytes: 115876
import Data.List

f :: [Int]->[Int]
f (x:[])=[]
f (x:y:zs)=(x-y):f (y:zs)

f2::String->[Int]
f2 e=f $ map read (words e)::[Int]

main = do
       e1<-getLine
       e2<-getLine
       e3<-getLine
       let m1=f2 e1
           m2=f2 e2
           m3=f2 e3
       putStrLn $ if m1==m2 && m2==m3 then "Yes" else "No"

Measured memory_bytes: 508
program zabuton
  implicit none
  integer(8), parameter :: infty = 1000000000000000000_8
  integer :: n, i, j
  integer(8) :: h(5000), p(5000), dp(0:5000,0:5000)
  h = 0_8
  p = 0_8
  dp = infty
  dp(0,0) = 0_8
  read(*,*) n
  do i = 1, n
    read(*,*) h(i), p(i)
  end do
  call merge_sort(h(1:n),p(1:n))
  do i = 1, n
    do j = n, 1, -1
      dp(i,j) = dp(i-1,j)
      if (dp(i-1,j-1).le.h(i)) dp(i,j) = min(dp(i,j),dp(i-1,j-1)+p(i))
    end do
  end do
  do i = n, 1, -1
    if (dp(n,i).ne.infty) then
      write(*,'(i0)') i
      stop
    end if
  end do
  stop
contains
  subroutine merge_sort(x,y)
    implicit none
    integer(8), intent(inout) :: x(:), y(:)
    integer :: n, m, l, i, u
    n = size(x)
    m = n
    l = 1
    do while (m.gt.1)
      do i = 1, m/2
        u = min(2*i*l,n)
        call merger(x(2*(i-1)*l+1:(2*i-1)*l),x((2*i-1)*l+1:u), &
        &           y(2*(i-1)*l+1:(2*i-1)*l),y((2*i-1)*l+1:u))
      end do
      l = 2*l
      m = (m+1)/2
    end do
    return
  end subroutine merge_sort
  subroutine merger(x1,x2,y1,y2)
    implicit none
    integer(8), intent(inout) :: x1(:), x2(:), y1(:), y2(:)
    integer(8) :: x(size(x1)+size(x2)), y(size(y1)+size(y2))
    integer :: i1, i2, n1, n2
    i1 = 1
    i2 = 1
    n1 = size(x1)
    n2 = size(x2)
    do while (i1.le.n1.and.i2.le.n2)
      if (x1(i1)+y1(i1).le.x2(i2)+y2(i2)) then
        x(i1+i2-1) = x1(i1)
        y(i1+i2-1) = y1(i1)
        i1 = i1+1
      else
        x(i1+i2-1) = x2(i2)
        y(i1+i2-1) = y2(i2)
        i2 = i2+1
      end if
    end do
    if (i1.le.n1) then
      x(i1+i2-1:n1+n2) = x1(i1:n1)
      y(i1+i2-1:n1+n2) = y1(i1:n1)
    else if (i2.le.n2) then
      x(i1+i2-1:n1+n2) = x2(i2:n2)
      y(i1+i2-1:n1+n2) = y2(i2:n2)
    end if
    x1 = x(1:n1)
    x2 = x(n1+1:n1+n2)
    y1 = y(1:n1)
    y2 = y(n1+1:n1+n2)
    return
  end subroutine merger
end program zabuton

Measured memory_bytes: 195712
class UFtree
    def initialize(len)
        @len=len
        @Tree=Array.new(len,-1)
        @Rank=Array.new(len,0)
    end

    def find_root(x)

        if @Tree[x] < 0 
            return x
        end
        root=find_root(@Tree[x])
        @Tree[x]=root
        return root
    end

    def unite(x,y)
        x=find_root(x)

        y=find_root(y)

        if x==y
            return
        elsif @Rank[x] > @Rank[y] then
            @Tree[x]+=@Tree[y]
            @Tree[y]=x
        else
            @Tree[y]+=@Tree[x]
            @Tree[x]=y

            if @Rank[x]==@Rank[y]
                @Rank[y]+=1
            end
        end
    end




end


N,K,L =gets.split.map{|i| i.to_i}
RoadTree=UFtree.new(N)
TrainTree=UFtree.new(N)
for i in 1..K
    p,q=gets.split.map{|i| i.to_i-1}
    RoadTree.unite(p,q)

end

for i in 1..L
    p,q=gets.split.map{|i| i.to_i-1}
    TrainTree.unite(p,q)
end

cmbnations={}

for i in 0...N
    r=RoadTree.find_root(i)
    l=TrainTree.find_root(i)
    if !cmbnations.has_key?(r)
        cmbnations[r]={}
    end
    if !cmbnations[r].has_key?(l)
        cmbnations[r][l]=0
    end


    cmbnations[r][l]+=1


end

puts (0...N).map{|i| cmbnations[RoadTree.find_root(i)][TrainTree.find_root(i)]}.join(" ")




Measured memory_bytes: 73980
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, k, s, t, a[55];
long long ans, candi[2][18], combi[60][60], F[60];
vector<int> vec;

int cnt_bit(long long x)
{
	int cnt = 0;
	while (x) {
		if (x & 1) cnt++;
		x = x >> 1;
	}
	return cnt;
}

void fun(int cur, int sign, long long res, int v)
{
	if (cur == 18) {
		int tmp = cnt_bit(res);
		ans += sign * F[tmp];
	}
	else {
		if (((t >> cur) & 1) ^ ((s >> cur) & 1)) {
			if ((v >> cur) & 1) {
				fun(cur + 1, sign, res, v);
				fun(cur + 1, -sign, res & candi[1][cur], v);
			}
			else {
				fun(cur + 1, sign, res, v);
				fun(cur + 1, -sign, res & candi[0][cur], v);
			}
		}
		else fun(cur + 1, sign, res, v);
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for (int i = 1; i <= 50; i++) combi[i][0] = 1;
	combi[1][1] = 1;
	for (int i = 2; i <= 50; i++) {
		for (int j = 1; j <= i; j++) {
			combi[i][j] = combi[i - 1][j] + combi[i - 1][j - 1];
		}
	}
	cin >> n >> k;
	cin >> s >> t;
	for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i <= 50; i++) {
		for (int j = 1; j <= min(i, k - 1); j++) {
			F[i] += combi[i][j];
		}
	}
	if (((s & t) != s) || ((s | t) != t)) {
		cout << 0 << E;
	}
	else {
		for (int i = 0; i < n; i++) {
			if ((a[i] & s) != s) continue;
			if ((a[i] | t) != t) continue;
			vec.pb(a[i]);
		}
		int sz = vec.size();
		for (int i = 0; i < sz; i++) {
			if (s == t && vec[i] == t) {
				ans++;
			}
			memset(candi, 0, sizeof(candi));
			for (int j = 0; j < i; j++) {
				for (int u = 0; u < 18; u++) {
					candi[(vec[j] >> u) & 1][u] += 1LL << j;
				}
			}
			fun(0, 1, (1LL << i) - 1, vec[i]);
		}
		cout << ans << E;
	}
	//system("pause");
	return 0;
}

Measured memory_bytes: 3684
#include <iostream>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
    set<char>st;
    string p;
    cin >> p;
    for(int i = 0; i < 3; i++)
    {
        st.insert(p[i]);
    }
    if(st.size() == 2)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
from collections import deque
dic = {}
def make_map(a, b, dic):
    if a in dic.keys():
        dic[a].append(b)
    else:
        dic[a] = [b]
N, M = map(int, input().split())
for m in range(M):
    a, b = map(int, input().split())
    make_map(a-1, b-1, dic)
    make_map(b-1, a-1, dic)
queue = deque([0])
count = 0
dekai = 10**5
lenlist = [dekai]*N
lenlist[0] = 0
while queue:
    a = queue.popleft()
    for i in dic[a]:
        if lenlist[i] ==dekai or a == 0:
            queue.append(i)#今までいったことないなら見るリストに追加
            lenlist[i] = a #今いる座標の距離+!が次の座標の距離
print("Yes")
for n in range(1,N, 1):
    print(lenlist[n]+1)

Measured memory_bytes: 43424
from collections import deque

s = input()
q = int(input())

que = deque(s)

flipped = False
for i in range(q):
    query = input()
    if query[0] == "1":
        flipped = not flipped
    else:
        t, f, c = query.split()
        if (f == "1") ^ flipped:
            que.appendleft(c)
        else:
            que.append(c)
s = "".join(que)
if flipped:
    s = s[::-1]
print(s)

Measured memory_bytes: 8684
import itertools
from bisect import bisect
N, M, K = map(int, input().split())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)
B_sum = [0]
for b in B:
    B_sum.append(B_sum[-1]+b)
ans = 0
for i, num in enumerate(A_sum):
    target = K - num
    if target < 0:
        break
    j = bisect(B_sum, target)
    ans = max(ans, i+j-1)
print(ans)

Measured memory_bytes: 143592
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner cin = new Scanner(System.in);
		
		int S,W;
		
		S = cin.nextInt();
		W = cin.nextInt();
		
		System.out.println(W>=S?"unsafe":"safe");
	}

}


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


int main() {
    int N,K;
    cin >> N >> K;
    
    int X = (N-1)*(N-2)/2 - K;
    
    if ( X < 0 ){
        cout << -1 << endl;
    } else {
        cout << N - 1 + X << endl;
        for ( int i = 0; i < N-1; ++i){
            cout << 1 << " " << i+2 << endl;
        }
        int count = 0;
        bool flg = false;
        if ( X != 0 ){
            for ( int i = 2; i < N; ++i){
                for ( int j = i + 1; j <= N; ++j){
                    cout << i << " " << j << endl;
                    ++count;
                    if ( count == X ) {
                        flg = true;
                        break;
                    }
                }
                if ( flg ) break;
            }
        }
    }
    
    return 0;
}


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

int main(){
    int a[20],b[110],c[20];
    int N;
    for(int i = 0;i < 9;i++){
        cin >> a[i];
    }
    for(int i = 0;i < 9;i++) c[i] = a[i];
    cin >> N;
    for(int i = 0;i < N;i++){
        cin >> b[i];
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < 9;j++){
            if(b[i] == c[j]) a[j] = 0;
        }
    }
        int f = a[0] + a[1] + a[2];
        int g = a[3] + a[4] + a[5];
        int h = a[6] + a[7] + a[8];
        int j = a[0] + a[3] + a[6];
        int k = a[1] + a[4] + a[7];
        int l = a[2] + a[5] + a[8];
        int z = a[0] + a[4] + a[8];
        int t = a[2] + a[4] + a[6];
        if(f==0|| g==0 || h==0 || j==0 || k==0 || l==0 || z==0 || t==0){
            cout << "Yes" << endl;
        }else cout << "No" <<endl;
    return 0;
}

Measured memory_bytes: 256
import math
N = int(input())
S = []
ans = 0
count = 1
for _ in range(N):
    s = list(input())
    s.sort()
    S.append(''.join(s))
S.sort()
S.append('a')

for i in range(N):
    if S[i] == S[i+1]:
        count += 1
    else:
        if count > 2:
            ans += math.factorial(count)//(math.factorial(count-2)*math.factorial(2))
        elif count == 2:
            ans += 1
        count =1

print(ans)

Measured memory_bytes: 11476
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  double v,ans;
  cin>>N;
  vector<double>X(N);
  
  for(int i=0;i<N;i++){
  	cin>>X.at(i);
  }
  
  vector<double>Y(100);
  for(int e=0;e<100;e++){
  	Y.at(e)=0;
    for(int f=0;f<N;f++){
  		Y.at(e)+=(X.at(f)-e)*(X.at(f)-e);
  	}
  }
  ans=min(Y.at(0),Y.at(1));
  for(int k=0;k<100;k++){
  	ans=min(ans,Y.at(k));
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I() + 1
A = LI()
D = defaultdict(lambda:-1)
for i in range(n):
    if D[A[i]] != -1:
        l = D[A[i]]
        r = n - i - 1
        break
    else:
        D[A[i]] = i


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


for j in range(1, n + 1):
    print((comb(n, j) - comb(r + l, j - 1)) % mod)


Measured memory_bytes: 65568
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s, n) for(int i = s; i < (int)(n); i++)
#define co(x) cout<<x<<endl
#define SQvec(i,j) vector<vector<int>> data(i, vector<int>(j))
#define mod 1000000007
typedef long long int lint;

int main(){
  int A,B;
  cin >> A >> B;
  
  co(A*B);  
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
std::string s;
int len;
int ans=INF;
int main(){
	std::cin>>s;
	len=s.size();
	for(int i=0;i<len;i++){
		if(s[i]!=s[i-1]) ans=std::min(ans,std::max(i,len-i));
	}
//	ans=std::min(ans,len);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 512
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    int a, b, c,d;
    cin >> a >> b >> c >> d;
    cout << min(a, b) + min(c,d) << endl;
}

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

int main(){
    int n, m, ans = 0, count = 0;
    string str;
    vector<string> s(100);
    vector<string> t(100);
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> s.at(i);
    }
    cin >> m;
    for(int i = 0; i < m; ++i){
        cin >> t.at(i);
    }
    for(int i = 0; i < n; ++i){
        str = s.at(i);
        count = 0;
        for(int j = 0; j < n; ++j){
            if(str == s.at(j))
                count++;
        }
        for(int j = 0;j < m; ++j){
            if(str == t.at(j))
                count--;
        }
        if(count > ans)
            ans = count;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3168
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define ll long long
#define db double
ll a[100005];
ll sumj[100005];
ll sumo[100005];
int main()
{
    ll n,cntj=1,cnto=1;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(i%2)
        {
            sumj[cntj]=sumj[cntj-1]+a[i];
            cntj++;
        }
        else
        {
            sumo[cnto]=sumo[cnto-1]+a[i];
            cnto++;
        }
    }
    ll sum=sumj[cntj-1]+sumo[cnto-1];
    for(int i=1;i<=n;i++)
    {
        if(i%2)
        {
            ll ans=a[i]-sumj[(i-1)/2]+sumo[(i-1)/2]+(sumj[cntj-1]-sumj[(i+1)/2])-(sumo[cnto-1]-sumo[(i-1)/2]);
            printf("%lld ",ans);
        }
        else
        {
            ll ans=a[i]+sumj[i/2]-sumo[i/2-1]+(sumo[cnto-1]-sumo[i/2])-(sumj[cntj-1]-sumj[i/2]);
            printf("%lld ",ans);
        }
    }
    return 0;
}




Measured memory_bytes: 5396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define foreach( gg,itit )  for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define mp make_pair
#define pb push_back
#define all(s) s.begin(),s.end()
#define present(c,x) ((c).find(x) != (c).end())
const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF = 1e18;

//#define DEBUG
ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}
#ifdef DEBUG
#define dprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#else
#define dprintf(fmt,...)
#endif

set<int> S;
int main(){
  int n; scanf("%d",&n);
  int x=0;
  REP(i,n){
    int p ; scanf("%d",&p);
    if(S.count(p)) x++;
    S.insert(p);
  }
  if(x%2) x++;
  printf("%d\n",n-x);
  return 0;
}

Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		
		
		int count=0;
		for (int i=1;i<=n;i++) {
			int p= sc.nextInt();
 
			if (p!=i) {
				count++;
			}
 
		}
		if(count<=2) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}

	}

}


Measured memory_bytes: 23764
/*input

*/


//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 2e6+5,mod = 1e9+7;
vi fact_mod(N),inv_fact_mod(N);

ll power(ll x,ll y)
{
	ll ans=1;
	while(y)
	{
		if(y&1) ans = (ans*x)%mod;
		y>>=1;
		x=(x*x)%mod;
	}
	return ans;
}

ll inv(ll n)
{
	return power(n,mod-2);
}

void init()
{
	fact_mod[0]=inv_fact_mod[0]=1;
	rep(i,1,N) fact_mod[i] = (fact_mod[i-1]*i)%mod,inv_fact_mod[i] = (inv_fact_mod[i-1]*inv(i))%mod;
}

ll ncr(ll n,ll r)
{
	if(r<=n && n>=0 && r>=0)
	{
		ll ans = fact_mod[n];
		ans = (ans*inv_fact_mod[n-r])%mod;
		ans = (ans*inv_fact_mod[r])%mod;
		return ans;
	}
	else return 0;
}

ll nSr(ll n,ll k)
{
	ll ans=0;
	rep(i,0,k+1)
	{
		ll temp_ans = (ncr(k,i)*power(k-i,n))%mod;
		ans = (ans+(i%2==0?1:-1)*temp_ans+mod)%mod;
	}
	ans = (ans*inv_fact_mod[k])%mod;
	return ans;
}

ll g(ll a,ll d)
{
	ll ans = 0;
	rep(x,0,a+1)
	{
		ans+=ncr(d+1+x,d);
		if(ans>=mod) ans-=mod;
	}
	return ans;
}

//574642047

int solve()
{
	init();
	ll a,b,c,d;cin>>a>>c>>b>>d;
	ll ans = g(b,d);
	ans = (ans - g(a-1,d)+mod)%mod;
	ans = (ans - g(b,c-1)+mod)%mod;
	ans = (ans+g(a-1,c-1))%mod;

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

int main()
{
	auto start = chrono::high_resolution_clock::now();

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	// cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

Measured memory_bytes: 31488
#include <iostream>
#include <stack>

using namespace std;

typedef struct tree {
	int item;
	tree* right = NULL;
	tree* left = NULL;
}tree;

int n;
int k = 0;
int a[101];
int b[101];

void print(tree* p) {
	if (p->left != NULL) {
		print(p->left);
	}
	if (p->right != NULL) {
		//cout << ' ';
		print(p->right);
	}
	cout << p->item << ' ';
}

void rebuild(int root, int begin, int left, tree * p) {
	p->item = b[root];
	k++;
	
	if(root != begin)
		for (int i = begin; i < root; ++i) {
			if (a[k] == b[i]) {

				p->left = new tree();
				rebuild(i, begin, root - 1, p->left);
			}
		}
	if(root != left)
		for (int i = root+1; i < left+1; ++i) {
			if (a[k] == b[i]) {
				p->right = new tree();
				rebuild(i, root+1, left, p->right);
			}
		}
}

int main() {
	cin >> n;
	tree trees;
	tree* p1 = &trees;
	stack<tree> T;

	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}
	
	for (int i = 0; i < n; ++i) {
		if (b[i] == a[0]) {
			rebuild(i, 0, n - 1, p1);
			break;
		}
	}

	p1 = &trees;
	if (p1->left != NULL) {
		print(p1->left);
	}
	if (p1->right != NULL) {
		//cout << ' ';
		print(p1->right);
	}
	cout << p1->item<<endl;

	return 0;
}


Measured memory_bytes: 3100
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = 1ll << 60;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	vector<ll> a(n);
	vector<ll> b(n - 1);

	for (ll i = 0; i < n - 1; i++)
	{
		cin >> b[i];
	}

	a[0] = b.front();
	a[n - 1] = b.back();

	for (ll i = 1; i < n - 1; i++)
	{
		a[i] = min(b[i - 1], b[i]);
	}

	println(accumulate(all(a), 0LL));
}


Measured memory_bytes: 256
K = input()
A = map(int, raw_input().split())
if A[-1]!=2:
  print -1
  exit(0)
mn = 2
mx = 3
for a in A[-2::-1]:
  mn = (mn+a-1)/a*a
  mx = mx/a*a+a-1
if mn<=mx:
  print mn, mx
else:
  print -1


Measured memory_bytes: 11340
N=int(input())
ans=[]
m=10**10
for i in range(0,N):
    a=int(input())
    if m>=a:
        ans.append(a)
        m=a
    else:
        start=0
        end=len(ans)-1
        while end-start>1:
            test=(end+start)//2
            if a>ans[test]:
                end=test
            else:
                start=test
        if a>ans[start]:
            ans[start]=a
            if start==len(ans)-1:
                m=a
        else:
            ans[end]=a
            if end==len(ans)-1:
                m=a

print(len(ans))


Measured memory_bytes: 55640
#include <stdio.h>

int main(void)
{
    int i, j;

    int a[4], b[4];
    while (scanf("%d", a) != EOF) {
        for (i = 1; i < 4; i++) {
            scanf("%d", a + i);
        }
        for (i = 0; i < 4; i++) {
            scanf("%d", b + i);
        }

        int hit = 0, blow = 0;
        for (i = 0; i < 4; i++) {
            for (j = 0; j < 4; j++) {
                if (a[i] == b[j]) {
                    if (i == j) {
                        hit++;
                    } else {
                        blow++;
                    }
                }
            }
        }

        printf("%d %d\n", hit, blow);
    }

    return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <math.h>

using namespace std;

int main() {
    long long int h;
    cin >> h;

    long long int log2h = (long long int) log2(h);
    long long int expAns = (long long int) exp2(log2h);
    long long int ans = 2 * expAns - 1;

    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 640
import Control.Monad
import Data.Fixed
import Data.List
import Data.Monoid
import Data.Ord
import Text.Printf
 
readInt = read :: String -> Int
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y

angleFrom (x0,y0) (x,y) = atan2 (fromIntegral (y-y0)) (fromIntegral (x-x0))

convex :: [(Int,Int)] -> [(Int,Int)]
convex ps = firstP : sub firstP 0
  where
    sub p a = let np = nextP p a in if np==firstP then [] else np : sub np (angleFrom p np)
    firstP = minimumBy (comparing snd <> flip (comparing fst)) ps
    nextP p a = minimumBy (comparing (flip mod' (2*pi) . subtract a . angleFrom p)) (delete p ps)

solve :: Int -> [(Int,Int)] -> [Double]
solve 2 ps = [0.5,0.5]
solve n ps = [if p `elem` cvx then calc p else 0.0 | p <- ps]
  where
    cvx = convex ps
    calc p = fsub (cycle cvx) p
    fsub (v1:r@(v2:v3:_)) p
      | v2==p = mod' (angleFrom v3 v2 - angleFrom v2 v1) (2*pi) / (2*pi)
      | otherwise = fsub r p

main = do
    n <- getInt
    ps <- map (apply2 (,)) <$> replicateM n getInts
    forM_ (solve n ps) $ printf "%.15f\n"


Measured memory_bytes: 1404
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,i,j,k,qx[1005*1005],qy[1005*1005],bg,ed,dis[1005][1005],f[10][5]={{-1,0},{1,0},{0,-1},{0,1}};
char s[1005][1005];
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
	{	
		scanf("%s",s[i]+1);
		for(j=1;j<=m;++j)
			if(s[i][j]=='#')
			{
				++ed;
				qx[ed]=i,qy[ed]=j;
			}
			else
				dis[i][j]=-1;
	}
	bg=1;
	while(bg<=ed)
	{
		for(i=0;i<4;++i)
		{
			j=qx[bg]+f[i][0],k=qy[bg]+f[i][1];
			if(j>=1&&j<=n&&k>=1&&k<=m&&dis[j][k]==-1)
			{
				dis[j][k]=dis[qx[bg]][qy[bg]]+1;
				++ed;
				qx[ed]=j,qy[ed]=k;
			}
		}
		++bg;
	}
	k=0;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			k=max(k,dis[i][j]);
	printf("%d",k);
	return 0;
}


Measured memory_bytes: 12928
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
using ll = long long;
using P = pair<int, int>;
const int INF (1<<30);

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  int ans;

  if (K <= A) {
    ans = K;
  }
  else if (K <= (A+B)) {
    ans = A;
  }
  else {
    ans = A - (K-(A+B));
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define pb(a) push_back(a)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n, len;
    while(cin >> n, n){
        string s; 
        cin >> len >> s;
        int ans = 0, count = 0;
        rep(i,len - 2){
            if(s[i] == 'I'){
                if(s[i + 1] == 'O' && s[i + 2] == 'I'){
                    count++;
                }else{
                    count = 0;
                }
                if(count >= n) ans++;
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 2108
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
ll a[maxn];
 
int main()
{
	ll n,q,x,y;ll sum=0;
	cin>>n;map<ll,ll> mp;
	for(ll i=0;i<n;i++){
		cin>>a[i];mp[a[i]]++;sum+=a[i];
	} 
	cin>>q;
	while(q--){
		cin>>x>>y;
		ll num=mp[x];
		sum-=num*x;mp[x]=0;
		sum+=num*y;mp[y]+=num;
		cout<<sum<<endl;
	}
	return 0;	
}

Measured memory_bytes: 9744
#!/usr/bin/perl

$line = 0;
while (<>) {
    @p = split /\s+/, $_;
}

$n = 0;
foreach (sort {$a <=> $b} @p) {
    if($n > 1) {
        last;
    }
    $total += $_;
    $n++;
}

print "$total\n";


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

int main(){
  int N; cin>>N;
  
  vector<vector<ll>> wf(N,vector<ll>(N));
  REP(i,N)REP(j,N) cin>>wf[i][j]; 
  
  REP(k,N)REP(i,N)REP(j,N)
    if(wf[i][j]>wf[i][k]+wf[k][j]) {
      cout<<-1<<endl; 
      return 0;
    }

  ll ans=0;
  REP(i,N)REP(j,N){
    ans+=wf[i][j];
    REP(k,N) {
      if(i!=k&&k!=j&&wf[i][j]==wf[i][k]+wf[k][j]) {
        ans-=wf[i][j];
        break;
      }
    }
  }
  ans/=2;
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

/* LIS variation */

const int mod = 1e9+7;
const int maxn = 2e3+3;
int dp[maxn][maxn]; VI S,T;

int dfs(const int i, const int j)
{
    if (i == S.size() || j == T.size())
        return 0;
    int& ans = dp[i][j];
    if (-1 == ans) {
        ans = 0;
        if (S[i] == T[j]) {
            /* sequence starting at i,j; +1 for just i,j */
            ans += dfs(i+1,j+1) + 1;
            ans %= mod;
        }
        /* not use i */
        ans += dfs(i+1,j);
        ans %= mod;
        /* not use j */
        ans += dfs(i,j+1);
        ans %= mod;
        /* overlap */
        ans -= dfs(i+1,j+1);
        ans %= mod;
    }
    return ans;
}

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    int n,m;
    while (cin >> n >> m) {
        memset(dp,-1,sizeof(dp));
        S = VI(n); T = VI(m);
        FOR(i,0,n)
            cin >> S[i];
        FOR(i,0,m)
            cin >> T[i];
        /* +1 for empty set */
        cout << (dfs(0,0) + 1 + mod) % mod << endl;
    }
    return 0;
}


Measured memory_bytes: 16256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<int> vec;

void solve() {
	int a, b, x; cin >> a >> b >> x;
	if (a <= x && x <= a + b) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(6);
	//init();
	solve();
	stop
		return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int N,a[1010]={};
int main(){
  cin >> N;
  for (int i=0;i<N;i++){
    cin >> a[i];
  }
  sort(a,a+N);
  cout << a[N-1] - a[0] << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int n;
int hap[100002][3]={};
int max(int a,int b)
{
	return a>b? a:b;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=0;j<3;j++)
		{
			scanf("%d",&hap[i][j]);
			hap[i][j]+=max(hap[i-1][(j+1)%3],hap[i-1][(j+2)%3]);
		}
	printf("%d",max(hap[n][0],max(hap[n][1],hap[n][2])));
	return 0;
}

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

const long long MOD = 1e9+7;

long long getPower(long long base, long long power){
    if(power==0){
        return 1;
    }
    long long x=getPower(base, power/2);
    x=(x*x)%MOD;

    if(power%2){
        return (base*x)%MOD;
    }else{
        return (x)%MOD;
    }
}

long long buildAnswer(long long n){
    long long x=getPower(10, n);
    long long y=getPower(9, n);
    y=(y*2)%MOD;
    long long z=getPower(8, n);

    return (x-y+z+MOD)%MOD;
}

int main(){
    long long n;
    cin>>n;
    cout<<buildAnswer(n)<<endl;
}

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

int main() {
    int n, ans = 0, tmp = 0;
    cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; ++i) {
        cin >> h[i];
        if(i == 0)
            continue;
        if(h[i] <= h[i - 1])
            tmp++;
        else {
            ans = max(ans, tmp);
            tmp = 0;
        }
    }
    cout << max(ans, tmp) << endl;
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>

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

using namespace std;

int main(){
    int k; cin >> k;
    int array[k]; REP(i, k) cin >> array[i];

    sort(array, array + k);
    cout << array[k/2] - array[k/2 - 1];                               
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int acs(const void *a, const void *b) { 
  return *(int*)a - *(int*)b;
} /* 1,2,3,4.. */
int des(const void *a, const void *b) {
  return *(int*)b - *(int*)a;
} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { 
  return *(char*)a - *(char*)b;
} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
} /* aaa,aab.. */
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  int n, r;
  scanf("%d %d", &n, &r);

  if (n >= 10) printf("%d\n", r);
  else printf("%d\n", r + 100 * (10 - n));
  return 0;
}


Measured memory_bytes: 128
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    ll n,ans=0; cin>>n;
    vector<ll> a(n,0),b(n,0);
    rep(i,n){
        cin>>a[i]>>b[i];
    }
    reverse(al(a)); reverse(al(b));
    rep(i,n){
        ans+=(b[i]-(a[i]+ans)%b[i])%b[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1920
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
q_list = [0]*Q
for i in range(Q):
    a, b, c, d = map(int, input().split())
    q_list[i] = [a-1, b-1, c, d]

As = combinations_with_replacement(range(1, M+1), N)

ans = 0
for A in As:
    now = 0
    for q in q_list:
        if A[q[1]] - A[q[0]] == q[2]:
            now += q[3]
    ans = max(ans, now)

print(ans)

Measured memory_bytes: 9216
import math
a,b,x = map(int,input().split())
if x == a*a*b:
    print(0)
    exit()
if a*a*b/2 < x:
    x = a*a*b - x
    b = x*2/(a*a)
p = x*2/(a*b)
print(math.degrees(math.atan(b/p)))

Measured memory_bytes: 3060
import sys
N, M = map(int, input().split())
ans = {}
ansstr = []
for _ in range(M):
    S, C = map(int, input().split())
    if S == 1 and C == 0:
        if N!=1:
            print('-1')
            sys.exit()
    elif S > N:
        print('-1')
        sys.exit()
    elif S in ans:
        if ans[S] != C:
            print('-1')
            sys.exit()
    else:
        ans[S] = C
for i in range(1, N+1):
    if i in ans:
        ansstr.append(ans[i])
    else:
        ansstr.append(0)


if ansstr[0]==0 and N==1:
    print(0)
    sys.exit()

if ansstr[0]==0:
    ansstr[0]=1



for i in range(N):
    print(ansstr[i], end="")


Measured memory_bytes: 9152
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();

		int[][] matrix = new int[h][w];
		int[][] dp = new int[h][w];
		int k=0;
		while(k<h) {
			String nextString = sc.next();
			for (int i = 0; i < nextString.length(); i++) {
				if (nextString.charAt(i) == '#') {
					matrix[k][i] = 1;
				} else {
					matrix[k][i] = 0;
				}
			}
			k++;
		}

		dp[0][0] = matrix[0][0];
		for (int i = 1; i < h; i++) {
			if (matrix[i][0] == 1 && matrix[i-1][0]==1) {
				dp[i][0] = dp[i - 1][0];
			} else {
				dp[i][0] = dp[i - 1][0] + matrix[i][0];
			}
		}
		for (int i = 1; i < w; i++) {
			if (matrix[0][i] == 1 && matrix[0][i-1]==1) {
				dp[0][i] = dp[0][i - 1];
			} else {
				dp[0][i] = dp[0][i - 1] + matrix[0][i];
			}
		}
		for (int i = 1; i < h; i++) {
			for (int j = 1; j < w; j++) {
				if (matrix[i][j] == 1 &&  matrix[i][j-1]==1 && matrix[i-1][j]==1) {
					dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]);
				} else if (matrix[i][j] == 1 &&  matrix[i][j-1]==1) {
					dp[i][j] = dp[i][j - 1];
				} else if (matrix[i][j] == 1 && matrix[i-1][j]==1) {
					dp[i][j] = dp[i-1][j];
				} else {
					dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
				}
			}
		}
		System.out.println(dp[h - 1][w - 1]);
	}

}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//:/
#define pb push_back
#define mp make_pair
#define nt _ll128
#define ld long double
long double PI =3.14159265358979323846;
using ll = long long;



const ll modo=998244353;
const ll inf=1e17;
const ll ms=(1e5)+5;

int ar[100][100]={0};


int main()
{
    idfc;
 //   freopen("taku.txt","r",stdin);
    string s,t;
    cin>>s>>t;
    int n=s.length();
    int i,j;

    int a,b;

    for(i=0;i<n;i++)
    {
        a=s[i]-97;
        b=t[i]-97;
        ar[a][b]++;
    }
    int c;
    int fl=0; int gg;
//    for(i=0;i<26;i++)
//    {
//        for(j=0;j<26;j++)cout<<ar[i][j]<<" ";
//        cout<<"\n";
//    }
    for(i=0;i<26;i++)
    {
        c=0;
        for(j=0;j<26;j++)
        {
            if(ar[i][j])c++;
        }
        if(c>1){fl=1;break;}
        if(c==0)continue;
        while(true)
        {
            gg=-1;
            for(j=0;j<26;j++)
            {
                if(ar[i][j])gg=j;
            }
          //  cout<<i<<" "<<gg<<"\n";
            if(gg==i||gg==-1)break;
            a=0; b=0;
            for(j=0;j<26;j++)
            {
                if(ar[gg][j])
                {
                    a++;
                    b=j;
                }
            }

            if(a>1)
            {
                fl=1; break;
            }

            if(a)
            {
               // cout<<i<<" "<<gg<<"\n";
                if(gg==b){fl=1; break;}

               // if(ar[i][gg]>ar[gg][b]){fl=1; break;}
                ar[i][gg]=0;
                ar[gg][gg]=ar[gg][b];
                ar[gg][b]=0;
                ar[i][b]=ar[gg][gg];
            }
            else{
                ar[gg][gg]=ar[i][gg];
                ar[i][gg]=0;
            }
        }
        if(fl)break;
    }
    if(fl)cout<<"No";
    else cout<<"Yes";
    return 0;
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 220
// 44

using namespace std;

const int MAXN = (int) 2e5;

int arr[MAXN + 1];
ll sp[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
        arr[i] -= i;
    }
    sort(arr + 1, arr + n + 1);
    for(i = n; i >= 1; i--) {
        sp[i] = sp[i + 1] + arr[i];
    }
    ll ans = 1e18, sum = 0;
    for(i = 1; i <= n; i++) {
        sum += arr[i];
        ans = min(ans, 1LL * arr[i] * i - sum + sp[i] - 1LL * arr[i] * (n - i + 1));
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep2(i,x,n) for(int i=x;i<n;++i)

int n;
vector<vector<double>> d;

void dfs(int cur, int prev, double tmp_d, vector<bool>& checked, vector<double>& dists)
{
    if(cur == n)
    {
        dists.push_back(tmp_d);
        return;
    }

    rep(i,n)
    {
        if(checked[i]) continue;
        checked[i] = true;
        int prev_ = cur == 0 ? i : prev;
        dfs(cur+1, i, tmp_d+d[prev_][i], checked, dists);
        checked[i] = false;
    }
}

int main()
{    
    
    cin >> n;
    vector<double> x(n);
    vector<double> y(n);
    rep(i,n) cin >> x[i] >> y[i];

    d.resize(n);
    rep(i,n) 
        rep(j,n)
        {
            double dij = sqrt(pow(x[i]-x[j], 2)+pow(y[i]-y[j], 2));
            d[i].push_back(dij);
        }

    vector<double> dists;
    vector<bool> checked(n, false);
    dfs(0, 0, 0, checked, dists);
    double avg = accumulate(dists.begin(),dists.end(),0.0) / dists.size();

    cout << fixed << setprecision(15) << avg << endl;
    return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
#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 each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

bool check(vi a, int n){
  rep(i,n){
    int x = a[i+1];
    rep(j,a[i]){
      if(a[i+j+1] != x) return false;
    }
  }
  return true;
}

int ans = 0;
void rec(int d, int n, vi cur){
  if(d==n){
    rep(i,n) cur.eb(cur.back());
    if(check(cur,n)){
      ans++;
      rep(i,cur.size()) cerr << cur[i] << " ";
      cerr << endl;
    }
    return;
  }

  rep(i,n){
    cur.eb(i+1);
    rec(d+1,n,cur);
    cur.pop_back();
  }
}

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

  vl dp(n+1,0), acc(n+1,0);
  dp[0] = 1; dp[1] = n;
  acc[0] = 1; acc[1] = n+1;
  for(ll i=2;i<=n;i++){
    dp[i] = dp[i-1];
    (dp[i] += (i>=3 ? acc[i-3] : 0)) %= MOD;
    (dp[i] += (n-1)*(n-1) + (n-i+1)) %= MOD;
			     /*
    for(int j=2;j<=n;j++){
      dp[i] += n-1 + (i-1>=j ? dp[i-j-1] : 1);
    }
			     */
    acc[i] = (acc[i-1] + dp[i]) % MOD;
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 15872
#include <stdio.h>

int main(void) {
  int a,b,c,x,count = 0;

  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&c);
  scanf("%d",&x);

  for (int i = 0; i <= a; i++){
    for (int j = 0; j <= b; j++){
      for (int k = 0; k <= c; k++){
        if (i*500 + j*100 + k*50 == x)
          count++;
      }
    }
  }

    printf("%d", count);

  return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**7)

# Override `input` function because `stdin.readline()` is 10x faster than built-in `input()`
input = sys.stdin.readline


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    a, b = read_h()
    if (a + b) % 2 == 0:
        print((a + b) // 2)
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060