akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
using namespace std;

void moveE(int dice[]);
void moveN(int dice[]);
void moveS(int dice[]);
void moveW(int dice[]);
void moveR(int dice[]);

int main(void)
{	
	int dice[6];
	for (int i = 0; i < 6; i++) cin >> dice[i];
	
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int num0, num1;
		cin >> num0 >> num1;
		
		int cnt = 0;
		while (dice[0] != num0) {
			if (cnt < 3) moveE(dice);
			else moveN(dice);
			cnt++;
		}
		while (dice[1] != num1) moveR(dice);
		
		cout << dice[2] << endl;
	}
	
	return 0;
}

void moveE(int dice[])
{
	int temp = dice[0];
	dice[0] = dice[3];
	dice[3] = dice[5];
	dice[5] = dice[2];
	dice[2] = temp;
}

void moveN(int dice[])
{
	int temp = dice[0];
	dice[0] = dice[1];
	dice[1] = dice[5];
	dice[5] = dice[4];
	dice[4] = temp;
}

void moveS(int dice[])
{
	int temp = dice[0];
	dice[0] = dice[4];
	dice[4] = dice[5];
	dice[5] = dice[1];
	dice[1] = temp;
}

void moveW(int dice[])
{
	int temp = dice[0];
	dice[0] = dice[2];
	dice[2] = dice[5];
	dice[5] = dice[3];
	dice[3] = temp;
}

void moveR(int dice[])
{
	int temp = dice[1];
	dice[1] = dice[2];
	dice[2] = dice[4];
	dice[4] = dice[3];
	dice[3] = temp;
}

Measured memory_bytes: 3128
n,d=map(int, input().split())
x=[]
for i in range(n):
    tmp=[int(x) for x in input().split()]
    x.append(tmp)

import math

def dist(x,y):
    tmp=0
    for i in range(d):
        tmp+=(x[i]-y[i])**2
    return math.sqrt(tmp)

ans=0
import itertools
for seq in itertools.combinations(range(n),2):
    if dist(x[seq[0]],x[seq[1]]).is_integer():
        ans+=1
print(ans)

Measured memory_bytes: 62716
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;

ll n, p, a[maxn];
ll sum;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p;
	for (int i = 0; i < n; i++)
	{
		int w, b;
		cin >> w >> b;
		a[i] = (100 - p) * w + p * b;
		sum += (100 - p) * w;
	}
	sort (a, a + n);
	for (int i = 0; i < n; i++)
	{
		sum -= a[i];
		if (sum < 0)
			return cout << n-i << endl, 0;
	}
	return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>

#define PI acos(-1);

using namespace std;

int main(){
	long long n,k;
	cin >> n >> k;
	
	long long mi;
	long long mx;
	long long ans=0;
	
	for(long long i=k;i<=n+1;i++){
		mi=i*(i-1)/2;
		mx=n*i-(i*(i-1))/2;
		ans+=(mx-mi+1);
		ans%=1000000007;
	}
	
	cout << ans << endl;
	return 0;
}


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

#define M 1000000
#define L 14

char H[M][L];

int getChar(char ch){
  if(ch=='A') return 1;
  else if(ch=='C') return 2;
  else if(ch=='G') return 3;
  else if(ch=='T') return 4;
}

long long int getKey(char str[]){
  long long int sum=0,p=1;
  for(int i=0;i<strlen(str);i++){
    sum+=p*(getChar(str[i]));
    p*=5;
  }
  return sum;
}

int h1(int key){ return key%M ; }
int h2(int key){ return 1+(key%(M-1)) ;}

int find(char str[]){
  long long int key,h;
  key=getKey(str);
  for(int i=0;;i++){
    h=(h1(key)+i*h2(key))%M;
    if(strcmp(H[h],str)==0) return 1;
    else if(strlen(H[h])==0) return 0;
  }
  return 0;
}


int insert(char str[]){
  long long int key,h;
  key=getKey(str);
  for(int i=0;;i++){
    h=(h1(key)+i*h2(key))%M;
    if(strcmp(str,H[h])==0) return 0;
    else if(strlen(H[h])==0){
      strcpy(H[h],str);
      return 0;
    }
  }
  return 0;
}

