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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] x = new long[n];
        long[] copy = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextLong();
            copy[i] = x[i];
        }
        Arrays.sort(copy);
        long midl = copy[n / 2 - 1];
        long midh = copy[n / 2];
        for (int i = 0; i < n; i++) {
            if (x[i] <= midl) {
                System.out.println(midh);
                continue;
            }
            System.out.println(midl);
        }
    }

}


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

int n;

int main()
{
    cin >> n;
    int a = 1;
    for(int i = 0; i < 5; i++){
        a *= 10;
        if(a == n){
            cout << 10 << endl;
            return 0;
        }
    }
    a = 0;
    while(n){
        a += n % 10;
        n /= 10;
    }
    cout << a << endl;


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n,0);
    rep(i,n) cin >> a[i];
    vector<int> b(n+100,0);
    rep(i,min(k,(int)(sqrt(n)+100))){
        rep(j,n){
            b[max(j-a[j],0)] ++;
            if(j + a[j] + 1>= n) continue;
            b[j+a[j]+1] --;
        }
        rep(j,n-1){
            b[j+1] += b[j];
        }
        swap(a,b);
        vector<int> empty(n+100,0);
        swap(b,empty);   
    }
    rep(i,n) cout << a[i] <<" " ;
    cout << endl;
    return 0;
}

Measured memory_bytes: 5824
n,x,y=map(int,input().split())
g=[[]*n for i in range(n)]
for i in range(n-1):
    g[i].append(i+1)
    g[i+1].append(i)
g[x-1].append(y-1)
g[y-1].append(x-1)

from collections import deque
distance=[]

for i in range(n):
    option=deque()
    option.append(i)
    completed=[False]*n
    memo=[0]*n
    while option:
        now=option.popleft()
        completed[now]=True
        for j in g[now]:
            if completed[j]==False and j not in option:
                memo[j]=memo[now]+1
                option.append(j)
    distance.append(memo)

ans=[0]*n
for i in range(n-1):
    for j in range(i+1,n):
        ans[distance[i][j]-1]+=1

for i in range(n-1):
    print(ans[i])
        

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

int arr[26];

int main()
{
	// fast;
	// #ifndef ONLINE_JUDGE
 //        freopen("input.txt", "r", stdin) ;
 //        // freopen("out.txt", "w", stdout);
 //    #endif
    int n,k,x,y;
    
    char s[101];
    scanf("%s",&s);
    int len = strlen(s);
    int i = 0;
    for(i=0;i<len;i++)
    {
    	arr[s[i]-97]++;
    }
    int flag = 1;
    for(i=0;i<25;i++)
    {
    	if (arr[i]%2 == 1)
    	{
    		flag = 0;
    		break;
    	}
    }
    // for(i=0;i<25;i++)
    // {
    // 	printf("%d\n", arr[i]);
    // }
    if (flag == 1)
    {
    	printf("Yes");
    }
    else if (flag == 0)
    {
    	printf("No");
    }
    return 0;
}

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

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  std::string S;
  std::cin >> S;

  if (S.length() == 2) {
    printf("0\n");  /// ???
    return 0;
  }

  for (int i=(S.length()-1)/2; i>=1; --i)
    if (S.substr(0, i) == S.substr(i, i)) {
      printf("%d\n", 2*i);
      return 0;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const int INF=1e9;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  int x,y,z,k;
  std::cin >> x >> y >> z >> k;
  std::vector<ll> A(x),B(y),C(z);
  rep(i,x) std::cin >> A[i];
  rep(i,y) std::cin >> B[i];
  rep(i,z) std::cin >> C[i];
  std::vector<ll> AB;
  rep(i,x){
    rep(j,y){
      AB.pb(A[i]+B[j]);
    }
  }
  sort(all(AB));
  sort(all(C));
  reverse(all(AB));
  reverse(all(C));
  std::vector<ll> ABC;
  for(int i=0; i<min(k,(int)AB.size()); i++){
    rep(j,z){
      ABC.pb(AB[i]+C[j]);
    }
  }
  sort(all(ABC));
  reverse(all(ABC));
  rep(i,k) std::cout << ABC[i] << '\n';

  return 0;
}


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

