akhauriyash/Code-Regression huggingface dataset:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from bisect import bisect_left # bisect_left(list, value)
#from fractions import gcd

sys.setrecursionlimit(10**7)
N, K = map(int, input().split())


for k in range(1, 1000):
    if N < K**(k):
        print(k)
        exit()



Measured memory_bytes: 38256
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    // 整数の入力
    int n;
    cin >> n;

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

    bool o = true;
    int top = h[0];
    for (int i = 1; i < n; i++) {
      if (h[i] >= top) top=h[i];
      else if (h[i] < top-1) o=false;
      else if (h[i] == h[i-1]-1) ;
    }

    cout << (o?"Yes":"No") << endl;
    return 0;
}


Measured memory_bytes: 640
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll n,m,x;
    cin >> n >> m >> x;
    ll a[m];
    ll lsum = 0;
    ll rsum = 0;
    F0R(i,m){
      cin >> a[i];
      if(x > a[i]) lsum++;
      if(x < a[i]) rsum++;
    }
    ll ans = min(lsum,rsum);
    cout << ans << endl;


    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
#include <iostream>
using namespace std;
signed main(){
    int n , W , v , w ;
    long long whight[2][100005] = {} , ans=0;
    cin >> n >> W;
    for(int i=0 ;i<n ;i++ ){
        cin >> w >> v;
        for(int j=0 ;j<w ;j++){
            whight[i%2][j] = max( whight[i%2][j] , whight[(i+1)%2][j]);
        }
        for(int j=w ;j<=W ;j++ ){
            whight[i%2][j] = max ( whight[(i+1)%2][j] , v + whight[(i+1)%2][j-w] );
            ans = max(ans , whight[i%2][j]);
        }   
    }
    
    cout << ans << endl;
    return(0);
}

Measured memory_bytes: 1792
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

fn main() {
    input! {
        n: usize, s: Chars
    }

    let mut ans = 0;
    for i in 0..n {
        let s = &s[i..];
        let mut z = vec![0; s.len()];
        z[0] = s.len();
        let mut pos = 1;
        let mut count = 0;
        while pos < s.len() {
            while pos + count < s.len() && s[count] == s[pos+count] {
                count += 1;
            }
            z[pos] = count;
            if count == 0 {
                pos += 1;
                continue;
            }

            let mut w = 1;
            while w < count && w + z[w] < count {
                z[pos+w] = z[w];
                w += 1;
            }
            pos += w;
            count -= w;
        }
        for pos in 0..s.len() {
            if pos >= z[pos] {
                ans = max(ans, z[pos]);
            }
        }
    }
    println!("{}", ans);
}

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

#西暦i年の藻類x_iグラム
#x_i+1=r*x_i-D

r, D, x = map(int, input().split())

res = []
res.append(x)

for i in range(1,11):
    res.append(r * res[i-1] - D)

for p in range(1,len(res)):
    print(res[p])



Measured memory_bytes: 2940
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N,W;
int nowv, noww;
int wgt[110];
int val[110];
int dp[110][350][110];//枚举第first个物品，容量second，一共选了third的物品
int main()
{
    scanf("%d %d", &N, &W);
    for(int i = 1; i <= N; i++)
    {
        scanf("%d %d", &wgt[i], &val[i]);
    }
    int ans = 0;
    int minn = min(N,W/(wgt[1]+3));
    int maxn = min(N,W/wgt[1]);
    if(minn == N){
        for(int i = 1; i <= N; i++)ans+=val[i];
        printf("%d\n", ans);
        return 0;
    }
    int MW = 3*maxn;
        for(int j = 1; j <= N; j++)
        {
            for(int k = 1; k <= j; k++)
            {
                for(int l = 0; l < wgt[j]-wgt[1]; l++)
                {
                    dp[j][l][k] = dp[j-1][l][k];
                }
                for(int l = wgt[j]-wgt[1]; l <= MW; l++)
                {
                    if(l > 0)dp[j][l][k] = max(dp[j][l][k],dp[j][l-1][k]);
                    dp[j][l][k] = max(dp[j-1][l-wgt[j]+wgt[1]][k-1] + val[j], dp[j-1][l][k]);
                }

            }
        }
        for(int i = minn; i <= N; i++)
        {
            for(int j = minn; j <= maxn; j++)
            {
                for(int l = 0; l <= min(MW,W-wgt[1]*j); l++)
                {
                    ans = max(ans,dp[i][l][j]);
                }
            }
        }

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


    return 0;
}


Measured memory_bytes: 16128
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  n <- getInt
  print $ (1000 - (n `mod` 1000)) `mod` 1000

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

int main() {
  int n, a, b;
  int count = 0;
  cin >> n >> a >> b;

  for (int i = 1; i <= n; i++) {
    int c = i;
    int res = 0;
    while (c > 0) {
      res += c % 10;
      c /= 10;
    }
    if (a <= res && res <= b) {
      count += i;
    }
  }

  cout << count << endl;
  return 0;
}

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