int main(){
    int n,h;
    char str[L],com[9];
    for (int i=0;i<M;i++) H[i][0]='\0';
    
    scanf("%d", &n);
    
    for(int i=0;i<n;i++){
	scanf("%s%s",com,str);
	
	if(com[0]=='i'){
	    insert(str);
	}else{
	  if(find(str)){
	    printf("yes\n");
	  }else{
	    printf("no\n");
	  }
	}
    }
    return 0;
}



Measured memory_bytes: 16808
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(n)]
cd = [list(map(int, input().split())) for i in range(m)]

for i in range(n):
  a, b = ab[i]
  
  dist = 1e+15
  ans = 0
  for j in range(m):
    c, d = cd[j]    

    if dist > abs(a - c) + abs(b - d):
      ans = j
      dist = abs(a - c) + abs(b - d)
  
  print(ans+1)
    
    
    

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

int main()
{
	string s,t;
	cin >>s>>t;
	int ans=0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != t[i])ans++;
	}
	cout << ans<<endl;
}


Measured memory_bytes: 3916
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll MOD = 1000000007;
const ll N=1e5+9;
int main()
{
    FASTINOUT;
    int x,y,m;
    cin>>x>>y>>m;
    pair<int,int>a[x],b[x];
    map<int,int>aa,bb;
    int mnf=1e9,mns=1e9;
    for (int i=0;i<x;i++){
        cin>>a[i].first;
        a[i].second=i;
        aa[i]=a[i].first;
        mnf=min(mnf,a[i].first);
    }
    for (int i=0;i<y;i++){
        cin>>b[i].first;
        b[i].second=i;
        bb[i]=b[i].first;
        mns=min(mns,b[i].first);
    }
    map<pair<int,int>,int>mp;
    int p1,p2,op;
    for (int i=0;i<m;i++){
        cin>>p1>>p2>>op;
        p1--,p2--;
        mp[{p1,p2}]=max(mp[{p1,p2}],op);
    }
    ll ans=1e18;
    for (auto j:mp){
        int kl=aa[j.first.first];
        int km=bb[j.first.second];
        int jo=j.second;
        if (ans>kl+km-jo){
            ans=kl+km-jo;
        }
    }
    cout<<min((ll)(mnf+mns),ans)<<endl;
    return 0;
}


Measured memory_bytes: 17408
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
const int MOD = 1000000007;

bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  ll A,B,C,res=0;
  cin >> A >> B >> C;
  if( A+B+1 <= C)
    res = B+A+1+B;
  else
    res = B+C;
  cout << res << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int N;
	scanf("%d",&N);
	char S[N];
	scanf("%s",S);
	int K;
	scanf("%d",&K);
	for (int i = 0; i < N; i++) {
		if (i == K - 1) continue;
		if (S[i] != S[K - 1]) {
			S[i] = '*';
		}
	}
	printf("%s\n",S);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(long long N, long long M, std::vector<long long> H, std::vector<long long> A, std::vector<long long> B){
  set<ll> dai;
  REP(N){
    dai.insert(i);
  }
  REP(M){
    if(H[A[i]]>H[B[i]]){
      dai.erase(B[i]);
    }else if(H[A[i]]<H[B[i]]){
      dai.erase(A[i]);
    }else{
      dai.erase(A[i]);
      dai.erase(B[i]);
    }
  }
  cout<<dai.size()<<endl;
}

int main(){
  cout<<setprecision(1000);
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> H(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&H[i]);
    }
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
        --A[i];--B[i];
    }
    solve(N, M, std::move(H), std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 10392
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

struct edge {
    int src,to;

    edge() = default;
    
    edge(int to) : src(-1), to(to) {}

    edge(int src, int to) : src(src), to(to) {}

};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string S; cin >> S;
    int N = S.size();

    bool ok = true;
    for (int i = 0; i < N; i++) {
        if (i == 0 || i == N-2) {
            if (S[i] == '0') ok = false;
        } else if (i == N-1) {
            if (S[i] == '1') ok = false;
        } else {
            if (S[i] != S[N-2-i]) ok = false;
        }
    }
    if (!ok) {
        cout << -1 << endl;
        return 0;
    }
    vector<edge> ans(N-1);
    int now = 0;    
    for (int i = 0; i < N-1; i++) {
        if (S[i] == '1') {
            ans[i].src = now;
            ans[i].to = i+1;
            now = i+1;
        } else {
            ans[i].src = now;
            ans[i].to = i+1;
        }
    }

    rep(i,N-1) cout << ans[i].src+1 << " " << ans[i].to+1 << endl;
}