int main() {
  string S,T;
  cin>>S>>T;
  int ans = 0;
  rep(i,S.size()){
    if(S.at(i)!=T.at(i)){
      ans += 1;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3916
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b);
int main(){
    long long a,b;
    cin>>a>>b;
    long long n=gcd(a,b);
    //cout<<n<<endl;
    vector<int> prime(1000001,0);
    int ans=1;
    for(long long i=2;i*i<=n;i++){
        //cout<<i<<" "<<n<<endl;
        if(n%i==0){
            while(n%i==0){
                n/=i;
            }
            ans++;
        }
    }
    if(n!=1)ans++;
    cout<<ans<<endl;
    return 0;
}

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

Measured memory_bytes: 4096
#include<stdio.h>
int main(void){
	int num,num2,x;
	scanf("%d %d %d",&num,&num2,&x);
	int a[num2];
	for(int i=0;i<num2;i++){
		scanf("%d",&a[i]);
	}
	int cunt1=0,cunt2=0;
	for(int i=0;i<x;i++){
		for(int j=0;j<num2;j++){
			if(i==a[j]){
				cunt1++;
			}
		}
	}
		for(int i=num;i>x;i--){
		for(int j=0;j<num2;j++){
				if(i==a[j]){
				cunt2++;
			}
		}
	}
	if(cunt1>cunt2){
		printf("%d",cunt2);
	}else{
		printf("%d",cunt1);
	}
	return 0;
}

Measured memory_bytes: 128
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

A,B,C = MI()
K = I()

a = 0  # 魔術を行った回数
while B <= A:
    B *= 2
    a += 1
while C <= B:
    C *= 2
    a += 1

print('Yes' if a <= K else 'No')


Measured memory_bytes: 61872
n = gets.to_i
array = []
n.times do |i|
  s, p = gets.split
  p = p.to_i
  array << [i, s, p]
end

array = array.sort_by { |x| x[1] }
array = array.group_by { |x| x[1] }
array.each do |x|
  x = x[1]
  x = x.sort_by { |value|  -1 * value[2] }
  x.each do |z|
    puts z[0] + 1
  end
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//const ll p = 1e9 + 7;
	//const ll p = 998244353;

	string s;
	cin >> s;
	if (s.back() == '3') cout << "bon" << endl;
	else if (s.back() == '0' || s.back() == '1' || s.back() == '6' || s.back() == '8') cout << "pon" << endl;
	else cout << "hon" << endl;
}


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Set         std::set
#define PQueue      std::priority_queue
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define HashMap     std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    template<class A, class B> A power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    template<class A, class B> A power ( A x, B n ) { return power( x, n, 1000000007 ); }
    template<class A> A gcd ( A x, A y ) { return x % y ? gcd( y, x % y ) : y; }
    template<class A, class B> A lcm   ( A x,  B y ) { return ( x / gcd(x, y) * y ); }
    template<class A> inline A abs ( A n ) { return ( n < 0 ) ? -n : n; }
    template<class A, class B> inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B> inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    int a[200200];

    signed call_of_Cthulhu( signed datum ) {

        int n, k;
        read n >> k;
        for ( int i = 0; i < n; i++ ) {
            int q;
            read q;
            a[q]++;
        }

        Vi vi;
        int cnt = 0;
        int ans = 0;
        for ( int i = 1; i < 200200; i++ ) {
            if ( a[i] ) {
                vi.bash(a[i]);
                cnt++;
            }
        }
        bozo_sort(alles(vi));
        for ( int i = 0; i < vi.size() && k < cnt; i++ ) {
            cnt--;
            ans += vi[i];
        }
        echo ans fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); int main_result = Rlyeh::call_of_Cthulhu(114514); return 0;}


Measured memory_bytes: 2292
import numpy as np

n = int(input())
p = list(map(float, input().split()))
index = n//2 + 1

dp = np.zeros((n+1, n+1))
dp[0][0] = (1-p[0])
dp[0][1] = p[0]

for i in range(1, n):
    dp[i] = (1-p[i]) * dp[i-1]
    dp[i][1:] += p[i] * dp[i-1][:-1]