int main()
{
  int N;
  cin >>N;
  string S,T;
  cin >>S>>T;
  string ans="";
  for(int i = 0;i<N;i++){
    ans = ans + S.at(i) + T.at(i);
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;


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

	ll N,x;
	cin >> N >> x;
	vector<ll> a(N);
	FOR(i,0,N)cin>>a[i];
	ll mc[N][N+1];
	FOR(i,0,N){
		FOR(j,0,N+1){
			if(j==0){
				mc[i][j]=a[i];
			}else{
				mc[i][j]=min(mc[i][j-1],a[((i-j)+N)%N]);
			}
		}
	}

	ll ans = INF;
	FOR(i,0,N+1){//2の呪文をi回やる
		ll p = x*i;
		FOR(j,0,N){
			p += mc[j][i];
		}
		ans = min(ans,p);
	}

	cout << ans << endl;

}


Measured memory_bytes: 31488
array=gets.chomp.split(" ").map(&:to_i)
a=array[0]
b=array[1]
c=array[2]
d=array[3]
c2=c
d2=d
while d2!=0 do #ユークリッドの互除法
 r=c2%d2
 c2=d2
 d2=r
end
gCD=c2
numB=b-b/c-b/d+b/(c*d/gCD)
numA=(a-1)-(a-1)/c-(a-1)/d+(a-1)/(c*d/gCD)
puts numB-numA

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;

#define rep(i, n) \
for(int i = 0; i <n; i++)
#define REP(i, a, b) \
for(int i = int(a); i <= int(b); i++)
#define TRvi(c, it) \
for(vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for(vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for(msi::iterator it = (c).begin(); it != (c).end(); it++)

#define INF 2000000000

#define MEMSET_INF 127
#define MEMSET_HALF_INF 63

void solve(){
    ll N;
    cin>>N;
    ll ans = 0;
    for(ll i=1;i<=N;++i){
        ll Y = N/i;
        ans+=(Y*(Y+1)*i)/2;
    }
    cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
// #define endl "\n"

int main(void) {
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
    ll n, w;
    cin >> n >> w;

    vector<ll> weight (n);
    vector<ll> value (n);

    for (ll i = 0; i < n; i++) {
        cin >>weight[i];
        cin >> value[i];
    }

    vector<vector<ll>> dp (w+1, vector<ll> (n));

    for (ll i = 0; i < w+1; i++) {
        if (i >= weight[n-1]) {
            dp[i][n-1] = value[n-1];
        } else {
            dp[i][n-1] = 0;
        }
    }

    for (ll j = n-2; j >= 0; j--) {
        // j is item
        for (ll i = 0; i < w+1; i++) {
            // i is available weight
            if (i < weight[j]) {
                dp[i][j] = dp[i][j+1];
            } else {
                dp[i][j] = max(value[j] + dp[i-weight[j]][j+1], dp[i][j+1]);
            }
        }
    }

    cout << dp[w][0] << endl;

    
    return 0;
}

Measured memory_bytes: 82304
//ΔAGC034C
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111111;
int n,k,b[N],l[N],r[N],ans;
LL s,f[N],g[N],w;
pair<LL,int> p[N];
LL cal(int i,int x){
	if(x>b[i])
		return (LL)(x-b[i])*r[i];
	return (LL)(x-b[i])*l[i];
}
int solve(int i,LL t){
	int le=0,ri=k,md;
	while(le<ri){
		md=le+ri>>1;
		if(cal(i,md)+t>=0)
			ri=md;
		else
			le=md+1;
	}
	return le;
}
int main()
{
	int i,j,o,x;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i=i+1){
		scanf("%d%d%d",b+i,l+i,r+i);
		f[i]=(LL)(k-b[i])*r[i];
		g[i]=(LL)(0-b[i])*l[i];
		s+=g[i];
		p[i]=make_pair(f[i]-g[i],i);
	}
	sort(p+1,p+n+1);
	reverse(p+1,p+n+1);
	j=0;
	while(s<0){
		j++;
		s+=p[j].first;
	}
	w=(LL)(j-1)*k;
	ans=k;
	for(i=1;i<=j;i=i+1){
		o=p[i].second;
		ans=min(ans,solve(o,s-f[o]));
	}
	s-=p[j].first;
	for(i=j;i<=n;i=i+1){
		o=p[i].second;
		ans=min(ans,solve(o,s-g[o]));
	}
	cout<<max(w+ans,(LL)0);
	return 0;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

const long long INF = 1e18;
//const ll mod = 1000000007;
ll dp[5005][5005];
ll N, A, B;
ll p[5000];

int main() {
    cin >> N >> A >> B;
    for(int i = 0; i < N; i++) {
        cin >> p[i];
    }
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= N; j++) {
            dp[i][j] = 1e18;
        }
    }
    dp[0][0] = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= N; j++) {
            if(p[i] < j) {
                chmin(dp[i+1][j], dp[i][j] + B);
            } else {
                chmin(dp[i+1][j], dp[i][j] + A);
                chmin(dp[i+1][p[i]], dp[i][j]);
            }
        }
    }
    ll ans = 1e18;
    for(int i = 0; i <= N; i++) {
        chmin(ans, dp[N][i]);
    }
    cout << ans << endl;
    return 0;
}


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