Measured memory_bytes: 2384
n = gets.to_i
H = Hash.new{|hash, key| hash[key] = 0}
n.times{
  a = gets.chomp
  H[a] += 1
}
puts "AC x #{H["AC"]}"
puts "WA x #{H["WA"]}"
puts "TLE x #{H["TLE"]}"
puts "RE x #{H["RE"]}"

Measured memory_bytes: 14396
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = int(input())

ans = 0

L = LI()

for i in range(0, N - 2):
  for j in range(i + 1, N - 1):
    for k in range(j + 1, N):
      if L[i] != L[j] and L[k] != L[j] and L[i] != L[k]:
        if L[i] + L[j] > L[k] and L[j] + L[k] > L[i] and L[k] + L[i] > L[j]:
          ans = ans + 1

print(str(ans))

Measured memory_bytes: 8980
package main
 
import "fmt"
 
func main() {
  var N, cnt int
  fmt.Scan(&N)
  
  a := make([]int, N)
  for i := 0; i < N; i++ {
    fmt.Scan(&a[i])
    if a[i] != i+1 {
      cnt++
    }
  }
  
  var str string
  if cnt > 2 {
    str = "NO"
  } else {
    str = "YES"
  }
  
  fmt.Println(str)
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Main {

    public static void main(String[] args) throws IOException {
        doit(args, System.in, System.out);
    }

    static void doit(String[] args, InputStream in, PrintStream out)
            throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        String line = null;
        while ((line = reader.readLine()) != null) {
            if (line.isEmpty()) {
                continue;
            }
            String[] values = line.split(",");
            int number = Integer.parseInt(values[0]);
            double weight = Double.parseDouble(values[1]);
            double height = Double.parseDouble(values[2]);
            double bmi = weight / height / height;
            if (bmi >= 25.0) {
                out.println(number);
            }
        }
    }
}

Measured memory_bytes: 9760
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> hoge(n);
    for(int i=0;i<n;i++) cin>>hoge.at(i);
    
    string ans="Yes";
    
    for(int i=0;i<n-1;i++){
     if(hoge[i]>=hoge[i+1]){
         if(i!=0){
             if(hoge[i-1]>=hoge[i]) hoge[i]=hoge[i];
             else hoge[i]--;
         }else{
             hoge[i]--;
         }
     }
    }
    
    for(int i=1;i<n;i++){
        if(hoge[i-1]>hoge[i]) ans="No";
    }
    
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 640
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

x = inint()

res = x % 100
lim = x//100

c = res//5
res %= 5
c += res//4
res %= 4
c += res//3
res %= 3
c += res//2
res %= 2
c += res//1
res %= 1

if lim < c:
    print(0)
else:
    print(1)

Measured memory_bytes: 61228
# AOJ 0098 Maximum Sum Sequence II 
# Python3 2018.6.17 bal4u


#include <stdio.h>

a = [[0 for c in range(102)] for r in range(102)]
s = [[0 for c in range(102)] for r in range(102)]

n = int(input())
for r in range(n):
	a[r] = list(map(int, input().split()))

for r in range(n):
	for c in range(n): s[r][c+1] += s[r][c]+a[r][c]

ans = s[0][1];
for c in range(n):
	for k in range(c+1, n+1):
		t = 0
		for r in range(n):
			if t < 0: t  = s[r][k]-s[r][c]
			else:     t += s[r][k]-s[r][c]
			if t > ans: ans = t

