akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, initial=1)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

a, b, c, K = MAP()

# for i in range(K):
#     a, b, c = b+c, a+c, a+b
#     print(a, b, c)

if K % 2 == 0:
    print(a-b)
else:
    print(b-a)


Measured memory_bytes: 5276
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
    int h, w;
    cin >> h >> w;

    string a[h];

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

	bool check;

	for(int i=0;i<h;i++) {
		check = true;
		for(int j=0;j<w;j++) {
			if(a[i].at(j) == '#') check = false;
		}
		if(check == true) {
			for(int k=i;k<h-1;k++) {
				a[k] = a[k+1];
			}
			i--;
			h--;
		}
	}

	for(int i=0;i<w;i++) {
		check = true;
		for(int j=0;j<h;j++) {
			if(a[j].at(i) == '#') check = false;
		}
		if(check == true) {
			for(int k=0;k<h;k++) {
				a[k].erase(a[k].begin() + i);
			}
			i--;
			w--;
		}
	}

	for(int i=0;i<h;i++) {
		cout << a[i] << endl;
	}
}


Measured memory_bytes: 256
import bisect
import numpy as np
import math
import itertools
def main():
    S, T = input().split()
    A, B = map(int, input().split())
    U = input()

    if S == U:
        A -= 1
    elif T == U:
        B -= 1
    print(A, B)
    return 0


    return 0
if __name__ == '__main__':
    main()

Measured memory_bytes: 21556
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int solve(string s) {
  int size = s.size();
  REP(i,size) {
    if (s[i] != s[size-1-i]) return 0;
  }
  return 1;
}

int main() {
  string s; cin >> s;
  int size = s.size();
  if (!solve(s)) { COUT("No"); return 0; }
  string s2 = s.substr(0,size/2);
  if (!solve(s2)) { COUT("No"); return 0; }
  string s3 = s.substr((size+1)/2);
  if (!solve(s3)) { COUT("No"); return 0; }
  COUT ("Yes");
  return 0;
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n;cin >> n;
    string s;cin >> s;
    int cnt[2][26];
    mset(cnt, 0);
    inc(i, 0, n) cnt[1][s[i]-'a']++;
    int ans = 0;
    inc(i, 0, n-1){
        cnt[0][s[i]-'a']++;
        cnt[1][s[i]-'a']--;
        int ans2 = 0;
        inc(j, 0, 26){
            if(cnt[0][j] > 0 && cnt[1][j] > 0){
                ans2++;
            }
        }
        ans = max(ans, ans2);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
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();
        int r = sc.nextInt();
        if(n < -r)System.out.println(-1);
        else if(n > -r)System.out.println(1);
        else System.out.println(0);
    }



}


Measured memory_bytes: 26228
#include<bits/stdc++.h>
using namespace std;
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
//order_of_key(k)= # of items strictly smaller than 'k'  //find_by_order(x)= iterator to x'th largest element (counting from ZERO) //erase("iterator") [log(n)] //end(<name>)
//os.find_by_order(os.order_of_key(x)=iterator to 'x' in the rb tree
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef priority_queue<ll> pq;                                        //min-heap-> multiply the values by '-1'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define forr(i,a,b) for (ll i = a; i < b; i++)
#define test ll t;cin>>t;while(t--)
#define summ(a,n) accumulate(a,a+n,0)
#define bsrch(v,n) lower_bound(v.begin(), v.end(), n)
#define minindex(v) distance(v.begin(),min_element(v.begin(),v.end()))         //returns index of minimum(/max) element in the vector
#define bp(x) _builtin_popcount(x)
#define inf 1000000000000
#define PI = 3.1415926535897932384626
#define mod 1000000007

vector<vi> adj;
ll dp[100001];
bool vis[100001];

void dfs(ll u)
{
    vis[u]=1;
    if(adj[u].size()==0) dp[u]=0;
    for(auto v:adj[u])
    {
        if(!vis[v]) dfs(v);
        dp[u]=max(dp[u],1+dp[v]);
    }
}

int main()
{
    ll n,m; cin>>n>>m;
    adj=vector<vi> (n+1);
    forr(i,0,m)
    {
        ll a,b; cin>>a>>b;
        adj[a].pb(b);
    }
    forr(i,1,n+1)
    {
        if(!vis[i]) dfs(i);
    }
    cout<<*max_element(dp+1,dp+n+1);
}