int main() {

  int X, N, K;
  X = 1;
  cin >> N >> K;
  for(int i = 0;i < N;i++){
  if((X * 2) > (X + K)){
  X = X + K;
  }else{
  X = X * 2;
  }
  }
  cout << X << endl;

}

Measured memory_bytes: 3616
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2700 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(i+1):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=dp[i][j][k]*(2*j+1)
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                if(j):
                    dp[i+1][j-1][k+2*(j-1)]+=dp[i][j][k]*j*j
                    dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

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

/*
1 6 7 9 10
2 3 4 5 8 

cast 1 2 6 8 9

7 10
3 4 5

*/

bool isLoop(int a[205], int n){
    bool taro, hana;
    taro = hana = false;
    range(i,1,n * 2 + 1){
        if(a[i] == 1) taro = true;
        if(a[i] == -1) hana = true;
    }
    return (taro && hana);
}

int main(){
    int n;
    while(cin >> n,n){
        int cards[205];
        rep(i,205) cards[i] = -1;
        rep(i,n){
            int inp;
            cin >> inp;
            cards[inp] = 1;
        }

        bool c = true;
        while(true){
            range(i,1,n * 2 + 1){
                if(c && cards[i] == 1){
                    cards[i] = 0;
                    c = false;
                }else if(!c && cards[i] == -1){
                    cards[i] = 0;
                    c = true;
                }
                if(not isLoop(cards, n)) break;
            }

            if(not isLoop(cards, n)) break;

            if(c) c = false;
            else c = true;
        }
        int sum = 0;
        range(i,1,2 * n + 1) sum += cards[i];
        if(sum < 0) cout << abs(sum) << endl << 0 << endl;
        else cout << 0 << endl << sum << endl;
    }
}

Measured memory_bytes: 1160
//https://atcoder.jp/contests/abc166/tasks/abc166_a
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
const ll LINF = 0x1fffffffffffffff;
#define FOR(i,a,b) for(ll i=(a);i<static_cast<ll>(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
  string S; cin>>S;
  if(S=="ABC")cout<<"ARC"<<endl;
  else cout<<"ABC"<<endl;
  return 0;
}