print(ans)


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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  
  if (N * A > B){
    cout << B << endl;
  }
  else if (N * A < B){
    cout << N * A << endl;
  }
  else {
    cout << B << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
#include <atcoder/modint>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using ll = long long;
using P = pair<int,int>;
constexpr int INF = 1001001001;
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; }

vector<mint> pow10m;
vector<mint> pow11m;
struct S {
    mint a;
    int size;
};

struct F {
    mint a, b;
};

S op(S l, S r) {
    return S{l.a * pow10m[r.size] + r.a, l.size + r.size};
}
S e() { return S{0, 0}; }
S mapping(F l, S r) {
    if (l.b == 1) return S{r.a, r.size};
    return S{l.a * pow11m[r.size], r.size};
}
F id() { return F{0, 1}; }
F composition(F l, F r) {return l.b == 1 ? r : l; }

int main() {
    int n, q;
    cin >> n >> q;
    vector<S> a(n);
    rep (i, n) a[i]= S{1, 1};
    
    pow10m.push_back(1);
    pow11m.push_back(0);
    rep (i, n+1) pow10m.push_back(pow10m.back()*10);
    rep (i, n+1) pow11m.push_back(pow11m.back()*10+1);
    
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    rep (i, q) {
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        seg.apply(l, r, F{d, 0});
        cout << seg.all_prod().a.val() << endl;
    }
    
    return 0;
}


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

using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i=0; i<n; i++) {
        cin >> p.at(i);
    }
    int ans = 0;
    for(int i=1; i<n-1; i++) {
        if((p.at(i-1) - p.at(i)) * (p.at(i) - p.at(i+1)) > 0) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for (auto &i : mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll a;
    cin >> a;
    cout << a + a * a + a * a * a << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
#define MOD 1000000007

using namespace std;

void comb(vector<vector <long long> > &v){
  for(int i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(int k = 1;k <v.size();k++){
    for(int j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j])%MOD;
    }
  }
}

int main(){
    ll n, k; cin >> n >> k;
    vector<vector<long long> > v(n+1,vector<long long>(n+1,0));
    comb(v);
    rep(i, k) {
        if(i == 0)
            cout << n-k + 1 << endl;
        else {
            if(n-k-i < 0)
                cout << 0 << endl;
            else {
                    cout << v[k-1][i] * v[n-k+1][i+1] %MOD << endl;
            }
        }
    }
}


Measured memory_bytes: 31616
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>

using namespace std;

int f(int k,
      const vector<int>& h,
      vector<int>& res) {
  if (k == 0) return 0;

  if (res[k] == -1) {
    res[k] = f(k - 1, h, res) + abs(h[k] - h[k - 1]);
    if (k >= 2) {
      res[k] = min(res[k], f(k - 2, h, res) + abs(h[k] - h[k - 2]));
    }
  }
  
  return res[k];
}

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

  // lets start from 0, to n-1
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  
  vector<int> res(n, -1);
  
  cout << f(n - 1, h, res);

  return 0;
}


Measured memory_bytes: 7296
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <unordered_map>

using namespace std;

int main(){
    char ch;
    cin>>ch;
    unordered_map<char,char> m;
    m['A']='T';
    m['T']='A';
  	m['C']='G';
  	m['G']='C';
  	cout<<m[ch];
  	return 0;
}


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

using namespace std;

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

int main(){
  int n, d;
  cin >> n >> d;
  d += d + 1;
  cout << (n + d - 1) / d << endl;
  return 0;
}

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

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

  int n; cin >> n; int arr[n+2]; int sf[n+2];
  for (int i = 0; i < n+2; i++) {
    cin >> arr[i];
    sf[i] = 1000000000;
  }
  sf[0] = 0;
  for (int i = 0; i < n-1; i++) {
    if (abs(arr[i]-arr[i+1]) + sf[i] < sf[i+1]) {
      sf[i+1] = sf[i] + abs(arr[i]-arr[i+1]); 
    }
    if (abs(arr[i]-arr[i+2]) + sf[i] < sf[i+2]) {
      sf[i+2] = sf[i] + abs(arr[i]-arr[i+2]); 
    }
  }
  cout << sf[n-1];

  return 0;
}


Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

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

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

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

	string ans;
	if (a > 0)
	{
		ans = "Positive";
	}
	else if (a <= 0 && b >= 0)
	{
		ans = "Zero";
	}
	else
	{
		if (abs(b - a) % 2 == 0)
		{
			ans = "Negative";
		}
		else
		{
			ans = "Positive";
		}
	}

	cout << ans << endl;
}

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