print(sum(dp[n-1][n//2 + 1:]))

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

int c[26];

int main() {
  string w;
  cin >> w;
  REP(i, w.length()) c[w[i] - 'a']++;
  REP(i, 26) {
    if (c[i] % 2 != 0) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define llong long long
#define fr(i,l,r) for(i=(l);i<(r);i++)
#define min(p,q)((p)<(q)?(p):(q))


int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}



int main(void)
{
	//変数の宣言
	int n;
	int h,m,w;
	
	//よく使う変数
	int i,j,k,l;
	int flag=0;
	llong int ans=0;
	int count=0;
	int sum=0;
	long int temp,temp1,temp2;
	int max,min;
	int len;
	//データの読み込み
	
	scanf("%d",&n);
	
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	
	for(h=1;h<=3500;h++){
		for(m=1;m<=3500;m++){
			if(4*h*m-n*m-n*h>0){
				w=(llong)n*h*m/(4*h*m-n*m-n*h);
			}
			
			if(4*h*m*w==n*m*w+n*h*w+n*h*m){
				printf("%d %d %d",h,m,w);
				return 0;
			}
		}
	}
	
//	printf("計算部分終了\n");
	//出力
	
	
//	printf("結果の出力終了\n");
	
	return 0;
	
}



Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(m);
    for(int i=0;i<m;i++){
        cin>>a[i];
    }
    
    int sum=0;
    for(int i=0;i<m;i++){
        sum+=a[i];
    }
    int day=n-sum;
    if(day<0){
        cout<<-1;
    }else{
        cout<<day;
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int L;
    cin >> L;

    vector<tuple<int, int, int>> G;

    int N_node = 1;
    int N_path = 0;
    int ind_node = 1;
    int add_node = 0;
    for(int i = 1; i <= L/2; i = i * 2){
        G.push_back(make_tuple(ind_node, ind_node+1, 0));
        G.push_back(make_tuple(ind_node, ind_node+1, i));
        ind_node++;
        N_node++;
        N_path += 2;
        add_node = i * 2;
    }

    // mask bitが立っていたらpathを追加
    int mask = 0;
    for(int i = N_node-2; i >= 0; i--){
        if(L & (1 << i)){
            G.push_back(make_tuple(i+1, N_node, add_node));
            add_node += (1<<i);
            N_path++;
        }
    }

    cout << N_node << " " << N_path << endl;

    for(int i = 0; i < G.size(); i++){
        cout << get<0>(G[i]) << " " << get<1>(G[i]) << " " << get<2>(G[i]) << endl;
    }


    return 0;
}



Measured memory_bytes: 256
import numpy as np

N, M = map(int, input().split())

A, B = [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A = np.array(A)
cheep_sort = A.argsort()

ans = 0
cnt = 0
for i in cheep_sort:
    if cnt + B[i] > M:
        ans += A[i] * (M - cnt)
        break
    else:
        ans += A[i] * B[i]
        cnt += B[i]

print(ans)


Measured memory_bytes: 20868
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


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


def ZIP(n): return zip(*(MAP() for _ in range(n)))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    n, m = MAP()
    a = LIST()
    print(max(n - sum(a), -1))


if __name__ == '__main__':
    main()


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

int64_t mod = 1000000007;
int64_t large = 9223372036854775807;
double PI = 3.141592653589793;

int main()
{
    int N, max, ans = 1;
    cin >> N;
    vector<int> list(N);
    for (int i = 0; i < N; i++)
        cin >> list[i];
    max = list[0];
    for (int i = 1; i < N; i++)
    {
        if (max <= list[i])
        {
            ans++;
            max = list[i];
        }
    }
    cout << ans;
}

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

set<int> st[26];

int main() {
    int n; string s; cin >> n >> s;
    for (int i = 0; i < n; i++)
        st[s[i] - 'a'].insert(i);
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int op; cin >> op;
        if (op == 1) {
            int j; char c; cin >> j >> c;
            --j;
            st[s[j] - 'a'].erase(j);
            st[c - 'a'].insert(j);
            s[j] = c;
        } else {
            int l, r; cin >> l >> r;
            --l, --r;
            int ans = 0;
            for (int j = 0; j < 26; j++) {
                auto it = st[j].lower_bound(l);
                if (it != st[j].end() and *it <= r)
                    ++ans;
            }
            cout << ans << "\n";
        }
    }
}


Measured memory_bytes: 24196
S = input()
T = input()
ans = len(T)

for i in range(len(S)-len(T)+1):
  s = S[i:i+len(T)]
  tmp = 0
  for j in range(len(T)):
    if s[j] != T[j]:
      tmp += 1
  ans = min(ans, tmp)
  
print(ans)

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
X, Y = MAP()

# ランレングス圧縮
A1, A2 = [], []
cnt = d = 0
for s in S:
    if s == 'T':
        if d == 0:
            A1.append(cnt)
        else:
            A2.append(cnt)
        cnt = 0
        d ^= 1
    else:
        cnt += 1
if d == 0:
    A1.append(cnt)
else:
    A2.append(cnt)
# 最初だけ右固定なので別処理
X -= A1[0]
A1.pop(0)

# 縦横独立に、到達可の場所を確認する
M1 = len(A1)
M2 = len(A2)
dpx = [set() for i in range(M1+1)]
dpy = [set() for i in range(M2+1)]
dpx[0].add(0)
dpy[0].add(0)
for i, a in enumerate(A1):
    for x in dpx[i]:
        dpx[i+1].add(x+a)
        dpx[i+1].add(x-a)
for i, a in enumerate(A2):
    for y in dpy[i]:
        dpy[i+1].add(y+a)
        dpy[i+1].add(y-a)

if X in dpx[M1] and Y in dpy[M2]:
    Yes()
else:
    No()


Measured memory_bytes: 269576
N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))

Measured memory_bytes: 119916
import java.util.*;
import java.io.*;

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

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int tmp = 0;
            for (int j = 0; j < m; j++) {
                tmp += sc.nextInt() * b[j];
            }
            if (tmp + c > 0)
                ans++;
        }
        System.out.println(ans);

    }
}

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