Measured memory_bytes: 3620
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define REP(i,a,b) for(register int i=(a); i<(b); i++)
#define REPE(i,a,b) for(register int i=(a); i<=(b); i++)
using namespace std;
typedef long long ll;
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <class T> inline void read(T&x) {
	x=0; char ch; do ch=getchar(); while(ch<=' ');
	while(ch>' ') {x=x*10+ch-'0'; ch=getchar();}
}
#define MAXN 200007
int n;
int a[MAXN];
int main() {
	read(n);
	REP(i,0,n) read(a[i]);
	sort(a,a+n);
	REP(i,1,n) if(a[i]==a[i-1]) { puts("NO"); return 0;}
	puts("YES");
}



Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size()-1; i++) {
        if (s[i] == s[i+1]) {
            cout << i+1 << " " << i+2;
            return 0;
        }
    }
    if (s.size() >= 3) {
        for (int i = 0; i < s.size()-2; i++) {
            if (s[i] == s[i+2]) {
                cout << i+1 << " " << i+3;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=500010;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s[k-1]=tolower(s[k-1]);
    cout<<s;

    return (0);
}


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

int main(){
	int a, b;
    cin >> a >> b;
  int t = (a + b) % 2;
  double q = (a + b) / 2;
  if (t == 1){
    cout << q + 1 << endl;
  }
    else if(t == 0){
  cout << q << endl;
    }
}

Measured memory_bytes: 3756
import sys

def solve():
    input = sys.stdin.readline
    A, B, K = map(int, input().split())
    Ans = set()
    for i in range(A, min(A + K, B + 1)): Ans |= {i}
    for i in range(max(A, B - K + 1), B + 1): Ans |= {i}
    Ans = list(Ans)
    Ans.sort()
    print("\n".join(map(str, Ans)))
        
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SHIFT_LEFT(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,l;cin>>n>>l;
  ll ans = 0;
  ll summ = 0;
  ll sa = llINF;
  for(int i=1;i<=n;i++)
    summ += l+i-1;
  for(int i=1;i<=n;i++){
    ll sum = 0;
    for(int j=1;j<=n;j++){
      if(i == j)continue;
      sum += l + j - 1;
    }
    if(abs(summ-sum) < sa){
      sa = abs(summ-sum);
      ans = sum;
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int takahashi = (A + D - 1) / D;
  int aoki = (C + B - 1) / B;
  string ans;
  if (takahashi >= aoki) {
    ans = "Yes";
  } else {
    ans = "No";
  }
  cout << ans << endl;
}


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

typedef struct {
	int *par, *size, *height;
} UF_forest;

void UF_initialize(UF_forest *F, int n)
{
	int i;
	F->par = (int*)malloc(sizeof(int) * (n + 1));
	F->size = (int*)malloc(sizeof(int) * (n + 1));
	F->height = (int*)malloc(sizeof(int) * (n + 1));
	for (i = 1; i <= n; i++) {
		F->par[i] = i;
		F->size[i] = 1;
		F->height[i] = 1;
	}
}

int UF_merge(UF_forest *F, int u, int v)
{
	for (; F->par[u] != u; u = F->par[u]);
	for (; F->par[v] != v; v = F->par[v]);
	if (u == v) return 0;
	else if (F->height[u] > F->height[v]) {
		F->par[v] = u;
		F->size[u] += F->size[v];
		return 1;
	} else {
		F->par[u] = v;
		F->size[v] += F->size[u];
		if (F->height[u] == F->height[v]) F->height[v]++;
		return 1;
	}
}

int main ()
{
	int i, N, M, u, w;
	scanf("%d %d", &N, &M);
	
	int ans = N - 1;
	UF_forest F;
	UF_initialize(&F, N);
	for (i = 0; i < M; i++) {
		scanf("%d %d", &u, &w);
		ans -= UF_merge(&F, u, w);
	}
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][3];
        String[] input = br.readLine().split(" ");

        arr[0][0] = Integer.parseInt(input[0]);
        arr[0][1] = Integer.parseInt(input[1]);
        arr[0][2] = Integer.parseInt(input[2]);

        for (int i = 1; i < n; i++) {
            input = br.readLine().split(" ");
            arr[i][0] = Math.max(arr[i - 1][1], arr[i - 1][2]) + Integer.parseInt(input[0]);
            arr[i][1] = Math.max(arr[i - 1][0], arr[i - 1][2]) + Integer.parseInt(input[1]);
            arr[i][2] = Math.max(arr[i - 1][0], arr[i - 1][1]) + Integer.parseInt(input[2]);
        }
        int max = 0;
        for (int i = 0; i < 3; i++) {
            if (arr[n - 1][i] > max) max = arr[n - 1][i];
        }
        System.out.println(max);
    }
}


Measured memory_bytes: 50736
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <math.h>

using namespace std;

typedef long long ll;

int main(void){
    ll n, l;
    cin >> n >> l;
    ll a = 0;
    for (ll i = 1;i <= n; i++){
        a += l + i - 1;
    }
    ll diff = 1145141919;
    for(ll i = 1; i <= n; i++){
        if (diff > abs(l + i - 1)){
            diff = abs(l + i - 1);
        }
    }
    if (a > 0){
        cout << a - diff << endl;
    }else{
        cout << a + diff <<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <cstring>

using namespace std;

#define REP(var, count) for(int var=0; var<count; var++)

int main(void) {
	while(true) {
		int W, H;
		scanf("%d %d", &W, &H);
		if ( W==0 ) { break; }
		
		char line[26][26];
		
		queue<pair<int, int> > que;
		
		strcpy(line[0], "#######################");
		strcpy(line[H+1], "#######################");
		
		for(int y=1; y<=H; y++) {
			line[y][0] = '#';
			scanf("%s", &line[y][1]);
			
			if ( char* p = strchr(line[y], '@') ) {
				que.push(make_pair(y, p - line[y]));
			}
		}
		
		int ret = 1;
		
		while(que.size()) {
			
			int y = que.front().first;
			int x = que.front().second;
			que.pop();
			
			int m[][2] = { {-1,0},{1,0},{0,1},{0,-1} };
			REP(d, 4) {
				if ( line[y+ m[d][0]] [x+ m[d][1]] == '.' ) {
					line[y+ m[d][0]] [x+ m[d][1]] = '+';
					ret++;
					que.push( make_pair(y+ m[d][0], x+ m[d][1]) );
				}
			}
		}
		
		cout << ret << endl;
	}
}

Measured memory_bytes: 3204
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cout<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}


typedef long long int64;


int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin>>a[i];

    int ans = INT_MAX;
    for (int i=-100; i<=100; i++) {
        int tmp = 0;
        for (int j=0; j<n; j++) {
            tmp += (i-a[j])*(i-a[j]);
        }
        ans = min(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int n, a[4], aa, i, j, count, tmp, bb;
	while(scanf("%1d%1d%1d%1d", &a[0], &a[1], &a[2], &a[3]) != 0){
		if(a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0) break;
		if(a[0] == 6 && a[1] == 1 && a[2] == 7 && a[3] == 4){
			printf("%d\n", 0);
			continue;
		}
		if(a[0] == a[1] && a[0] == a[2] && a[0] == a[3]){
			printf("NA\n");
			continue;
		}
		count = 0;
		aa = 0;
		while(aa != 6174){
			if(aa == 6174) break;
			count++;
			for(i = 0; i < 3; i++){
				for(j = i + 1; j < 4; j++){
					if(a[i] < a[j]){
						tmp = a[i];
						a[i] = a[j];
						a[j] = tmp;
					}
				}
			}
			aa = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
			bb = a[3] * 1000 + a[2] * 100 + a[1] * 10 + a[0];
			aa -= bb;
			a[0] = aa / 1000;
			a[1] = aa / 100 - a[0] * 10;
			a[2] = aa / 10 - (a[0] * 100 + a[1] * 10);
			a[3] = aa - (a[0] * 1000 + a[1] * 100 + a[2] * 10);
		}
		printf("%d\n", count);
	}
	return 0;
}

Measured memory_bytes: 608
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
H = LI()

for i in range(1,N)[::-1]:
    if (H[i] == H[i-1]-1):
        H[i-1] -= 1
    elif (H[i] < H[i-1]-1):
        break
else:
    print('Yes')
    quit()
print('No')


Measured memory_bytes: 60144
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long h, w;
  cin>>h>>w;
  if(h == 1 || w == 1){
    cout<<1<<endl;
    return 0;
  }
  if(h * w % 2 == 0){
    cout<<(h * w) / 2<<endl;
  }
  else{
    cout<<(h * w) / 2 + 1<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"


int main() {
	int N; cin >> N;
	long long int sum = 0;
	for (int i = 0; i < N; ++i) {
		int a; cin >> a; sum += a;
	}
	cout << sum / N << endl;
	return 0;
}

Measured memory_bytes: 2984
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

a,b=map(int,input().split())
print((a-1)*(b-1))

Measured memory_bytes: 68744
#include <iostream>
#include <string>
#include <cstring>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
using namespace std;
#define int long long
signed main(){
    int n;
    cin>>n;
    vector<pair<int, int> > a(n);
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        a[i]=make_pair(x, y);
    }
    int ans=n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            int p=a[i].first-a[j].first;
            int q=a[i].second-a[j].second;
            int t=n;
            for(int k=0;k<n;k++){
                if(k==j)continue;
                for(int l=0;l<n;l++){
                    if(a[k].first-p==a[l].first&&a[k].second-q==a[l].second)t--;
                }
            }
            ans=min(ans,t);
        }
    }
    cout<<ans<<endl;
    return 0;
}




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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

vector<ll> enum_div(ll n){
	vector<ll> ret;
	for(ll i=1;i*i<=n;++i){
		if(n%i==0){
			ret.push_back(i);
			if(i*i!=n){
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

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

	ll N=in<ll>(),M=in<ll>();
	auto ed = enum_div(M);
	sort(ALL(ed));
	auto res = find_if_not(ALL(ed),[&](ll v){return N<=M/v;});
	
	cout << *(res-1) << endl;
	return 0;
}


Measured memory_bytes: 256
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
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())

from collections import deque
H, W, K = MI()
S_ = [[] for _ in range(W)]
for i in range(H):
    s = S()
    for j in range(len(s)):
        S_[j].append(int(s[j]))



A = []
for i in range(2 ** (H - 1)):
    A_bit = []
    for j in range(H - 1):
        # 二進数表記でj回右にシフトして0桁目（一番下の桁）が1であればTrue
        if ((i >> j) & 1):
            A_bit.append(j)
    A.append(A_bit)


Ans_list = []
for a in A:
    sums = [0] * (len(a) + 1)
    ele = [0] * (len(a) + 1)
    ans = 0
    for s_ in S_:
        queue = deque(a)
        if queue == deque([]):
            ele[0] = sum(s_)
            if ele[0] > K:
                ans = 10 ** 6
                break
            sums[0] += sum(s_)
        else:
            x = queue.popleft()
            ele[0] = sum(s_[0:x + 1])
            if ele[0] > K:
                ans = 10 ** 6
                break
            sums[0] += sum(s_[0:x + 1])
            j = 1
            while queue != deque([]):
                y = queue.popleft()
                ele[j] = sum(s_[x + 1:y + 1])
                if ele[j] > K:
                    ans = 10 ** 6
                    break
                sums[j] += sum(s_[x + 1:y + 1])
                x = y
                j += 1
            ele[len(a)] = sum(s_[x + 1:H])
            if ele[len(a)] > K:
                ans = 10 ** 6
                break
            sums[len(a)] += sum(s_[x + 1:H])
        if max(sums) > K:
            ans += 1
            for k in range(len(a) + 1):
                sums[k] = ele[k]
    ans += len(a)
    Ans_list.append(ans)

print(min(Ans_list))

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

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

    ll ans = 0;

    if(b > n){
        ll k = a * n;
        ans = k / b;
    }else if(b == n){
        ll k = a * (n - 1);
        ans = k / b;
    }else{
        ll k = a * (b - 1);
        ans = k / b;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3620
MOD = 1000003
facts = [1,1] #階乗
invs = [1,1] #整数の逆元
invfacts = [1,1] #階乗の逆元
for ind in range(1, MOD):
    i = ind+1
    facts.append(facts[-1]*i % MOD)
    invs.append( -(MOD//i)*invs[MOD%i] % MOD )
    invfacts.append( invfacts[-1]*invs[i] % MOD )

def task(x, d, n, MOD=MOD):
    if x == 0:
        return 0
    if d == 0:
        return pow(x, n, MOD)
    
    xdivd = (x*invs[d]) % MOD
    if MOD <= xdivd + n -1:
        return 0
    ans = (facts[xdivd + n -1]*invfacts[xdivd - 1]) % MOD
    ans = (ans*pow(d, n, MOD)) % MOD
    return ans

Q = int(input())
for _ in range(Q):
    x, d, n = map(int, input().split())
    ret = task(x, d, n)
    print(ret)

Measured memory_bytes: 128008
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
int a[111];

int main() {
	cin >> n >> m;
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	double aver = sum * 1.0 / (4 * m);
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		double num = a[i] * 1.0;
		if(num >= aver) cnt++;
	}
	if(cnt >= m) puts("Yes");
	else puts("No");
	return 0;
}

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

using namespace std;

#define N 300000

int n,m,x,y,ans,a[N],vis[N],cnt,head[N],tot;
struct edge{int v,nxt;}e[N];

void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}

void dfs(int x){
	vis[x]=cnt;
	for (int i=head[x];i;i=e[i].nxt)
		if (!vis[e[i].v]) dfs(e[i].v);
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int j=1;j<=m;++j){
		scanf("%d%d",&x,&y); add(x,y); add(y,x);
	}
	for (int i=1;i<=n;++i)
		if (!vis[i]){++cnt; dfs(i);}
	for (int i=1;i<=n;++i)
		if (vis[i]==vis[a[i]]) ++ans;
	printf("%d\n",ans);
	
	return 0;
}
			

Measured memory_bytes: 5248
package main

import (
	"bufio"
			"os"
	"strconv"
	"strings"
	"sort"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

type Patient struct {
	ID, Distance int
}
type ByDistance []Patient
func (p ByDistance) Len() int { return len(p) }
func (p ByDistance) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p ByDistance) Less(i, j int) bool { return p[i]. Distance > p[j].Distance }

func main() {
	for scanner.Scan() {
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		patients := make([]Patient, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			buf := strings.Split(scanner.Text(), " ")
			id, _ := strconv.Atoi(buf[0])
			am, _ := strconv.Atoi(buf[1])
			pm, _ := strconv.Atoi(buf[2])
			patients[i] = Patient{id, am+pm}
		}
		sort.Sort(ByDistance(patients))
		fmt.Println(patients[0].ID, patients[0].Distance)
	}
}


Measured memory_bytes: 6000
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

struct UnionFind {
    vector<int> size, parents;
    UnionFind(int n){
        size.resize(n,0);
        parents.resize(n,0);
        for(int i = 0; i < n; i++){
            makeTree(i);
        }
    }
    void makeTree(int x){
        parents[x] = x;
        size[x] = 1;
    }
    bool isSame(int x, int y){return findRoot(x) == findRoot(y);}
    void unite(int x, int y){
        x = findRoot(x);
        y = findRoot(y);
        if(size[x] > size[y]){
            parents[y] = x;
            size[x] += size[y];
        }else{
            parents[x] = y;
            size[y] += size[x];
        }
    }
    int findRoot(int x){
        if(x != parents[x]){
            parents[x] = findRoot(parents[x]);
        }
        return parents[x];
    }
    int treeSize(int x){return size[findRoot(x)];}
};

int main(){
    int n, m; cin >> n >> m;
    vector<int> A(m), B(m);
    rep(i,m){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
    }
    UnionFind uf(n);
    ll cur = (ll)n * (n-1) / 2;
    vector<ll> res;
    rep(i,m){
        res.push_back(cur);
        int a = A[m - 1 - i], b = B[m - 1 - i];
        if(uf.isSame(a,b)) continue;
        cur -= (ll) uf.treeSize(a) * uf.treeSize(b);
        uf.unite(a,b);
    }
    reverse(ALL(res));
    rep(i,m) cout << res[i] << endl;
}

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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

vector<string> parse(const string& s) {
    stringstream ss(s);
    string t;
    vector<string> ret;
    while (getline(ss, t, '/')) {
        ret.emplace_back(t);
    }
    ret.back() += "@";  // "@" is added at the end of filename
    return ret;
}

bool match(const vector<string>& vs, const vector<string>& vt) {
    if (vt.size() < vs.size()) return false;
    rep(i, vs.size()) {
        if (vs[i] != vt[i]) return false;
    }
    return true;
}

bool exist(const vector<string>& vs, const vector<vector<string>>& paths) {
    for (const auto& vt : paths) {
        if (match(vs, vt)) return true;
    }
    return false;
}

// if connot be restored, return an empty vector
vector<string> restore(const vector<string>& vs, const vector<vector<string>>& paths) {
    vector<string> ret;
    for (const auto& s : vs) {
        if (s == ".") {
            continue;
        } else if (s == "..") {
            if (ret.empty()) return {};
            ret.pop_back();
        } else {
            ret.emplace_back(s);
            if (!exist(ret, paths)) return {};
        }
    }
    return ret;
}

void solve(int N, int M) {
    vector<vector<string>> paths;
    rep(i, N) {
        string s;
        cin >> s;
        paths.emplace_back(parse(s));
    }

    // queries
    rep(_, M) {
        vector<vector<vector<string>>> cand(2);
        rep(i, 2) {
            string s;
            cin >> s;
            if (s.back() == '/') {
                cand[i].emplace_back(parse(s + "index.html"));
            } else {
                cand[i].emplace_back(parse(s));
                cand[i].emplace_back(parse(s + "/index.html"));
            }
        }

        auto answer = [&]() {
            bool notfound = true;
            for (auto vs1 : cand[0]) {
                for (auto vs2 : cand[1]) {
                    auto vs = restore(vs1, paths);
                    auto vt = restore(vs2, paths);
                    if (!vs.empty() && !vt.empty()) {
                        notfound = false;
                        if (vs == vt) {
                            return "yes";
                        }
                    }
                }
            }
            return notfound ? "not found" : "no";
        };

        cout << answer() << endl;
    }
}

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

    int N, M;
    while (cin >> N >> M, N) {
        solve(N, M);
    }
}

Measured memory_bytes: 3212
using System;
using System.Numerics;

    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            BigInteger m = 0;
            BigInteger a = 0;
            BigInteger r = 0;
            BigInteger c = 0;
            BigInteger h = 0;
            for (var i = 0; i < N; i++)
            {
                var s0 = Console.ReadLine()[0];
                if (s0 == 'M') m++;
                if (s0 == 'A') a++;
                if (s0 == 'R') r++;
                if (s0 == 'C') c++;
                if (s0 == 'H') h++;
            }
            var D = new BigInteger[]{ m,a,r,c,h };
            var A = new int[] { 0,0,0,0,0,0,1,1,1,2};
            var B = new int[] { 1,1,1,2,2,3,2,2,3,3};
            var C = new int[] { 2,3,4,3,4,4,3,4,4,4};
            BigInteger sum = 0;
            for (var i = 0; i < 10; i++)
            {
                sum += D[A[i]] * D[B[i]] * D[C[i]];
            }
            Console.WriteLine(sum);
        }
    }

Measured memory_bytes: 15572
N,Ma,Mb=map(int,(input().split()))
a,b,c=[0]*N,[0]*N,[0]*N

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

MA=sum(a)
MB=sum(b)
dp=[[[float("inf") for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0]=0
for i in range(N):
  for j in range(MA):
    for k in range(MB):
      if dp[i][j][k]==float("inf"):
        continue
      dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
      dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i])

ans=float("inf")
for i in range(1,MA+1):
  for j in range(1,MB+1):
    if i*Mb==j*Ma:
      ans=min(ans,dp[N][i][j])

if ans==float("inf"):
  print(-1)
else:
  print(ans)

Measured memory_bytes: 103164
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int N;
    int d[N];
    cin >> N;
    for(int i=0; i<N;++i) cin >> d[i];
    
    int l[110] = {0}; //　バケット
    int answer=0; 
    for(int i=0;i<N;++i){
        for(int j=1;j<=100;++j){
            if(d[i] == j){
             l[j]++;
             if(l[j]==1) answer++;
        }
        }
    }
    cout << answer << endl;

}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
 