int main()
{
#ifdef LOCAL
    // 以降 cin の入力元が 'xxx.txt' になる
    std::ifstream in("a.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

    int x, a;
    cin >> x >> a;

    if (x < a)
    {
        cout << 0;
    }
    else
    {
        cout << 10;
    }

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a[3],min=0,idx;
    scanf("%d %d %d",&a[0],&a[1],&a[2]);
    for(int i=0;i<3;i++)
    {
        min=a[i];
        idx=i;
        for(int j=i+1;j<3;j++)
        {
            if(a[j]<min)
            {
                min=a[j];
                idx=j;
            }
        }
        if(idx!=i)
        {
            int temp;
            temp=a[i];
            a[i]=a[idx];
            a[idx]=temp;
        }
    }
    printf("%d\n",a[2]*10+a[1]+a[0]);
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define WRAP(y,x,h,w) (0<=y && y<h && 0<=x && x<w)

typedef long long ll;
typedef unsigned long long ull;
typedef string str;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

int main() {
	vll num(100001, 0);
	ll n, K;
	cin >> n>> K;
	REP(i, n) {
		ll a, b;
		cin >> a >> b;
		num[a] += b;
	}
	
	FOR(i,1, 100001) {
		if (K <= num[i]) {
			cout << i << endl;
			break;
		}
		K -= num[i];
	}
	return 0;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())




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

	int a[5];
	rep(i, 5)cin >> a[i];


	int s = 0;
	rep(i, 5) s += (a[i] + 9) / 10 * 10;

	int mi = 10;
	rep(i, 5) {
		if (a[i] % 10 != 0 && a[i] % 10 < mi)mi = a[i] % 10;
	}
	s -= 10 - mi;
	cout << s << endl;



	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}

int dp[210000][5];
vi a;

int cost(int i,int s){
  if(s==0) return a[i];
  else if(s==4) return a[i];
  else if(s==1||s==3){
    if(a[i]%2==0&&a[i]>0) return 0;
    else if(a[i]>0) return 1;
    else return 2;
  }else{
    if(a[i]%2==0) return 1;
    else return 0;
  }
}


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

  int l;
  cin>>l;
  a = vi(l);
  rep(i,l){
    cin>>a[i];
  }

  rep(i,200100){
    rep(j,5){
      dp[i][j]=inf;
    }
  }
  dp[0][0]=0;

  rep(i,l){
    rep(j,5){
      FOR(k,j,5){
        dp[i+1][k]=min(dp[i+1][k],dp[i][j]+cost(i,k));
      }
    }
  }

  int ans=inf;
  rep(j,5) ans=min(ans,dp[l][j]);

  cout<<ans<<endl;

}

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

int main(void){
    int n,k;
    cin >>n>>k;
    string words;
    cin >> words;
    if(words[k-1]=='A'){
        words[k-1]='a';
    }else if(words[k-1]=='B'){
        words[k-1]='b';
    }else{
        words[k-1]='c';
    }
    cout << words;
  

}


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