int main() {
  int n;
  cin >> n;
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
      ans += j;
    }
    //ll r = n / i;
    //ans += (r * (r + 1) / 2) * i;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3612
#include <iostream>

using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  int c5 = 0;
  int c7 = 0;

  if (a == 5) c5 ++; else if (a == 7) c7 ++;
  if (b == 5) c5 ++; else if (b == 7) c7 ++;
  if (c == 5) c5 ++; else if (c == 7) c7 ++;

  if (c5 == 2 && c7 == 1) {
    cout << "YES";
  } else {
    cout << "NO";
  }

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
    #define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
    #define pb push_back
    typedef long long int ll;
    using namespace std;
    int main(void){
    	fast;
    	ll n;
    	cin>>n;
    	string ans="";
    	while(n!=0){
    		n--;
    		char c=(char)(n%26+'a');
    		string add(1,c);
    		ans=add+ans;
    		n/=26;
    	}
    	cout<<ans<<endl;
    }

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;
int n, a[100010];
ll calc(ll s) {
  ll sum = 0, res = 0;
  for (int i = 0; i < n; ++i, s *= -1) {
    sum += a[i];
    if (sum * s > 0) continue;
    if (s > 0)
      res += (-sum + s), sum += (-sum + s);
    else
      res += (sum - s), sum += -(sum - s);
  }
  return res;
}
int main() {
  cin >> n;
  rep(i, n) cin >> a[i];
  cout << min(calc(1), calc(-1)) << endl;
  return 0;
}

Measured memory_bytes: 640
import fractions

N, X = map(int, input().split())

x = [X] + list(map(int, input().split()))
x.sort()

dic = []

for i in range(len(x) - 1):
    tmp = x[i + 1] - x[i]
    if tmp not in dic:
        dic.append(tmp)

ans = max(dic)

for i in range(len(dic) - 1):
    ans = min(ans, fractions.gcd(dic[i], dic[i + 1]))

print(ans)

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

const int INF = 1 << 25;
int d[100][100];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, m, s, g1, g2;
	while (cin >> n >> m >> s >> g1 >> g2 , n) {
		s-- , g1-- , g2--;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = (i == j) ? 0 : INF;
			}
		}

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

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}

		int ans = INF;
		for (int i = 0; i < n; i++) {
			ans = min(ans, d[s][i] + d[i][g1] + d[i][g2]);
		}

		cout << ans << endl;
	}
}