char a[10][6], b[10][6];
char *h[5], *v[5];
int diff[10];
int ans;
 
int check(int j){

    int i, k;
    
    for (k = 0; k <= j; k++) {
        for (i = 0; i <= j; i++) if (h[i][k] == v[k][i]) return 0;
    }

    return 1;
}
 
void solve(int k, int s){
    
    int i, x, y, bit;
 
    if (k == 10) { ans++; return; }
    x = k & 1, y = k >> 1;
    for (bit = 1, i = 0; i < 10; i++, bit <<= 1) {
        if (s & bit) continue;
        if (!x) {
            h[y] = a[i];
            solve(k+1, s | bit);
            if (diff[i]) {
                h[y] = b[i];
                solve(k+1, s | bit);
            }
        } else {
            v[y] = a[i];
            if (check(y)) solve(k+1, s | bit);
            if (diff[i]) {
                v[y] = b[i];
                if (check(y)) solve(k+1, s | bit);
            }
        }
    }
}
 
int main()
{
    int i, j;
 
    while(scanf("%s", a[0]) && a[0][0] != 'E') {
        for (i = 1; i < 10; i++) scanf("%s", a[i]);
        for (i = 0; i < 10; i++) {
            for (j = 0; j < 5; j++) b[i][j] = a[i][4-j];
            diff[i] = (memcmp(a[i], b[i], 5) != 0);
        }
        ans = 0;
        solve(0, 0);
        printf("%d\n", ans >> 3);
    }
    return 0;
}