int main()
{
  int64_t N, M, l, lcm, dn, dm;
  string S, T;
  cin >> N >> M >> S >> T;
  l = (N * M) / __gcd(N, M);
  dn = l / N;
  dm = l / M;
  lcm = (dn * dm) / __gcd(dn, dm);
  for (int64_t i = 0; i < l; i += lcm)
  {
    if (S.at(i / dn) != T.at(i / dm))
    {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << l << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
	string s,t;cin>>s>>t;
	for(int i=0;i<=s.length();i++){
		if(s==t){
			cout<<"Yes";return 0;
		}
		rotate(s.begin(),s.begin()+1,s.end());
	}
	cout<<"No";
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
using namespace std;
int main(){
	int n, a;
	cin >> n >> a;
	if (n % 500 <= a) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}



Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #各ノードの親番号
        self.rank = [0] * (n) #各ノードのランク（木の高さ）
        self.root = [-1]*(n+1) # -（各ノードの属するグループの要素数）

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            node = [x]
            cur = node[0]
            while self.par[cur] != cur:
                cur = self.par[cur]
                node.append(self.par[cur])
            
            for n in node:
                self.par[n] = cur
            
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
                
    # グループ数
    def groupsize(self):
        cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                cnt += 1
        return cnt

    # xの属すグループの要素数
    def size(self, x):
        return -self.root[self.find(x)]
    
    # xの属すグループの要素リスト
    def members(self, x):
        ret = []
        rootNode = self.find(x)
        for i in range(len(self.par)):
            if self.find(i) == rootNode:
                ret.append(i)
        return ret
    
    # ルートノードのリストを取得
    def get_roots(self):
        ret = []
        for i,x in enumerate(self.par):
            if x==i:
                ret.append(i)
        return ret
    
    # 各グループ毎の要素リストを取得
    def all_members(self):
        roots = self.get_roots()
        namedict = {}
        for i,r in enumerate(roots):
            namedict[r] = i            
        ret = [[] for _ in range(len(roots))]
        for i in range(len(self.par)):
            p = namedict[self.find(i)]
            ret[p].append(i)
        return ret
            
    

N,M,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
CD = [list(map(int,input().split())) for _ in range(K)]
    
uf = UnionFind(N)
for a,b in AB:
    uf.union(a-1,b-1)
    
ans = [0]*N
 
for group in uf.all_members():
    L = len(group)-1
    for a in group:
        ans[a] = L
        
# friends = [0]*N
# brock = [0]*N
for a,b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1
 
for c,d in CD:
    if uf.same_check(c-1,d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
 
print(*ans)
        
    
    
    
    
    
    
    

Measured memory_bytes: 115668
def li():
    return [int(x) for x in input().split()]


INF = 10 ** 60

N, W = li()
L = [li() for i in range(N)]
V = 10 ** 5
# W <= 10**9 なので、
# dp[i][w]: i番目の選択で重さwだった時の価値の最大値、は計算量厳しい
# dp[i][v]: i番目の選択で価値vだった時の重さの最小値、で考えて重さの最小値がW以下のものから最大価値を算出する

dp = [[INF] * (V+1) for _ in range(N)]

# 初期条件
# 選ばない
dp[0][0] = 0
# 選ぶ
w0, v0 = L[0]
dp[0][v0] = w0

for i in range(1, N):
    for v in range(V+1):
        cw, cv = L[i]
        # 選ばない
        dp[i][v] = min(dp[i][v], dp[i-1][v])
        # 選ぶ
        if v + cv > V:
            continue
        dp[i][v+cv] = min(dp[i][v+cv], dp[i-1][v] + cw)

# 重さの最小値がW以下で達成できるvの最大値
v_max = 0
for v in range(V+1):
    if dp[N-1][v] <= W:
        v_max = v
print(v_max)

Measured memory_bytes: 169720
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

char str[100];

ll calc(ll lhs, char c, ll rhs) {
  if (c == '+') { return lhs + rhs; }
  return lhs * rhs;
}
char *skip(char *p) {
  while (isdigit(*p)) { p++; }
  return p;
}

ll calc1() {
  char *p = str;
  ll lhs = atoi(p);
  p = skip(p);
  while (*p != 0) {
    char c = *p;
    p++;
    ll rhs = atoi(p);
    lhs = calc(lhs, c, rhs);
    p = skip(p);
  }
  return lhs;
}

ll calc2() {
  char *p = str;
  vector<ll> vs;
  ll lhs = atoi(p);
  p = skip(p);
  while (*p != 0) {
    char c = *p;
    p++;
    if (c == '+') { 
      vs.push_back(lhs);
      lhs = atoi(p);
    } else {
      ll rhs = atoi(p);
      lhs *= rhs;
    }
    p = skip(p);
  }
  FORIT(it, vs) { lhs += *it; }
  return lhs;
}

int main() {
  ll ans;
  while (scanf("%s %lld", str, &ans) > 0) {
    ll v1 = calc1();
    ll v2 = calc2();
    if (ans == v1 && ans == v2) {
      puts("U");
    } else if (ans == v1) {
      puts("L");
    } else if (ans == v2) {
      puts("M");
    } else {
      puts("I");
    }
  }
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 2019;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

int main() {
  string s;
  cin >> s;
  reverse(all(s));
  vl v(2019, 0);
  v[0]++;
  ll ans = 0;
  mint r = 0;
  rep(i, s.size()) {
    ll k = s[i] - '0';
    r = r + mint(10).pow(i) * k;
    ans += v[r.x];
    v[r.x]++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3780
N,M,X,Y = map(int, input().split())
x = [int(_) for _ in input().split()]
y = list(map(int, input().split()))
maxX = max(x)
minY = min(y)
flag = True
for i in range(Y+1):
    if X < i <= Y and maxX < i and minY >= i:
        print("No War")
        flag = False
        break
if flag:
    print("War")

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

int main(){
    int n,y;
    int ans=0;
    int flag=0;

    cin >>n>>y;

    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= n; j++){
            if(((n-(i+j))*1000 + 5000*j + 10000*i == y) && (n-(i+j)>=0)){
                flag=1;
                cout <<i<< " " <<j<< " " <<n-(i+j)<<endl;
                return 0;
            }
        }
    }

    if(flag==0)cout << "-1 -1 -1" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#ABC082C
N=int(input())
A=list(map(int,input().split()))
sA=set(A)
ans=0
d={}
for s in sA:
	d[s]=0
for a in A:
	d[a]+=1
for s in sA:
	if d[s]-s>=0:
		ans+=min(d[s],d[s]-s)
	else:
		ans+=d[s]
print(ans)
	

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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	// initialize();
	int a,b,c,d;
	cin >> a >> b >> c>>d;
	int A = a/d+(a%d >0), B = c/b+(c%b > 0);
	if (A>=B)
		cout << "Yes\n";
	else
		cout << "No\n";
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);

string mp[505],a[505],b[505];

int main()
{
    IOS();
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;++i)
    {
        cin >> mp[i];
        if(i&1)
            a[i].resize(m,'#'),b[i].resize(m,'.');
        else    
            b[i].resize(m,'#'),a[i].resize(m,'.');
        a[i][0]='#',a[i][m-1]='.';
        b[i][0]='.',b[i][m-1]='#';
    }   
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if(mp[i][j]=='#')
                a[i][j]=b[i][j]='#';
    for(int i=0;i<n;++i)
        cout << a[i] << "\n";
    cout << "\n";
    for(int i=0;i<n;++i)
        cout << b[i] << "\n";
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const ll INF = 1e17;
const ll MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;

int a[MAXN];

void solve(){
	int n;
	ll ans = INF, cur, sum;
	scanf("%d", &n);
	REP(i, 0, n) {
		scanf("%d", &a[i]);
	}
	REP(k, 0, 2) {
		if (k == 0) {
			if (a[0] > 0) {
				cur = a[0];
				sum = 0;
			} else {
				cur = 1;
				sum = 1 - a[0];
			}
		} else {
			if (a[0] < 0) {
				cur = a[0];
				sum = 0;
			} else {
				cur = -1;
				sum = a[0] + 1;
			}
		}
		REP(i, 1, n) {
			if (cur > 0) {
				cur += a[i];
				if (cur >= 0) {
					sum += cur + 1;
					cur = -1;
				}
			} else {
				cur += a[i];
				if (cur <= 0) {
					sum += 1 - cur;
					cur = 1;
				}
			}
		}
		ans = min(ans, sum);
	}
	printf("%lld\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
int const M=2e5+10,mod=1e9+7,inf=1e9+10;
int a[M],b[M];
int cnt[M];
bool check(int x,int y)
{
	if(x%y)return 1;
	return 0;
}
main()
{
	int n,h;
	cin>>n>>h;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	int sum=0,ans=inf;
	for(int i=n;i>=0;i--)
	{
		if(sum>=h)ans=min(ans,n-i);
		else ans=min(ans,((h-sum)/a[n]+check(h-sum,a[n])+n-i));
		sum+=b[i];
	}
	cout<<ans;
}

Measured memory_bytes: 2816
import java.io.*;
import java.util.*;
class Main{
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int k = saori.saori_hayami();
		int num = k/2;
		double ans = 0;
		if(k%2 == 0){
			ans = (double)num/k;
		} else {
			num++;
			ans = (double)num/k;
		}	
		System.out.println(ans);
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

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

inline int read()
{
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}

signed main()
{
	int n,m;
	n=read();
	m=read();
	if(n<10) m+=(10-n)*100;
	printf("%lld\n",m);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  vector<bool> table(1e6+1, false);

  sort(a.begin(), a.end());

  ll ans = 0;

  rep(i, n) {
    if (table[a[i]]) continue;
    for (ll j=1; a[i] * j<= 1e6; j++) {
      table[a[i]*j] = true;
    }
    if (a[i] != a[i+1])ans++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 4844
# ABC152d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)

    n = int(input())
    cou = 0
    for i in range(1, n + 1):
        if str(i)[-1] == '0':
            continue
        # print(i)
        if str(i)[0] == str(i)[-1]:
            cou += 1
        k = 2
        while True:
            b = int(str(i)[-1] + '0' * (k - 2) + str(i)[0])
            if b <= n:
                if k > 2:
                    if n - b > 10 ** (k - 1):
                        cou += 10 ** (k - 2)
                    else:
                        cou += (n - b)//10 + 1
                else:
                    cou += 1
                #print(i, k, cou)
                k += 1
                continue
            #print(i, cou)
            break
    print(cou)


if __name__ == '__main__':
    main()


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

#define ll     long long
#define fr     first
#define sec    second
#define rep(i,n)  for(i=0;i<n;i++)
#define vi     vector <int>
#define vc     vector <char>
#define vl     vector <ll>
#define vb     vector <bool>
#define pb     push_back
#define M      1000000007
#define ios    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define open   freopen("input.txt","r",stdin);
#define close  freopen("output.txt","w",stdout);
#define M_PI   3.14159265358979323846
#define pp     pair<int,int>
#define nn 100003
#define MM 1000000000
#define MN 1000000000000000000
int main()
{
    ios;
    ll n,i,f=0,gr=0,eq=0;
    cin>>n;
    vl a(n);
    rep(i,n)
    {
        cin>>a[i];
        if(a[i]>MM)
            gr++;
        else if(a[i]==MM)
            eq++;
        if(a[i]==0)
            f=1;
    }
    if(f==1)
    {
        cout<<"0";
        return 0;
    }
    if(gr>=2 || (gr>=1 && eq>=1))
    {
        cout<<"-1";
        return 0;
    }
    for(i=1;i<n;i++)
        a[i]*=a[i-1];
    
    if(a[n-1]>MN)
        cout<<"-1";
    else
        cout<<a[n-1];
    return 0;
}


Measured memory_bytes: 3952
#include <bits/stdc++.h>
using namespace std;
long long a[100010];
int main () {
  long long n,A,B;
  scanf("%lld%lld%lld", &n, &A, &B);
  for(int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
  }
  long long l = 0, r = (long long)1e9, best = -1;
  while(l <= r) {
    long long mid = (l + r) / 2;
    long long tmp = 0;
    for(int i = 0; i < n; i++) {
      if(a[i] <= mid * B) continue;
      long long t = a[i] - mid * B;
      if(t > 0) {
        tmp += t/(A - B) + (t%(A-B) != 0 ? 1 : 0);
      }
    }
    if(tmp <= mid) {
      best = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  printf("%lld\n", best);
  return 0;
}


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

int main() {
	int h,w,i,j;
	while(cin>>h>>w,h) {
		for(i=0;i<h;i++) {
			for(j=0;j<w;j++) {
				if((i+j)%2) {
					cout<<".";
				}
				else {
					cout<<"#";
				}
			}
			cout<<endl;
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1152