Measured memory_bytes: 1232
{-# LANGUAGE BangPatterns #-}

module Main
  ( main
  )
where

import           Control.Applicative
import           Control.Monad
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as MV
import           Control.Monad.ST
import           Data.Ord
import qualified Data.Vector.Unboxed           as UV

parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine
readIntegerList = map parseInteger . BS.words <$> BS.getLine

main = do
  digits <- UV.fromList . map digitToInt <$> getLine
  k      <- readInt
  let d      = UV.length digits
      cumsum = UV.tail
        $ UV.scanl' (\acc val -> if val /= 0 then acc + 1 else acc) 0 digits
      matched = if (UV.length . UV.filter (/= 0) $ digits) == k then 1 else 0
      lowerDigit =
        sum . map (\val -> combi (val - 1) (k - 1) * (9 ^ k)) $ [1 .. (d - 1)]
      topDigit = (UV.head digits - 1) * combi (d - 1) (k - 1) * 9 ^ (k - 1)
      zeroDigit =
        sum
          . map
              (\i ->
                combi (d - i - 1) (k - cumsum UV.! (i - 1))
                  * 9
                  ^ (k - cumsum UV.! (i - 1))
              )
          . filter
              (\i -> (digits UV.! i /= 0) && (k - cumsum UV.! (i - 1) >= 0))
          $ [1 .. (d - 1)]
      equalDigit =
        sum
          . map
              (\i ->
                max (digits UV.! i - 1) 0
                  * combi (d - i - 1) (k - cumsum UV.! i)
                  * 9
                  ^ (k - cumsum UV.! i)
              )
          . filter (\i -> (digits UV.! i /= 0) && (k - cumsum UV.! i >= 0))
          $ [1 .. (d - 1)]
  print $ matched + lowerDigit + topDigit + zeroDigit + equalDigit

combi n k
  | n < 0 || k < 0   = 0
  | n < k            = 0
  | n == 0 || k == 0 = 1
  | otherwise = foldl' (*) 1 [(n - k + 1) .. n] `div` foldl' (*) 1 [1 .. k]


Measured memory_bytes: 508
def d_Candidates_of_No_Shortest_Paths(N, M, E):
    # 初期化
    dist = [[float('inf') for j in range(N)] for i in range(N)]
    for i in range(N):
        dist[i][i] = 0
    # 構築
    for a, b, c in E:
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
    # ワーシャル・フロイド法
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    ans = M  # 最短経路として使われない辺の数
    for a, b, c in E:
        a -= 1
        b -= 1
        for s in range(N):
            if dist[s][a] + c == dist[s][b]:
                # 条件を満たした辺は使われる。1引く
                ans -= 1
                break
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(d_Candidates_of_No_Shortest_Paths(N, M, E))

Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

void printvec(vi& x, int size = 0) {
    if (x.size() == 0) {
        cout << endl;
        return;
    }
    cout << x.front();
    for (int i = 1; i < (size == 0 ? x.size() : size); i++) {
        cout << " " << x[i];
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    vi as(n);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
    }
    vi bs(as), cs(as);

    if (prev_permutation(bs.begin(), bs.end())) {
        printvec(bs);
    }
    printvec(as);
    if (next_permutation(cs.begin(), cs.end())) {
        printvec(cs);
    }
}


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const long long mod = 1000000007LL;

ll a[55];
ll p[55];

ll thick(ll n) {
  if(n==0) return 1LL;
  return 2LL*thick(n-1LL)+3LL;
}

ll pn(ll n) {
  if(n==0) return 1LL;
  return 2LL*pn(n-1LL)+1LL;
}

ll f(ll n, ll x) {
  if(n==0) {
    if(x<=0) return 0LL;
    else return 1LL;
  }
  else if(x==1) return 0LL;
  else if(1<x && x<=1+a[n-1]) return f(n-1,x-1);
  else if(x==2+a[n-1]) return p[n-1]+1;
  else if(2+a[n-1]<x && x<=2+2*a[n-1]) return p[n-1]+1LL+f(n-1,x-2-a[n-1]);
  else if(x==3+2*a[n-1]) return 2*p[n-1]+1LL;
}

int main() {
  ll n, x;
  cin >> n >> x;
  rep(i,55) a[i] = thick(i);
  rep(i,55) p[i] = pn(i);
  cout << f(n,x) << endl;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
said={}
ans="Yes"
s=input()
said[s]=1
pre=s
for _ in range(n-1):
    s=input()
    if s not in said:
        if pre[len(pre)-1] == s[0]:
            said[s]=1
            pre=s
        else:
            ans="No"
            break
    else:
        ans="No"
        break


print(ans)





Measured memory_bytes: 3060
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [H, W] = input[0].map(Number);

  const empty = ".";
  const bomb = "#";

  const field = input.slice(1, -1).map((line) => line[0].split(""));

  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (field[i][j] !== empty) {
        continue;
      }

      let bombs = 0;

      for (let ii = i - 1; ii <= i + 1; ii++) {
        for (let jj = j - 1; jj <= j + 1; jj++) {
          if (ii === i && jj === j) {
            continue;
          }
          if (ii < 0 || ii >= H || jj < 0 || jj >= W) {
            continue;
          }

          if (field[ii][jj] === bomb) {
            bombs += 1;
          }
        }
      }

      field[i][j] = bombs.toString();
    }
  }

  return field.map((row) => row.join("")).join("\n");
};

console.log(main(read()));


Measured memory_bytes: 32544
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 1e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, k, arr[110], dp[maxn][2];
int solve(int sum, int f)
{
    if(dp[sum][f] != -1) return dp[sum][f];
    int res = !f;
    for(int i = 1; i <= n; i++)
    {
        if(sum - arr[i] >= 0 && solve(sum - arr[i], !f) == f)
            res = f;
    }
    return dp[sum][f] = res;
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    memset(dp, -1, sizeof dp);
    cout << (solve(k, 1) == 1 ? "First" : "Second") << "\n";
    return 0;
}


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

int main(){
    double a, b, x;
    double pi = 3.1415926535;
    cin >> a >> b >> x;
    double s;
    if(a*a*b >= 2*x){
        s = a*b*b/(2*x);
    }
    else{
        s = (a*b - x/a)*2/(a*a);
    }
    double theta = atan(s);
    cout << setprecision(10) << theta*180/pi << endl;
}

Measured memory_bytes: 256
n = int(input())
li =[list(map(int, input().split())) for _ in range(n-1)]
for i in range(n):
    t = 0
    for j in range(i,n-1):
        if t <= li[j][1]:
            t =  li[j][1] + li[j][0]
        else:
            k = t  // li[j][2]
            if t % li[j][2] == 0:
                t += li[j][0]
            else:
                t += li[j][0] + (li[j][2] -   t % li[j][2])
    print(t)

Measured memory_bytes: 3316
N=int(input())
A=list(map(int,input().split()))

A.sort(reverse=True)
P=[]
M=[]