Measured memory_bytes: 2044
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://arc069.contest.atcoder.jp/tasks/arc069_b>
問題文============================================================
 すぬけくんは動物が好きなので動物園を作りました。
 
 この動物園では 1,2,3,…,N の番号を割り振られた N 匹の動物が円環状に並べられています。
 i(2≦i≦N−1) 番の動物は i−1 番の動物と i+1 番の動物と隣り合っています。
 また、1 番の動物は N 番の動物と 2 番の動物と隣り合っており、
 N 番の動物は N−1 番の動物と 1 番の動物と隣り合っています。
 
 動物園には本当のことしか言わない正直者の羊と、嘘しか言わない嘘つきの狼の 2 種類の動物がいます。
 
 すぬけくんには羊と狼の区別がつかないので、それぞれの動物に両隣の動物が同じ種類かどうかを訪ねたところ、
 i 番目の動物は si と答えました。si が o ならば両隣の動物が同じ種類であると、
 x ならば異なる種類であると i 番の動物が言ったことを示します。
 
 より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のとき o と答え、そうでないとき x と答えます。
 狼は両隣の動物がどちらも羊あるいはどちらも狼のとき x と答え、そうでないとき o と答えます。
 
 これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。
 存在するならば一例を示し、存在しないならば -1 を出力しなさい。
 