Measured memory_bytes: 12228
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 1<<20, mod = 998244353;
template<typename T>
inline void read(T &x){
    int ch = getchar(); x = 0; bool f = false;
    for(;ch < '0' || ch > '9';ch = getchar()) f |= ch == '-';
    for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
    if(f) x = -x;
}
void qmo(int &x){x += x >> 31 & mod;}
int ksm(int a, int b){
    int res = 1;
    for(;b;b >>= 1, a = (LL) a * a % mod) if(b & 1) res = (LL) res * a % mod;
    return res;
}
int n, m, lim, rev[N], w[2][N], a[N], b[N];
void calrev(int len){
    int L = -1; lim = 1;
    while(lim <= len){lim <<= 1; ++ L;}
    for(Rint i = 0;i < lim;++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L);
    for(Rint mid = 1;mid < lim;mid <<= 1){
        w[0][mid] = w[1][mid] = 1; int Wn = ksm(3, (mod - 1) / (mid << 1));
        for(Rint i = 1;i < mid;++ i) w[0][mid+i] = (LL) w[0][mid+i-1] * Wn % mod;
        for(Rint i = 1;i < mid;++ i) w[1][mid+i] = mod - w[0][(mid<<1)-i];
    }
}
void NTT(int *A, int op){
    for(Rint i = 0;i < lim;++ i) if(i < rev[i]) swap(A[i], A[rev[i]]);
    for(Rint mid = 1;mid < lim;mid <<= 1)
        for(Rint i = 0;i < lim;i += mid<<1)
            for(Rint j = 0;j < mid;++ j){
                int tmp = (LL) A[mid + i + j] * w[op][mid + j] % mod;
                qmo(A[i + j + mid] = A[i + j] - tmp); qmo(A[i + j] += tmp - mod);
            }
    if(op){
        int inv = ksm(lim, mod - 2);
        for(Rint i = 0;i < lim;++ i) A[i] = (LL) A[i] * inv % mod;
    }
}
int main(){
    read(n); read(m); calrev(n+m-2);
    for(Rint i = 0;i < n;++ i) read(a[i]);
    for(Rint i = 0;i < m;++ i) read(b[i]);
    NTT(a, 0); NTT(b, 0);
    for(Rint i = 0;i < lim;++ i) a[i] = (LL) a[i] * b[i] % mod;
    NTT(a, 1);
    for(Rint i = 0;i < n+m-1;++ i) printf("%d ", a[i]);
}

Measured memory_bytes: 31344
/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

// const ll MAX_N = 1e5;
// ll N;
// ll h[MAX_N];
// ll dp[MAX_N+1]; // メモ化テーブル
 
// // i番目以降の品物から重さの総和がj以下になるように選ぶ
// void rec(ll i){
// 	if (i==0) dp[i] = 0;
// 	else if (i==1) dp[i] = abs(h[1]-h[0]);
// 	else dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
// 	return;
// }
 
 
int main() {
	// 入力
	ll N;
	cin >> N;
	ll A[N];
	for (ll i = 0; i < N; ++i) cin >> A[i];
 
	// 解法
	bool ans = false;
	REP(i,N){
		REP(j,N){
			// if (i==j) continue;
			vector<ll> B;
			REP(k,N){
				if (k==i) B.pb(A[j]);
				else if (k==j) B.pb(A[i]);
				else B.pb(A[k]);
			}
			bool tmp = true;
			REP(k,N-1){
				if (B[k]>B[k+1]){
					// printf("%lld > %lld\n", B[k], B[k+1]);
					tmp = false;
					break;
				}
			}
			// REP(k,N)printf("%lld ", B[k]);
			// printf("tmp %d, ans %d\n", tmp, ans);
			if (tmp==true){
				ans = true;
				break;
			}
		}
		if (ans) break;
	}
	
	if (ans) printf("YES\n");
	else printf("NO\n");
}


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

using namespace std;

int main()
{
	int n;
	char s[100000];
	
	cin >> n;
	cin >> s;
	
	char t;
	char result[100000];
	int resultCount = 0;
	t = s[0];
	result[resultCount++] = s[0];
	for (int i = 1; i < n; i++)
	{
		if (t == s[i])
		{
			continue;
		}
		else
		{
			result[resultCount++] = s[i];
			t = s[i];
		}
	}
	result[resultCount] = 0;

	cout << resultCount;


	//system("pause");
	return 0;
}

Measured memory_bytes: 384
N = int(input())

A = list(map(int,input().split()))

B = list(map(int,input().split()))

total = 0

for i in range(N):
    if A[i] + A[i+1] <= B[i]:
        total += A[i] + A[i+1]
        A[i+1] =0
    else:
        if A[i] < B[i]:
            total += B[i]
            A[i+1] -= B[i] - A[i]
        else:
            total += B[i]
print(total)