for i in A:
    if i<0:
        M.append(i)
    else:
        P.append(i)

ans=[]
if len(M)==0:
    if P[0]==0:
        print(0)
        for i in range(N-1):
            print(0,0)
        exit()
    else:
        x=P.pop()
        y=P.pop(0)
        ans.append([x,y])
        M.append(x-y)
if len(P)==0:
    x=M.pop(0)
    y=M.pop()
    ans.append([x,y])
    P.append(x-y)


for i in range(len(P)-1):
    y=P.pop()
    x=M.pop()
    ans.append([x,y])
    M.append(x-y)

for i in range(len(M)):
    y=M.pop()
    x=P.pop()
    ans.append([x,y])
    P.append(x-y)

print(P[0])

for x,y in ans:
    print(x,y)







Measured memory_bytes: 23948
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;cin>>s;
	int len=s.length();int cnt=0;string be="";
	int id=0;
	do{
		string tmp="";tmp+=s[id];
		while(id<len&&tmp==be)
		{
			id++;
			if(id>=len) break;
			tmp+=s[id];
			//cout<<id<<endl;
		}
		//cout<<id<<" "<<tmp<<endl;
		if(tmp!=be)cnt++;
		be=tmp;id++;
	}while(id<len);
	cout<<cnt<<endl;
}

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

using Pair = std::pair<int, int>;

constexpr int MAX_N = 100000;

int N;
std::vector<Pair> edges[MAX_N];
int distance[MAX_N];

void dfs(int n = 0, int prev = 0);

int main(){

	std::cin >> N;

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

		int u, v, w;

		std::cin >> u >> v >> w;

		--u, --v;

		edges[u].push_back(Pair(v, w));
		edges[v].push_back(Pair(u, w));
	}

	dfs();

	for(int i = 0; i < N; ++i){
		if(distance[i] % 2 == 0){
			std::cout << 1 << std::endl;
		}
		else{
			std::cout << 0 << std::endl;
		}
	}

	return 0;
}

void dfs(int n, int prev){

	for(auto & edge : edges[n]){
		if(edge.first != prev){
			distance[edge.first] = distance[n] + edge.second;
			dfs(edge.first, n);
		}
	}
}


Measured memory_bytes: 8320
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

L.sort(key=lambda x:x[2])

for x in range(101):
    for y in range(101):
        h = L[-1][2] + abs(x-L[-1][0]) + abs(y-L[-1][1])
        for l in L: 
            if l[2] == 0:
                if h - (abs(x-l[0]) + abs(y-l[1])) > 0:
                    flag = 0
                    break
            else:

                if h == l[2] + abs(x-l[0]) + abs(y-l[1]):
                    flag = 1
                
                else:
                    flag = 0
                    break
                
                
        if flag == 1:
            gx = x
            gy = y
            gh = h
            break
                
                    
    if flag == 1:
        break
        
print(gx, gy, gh)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;