=================================================================

解説=============================================================

 動物を 1,2番目を決めてしまえば、 1...Nまでの全ての動物の状態を一意に決定できる
 よって、 SW SS WS WW の４パターンから状態を復元して矛盾がなければそれを結果として出力する
================================================================
*/

string check(string SW,const string& s,const ll &N){
    for(int i = 1; i < N;i++){
        if(s[i] == 'o'){
            if(SW[i] == 'S'){
                SW.push_back(SW[i-1]);
            }else{
                if(SW[i-1] == 'S') SW.push_back('W');
                else SW.push_back('S');
            }
        }else{
            if(SW[i] == 'S'){
                if(SW[i-1] == 'S') SW.push_back('W');
                else SW.push_back('S');
            }else{
                SW.push_back(SW[i-1]);
            }
        }
    }
    if(SW[0] != SW[N]) return "";
    
    if(s[0] == 'o'){
        if(SW[0] == 'S'){
            if(SW[1] != SW[N-1]) return "";
        }else{
            if(SW[1] == SW[N-1]) return "";
        }
    }else{
        if(SW[0] == 'S'){
            if(SW[1] == SW[N-1]) return "";
        }else{
            if(SW[1] != SW[N-1]) return "";
        }
    }
    return SW;
}
void solve(){
    ll N; cin >> N;
    string s; cin >> s;
    
    string ss[4] = {"SS","SW","WS","WW"};
    string ret;
    for(int i = 0; i < 4;i++){
        ret = check(ss[i],s,N);
        if(ret.length() != 0){
            cout << ret.substr(0,N) << endl;
            return;
        }
    }
    cout << -1 << endl;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    solve();
	return 0;
}