Measured memory_bytes: 18624
import sys
read = sys.stdin.read
from math import gcd
from math import floor
def main():
    n, m, *a = map(int, read().split())
    if n == 1:
        r = m >= a[0]//2
        r += floor((m - a[0]//2) / a[0])
        print(int(r))
        sys.exit()
    d = [0] * n
    for i, ae in enumerate(a):
        t1 = 0
        while ae > 1:
            if ae % 2 == 0:
                t1 += 1
                ae /= 2
            else:
                break
        d[i] = t1
    d_c = [de == d[0] for de in d]
    if not all(d_c):
        print(0)
        sys.exit()
    
    div = 2
    a2 = [ae // div for ae in a]
    g = (a2[0] * a2[1]) // gcd(a2[0], a2[1])
    for i1 in range(1, n):
        g = (g * a2[i1]) // gcd(g, a2[i1])
        if g > m:
            print(0)
            sys.exit()
    r = m >= g
    r += floor((m - g) / (g * 2))
    print(int(r))

if __name__ == '__main__':
    main()

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

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main() {
    long long N;
    scanf("%lld", &N);
    long long M;
    scanf("%lld", &M);

    vpll a(N);
    rep(i, N) { cin >> a[i].first >> a[i].second; }

    sort(all(a));

    ll ans = 0;
    for (int i = 0; i < N && M > 0; i++) {
        ans += a[i].first * min(M, a[i].second);
        M -= min(M, a[i].second);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
inpt = input()
 
inpt = inpt.split(" ")
inpt = [int(i) for i in inpt]
 
A = inpt[0]
B = inpt[1]
K = inpt[2]
 
if A >= K:
  A = A - K
else:
  K = K - A
  A = 0
  B = max(0,B - K)

print(A,B)


Measured memory_bytes: 3060
Ss = readlines.drop(1).map{|l| l.chomp.split(//)}

ss = Ss.map{|s| s.sort.group_by(&:itself).map{|n, a| [n, a.size]}}
ks = ss.map{|s| s.map(&:first)}.inject(('a' .. 'z').to_a){|r, a| r & a}
h = ss.flatten(1).group_by(&:first).map{|k, a| [k, a.map(&:last).min]}.to_h
puts ks.inject(""){|r, k| r + k * h[k]} || ""

Measured memory_bytes: 2172
#include <iostream>
using namespace std;
int main() {
    int n, t, a, h, ans=-1, dif=1000000;
    cin >> n >> t >> a;
    for(int i=0; i<n; i++) {
        cin >> h;
        if(dif>abs(a*1000-(t*1000-h*6))) {
            ans = i+1;
            dif = abs(a*1000-(t*1000-h*6));
        }
    }
    cout << ans << endl;    
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
# https://atcoder.jp/contests/arc098/tasks/arc098_a

# i番目の人をリーダーにしたときに何人向く方向を変えるかを高速に取得できれば良い
# [0,i)のWの人数+[i+1,)のEの人数がi番目の人をリーダーにしたときに変える個数
# 上記の一行目と二項目はi→i+1のときに逐次計算できる
N = read_a_int()
S = read()[:-1]
n_W = 0
n_E = S.count('E')
ans = 10**6
for s in S:
    if s == 'E':
        n_E -= 1
    ans = min(ans, n_E + n_W)
    if s == 'W':
        n_W += 1
print(ans)


Measured memory_bytes: 42144
l=["A", "C", "G", "T"]

s=input()
ans=0
a=[]
for i in range(len(s)):
    if s[i] in l:
        ans+=1
        if i==len(s)-1:
            a.append(ans)
    elif s[i] not in l and i==len(s)-1:
        a.append(ans)
        ans=0
    else:
        a.append(ans)
        ans=0
print(max(a))    


Measured memory_bytes: 3060
from collections import deque
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '#':
            S[i][j] = WALL
        else:
            S[i][j] = INI

directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]

d = deque()
d.appendleft((Ch, Cw, 0))

while len(d):
    y, x, c = d.popleft()
    #print("y = ", y, "x = ", x, "c = ", c)
    if S[y][x] != INI:
        continue
    S[y][x] = c
    if y == Dh and x == Dw:
        break
    for dy, dx in directions:
        ny = y + dy
        nx = x + dx
        if ny >= 0 and ny < h and nx >= 0 and nx < w:
            if S[ny][nx] == INI:
                d.appendleft((ny, nx, S[y][x]))
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny = y + dy
            nx = x + dx
            if ny >= 0 and ny < h and nx >= 0 and nx < w:
                if S[ny][nx] == INI:
                    d.append((ny, nx, S[y][x] + 1))

print(S[Dh][Dw])

Measured memory_bytes: 242416
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
using ll = long long;
signed main() {
	int n;
	while (cin >> n, n) {
		vector<int>v(n + 1, 0); rep(i, 1, n + 1)cin >> v[i];
		sort(all(v));
		dumpc(v);
		rep(i, 1, n + 1)v[i] += v[i - 1];
		int sum(0);
		rep(i, 1, n) {
			sum += v[i];
		}
		cout << sum << endl;
		dumpc(v);
	}
	return 0;
}

Measured memory_bytes: 3216
n = int(input())
p = list(map(int, input().split()))
num = 0
for i in range(1, n - 1):
    if p[i] > p[i - 1] and p[i] < p[i + 1]:
        num += 1
    elif p[i] < p[i - 1] and p[i] > p[i + 1]:
        num += 1
    else:
        continue
print(num)

Measured memory_bytes: 9168
#include<stdio.h>
#include<stdlib.h>

int main(){
	int n;
	scanf("%d",&n);
	int weight[n];
	for(int i=0; i<n; i++){
		scanf("%d",&weight[i]);
	}
	int sig1=weight[0],sig2=0;
	for(int i=1; i<n; i++){
		sig2 = sig2+weight[i];
	}
	int min = abs(sig1-sig2);
	for(int i=1; i<n; i++){
		sig1 += weight[i];
		sig2 -= weight[i];
		if(abs(sig1-sig2) < min){
			min = abs(sig1-sig2);
		}
	}
	printf("%d",min);	
	
	return 0;
}

Measured memory_bytes: 128
while 1:
    n, m, a = map(int, raw_input().split())
    if not n: break
    V = [map(int, raw_input().split()) for i in xrange(m)]
    V.sort()
    r = range(n+1)
    for h, p, q in V:
        r[p], r[q] = r[q], r[p]
    print r[a]

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

#define ll long long
#define mx  100005
#define mod 1000000009
#define lim 10000000

using namespace std;

struct hA{
     int l,r;
     bool operator<(hA p)
     {
     	if(r<p.r)return true;
		return false;
     }
}seg[mx];

int main(){
	ios_base::sync_with_stdio(false);
     int n,m;cin>>n>>m;

     for(int i=0;i<m;i++)
     	cin>>seg[i].l>>seg[i].r;
	sort(seg,seg+m);

	int ans=1,pr=0;
	for(int i=1;i<m;i++)
	{
		if(seg[i].l>=seg[pr].r)
			ans++,pr=i;
	}

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


Measured memory_bytes: 1024
h,w,d=map(int,input().split())
a=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
a1=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
for i in range(h):
  i+=1
  tmp=list(map(int,input().split()))
  for j in range(w):
    num=tmp[j]
    j+=1
    a[num%d][int( (num-1)/d)]=[i,j]
for i in range(len(a)):
  a1[i][0]=0
  for j in range(len(a[i])-1):
    j=j+1
    if a[i][j]!=[]:
      a1[i][j]=a1[i][j-1]+abs(a[i][j][0]-a[i][j-1][0])+abs(a[i][j][1]-a[i][j-1][1])

q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(a1[l%d][int((r-1)/d)]-a1[l%d][int((l-1)/d)])

Measured memory_bytes: 50676
import java.util.*
import kotlin.math.acos
import kotlin.math.cos
import kotlin.math.round
import kotlin.math.sin

fun main(args: Array<String>) {
    val n = readInt()
    val a = readIntList()
    val cnt = mutableMapOf<Int, Int>()

    a.forEach {
        if (cnt.containsKey(it)) cnt[it] = cnt[it]!! + 1
        else cnt[it] = 1
    }
    var ans = 0L
    cnt.forEach { (k, v) ->
        if (k < v) ans += v - k
        if (k > v) ans += v
    }
    println(ans)
}

// read
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

const long long MAX = 510000;  // 最大を決めておく
// fac…階乗、inv…逆数、finv…逆数の累積積
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理、先にやっておく
void nCr_init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// nCrを計算する (前処理は忘れないように)
long long nCr(int n, int r) {
  if (n < r) return 0;
  if (n < 0 || r < 0) return 0;
  return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

// nHrを計算する (nCrとセットです)
// n個の区別する箱にr個の区別しない玉を入れる組み合わせ
long long nHr(int n, int r) {
  return nCr(n + r - 1, r);
}

// ====================================================================

int main() {
  nCr_init();
  ll n, k;
  cin >> n >> k;
  ll ans = 0;
  for (int x = 0; x <= min(n - 1, k); x++) {  // 人数0の部屋の数がxのとき
    ans = (ans + nCr(n, x) * nHr(n - x, x) % MOD) % MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 12288
#include <iostream>

using namespace std;

int main() {
  int N;
  int d, d_min;
  char S[101];

  cin >> N;
  cin >> S;

  d = 0;
  d_min = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == '(') d++;
    else d--;
    if (d_min > d) d_min = d;
  }

  for (int i = 0; i < -d_min; i++) {
    putchar('(');
  }
  cout << S;
  for (int i = 0; i < d - d_min; i++) {
    putchar(')');
  }
  putchar('\n');

  return 0;
}


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

before_H = H[0]
ans = 0
tmp = 0

for i in range(1, N):
    if before_H >= H[i]:
        tmp += 1
        before_H = H[i]
    else:
        ans = max(ans, tmp)
        tmp = 0
        before_H = H[i]

if tmp > 0:
    ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 14252
s = gets.rstrip
a = "10" * ((s.size/2).to_i + 1)
b = "01" * ((s.size/2).to_i + 1)
if s.size%2 == 1
  a.chop!
  b.chop!
end

a_count, b_count = 0, 0
0.upto(s.size-1) do | i |
  a_count += 1 if s[i] != a[i]
  b_count += 1 if s[i] != b[i]
end


puts a_count <= b_count ? a_count : b_count

Measured memory_bytes: 4220
n=int(input())
s=[input() for i in range(n)]
d=[]
x=0
count=1
s.sort()
for i in range(n-1):
  if s[i]==s[i+1]:
    count+=1
  else:
    d.append([count,s[i]])
    count=1
d.append([count,s[-1]])
d.sort()
x=d[-1][0]
for i in range(len(d)):
  if x==d[i][0]:
    print(d[i][1])

Measured memory_bytes: 39112
#include<iostream>
#include<bitset>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	int n,cnt,alt;
	while(cin>>n,n){
		long long number[n];
		bool d[n][30];
		rep(i,n){
			number[i]=(1LL<<i);
			rep(j,30)d[i][j]=0;
			cin>>cnt;
			rep(j,cnt){
				cin>>alt;
				if(alt>0)d[i][alt-1]=1;
			}
		}
		bool check=true;
		rep(j,30){
			long long temp=0;
			rep(i,n)if(d[i][j])temp|=number[i];
			rep(i,n)if(d[i][j])number[i]|=temp;
			rep(i,n){
				if(number[i]==(1LL<<n)-1){
					check=false;
					cout<<j+1<<endl;
					break;
				}
			}
			if(!check)break;
		}
		if(check)cout<<-1<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<stdio.h>
#include<math.h>

void solve(double p[],double *x,double *y){
  double a,b,c,d,s,t;
  a=p[0]-p[4];
  b=p[1]-p[5];
  c=p[2]-p[4];
  d=p[3]-p[5];
  s=-(p[0]*p[0]+p[1]*p[1])+(p[4]*p[4]+p[5]*p[5]);
  t=-(p[2]*p[2]+p[3]*p[3])+(p[4]*p[4]+p[5]*p[5]);
  double det=a*d-b*c;
  *x=1/det*(d*s-b*t);
  *y=1/det*(-c*s+a*t);
}

void run(void){
  int n;
  scanf("%d",&n);
  while(n--){
    double p[6];
    int i;
    for(i=0;i<6;i++) scanf("%lf",p+i);
    double x,y;
    solve(p,&x,&y);
    x/=-2;
    y/=-2;
    printf("%.3lf %.3lf %.3lf\n",x,y,sqrt((x-p[0])*(x-p[0])+(y-p[1])*(y-p[1])));
  }
}

int main(void){
  run();
  return 0;
}



Measured memory_bytes: 2028
#include<bits/stdc++.h>
#define ll  long long
#define pp pair<int,int>
#define ppn pair<pp,int>
#define F first
#define S second
#define N 200005
#define mod 1000000007
#define pi 3.14159265358979323846

using namespace std;


int main()
{


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

    int n;
    ll x=1000;
    cin>>n;
    ll a[n];
    for(int i=0; i<n; i++){
            cin>>a[i];
           // if(i<k)x*=a[i];

    }

    for(int i=0; i<n; i++){
           // cout<<i<<endl;
        int j=i+1;
        if(a[j]>a[i]){
          while(j<n && a[j]>=a[j-1])j++;
    //cout<<j<<"J"<<endl;
         if(j!=i+1){
            ll u = x/a[i];
            x%=a[i];
            x+=a[j-1]*u;

            i=j-1;

        }
        }
    }
     cout<<x<<endl;



}


Measured memory_bytes: 3652
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
int main(void)
{
	int i,n,s[1000],sum;
	double m,a2,a1,s2;
	while(1)	{
		scanf("%d",&n);
		if(n==0)	break;
		for(i=0;i<n;i++)	scanf("%d",&s[i]);
		sum=0;
		for(i=0;i<n;i++)	sum+=s[i];
		m=(double)sum/n;
		s2=0.0;
		for(i=0;i<n;i++)	s2+=((double)s[i]-m)*((double)s[i]-m);
		a2=s2/n;
		a1=sqrt(a2);
		printf("%.8lf\n",a1);
	}
	return 0;
}


Measured memory_bytes: 2724
#include <bits/stdc++.h>
#define INT(name) int name; scanf("%d",&name);
#define VINT(name,n) vector<int> name(n); for(int i = 0;i < n;i++) scanf("%d",&name[i]);

using namespace std;

int main(int argc, char const *argv[]){
	vector<unsigned long long> data(4000);
	vector<int> f(4000);
	int i;
	long long a,b,c;
	bool check;

	cin >> i;
	while(i){

		for(int j = 0;j < 4000;j++){
			data[j] = 0;
		}


		for(int j = 0;j < i;j++){
			cin >> a >> b >> c;
			data[a - 1] += (long long)b * c;
			f[j] = a - 1;
		}


		check = false;

		for(int j = 0;j < i;j++){
			if(data[f[j]] >= 1000000){
				printf("%d\n",f[j] + 1);
				data[f[j]] = 0;
				check = true;
			}
		}

		if(!check) printf("NA\n");

		cin >> i;
	}

	return 0;
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void readin(T &x) {
	x = 0;
	T fh = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	x *= fh;
}
inline void d_read(double &x) {
	x = 0.0;
	int fh = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
	if (ch == '.') {
		double num = 1.0;
		ch = getchar();
		for (; isdigit(ch); ch = getchar()) x = x + (num /= 10) * (ch ^ 48);
	}
	x *= fh;
}

template <typename T>
inline void wt(T x) {
	if (x > 9) wt(x / 10);
	putchar(x % 10 + 48);
}
template <typename T>
inline void writeln(T x, char c) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	wt(x);
	putchar(c);
}
struct info{
	int l, r, id;
}a[500005];
int b[500005], c[500005], t[500005], bel[500005];
inline bool comp(info x, info y) {
	if (bel[x.l] ^ bel[y.l]) return bel[x.l] < bel[y.l];
	if (bel[x.l] & 1) return x.r < y.r;
	return x.r > y.r;
}
int main() {
	int n, q;
	readin(n); readin(q);
	for (int i = 1; i <= n; i ++) {
		readin(c[i]);
	}
	for (int i = 1; i <= q; i ++) {
		readin(a[i].l);
		readin(a[i].r);
		a[i].id = i;
	}
	int siz = sqrt(n);
	for (int i = 1; i <= n; i ++) {
		bel[i] = (i - 1) / siz + 1;
	}
	sort(a + 1, a + q + 1, comp);
	int li = 1, ri = 0, ans = 0;
	for (int i = 1; i <= q; i ++) {
		while(ri < a[i].r) {
			ri ++;
			if (!b[c[ri]]) ans ++;
			b[c[ri]] ++;
		}
		while(ri > a[i].r) {
			b[c[ri]] --;
			if (!b[c[ri]]) ans --;
			ri --;
		}
		while(li > a[i].l) {
			li --;
			if (!b[c[li]]) ans ++;
			b[c[li]] ++;
		}
		while(li < a[i].l) {
			b[c[li]] --;
			if (!b[c[li]]) ans --;
			li ++;
		}
		t[a[i].id] = ans;
	}
	for (int i = 1; i <= q; i ++) {
		writeln(t[i], '\n');
	}
	return 0;
}




Measured memory_bytes: 17352
#include <iostream>

using namespace std;

int main(){
    int K, S;
    cin >> K >> S;
    int count = 0;

    for(int i=0; i <= K; i++){
        for(int j=0; j <= K; j++){
            if((S-i-j)>=0 && (S-i-j) <= K){
                count++;
                //cout << i << j << endl;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX/2
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;
struct edge { ll from; ll to; ll cost; };



int main(){
	int H, W, h, w;
	cin >> H >> W >> h >> w;

	cout << (H-h)*(W-w) << endl;

	return 0;
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    x=parseInt(readline())
    for a in 0:1000
        for b in -1000:1000
            if a^5-b^5==x
                println("$a $b")
                return
            end
        end
    end
end
main()

Measured memory_bytes: 164104
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    string s;
    cin >> s;
    int ans=700;
    if(s.at(0) == 'o')ans+=100;
    if(s.at(1) == 'o')ans+=100;
    if(s.at(2) == 'o')ans+=100;
    cout << ans <<endl;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	string s; cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
lis1 = list(map(int,input().split()))
lis2 = list(map(int,input().split()))
lis3 = list(map(int,input().split()))
a = lis1[0] -lis2[0]
if lis1[1] - lis2[1] == a and lis1[2] - lis2[2] == a:
 b = lis2[0] - lis3[0]
 if lis2[1] - lis3[1] == b and lis2[2] - lis3[2] == b:
  c = lis1[1] - lis1[0]
  if lis2[1] - lis2[0] == c and lis3[1] - lis3[0] == c:
   d = lis1[2] - lis1[1]
   if lis2[2] - lis2[1] == d and lis3[2] - lis3[1] == d:
    print("Yes")
   else:
    print("No")
  else:
   print("No")
 else:
  print("No")
else:
 print("No")

Measured memory_bytes: 3064
/*==============================================*\
Codeforces ID:    mdshihab
                                                  |
Name:     Md. Shihabul Minhaz                     |
Study:      CSE, JKKNIU                           |
Address:  Trishal, Mymensingh, Bangladesh         |
                                                  |
 mail:   mdshihabul20171@gmail.com                |
 FB  :   fb.com/mdshihabul.minhaz.7               |
 github: Shihabulminhaz                           |
stopstalk :  mdshihab                             |
                                                  |
@uthor   Md. Shihabul Minhaz (shihab)             |
\*===============================================*/


#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
void FI()
{
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\SHIHAB\\Desktop\\input.in","r",stdin);
#endif // ONLINE_JUDGE
}

int main()
{
    fast
   // FI(); /// skip this line for compile
    ll n,d,x,y,cnt=0;
    cin >> n >> d;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        if(sqrtl(x*x+y*y)<=d) cnt++;
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#define INF (1e9)
#define J 2001
#define N 50
using namespace std;
int main(){
  int n,c[N],dp[J],dn[J],C=0;
  while(1){
    cin>>n;
    if(!n) break;
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=0;i<J;i++) dp[i]=dn[i]=INF;
    sort(c,c+n);
    dp[0]=0;
    for(int i=0;i<n;i++)
      for(int j=1;j<J;j++)
	if(j>=c[i]) dp[j]=min(dp[j],dp[j-c[i]]+1);
    sort(c,c+n);
    reverse(c,c+n);
    for(int i=0;i<J;i++){
      int cnt=0,sum=i;
      for(int j=0;j<n;j++){
	cnt+=sum/c[j];
	sum%=c[j];
      }
      if(sum==0) dn[i]=cnt;
    }
    int flag=0;
    for(int i=1;i<J;i++){
      if(dp[i]==INF||dn[i]==INF){
	flag=1;
	break;
      }
      if(dp[i]!=dn[i]){
	flag=2;
	break;
      }
    }
    C++;
    cout<<"Case #"<<C<<": ";
    if(!flag) cout<<"OK"<<endl;
    else if(flag==1) cout<<"Cannot pay some amount"<<endl;
    else cout<<"Cannot use greedy algorithm"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1200
n = int(input())
d,x = map(int,input().split())
counter = 0

for i in range(n):
    a = int(input())
    if d%a==0:
        b =int(d/a)
        counter += b
    else:
        b = int(d/a)
        counter += b+1
    
print(counter+x)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <sstream>
#include <functional>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;

int ToInteger ( string s )
{
	ISS iss; iss.str(s);
	int x;
	iss >> x;
	return x;
}

int dfs ( string s, int &idx )
{
	vector<int> vn;
	while (idx < s.size()) {
		char c = s[idx];
		if (c == '[') {
			char nx = s[idx+1];
			if (nx == '[') {
				++idx;
				vn.push_back(dfs(s, idx));
			}
			else {
				string num;
				++idx;
				while (idx < s.size()) {
					if (s[idx] == ']') { break; }
					num += s[idx];
					++idx;
				}
				vn.push_back(ToInteger(num));
			}
		}
		if (c == ']') {
			char pr = s[idx-1];
			if (pr == ']') {
				++idx;
				break;
			}
			else { ++idx; }
		}
	}
	int res = 0;
	sort(vn.begin(), vn.end());
	for (int i = 0, I = vn.size()/2+1; i < I; ++i) {
		res += (vn[i] / 2 + 1);
	}
	return (res-1)*2;
}

int main ( void )
{
	int n;
	string s;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> s;
		int idx = 0;
		cout << dfs(s, idx) / 2 + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 1332
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;

int sumOfDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    int sum = sumOfDigits(n);
    string ans = (n % sum == 0)? "Yes" : "No";

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

Measured memory_bytes: 256
#include<cstdio>
const int MaxK=100010,MaxQ=100010;
int X,K,r[MaxK],Q,t[MaxQ],a[MaxQ];
int L,R,b,T;
bool dir;
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
void mov(int t){
	if(dir){
		b+=min(t-T,X-b-L);
		R=min(R,X-b);
	}
	else{
		b-=min(t-T,b+R);
		L=max(L,-b);
	}
	T=t;
}
int main(){
	scanf("%d%d",&X,&K);
	for(int i=0;i<K;i++)scanf("%d",r+i);
	scanf("%d",&Q);
	for(int i=0;i<Q;i++)scanf("%d%d",t+i,a+i);
	R=X;
	for(int i=0,j=0;i<K||j<Q;){
		if(j==Q||i<K&&r[i]<t[j]){
			mov(r[i++]);
			dir^=1;
		}
		else{
			mov(t[j]);
			printf("%d\n",b+min(max(a[j++],L),R));
		}
	}
}

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

int main() {

  long long A, B, V, W, T;
  cin >> A >>V;
  cin >> B >> W;
  cin >> T;
  
  if(V <= W){
  cout << "NO" << endl;
  }
  
  else if(T*(V-W) < abs(A-B)){
  cout << "NO" << endl;
  }
  
  else{
  cout << "YES" << endl;
  }

}

Measured memory_bytes: 3620
n,m = map(int,input().split())
s = [0]*m
c = [0]*m
for i in range(m):
    s[i], c[i] = map(int, input().split())
 
if n == 1:
    start = 0
elif n == 2:
    start = 10
else:
    start = 100
for i in range(start,10**n):
    num = str(i)
    for j in range(m):
        if num[s[j]-1] != str(c[j]):
            break
    else:
        break
else:
    print(-1)
    exit()
print(num)

Measured memory_bytes: 9200
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;

int N, Q;
string S;

int main() {
    cin >> N >> Q;
    cin >> S;
    
    vector<int> s(N+1, 0);
    for (int i = 0; i < N; i++) {
        if (S[i] == 'A' && S[i+1] == 'C') s[i+1] = s[i] + 1;
        else s[i+1] = s[i];
    }

    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        
        cout << s[r-1] - s[l-1] << endl;
    }
}

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

int main(void){
  int n; 
  cin >> n;
  
  double ans = 0.0;
  
  for (int i = 1; i <= n; i++) {
    double x;
    string u;
    cin >> x >> u;
    
    if (u == "JPY") {
      ans += x;
    }
    else {
      ans += x * 380000.0;
    }
  }
  
  printf("%f", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; i++)
#define RFOR(i, a, n) for (ll i = (ll)n - 1; i >= (ll)a; i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define bra(first, second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 1001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template <typename T>
void remove(std::vector<T> &vector, unsigned int index)
{
   vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

// MOD確認

ll H,W,M;

pair<ll,ll> Y[300010];
pair<ll,ll> X[300010];



int main(){
  cin >> H >> W >> M;
  map<pair<ll,ll>,ll> mp;
  rep(i,300010){
     Y[i].second = i;
     X[i].second = i;
  }
  rep(i,M){
     ll h,w;
     cin >> h >> w;
     h--;w--;
     mp[make_pair(h,w)]++;
     Y[h].first++;
     X[w].first++;
  }
  ll ans = 0;
  sort(X,X+300010);
  sort(Y,Y+300010);
  reverse(X,X+300010);
  reverse(Y,Y+300010);
  rep(i,10) rep(j,M){
     ll num = Y[i].first + X[j].first;
     if(mp[make_pair(Y[i].second,X[j].second)] >= 1){
        num--;
     }
     ans = max(ans,num);
  }
  rep(i,M) rep(j,10){
     ll num = Y[i].first + X[j].first;
     if(mp[make_pair(Y[i].second,X[j].second)] >= 1){
        num--;
     }
     ans = max(ans,num);
  }
  cout << ans << endl;
}

Measured memory_bytes: 406656
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a,b;
int main()
{
	cin>>a>>b;
	if (a+b==15) cout<<"+";
	    else if (a*b==15) cout<<"*";
	        else cout<<"x";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    int N, A;
    cin >> N >> A;
    vector<int> x(N);
    for(int i = 0; i < N; i++){
        cin >> x[i];
    }
    vector<int> y(N);
    for(int i = 0; i < N; i++){
        y[i] = x[i] - A;
    }

    vector<vector<long long>> cnt(N + 1, vector<long long>(10000, 0));
    cnt[0][5000] = 1;
    for(int i = 0; i < N; i++){
        int tempY = y[i];

        for(int j = -2500; j <= 2500; j++){
            cnt[i + 1][j + 5000] = cnt[i][j + 5000] + cnt[i][j + 5000 - tempY];
        }
    }

    cout << cnt[N][5000] - 1 << endl;

    return 0;
}

Measured memory_bytes: 4352
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;

char str[300][301];
int a[300][305];

int main(int argc, char* argv[])
{
    int H,W,K;
    scanf("%d%d%d", &H, &W, &K);
    vector<int> cnt(H);
    int i,j;
    for(i=0; i<H; i++) {
        scanf("%s", str[i]);
        for(j=0; j<W; j++) {
            if(str[i][j]=='#') cnt[i]++;
        }
    }
    int curr=1;
    for(i=0; i<H; i++) {
        if(cnt[i]) {
            int flag=0;
            for(j=0; j<W; j++) {
                if(str[i][j]=='#') {
                    if(flag==0) flag=1;
                    else {
                        curr++;
                    }
                }
                a[i][j]=curr;
            }
            curr++;
        }
    }

    for(i=1; i<H; i++) {
        if(a[i][0]==0 && a[i-1][0]) {
            for(j=0; j<W; j++) {
                a[i][j]=a[i-1][j]; 
            }
        }
    }
    for(i=H-2; i>=0; i--) {
        if(a[i][0]==0 && a[i+1][0]) {
            for(j=0; j<W; j++) {
                a[i][j]=a[i+1][j]; 
            }
        }
    }

    for(i=0; i<H; i++) {
        for(j=0; j<W; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }


    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
const unsigned long long mod = 1e9 + 7;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N;		cin>>N;
	string S;		cin>>S;
	int count=0;
	FOR(i,0,N)	if(S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C')	count++;	
	cout<<count<<endl;


    return 0;
}




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

#define rep(i, o) for (int i = 0; i < (o); ++i)
#define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
#define NUM 1e5

typedef long long ll;
typedef unsigned long long ull;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

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

  ll length = s.size();
  string ans = (length <= k) ? s : s.substr(0,k) + "...";
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
import java.util.*;
import java.util.Arrays;
     
public class Main {
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int N = sc.nextInt();
    	int A = sc.nextInt();
    	int B = sc.nextInt();
    	int C = sc.nextInt();
    	
    	int[] D = new int[N];
    	int s = 0;
    	double[] answer = new double[N + 1];
    	
    	for(int i = 0;i < N;i++){
    		D[i] = sc.nextInt();
    	}
    	
    	Arrays.sort(D);
    	
    	for(int j = 0;j < N;j++){
    		int kal_sum = C;
    		int pay_sum = A + B * s;
    		for(int i = N - 1;i > N - 1 - s;i--){
    			kal_sum += D[i];
    		}
    		//System.out.println(j+" "+kal_sum+" "+pay_sum);
    		answer[s] = kal_sum / pay_sum;
    		s++;
    	}
    	
    	int max = (int)answer[0];
    	for(int i = 0;i < N + 1;i++){
    		if(max < answer[i])
    			max = (int)answer[i];
    	}
    	
    	System.out.println(max);
    	
    	
    }
}

Measured memory_bytes: 18160
#include<stdio.h>
#include<stdlib.h>

void run(void){
  int n,k;
  scanf("%d%d",&n,&k);
  const int mod=1000000007;
  int *dp=(int *)calloc(k+1,sizeof(int));
  dp[0]=1;
  while(n--){
    int a;
    scanf("%d",&a);
    int sum=0;
    int i;
    for(i=k;i>k-a;i--) sum=(sum+dp[i])%mod;
    for(i=k;i>=0;i--){
      if(i-a>=0) sum=(sum+dp[i-a])%mod;
      int sub=dp[i];
      dp[i]=sum;
      sum=(sum+mod-sub)%mod;
    }
  }
  printf("%d\n",dp[k]);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200009];
ll b[200009];
ll tree[800009];
void upd(int node,int l,int r,int k,ll val){
	if(l == r){
		tree[node] = val;
		return;
	}
	if(k <= (l+r)/2) 
		upd(node*2,l,(l+r)/2,k,val);
	else 
		upd(node*2+1,(l+r)/2+1,r,k,val);
	tree[node] = max(tree[node*2],tree[node*2+1]);
}
ll query(int node,int l,int r,int s,int e){
	if(s <= l && e >= r)
		return tree[node];
	if(s <= (l+r)/2 && e >= (l+r)/2+1){
		return max(query(node*2,l,(l+r)/2,s,e),query(node*2+1,(l+r)/2+1,r,s,e));
	}
	if(s <= (l+r)/2) 
		return query(node*2,l,(l+r)/2,s,e);
	return query(node*2+1,(l+r)/2+1,r,s,e);
}
int main(){
	int n; cin>>n;
	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++){
		ll id = a[i],val = b[i];
		ll x = query(1,0,n-1,0,id-1);
		upd(1,0,n-1,id,x+val);
	}
	cout<<tree[1]<<endl;
}

Measured memory_bytes: 9600