int main ()  {
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    bool turn = true;

    while (true) {
        if (turn) {
            c -= b;
            if (c <= 0) return !printf("Yes");
        } else {
            a -= d;
            if (a <= 0) return !printf("No");
        }
        turn ^= 1;
    }
}
/*
    Good Luck
        -Lucina
*/


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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 (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;


template <typename T>
class RMQ {
	T query(int l, int r, int a, int b, int k){
		if( l <= a && b <= r ){
			return seg[k];
		}else if( l < b && a < r ){
			int m = (b+a)/2;
			T vl = query(l,r, a, m, k*2);
			T vr = query(l,r, m, b, k*2+1);
			return min(vl, vr);	// merge
		}
		return INF;	// default value
	}
public:
	vector<T> seg;	// セグメントツリー (親:k/2  子:k*2,k*2+1)
	int N;
	RMQ(int size){
		N = 1;
		while( N < size ) N<<=1;
		seg.assign(N*2, INF);		// default value
	}
	void update(int pos, T v){
		for(int k=N+pos; k>0; k/=2){
			seg[k] = v;
			v = min(seg[k], seg[k^1]);	// merge
		}
	}
	// [l,r)
	T get(int l, int r){
		return query(l, r, 0, N, 1);
	}
	T get(int pos){		// =get(pos, pos+1)
		return seg[N+pos];
	}
	void add(int pos, T val){
		update(pos, get(pos) + val);
	}
	void chmin(int pos, T val){
		if(get(pos) > val) update(pos, val);
	}
};


int cnt[2][500005];
int check[500005];
int main(){
	int N, K;
	string S, T;

	cin >> N >> K;
	cin >> S >> T;

	rrep(i,N) cnt[0][i] = cnt[0][i+1] + (T[i] == 'B' && T[i+1] != 'B');
	rrep(i,N) cnt[1][i] = cnt[1][i+1] + (T[i] == 'W' && T[i+1] != 'W');
	rrep(i,N) check[i] = (T[i] == 'B');

	vector<RMQ<int>> dp(2, N+2);
	rep(k,2) rep(i,N+1) dp[k].update(i, cnt[k][i]);
	rep(i,N){
		int nex = INF;
		if( S[i] == T[i] ) chmin(nex, dp[0].get(i) - cnt[0][i]);
		rep(k,2) chmin(nex, dp[k].get(max(0,i-K+1), i+1) - cnt[k][i] + (check[i]^k) + 1);
		rep(k,2) dp[k].add(i+1, nex);
	}

	int ans = INF;
	rep(k,2) chmin(ans, dp[k].get(N));

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 22180
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
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(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    debug("debug test\n");
    int n,m;
    cin>>n;
    ll now = 0;
    rep(i, n){
        ll ne;cin>>ne;
        if(now+1<=ne){
            now = ne-1;
        }else if(now==ne){
            
        }else{
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
//code by lynmisakura.wish to be accepted!
/****************************/
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<ll, ll> pi;
typedef vector<pair<ll, ll>> vpi;

//const long long INF = 1LL << 55;

#define itn ll
#define endl '\n'
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ss second
#define ff first
#define dup(x,y) ((x) + (y) - 1)/(y)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(ll i = 0;i < n;i++)
#define rep(i,n) for(ll i = 0;i < n;i++)
#define flush fflush(stdout)
#define rrep(i,n) for(ll i = n - 1;i >= 0;i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define ioboost cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, ll mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }

#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

ll n,m;
vector<ll> G[100010];
void input(){
    cin >> n >> m;
    rep(i,m){
        ll s,t;cin >> s >> t;
        s--,t--;
        G[s].pb(t);
    }
}
double run(ll d){
    vector<double> dp(n,(double)LONG_MAX);
    dp[n-1] = (double)0;
    for(ll i = n-2;i >= 0;i--){
        double sum = 0.0000000;
        double maxdp = (double)0;
        ll m = G[i].size();
        for(auto j : G[i]){
            if(maxdp < dp[j])maxdp = dp[j];
            sum += dp[j];
        }
        if(i == d and G[i].size() > 1){
            sum -= maxdp;
            m--;
        }
        dp[i] = (double)1 + sum / (double)m;
    }
    return dp[0];
}
int main(void){
    ioboost;
    input();
    double ans = (double)LONG_MAX;
    for(ll i = 0;i < n-1;i++){
        if(ans > run(i))ans = run(i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4864
#include <stdio.h>

int S[100000],x;
int bi(int );

int main(){
    int i,a,b,sum;
    
    scanf("%d",&x);
    for(i=0;i<x;i++){
        scanf("%d",&S[i]);
    }
    scanf("%d",&a);
    sum = 0;
    for(i=0;i<a;i++){
        scanf("%d",&b);
        if(bi(b)) sum++;
    }
    printf("%d\n",sum);
    
    return 0;
    
}

int  bi(int f){
    int l = 0;
    int r = x;
    int cen;
    while(l<r){
        cen = (l + r) / 2;
        if(f == S[cen]) return 1;
        if(f > S[cen]) l = cen+1;
        else if(f < S[cen]) r = cen;
    }
    return 0;
}



Measured memory_bytes: 2132
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    int n, X, Y;
    cin >> n >> X >> Y;
    vector<int> a(n);
    forn(i,0, n) cin >> a[i];
    forn(i, 0, n - 1) a[i] = abs(a[i] - a.back());
    vector<int> x(n - 1), y(n - 1);
    ford(i, 0, n - 1) {
        x[i] = a[i];
        forn(j, i + 1, n - 1) setmax(x[i], y[j]);
        y[i] = a[i];
        forn(j, i + 1, n - 1) setmin(y[i], x[j]);
    }
    int ans = abs(Y - a.back());
    forn(i, 0, n - 1) setmax(ans, y[i]);
    cout << ans << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define int long long
#define INF 1000000000000000
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);

#define MAX_V 300
int V;
struct edge{int to, cost;};
vector<edge> G[MAX_V];

void add_edge(int from, int to, int cost){
    G[from].push_back(edge({to, cost}));
}

void add_edge2(int v1, int v2, int cost){
    G[v1].push_back(edge({v2, cost}));
    G[v2].push_back(edge({v1, cost}));
}

int d[MAX_V];
void dijkstra(int s, int t){
    priority_queue<Pii, vector<Pii>, greater<Pii>> que;
    fill(d, d + V, INF);
    d[s] = 0;
    que.push(Pii(0, s));

    while(!que.empty()){
        Pii p = que.top(); que.pop();
        int v = p.second;
        if(v == t) return;
        if(d[v] < p.first) continue;
        REP(i, G[v].size()){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(Pii(d[e.to], e.to));
            }
        }
    }
}

signed main(){

    int N;
    cin >> N;
    V = N;
    vector< vector<int> > A(N, vector<int>(N));
    REP(i, N) readvec(A[i]);

    typedef pair<int, Pii> PiP;
    vector<PiP> dist(0);

    REP(i, N){
        FOR(j, i + 1, N){
            dist.push_back(PiP(A[i][j], Pii(i, j)));
        }
    }

    SORT(dist);

    int ans = 0;
    REP(i, dist.size()){
        int c = dist[i].first;
        int s = dist[i].second.first;
        int t = dist[i].second.second;
        dijkstra(s, t);
        if(d[t] < c){
            cout << -1;
            return 0;
        }
        if(d[t] > c){
            add_edge2(s, t, c);
            ans += c;
        }
    }

    cout << ans;
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 2684
#include<cstdio>
#include<cstring>
const int N=5e5+5;
int n,i,a[N],l,r,m,f[N];
char s[N];
bool chk(int k){
	for (f[n+1]=0,i=1;i<=n;i++) f[i]=a[i]*9;
	int sum=0;
	for (f[1]+=9*k,i=1;i<=n;i++)
		f[i+1]+=f[i]/10,f[i]%=10,sum+=f[i];
	return sum+f[n+1]<=9*k;
}
int main(){
	scanf("%s",s);n=strlen(s);
	for (i=0;i<n;i++) a[n-i]=s[i]-48;
	for (l=1,r=9*n;l<r;){m=l+r>>1;
		if (chk(m)) r=m; else l=m+1;
	}
	printf("%d",l);
}

Measured memory_bytes: 4608
#include <iostream>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
constexpr int64_t MOD = 1e9 + 7;

int main(){
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int32_t N, M;
  cin >> N >> M;
  int32_t res = N;
  for (int i = 0; i < M; i++) {
    int32_t A;
    cin >> A;
    res -= A;
    if (res < 0) {
      res = -1;
      break;
    }
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3664
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
//typedef __int64 LL;
typedef pair<int,int> P;
const int INF=100000000;
const int MOD_2=998244353;


int main()
{
	int h,a;
	cin>>h>>a;
	if(h%a==0)cout<<h/a<<"\n";
	else cout<<h/a+1<<"\n";	
	return 0;
}
	

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef unsigned long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)

class Solve
{
	public:

		int a, b, c;
		int ans;

		void input()
		{
			cin >> a >> b >> c;
		}

		void solve()
		{
			ans = c - (a - b);
          	if(ans < 0)
            {
              ans = 0;
            }
		}

		void output()
		{
			cout << ans << endl;
        }
};

Solve s;
int main()
{
    s.input();
	s.solve();
	s.output();
	return 0;
}


Measured memory_bytes: 256
n = int(input())
cs = input()
l = len(cs)

ans = 0

i = 0
j = 1
while i < l:
  if cs[i] == "W":
    while j <= l - i:
      if cs[-j] == "R":
        ans += 1
        j += 1
        break
      j += 1

  i += 1

print(ans)

Measured memory_bytes: 67944
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;cin>>n>>m;
  int a;
  int ans=0;
  for(int i=0;i<m;i++){cin>>a;ans+=a;}
  ans=n-ans;
  if(ans>=0){
    cout<<ans<<endl;
  }else{
    cout<<"-1"<<endl;
  }
  return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional> // std::function<void(int)>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int Dy[8] = {-1,-1,0,1,1,1,0,-1};
int Dx[8] = {0,1,1,1,0,-1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(All(b));
    unordered_map<int,int> d;
    for(int i=0;i<n;i++){
        d[b[i]]=i;
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        int di=abs(d[a[i]]-i);
        if(di%2==1)cnt++;
    }
    cout<<cnt/2<<endl;
}

Measured memory_bytes: 5924
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for(ll i = l; i < (ll)(r); i++)
#define rep(i, N) FOR(i, 0, N)
#define ALL(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
const ll MOD = 1000000007LL;

int main() {
    string S; cin >> S;
    int ans = 0,tmp = 0;
    rep(i,(ll)S.size()){
        if(S[i] == 'A'||S[i] == 'C'
        || S[i] == 'G'||S[i] == 'T'){
            tmp++;
        }else{
            tmp = 0;
        }
        ans = max(ans,tmp);
    }

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


Measured memory_bytes: 3620
import java.util.*;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[]d = new int[N];
    ArrayList<Integer>dan = new ArrayList<>();
    
    for(int i=0; i<N; i++){
       d[i] = sc.nextInt();
    if(!dan.contains(d[i])){
        dan.add(d[i]);
   } 
}
        System.out.println(dan.size());
    }
}


Measured memory_bytes: 35924