Measured memory_bytes: 768
//ProblemC

#ifdef _MYPC
#include "mypc.h"
#endif // _MYPC

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <memory>
#include <cstdio>
#include <cstring>

using namespace std;

//ProblemC

#define MAXN 1000

class Solve {
private:
	int N, M, A, B;

	char c[MAXN][MAXN + 1]{};

#define No_Exit \
	{ cout << "NO" << endl; return; }

	void solve() {
		cin >> N >> M >> A >> B;
		for (int i = 0; i < N; i++) for (int j = 0; j < M; j++)
			c[i][j] = '.';

		int S = (N * M) / 2;
		int SA = N * (M / 2);
		int SB = M * (N / 2);
		if (S < A + B || SA < A || SB < B) No_Exit;

		if (N % 2 != 0) {
			for (int j = 0; j + 1 < M && A > 0; j += 2) {
				c[N - 1][j] = '<';
				c[N - 1][j + 1] = '>';
				A--;
			}
		}

		if (M % 2 != 0) {
			for (int i = 0; i + 1< N && B > 0; i += 2) {
				c[i][M - 1] = '^';
				c[i+1][M - 1] = 'v';
				B--;
			}
		}

		int i = 0, j = 0;
		while (i + 1 < N && j + 1 < M) {
			if (A > 1) {
				c[i][j] = '<'; c[i][j + 1] = '>'; A--;
				c[i + 1][j] = '<'; c[i + 1][j + 1] = '>'; A--;

				j += 2;
				if (j + 1 >= M) { i += 2; j = 0; }
			}
			else if (B > 1) {
				c[i][j] = '^'; c[i + 1][j] = 'v'; B--;
				c[i][j + 1] = '^'; c[i + 1][j + 1] = 'v'; B--;

				j += 2;
				if (j + 1 >= M) { i += 2; j = 0; }
			}
			else {
				break;
			}
		}

		if (A > 0) {
			c[i][j] = '<'; c[i][j + 1] = '>'; A--;
			j += 2;
			if (j + 1>= M) { i += 2; j = 0; }
		}
		
		if (B > 0) {
			if (i + 1 < N) {
				c[i][j] = '^'; c[i + 1][j] = 'v'; B--;
			}
			else {
				if (N % 2 == 0 || M % 2 == 0) No_Exit;

				c[N-1][M-2] = '<'; c[N - 1][M - 1] = '>';
				c[N - 2][M - 3] = '^'; c[N - 1][M - 3] = 'v';
			}
		}

		cout << "YES" << endl;
		for (int i = 0; i < N; i++) {
			cout << c[i] << endl;
		}
	}

public:
	Solve() { solve(); }
};

int main(int argc, char* argv[]) {
	unique_ptr<Solve> solve = make_unique<Solve>();
	return 0;
}


Measured memory_bytes: 2176
import scala.io.StdIn

object Main extends App {
  StdIn.readLine()
  val heights=StdIn.readLine().split(' ').map(_.toLong)

  var humidai:Long=0
  var highest:Long=0
  for(h <- heights){
    if(h < highest){
      humidai = humidai + highest-h
    }
    if(h>highest){
      highest=h
    }

  }
  println(humidai)
}








Measured memory_bytes: 86396