akhauriyash/Code-Regression huggingface dataset:
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
template<typename T>
T chmin(T& l, T r) {
    return l = min(l, r);
}
template<typename T>
T chmax(T& l, T r) {
    return l = max(l, r);
}
// ============ template finished ============
using pis = pair<int, string>;

pii analyzer(string s) {
    int acc = 0, minv = 0;
    for (char c : s) {
        acc += c == '(' ? 1 : -1;
        minv = min(minv, acc);
    }
    int least = max(0, -minv);
    return { least,acc };
}

string join(vector<string> brackets) {
    vector<pis> parsed;
    for (auto bracket : brackets) {
        auto[least, acc] = analyzer(bracket);
        parsed.push_back({ least,bracket });
    }
    sort(parsed.begin(), parsed.end());

    string res;
    for (auto p : parsed)res += p.second;
    return res;
}

void bracket_reverse(string& brackets) {
    reverse(brackets.begin(), brackets.end());
    for (char&c : brackets)c = c == '(' ? ')' : '(';
}

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

    vector<string> S(N);
    rep(i, N) cin >> S[i];

    vector<string> up, down;
    for (auto s : S) {
        auto[least, acc] = analyzer(s);
        if (acc > 0) {
            up.push_back(s);
        }
        else {
            bracket_reverse(s);
            down.push_back(s);
        }
    }
    string front = join(up);
    string back = join(down);
    bracket_reverse(back);

    string res = front + back;
    auto[least, acc] = analyzer(res);
    if (least == 0 && acc == 0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 122440
#include<iostream>
using namespace std;
int main()
{
    int a, b, c, d;
    cin>>a>>b>>c;
    if(a>=(b+c))
    {
        c=0;
    cout<<c<<endl;
    }
    else if(a<(b+c) || a<(b+c))
        {
        d=(b+c)-a;
    cout<<d<<endl;
        }

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
const int dm = 1 << 21;
char dn[dm], * di = dn;
inline void putint(ll X) {
	int keta = 0;
	char C[20];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

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

	pair<int, int> LR[200000];
	int T = getint();
	rep(t, T) {
		int N = getint();

		if (N <= 2) {
			int k = getint(), l = getint(), r = getint();
			if (N == 1) putint(l);
			else if (k == 2) {
				int k2 = getint(), l2 = getint(), r2 = getint();
				if (k2 == 2) putint(l + l2);
				else putint(l + max(l2, r2));
			}
			else {
				int k2 = getint(), l2 = getint(), r2 = getint();
				if (k2 == 2) putint(l2 + max(l, r));
				else putint(max(l + r2, l2 + r));
			}
			continue;
		}

		ll saishou = 0;
		int k1 = 0, k2 = N;
		rep(i, N) {
			int k = getint(), l = getint(), r = getint();

			if (l < r) {
				LR[--k2] = mp(k + 1, r - l);
				saishou += l;
			}
			else {
				LR[k1++] = mp(k, l - r);
				saishou += r;
			}
		}
		sort(LR, LR + k1);
		sort(LR + k1, LR + N);

		priority_queue<int> PQ;
		int i = k1;
		while (i < N && LR[i].first < k1) {
			PQ.push(LR[i++].second);
		}
		for (int j = k1; j <= N; j++) {
			while (i < N && LR[i].first <= j) {
				PQ.push(LR[i++].second);
			}
			if (PQ.size()) {
				auto q = PQ.top();
				PQ.pop();
				saishou += q;
			}
		}
		PQ = priority_queue<int>();
		i = k1 - 1;
		while (i >= 0 && LR[i].first > k1) {
			PQ.push(LR[i--].second);
		}
		for (int j = k1 - 1; j >= 0; j--) {
			while (i >= 0 && LR[i].first > j) {
				PQ.push(LR[i--].second);
			}
			if (PQ.size()) {
				auto q = PQ.top();
				PQ.pop();
				saishou += q;
			}
		}
		putint(saishou);
	}

	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);

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

    map<ll, int> p;

    for (int i = 0; i < A.size(); i++)
    {
        if(p[A[i]] == 1) {
            p[A[i]] = 0;
        } else
        {
            p[A[i]] += 1;
        }
        
        
        
    }
    
    ll ans = 0;
    
    for (auto i : p)
    {
        if(i.second >= 1)
        ans += 1;
    }
    
    cout << ans << endl;
    
    return 0;

}

Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 510000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

int main() {
  int X;
  cin >> X;
  if (X>=30) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
// template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
// template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
bool is_palindrome(string s){return s == string(s.rbegin(),s.rend());}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
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;
}



int main(){
    long long N;
    scanf("%lld",&N);
    if(N%1000==0){
        cout << 0 << endl;
        return 0;
    }
    cout << 1000-N%1000 << endl;

    return 0;
}


Measured memory_bytes: 3684
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define M 2000000000
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 2000100
vector<int>e[N];
int n, m;
bool used[N];
bool used2[N];
int a[N];
int b[N];
void dfs(int k, int d) {
	used[k] = true;
	if (d == 0)return;
	f(i, e[k].size()) {
		if (!used[e[k][i]]) {
			dfs(e[k][i], d - 1);
		}
	}
	return;
}

int main(void) {
	scanf("%d %d", &n, &m);
	int x, y, z;
	int ans = 0;
	f(i, n - 1) {
		scanf("%d %d", &x, &y);
		e[x - 1].push_back(y - 1);
		e[y - 1].push_back(x - 1);
		a[i] = x - 1;
		b[i] = y - 1;
	}
	if (m % 2 == 0) {
		f(ii, n) {
			f(i, n)used[i] = false;
			dfs(ii, (m/2));
			x = 0;
			f(i, n)if (used[i])x++;
			ans = max(ans, x);
		}
	}
	else {
		f(ii, n - 1) {
			f(i, n)used2[i] = false;
			f(i, n)used[i] = false;
			dfs(a[ii], (m / 2));
			f(i, n)if (used[i])used2[i] = true;
			f(i, n)used[i] = false;
			dfs(b[ii], (m / 2));
			f(i, n)if (used[i])used2[i] = true;
			x = 0;
			f(i, n)if (used2[i])x++;
			ans = max(ans, x);
		}
	}
	printf("%d\n", n - ans);
}

Measured memory_bytes: 54528
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

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

    vector<vector<int>> pref(n, vector<int>(m));
    rep(i, n)
    {
        rep(j, m)
        {
            int k;
            cin >> k;
            pref[i][k - 1] = j;
        }
    }

    int lb = 0, ub = n;
    while (ub - lb > 1)
    {
        int mid = (lb + ub) / 2;
        //cout << "lb: " << lb << " ub: " << ub << " mid: " << mid << endl;

        vector<map<int, int>> s(n, map<int, int>());
        rep(i, n)
        {
            rep(j, m)
            {
                s[i].insert(make_pair(pref[i][j], j));
            }
        }

        while (!s[0].empty())
        {
            vector<int> cnt(m, 0);
            rep(i, n)
            {
                cnt[s[i].begin()->second]++;
            }

            bool b = true;
            rep(j, m)
            {
                if (cnt[j] > mid)
                {
                    b = false;
                    rep(i, n)
                    {
                        s[i].erase(pref[i][j]);
                    }
                }
            }
            if (b)
            {
                break;
            }
        }

        (s[0].empty() ? lb : ub) = mid;
    }
    cout << ub << endl;

    return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> AC(N);
	
  	int cnt = 0;
    for (int i=1; i<N; i++) {
        if (S.at(i-1)=='A' && S.at(i)=='C') {
          cnt++;	
        }
      	AC.at(i) = cnt;
    }

    vector<int> left(Q);
    vector<int> right(Q);

    for (int i=0; i<Q; i++) {
        cin >> left.at(i) >> right.at(i);
        cout << AC.at(right.at(i)-1) - AC.at(left.at(i)-1) << endl;
    }

}

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

int main() {
  int64_t n, a, b;
  cin >> n >> a >> b;
  int64_t atom = a + b;
  int64_t num_of_unit = n / atom;
  int64_t remnant = n % atom;
  int64_t remnant_blue;
  if (remnant > a) {
    remnant_blue = a;
  } else {
    remnant_blue = remnant;
  }
  cout << num_of_unit * a + remnant_blue << endl;
}


Measured memory_bytes: 256
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<map>
using namespace std;

int main(){
//srandom((unsigned long)time(NULL));

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

int ans[n];
long long min=10000000000;
for(int i=0;i<n;i++){
    min=10000000000;
    for(int j=0;j<m;j++){
        if(abs(a[i]-c[j])+abs(b[i]-d[j])<min){
            min=abs(a[i]-c[j])+abs(b[i]-d[j]);
            ans[i]=j+1;
        }
    }
}

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


return 0;
}

Measured memory_bytes: 256
'''
（gcd(A, B)を素因数分解したときの素因数の個数）+1が答え。
入力例2を考えます。
「420と660の正の公約数の中からいくつか約数を選んで、
選んだやつのどの異なる2つの整数も互いに素となる最大の約数の個数は何か？」
という問題になります。
420と660の正の公約数は、必ず最大公約数以下の値になります。
よって約数のとりうる範囲は1 ~ 最大公約数になります。
420と660 の最大公約数gcd(420, 660)は60です。
60の約数を列挙してみます。
1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
このうち、どの2つの整数も互いに素となる約数の個数が最大となる選び方は、
1, 2, 3, 5 の4つです。見やすく表にして整理すると、
60の約数	1	2	3	4	5	6	10	12	15	20	30	60
答え	     1	 2   3		 5							
たとえば15はなぜいけないのでしょうか？それは15を素因数分解すると
15=3^1∗5^1 なので、15を選ぶと3と5が選べなくなってしまいます。 
よって15を選ぶより3と5を選んだほうが多くを選べるということになります。
12や20なんかも同様の理由で選べません。
4はどうでしょうか？これは素因数分解すると4=2^2になります。
つまり4を選ぶと2を選べなくなります。この2を選ばないパターンの
1 3 4 5は、どの2つの整数も互いに素となっているのでOKです。
よって2の代わりに4を選ぶのはありですが、選ぶメリットは特にない。
素数しか選ばないというルールのほうが問題を簡単化できます。
ということで入力例2の場合では、gcd(420, 660)で最大公約数を求めて、
その最大公約数を素因数分解したときの素因数を選べば、
どの2つの整数も互いに素となります。あとついでに1も約数なので
これも加えます。これが答えになります。
制約A,B≦10^12を考えます。Nがでかすぎるので、O(N)の解法はTLEします。
この問題におけるNとは、AとBの最大公約数gcd(A, B)の値です。
1～gcd(A, B)の範囲で素因数を数えることになります。
gcd(A, B)の最大値は10^12なので、O(N)は無理です。
ですが実は、最大公約数Nが何かの整数pで割り切れるときは、
N=p∗q と書けますので、p≦√Nとなります.
（例：N=10^12 のとき、p=10^6、q=10^6 ）。
なのでNまで調べる必要はなく、O(√N)で解くことができます。
コーナーケース:最大公約数が1のとき、1を出力して終了
'''
import sys
from fractions import gcd
from collections import Counter

def prime_factorization(n):
    """nを素因数分解する
    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す
    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m + 1 if m == 2 else m + 2  
        # m=3からは、m+=2する（偶数は明らかに素数ではないので）

    if n > 1:
        d[n] += 1
    return d

def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:  # コーナーケース
        print(1)
        return

    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)

if __name__ == "__main__":
    solve()

Measured memory_bytes: 5076
import java.util.*;
public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	   int n = sc.nextInt();
	   int A[] = new int[n];
	   for(int i=0;i<n;i++){
	       A[i]=sc.nextInt();
	   }
        System.out.println(find(A,n));
    } 
    static int find(int arr[], int n) 
    { 
        // Count of triangles 
        int count = 0; 
      
        // The three loops select three 
        // different values from array 
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j < n; j++) { 
      
                // The innermost loop checks for 
                // the triangle property 
                for (int k = j + 1; k < n; k++) 
      
                    // Sum of two sides is greater 
                    // than the third 
                    if ( 
                        arr[i] + arr[j] > arr[k] 
                        && arr[i] + arr[k] > arr[j] 
                        && arr[k] + arr[j] > arr[i])
                        if(arr[i]!=arr[j]&&arr[j]!=arr[k]&&arr[k]!=arr[i])
                        count++; 
            } 
        } 
        return count; 
    } 
}


Measured memory_bytes: 36844
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef pair<int, int> P;
P z[maxn];
int sum[maxn << 2];
void pushUp(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt) {
	if (l == r) {
		sum[rt] = z[l].first;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushUp(rt);
}
int query(int L, int R, int l, int r, int rt) {
	if (L <= l && R >= r) {
		return sum[rt];
	}
	int mid = (l + r) >> 1;
	int ans = 0;
	if (L <= mid) ans += query(L, R, l, mid, rt << 1);
	if (R > mid) ans += query(L, R, mid + 1, r, rt << 1 | 1);
	return ans;
}
int main() {
	int n, k;
	char s[maxn];
	scanf("%d%d", &n, &k);
	scanf("%s", s);
	int pre, now;
	int ans = 0;
	now = pre = s[0] - '0';
	int num = 1, pos = 1;
	for (int i = 1; i < n; i++) {
		now = s[i] - '0';
		num++;
		if (now != pre) {
			z[pos].first = num - 1, z[pos++].second = pre;
			if (num - 1 > ans) ans = num - 1;
			pre = now;
			num = 1;
		}
	}
	z[pos].first = num, z[pos].second = now;
	if (num > ans) ans = num;
	int tmp, cnt = 0;
	if (k) {
		build(1, pos, 1);
		for (int i = 1; i <= pos; i++) {
			tmp = 0;
			if (z[i].second) tmp = query(i, i + k * 2, 1, pos, 1);
			else tmp = query(i, i + k * 2 - 1, 1, pos, 1);
			if (tmp > ans) ans = tmp;
			cnt = 0;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pbds tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define mod 1000000007
#define deb(x) cerr << "\n" \
                    << #x << "=" << x << "\n";
#define deb2(x, y) cerr << "\n"                   \
                        << #x << "=" << x << "\n" \
                        << #y << "=" << y << "\n";
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string a, b;
    cin >> a >> b;

    b.pop_back();
    if (a == b)
        cout << "Yes";
    else
    {
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 3652
def main():
    x, y = map(int, input().split())
    g1 = {1,3,5,7,8,10,12}
    g2 = {4,6,9,11}
    g3 = {2}
    if x in g1 and y in g1:
        return "Yes"
    if x in g2 and y in g2:
        return "Yes"
    if x in g3 and y in g3:
        return "Yes"
    return "No"

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
int main(void) {
	int n, q;
	int InputA, InputM;
	int Max = 0;
	std::cin >> n;
	std::vector<bool>AnswerBox(2001, false);
	AnswerBox[0] = true;
	for (int i = 0; i < n; ++i) {
		std::cin >> InputA;
		Max += InputA;
		for (int j = Max; j >= 0; --j) {
			if (InputA + j < 2001) {
				AnswerBox[InputA + j] = AnswerBox[j] | AnswerBox[InputA + j];
			}
		}
	}
	std::cin >> q;
	for (int i = 0; i < q; ++i) {
		std::cin >> InputM;
		std::cout << (AnswerBox[InputM] ? "yes" : "no") << "\n";
	}
	//	system("pause");
	return 0;
}

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

using namespace std;

#define MAX_N 100000
#define MAX_M 100000

struct Rail {
    int a, b, c;
    long long cnt = 0;
    int sum = 0;
} rail[MAX_N + 1];

int sche[MAX_M];

int main() {
    int n, m;
    cin >> n >> m;
    for (int  i = 0; i < m; i++) {
        cin >> sche[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> rail[i].a >> rail[i].b >> rail[i].c;
    }
    for (int i = 0; i < m - 1; i++) {
        int from = sche[i];
        int to = sche[i + 1];
        if (from > to) {
            swap(from, to);
        }
        rail[from].sum++;
        rail[to].sum--;
    }
    for (int i = 1; i < n; i++) {
        rail[i].cnt = rail[i - 1].cnt + rail[i].sum;
    }
    long long ans = 0;
    for (int i = 1; i < n; i++) {
        ans += min(rail[i].cnt * rail[i].a, rail[i].cnt * rail[i].b + rail[i].c);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6588
program main
  implicit none

  integer(8) :: n, i, j, k, l, p
  character(len=6) :: s, r

  read(*,*) n

  i = 0
     
  write(*,*) i
  read(*,*) s

  if (s == 'Vacant') then
     stop
  end if

  r = s

  j = i
  i = n / 2

  do p = 1, 19
     s = ''
     write(*,*) i
     read(*,*) s

     if(s == 'Vacant') then
        stop
     end if

     if(mod(j-i,2) == 0) then
        if(s == r) then
           l = i
           k = i + (n-i) / 2
        else
           l = i
           k = i - (i-j) / 2
           n = j
        end if

     else
        if(s /= r) then
           l = i
           k = i + (n-i) / 2
        else
           l = i
           k = i - (i-j) / 2
           n = j
        end if
     end if

     r = s
     i = k
     j = l
  end do

end program main

        
  


Measured memory_bytes: 3852
// Copyright 2019 yaito3014
#include "bits/stdc++.h"
using namespace std;
using namespace literals;

int main() {
  cin.tie(0); ios::sync_with_stdio(0);
  int a, b, x;
  cin >> a >> b >> x;
  constexpr double PI = 3.14159265358979;
  double ans = 0;
  if (x >= a * a * b / 2) {
    double V = a * a * b - x;
    double h = V * 2 / (a * a);
    ans = atan(h / a) * 180 / PI;
  }
  else {
    double h = x * 2. / b / a;
    ans = atan(b / h) * 180 / PI;
  }
  cout << fixed << setprecision(7) << ans << endl;
}


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

void BubbleSort(vector<pair<char, int>>& vec, int N) {
    rep(i, N) {
        for (int j=N-1; j>i; --j) {
            if (vec[j].second < vec[j-1].second) {
                swap(vec[j], vec[j-1]);
            }
        }
    }
}

void SelectionSort(vector<pair<char, int>>& vec, int N) {
    rep(i, N) {
        int minj = i;
        for (int j=i; j<N; ++j) {
            if (vec[j].second < vec[minj].second) minj = j;
        }
        swap(vec[i], vec[minj]);
    }
}

bool isStable(vector<pair<char, int>> input, vector<pair<char, int>> output, int N) {
    rep(i, N) {
        for(int j=i+1; j<N; ++j) {
            rep(a, N) {
                for(int b=a+1; b<N; b++) {
                    if ((input[i].second == input[j].second) && (input[i] == output[b]) && (input[j] == output[a])) return false;
                }
            }
        }
    }
    return true;
}

int main() {
    int N;
    cin >> N;
    string card;
    char mark;
    int num;
    vector<pair<char, int>> input;

    rep(i, N) {
        cin >> card;
        mark = card[0];
        num = card[1] - 48;
        input.emplace_back(mark, num);
    }

    vector<pair<char, int>> vec(N);
    vector<pair<char, int>> vec2(N);
    copy(begin(input), end(input), begin(vec));
    copy(begin(input), end(input), begin(vec2));

    BubbleSort(vec, N);
    SelectionSort(vec2, N);

    rep(i, N) {
        cout << vec[i].first << vec[i].second;
        if (i != N-1) cout << " ";
    }
    cout << endl;
    if (isStable(input, vec, N)) cout << "Stable" << endl;
    else cout << "Not stable" << endl;
    rep(i, N) {
        cout << vec2[i].first << vec2[i].second;
        if (i != N-1) cout << " ";
    }
    cout << endl;
    if (isStable(input, vec2, N)) cout << "Stable" << endl;
    else cout << "Not stable" << endl;
}



Measured memory_bytes: 3148
#include<bits/stdc++.h>
#define ull unsigned long long int 
#define pb push_back
#define F first
#define S second
#define ll long long 
#define ld long double 

#define int long long int

const int mod = 1e9+7;
const ll inf = 1e18; 
 
int power(int x,int y){int res=1;x=x%mod;while(y>0){if(y&1)res=(res*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
int ncr(int n, int r){ int C[r+1]; memset(C, 0, sizeof(C)); C[0] = 1; for(int i = 1; i <= n; i++) {int t=i;if(r<t)t=r; for (int j = t; j > 0; j--) C[j] = C[j] + C[j-1]; }return C[r];} 
int gcd(int a,int b){if (a==0)return b;return gcd(b%a,a);}
int lcm(int a,int b){return (a/gcd(a,b)*b);}

int min(int a , int b){return a < b ? a : b;}
int max(int a , int b){return a > b ? a : b;}

using namespace std;

int black[100005] = {} , white[100005] = {};

pair<int , int> solve(int x , int parent , vector<vector<int>> &adj){
	if(black[x] && white[x]){
		return {black[x] , white[x]};
	}
	
	int black_way = 1 , white_way = 1;
	for(int i : adj[x]){
		if(i != parent){
			pair<int , int> ways = solve(i , x , adj);
			int b = ways.F;
			int w = ways.S;
			
			black_way = (black_way*w)%mod;
			white_way = (white_way*((b+w)%mod))%mod;
		}
	}
	
	black[x] = black_way;
	white[x] = white_way;
	
	return {black[x] , white[x]};
}

signed main(){

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

	int n;
	cin >> n;
	vector<vector<int>> adj(n+1);
	
	for(int i = 0 ; i < n-1 ; i++){
		int x , y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	
	pair<int , int> ans = solve(1 , 0 , adj);
	
	cout << (ans.F + ans.S)%mod;
}











Measured memory_bytes: 18424
using System;

namespace ITP1_4_B
{
    class Program
    {
        static void Main(string[] args)
        {
            double r = Convert.ToDouble(Console.ReadLine());

            double s = r * r * Math.PI;
            double len = 2 * r * Math.PI;

            Console.WriteLine( s.ToString("F6") +" "+ len.ToString("F6") );

        }
    }
}

Measured memory_bytes: 5792
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();

    let mut x: Vec<usize> = Vec::with_capacity(n);
    let mut total: usize = 0;
    for _i in 0..n {
        let xi: usize = iterator.next().unwrap().parse().unwrap();
        x.push(xi);
        total += xi;
    }

    let average = ((total as f64) / (n as f64)).round() as usize;

    let mut answer: usize = 0;
    for i in 0..n {
        answer += (x[i] as i64 - average as i64).pow(2) as usize;
    }

    return format!("{}", answer);
}


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

public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        
        char[] str = in.next().toCharArray();
        int n = in.nextInt();

        for(int i = 0; i < n; i++){
            String order = in.next();
            int beginIndex = in.nextInt(), endIndex = in.nextInt();

            if(order.equals("print")){
                print(str, beginIndex, endIndex);
            }
            else if(order.equals("reverse")){
                reverse(str, beginIndex, endIndex);
            }
            else if(order.equals("replace")){
                char[] rep = in.next().toCharArray();
                replace(str, rep, beginIndex, endIndex);
            }
        }
    }

    static void print(char[] str, int beginIndex, int endIndex){
        PrintWriter out = new PrintWriter(System.out);

        for(int i = beginIndex; i <= endIndex; i++){
            out.print(str[i]);
        }
        out.println();
        out.flush();

        return;
    }

    static void replace(char[] str, char[] rep, int beginIndex, int endIndex){
        for(int i = 0; i < rep.length; i++){
            str[beginIndex + i] = rep[i];
        }

        return;
    }

    static void reverse(char[] str, int beginIndex, int endIndex){
        char[] str_rev = new char[endIndex - beginIndex + 1];

        for(int i = 0; i < str_rev.length ; i++){
            str_rev[i] = str[endIndex - i];
        }

        replace(str, str_rev, beginIndex, endIndex);

        return;
    }

    
}


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

using namespace std;

#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int a[200002];
bool mark[1000002];

int main()
{
    FAST();
    int i,j,n,ans=0;
    cin >> n;
    for(i=0;i<n;i++)cin >> a[i];
    sort(a,a+n);
    for(i=0;i<n;i++)
    {
        if(!mark[a[i]])
        {
            if(i+1 < n  &&  a[i] == a[i+1])
            {
                for(j=a[i];j<=1000000;j+=a[i])mark[j]=1;
            }
            else
            {
                ans++;
                for(j=a[i]+a[i];j<=1000000;j+=a[i])mark[j]=1;
            }
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 5380
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string.h>
#include<string>
#include<set>
#include<limits.h>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<functional>
#include<stack>
#include<deque>
#include<queue>
using namespace std;

map<int, int>m;
signed main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		m[a]++;
	}
	int ans = 0;
	for (pair<int, int>b : m) {
		if (b.first <= b.second)ans += b.second - b.first;
		else ans += b.second;
	}
	cout << ans << endl;
}

Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
vector <pair<int,int>> l;
#define k 1000000007
int main()
{
    ll i,n,sum=0,b,c,d=1;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        sum=sum+a[i];
    }
    b=(n/2);
    if(n%2==0)
    c=b*b*2;
    else
    c=2*b*(b+1);
    for(i=0;i<b;i++)
    d=(d*2)%k;
    if(d>k)
    d=d%k;
    if(sum==c)
    cout<<d;
    else
    cout<<0;

    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner

object Main extends App {

  val sc = new Scanner(System.in)

  val a, b, c = sc.next()

  if (a.charAt(a.length - 1) == b.charAt(0) && b.charAt(b.length - 1) == c.charAt(0)) {
    println("YES")
  } else {
    println("NO")
  }
}


Measured memory_bytes: 25536
import std.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;

void solve(Cond[] cs, int[][] qs) {
    //writeln("solve: ", cs, qs);
    bool match(int x, int y, int z) {
        foreach (c; cs) {
            if (c.c[0] * x + c.c[1] * y + c.c[2] * z != c.v) {
                return false;
            }
        }
        return true;
    }
    int[][] cands; // 考えられるR, C, Sの組すべて
    void prepare() {
        for (int i = 1; i <= 20; i++) {
            for (int j = 1; j <= 20; j++) {
                for (int k = 1; k <= 20; k++) {
                    if (match(i, j, k)) {
                        cands ~= [i, j, k];
                    }
                }
            }
        }
    }
    prepare;

    int[] ans;
    foreach (q; qs) {
        int[] pos;
        foreach (cand; cands) {
            pos ~= cand[0] * q[0] + cand[1] * q[1] + cand[2] * q[2];
        }
        if (pos.sort.uniq.array.length == 1) {
            ans ~= pos[0];
        } else {
            ans ~= -1;
        }
    }
    ans.map!(to!string).join(" ").writeln;
}

struct Cond {
    int[] c;
    int v;
}

void main() {
    int p, q;
    while (readf("%d %d\n", &p, &q), p || q) {
        string[] P = new string[p];
        string[] Q = new string[q];
        foreach (i; 0 .. p) 
            P[i] = readln.chomp;
        foreach (i; 0 .. q) 
            Q[i] = readln.chomp;

        int[] c = new int[3];
        Cond[] conds;
        foreach (i; 0 .. p) {
            int dots = cast(int)P[i].countUntil!(a => a != '.');
            conds ~= Cond(c.dup, dots);
            foreach (j; 0 .. P[i].length) {
                switch (P[i][j]) {
                    case '(': c[0]++; break;
                    case ')': c[0]--; break;
                    case '{': c[1]++; break;
                    case '}': c[1]--; break;
                    case '[': c[2]++; break;
                    case ']': c[2]--; break;
                    default: // DO NOTHING
                }
            }
        }

        c[] = 0;
        int[][] queries;
        foreach (i; 0 .. q) {
            queries ~= c.dup;
            foreach (j; 0 .. Q[i].length) {
                switch (Q[i][j]) {
                    case '(': c[0]++; break;
                    case ')': c[0]--; break;
                    case '{': c[1]++; break;
                    case '}': c[1]--; break;
                    case '[': c[2]++; break;
                    case ']': c[2]--; break;
                    default: // DO NOTHING
                }
            }
        }
        solve(conds, queries);
    }
}

Measured memory_bytes: 2828
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
	Scanner scan=new Scanner(System.in);
	int A=scan.nextInt();
	int B=scan.nextInt();
	int sum,sub,mul=0;
	sum=A+B;
	sub=A-B;
	mul=A*B;
	if(sum>=sub &&(sum>=mul)){
		System.out.println(sum);
	}
	else if(sub>=sum &&(sub>=mul)){
		System.out.println(sub);
	}
	else{
		System.out.println(mul);
	}
	}
}

Measured memory_bytes: 35696
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int main()
{
	ll n;
	ll a[N];
	memset(a,0,sizeof(a));
	cin>>n;
	for(ll i = 0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	ll x,y;
	int flag = 0; 
	ll  i ,j;
	for(i = n-1;i>=0;i--)
	{
		if(a[i]==a[i-1])
		{
			i--;
			x =a[i];
			for(j=i-1;j>=0;j--)
			{
				if(a[j]==a[j-1])
				{
					y = a[j];
					flag = 1;
					break;
				}
			}
			break;
		 } 
	}
	if(flag==0) cout<<"0"<<endl;
	else
	cout<<x*y<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define double long double
const int maxn=2e5+10;
const int mod=998244353;
double dis[1005];
vector<pair<int,double>>E[1005];

struct ac
{
    double x,y,r;
};
ac a[1005];




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    double sx,sy,ex,ey;
    cin>>sx>>sy>>ex>>ey;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       cin>>a[i].x>>a[i].y>>a[i].r;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            double temp=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
            temp-=a[i].r+a[j].r;
            if(temp<0)
                temp=0;
            E[i].pb({j,temp});
            E[j].pb({i,temp});
        }
    }
    double t=sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey));
    /*E[0].pb({n+1,t});
    E[n+1].pb({0,t});*/
    dis[n+1]=t;
    for(int i=1;i<=n;i++)
    {
        double temp=sqrt((sx-a[i].x)*(sx-a[i].x)+(sy-a[i].y)*(sy-a[i].y));
        double temp2=sqrt((ex-a[i].x)*(ex-a[i].x)+(ey-a[i].y)*(ey-a[i].y));
        temp-=a[i].r;
        temp2-=a[i].r;
        if(temp<0)
            temp=0;
        if(temp2<0)
            temp2=0;
        E[i].pb({0,temp});
        E[0].pb({i,temp});
        E[n+1].pb({i,temp2});
        E[i].pb({n+1,temp2});

    }
    priority_queue<pair<double,int>>q;
    for(int i=1;i<=n;i++)
    {
        dis[i]=1e10;
    }
    dis[0]=0;
    q.push({0,0});
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        //cout<<"here"<<'\n';
        for(auto &v:E[u])
        {
            if(dis[v.first]>dis[u]+v.second)
            {
                dis[v.first]=dis[u]+v.second;
                q.push({-dis[v.first],v.first});
            }
        }
    }
    cout<<fixed<<setprecision(10)<<dis[n+1]<<'\n';



}


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

def main():
    A, V = map(int, input().split())
    B, W = map(int, input().split())
    T =int(input())
    AB = abs(A-B)
    if V < W:
        ans='NO'
    elif AB <= (V-W)*T:
        ans='YES'
    else:
        ans='NO'
    print(ans)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 9176
import java.util.*;
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner stdIn = new Scanner(System.in);
		while(stdIn.hasNext())
		{
			double a = stdIn.nextDouble();
			double l = stdIn.nextDouble();
			double x = stdIn.nextDouble();
			double s1 = a / 4 * Math.sqrt((a + 2 * l) * (2 * l - a));
			double maxS2 = 0;
			for(double i = 0.00001; i < 1.0; i += 0.00001)
			{
				double len1 = i * (l + x);
				double len2 = (1.0 - i) * (l + x);
				double s = (l + len1 + len2) / 2.0;
				if(s * (s - l) * (s - len1) * (s - len2) < 0)
				{
					continue;
				}
				else
				{
					double s2 = Math.sqrt(s * (s - l) * (s - len1) * (s - len2));
					if(maxS2 < s2)
					{
						maxS2 = s2;
					}
				}
			}
			System.out.printf("%6f\n", s1 + 2 * maxS2);
		}
	}
}

Measured memory_bytes: 13000
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String s= sc.next();
		
		if(a>=3200) {
			System.out.println(s);
		}else {
			System.out.println("red");
		}
	}
}



Measured memory_bytes: 21332
package main

import (
	"fmt"
)

const (
	MaxN = 101
	MaxW = 100001
)

func main() {
	var N, W int
	fmt.Scan(&N, &W)

	w := make([]int, N)
	v := make([]int, N)

	for i := 0; i < N; i++ {
		fmt.Scan(&w[i], &v[i])
	}

	// dp[i][j]はi番目以降の品物から
	// 重さの和がj以下になるように選んだときの価値の和の最大値を表す
	var dp [MaxN][MaxW]int
	for i := 1; i < len(dp); i++ {
		dp[N][i] = 0
	}
	for i := N - 1; i >= 0; i-- {
		for j := 0; j <= W; j++ {
			// 容量が足りないため、i番目の品物を入れることができない
			if j < w[i] {
				dp[i][j] = dp[i+1][j]
			} else {
				// i番目の品物を入れるか入れないかで最大の方を選択
				dp[i][j] = maxInt(dp[i+1][j-w[i]]+v[i], dp[i+1][j])
			}
		}
	}
	fmt.Println(dp[0][W])
}

func maxInt(x, y int) int {
	if x > y {
		return x
	}
	return y
}


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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        boolean all=true;
        long sum =0;
        int min=(int)1e9;
        for (int i =0;i<n;i++){
            int a= sc.nextInt();
            int b = sc.nextInt();
            all&=a==b ;
            sum+=a;
            if (a>b)min=Math.min(min,b);
        }
        pw.println(all?0:sum-min);
        pw.close();

    }
    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public int[] nextIntArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(next());
            }
            return arr;
        }

    }

}


Measured memory_bytes: 41472
N, Q = map(int, input().split())
C = [int(i) for i in input().split()]

pi = [-1]*(N+1)
ps = [[] for _ in range(N+1)]
for i in range(N):
    l = pi[C[i]]
    if l != -1:
        ps[l].append(i)
    pi[C[i]] = i

qs = [[] for _ in range(N+1)]
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r, i))


bit = [0]*(N+1)


def bit_sum(idx):
    res_sum = 0
    while idx > 0:
        res_sum += bit[idx]
        idx -= idx & (-idx)
    return res_sum


def bit_add(idx, x):
    while idx <= N:
        bit[idx] += x
        idx += idx & (-idx)
    return True


ans = [0]*Q
for x in range(N-1, -1, -1):
    for y in ps[x]:
        bit_add(y, 1)
    for r, i in qs[x]:
        ans[i] = r-x+1-bit_sum(r)


for i in range(Q):
    print(ans[i])


Measured memory_bytes: 224384
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def main():
    N, M = map(int, input().split())
    m = defaultdict(list)
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        m[L].append((R, D))
        m[R].append((L, -D))

    x = [None] * N
    for k in range(N):
        if x[k] is not None:
            continue

        x[k] = 0
        que = deque()
        que.append(k)
        while len(que) != 0:
            i = que.popleft()

            for j, d in m[i]:
                if x[j] is None:
                    x[j] = x[i] + d
                    que.append(j)
                else:
                    if x[j] != x[i] + d:
                        print(No)
                        return

    print(Yes)


if __name__ == '__main__':
    main()


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

#include <utility>
using namespace std;

#define REP(i, n) for ( int i = 0; i < (n); i++ )
const int INF = 1e9;
using Pii = pair<int, int>;

const int con_type = 26;
int D = 365;
int C[con_type];
int S[365][con_type];
vector<int> ans;
int last[con_type];

struct State {
  int cost;
  vector<int> ans;
  vector<int> last;

  State() {
    cost = 0;
    last = vector<int>(26, -1);
  }

  State(int cost, vector<int> ans, vector<int> last):
    cost(cost), ans(ans), last(last) {};

  bool operator<( const State& s ) const {
    return cost < s.cost;
  }

  bool operator>( const State& s ) const {
    return cost > s.cost;
  }
};

void solve() {
  priority_queue<State> Q;
  Q.push(State());
  REP(d, D) {
    priority_queue<State> nQ;
    while ( !Q.empty() ) {
      State now = Q.top(); Q.pop();
      vector<Pii> add_cost;
      int sum = 0;
      int type_cost[26];
      REP(i, con_type) {
        sum += (d-now.last[i])*C[i];
        type_cost[i] = (d-now.last[i])*C[i];
      }
      REP(i, con_type) {
        add_cost.emplace_back(Pii(S[d][i]+(d-now.last[i])*C[i]-sum, i));
      }
      sort(add_cost.begin(), add_cost.end(), greater<Pii>());
      REP(i, 10) {
        int id = add_cost[i].second;
        State next = now;
        next.cost += S[d][id];
        next.cost -= sum;
        next.cost += type_cost[id];
        next.ans.emplace_back(id);
        next.last[id] = d;
        nQ.push(next);
      }
    }
    Q = priority_queue<State>();
    REP(i, min(1000, (int)nQ.size())) {
      Q.push(nQ.top()); nQ.pop();
    }
  }

  ans = Q.top().ans;
}

void input() {
  cin >> D;
  REP(i, con_type) {
    cin >> C[i];
    last[i] = -1;
  }
  REP(i, D) REP(j, con_type) cin >> S[i][j];
}

void output() {
  REP(i, D) cout << ans[i]+1 << endl;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  input();
  solve();
  output();

  return 0;
}


Measured memory_bytes: 20932
#include <stdio.h>

int main(void)
{
	int b1,b2,b3;
	scanf("%d %d %d",&b1,&b2,&b3);
	if(b1==1){
		if(b2==1)
			printf("Open\n");
		else
			printf("Close\n");
	}
	else{
		if(b2==1)
			printf("Close\n");
		else{
			if(b3==1)
				printf("Open\n");
			else
				printf("Close\n");
		}
	}
	return 0;
}


Measured memory_bytes: 2120
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,k=mp()
a=lmp()
l=[]
i=0
ch=[0]*(n+1)
while True:
    if ch[i]==1:
        break
    else:
        ch[i]=1
        l.append(a[i])
        i=a[i]-1


x=l.index(a[i])
y=len(l)-x

if k<=x:
    print(l[k-1])
else:
    print(l[(k-x-1)%y+x])



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

using namespace std;

using ll = long long;

int main()
{
    int N, X, Y;
    cin >> N >> X >> Y;

    vector<ll> d(N);

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int n = min(j - i, abs(Y - 1 - j) + abs(X - 1 - i) + 1);
            d[n]++;
        }
    }

    for (int i = 1; i < d.size(); i++) {
        cout << d[i] << endl;
    }
}


Measured memory_bytes: 256
st=[]

while True:
  try:
    n=input()
    if n=="":
      break
    st += n.lower()
  except:
    break
   
char = "abcdefghijklmnopqrstuvwxyz"
for i in range(len(char)):
  print(char[i],":",st.count(char[i]))    


Measured memory_bytes: 5572
H, W, M = map(int, input().split())
boms = []
h, w = [0] * (H + 1), [0] * (W + 1)
for _ in range(M):
    h_, w_ = map(int, input().split())
    boms.append([h_, w_])
    h[h_] += 1
    w[w_] += 1

hmax = max(h)
wmax = max(w)

cnt = h.count(hmax) * w.count(wmax)
for hh, ww in boms:
    if hmax == h[hh] and wmax == w[ww]:
        cnt -= 1

print(hmax + wmax - (cnt == 0))


Measured memory_bytes: 126304
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

#define int long long
int N;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  for (int a=1; a<=3500; a++) {
    for (int b=1; b<=3500; b++) {
      long long A = a+b, B = a*b;
      long long p = 1LL*B*N, q = 4LL*B - 1LL*A*N;
      if (q > 0 && p >= q && p % q == 0) {
        long long x = p/q;
        cout << a << " " << b << " " << x << "\n";
        return 0;
      }
    }
  }
  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++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

template <typename T>
void printlnVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << endl;
  }
}

template <typename T>
void printVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << " ";
  }
  cout << endl;
}

int main()
{
  vector<int> count(4);
  rep(i, 3)
  {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    count[a]++;
    count[b]++;
  }

  rep(i, 4)
  {
    if (count[i] > 2)
    {
      cout << "NO" << endl;
      return 0;
    }
  }

  cout << "YES" << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main()
{
    int D, G;
    cin >> D >> G;
    vector<int> P(D+1), C(D+1);
    for (int i = 1; i <= D; i++) cin >> P[i] >> C[i];
    
    int best = INT_MAX;
    for (int bit = 0; bit < 1<<D; bit++) {
        int score = 0, count = 0, m = 0;
        for (int j = 1; j <= D; j++) {
            if (bit & (1 << (j-1))) {
                score += j * 100 * P[j] + C[j];
                count += P[j];
            } else if (P[j] > 1) {
                m = max(m, j);
            }
        }
        if (score >= G) {
            best = min(count, best);
        } else if (score + m * 100 * (P[m]-1) >= G) {
            count += (G - score + m * 100 - 1) / (m * 100);
            best = min(count, best);
        }
    }
    cout << best << endl;
    return 0;
}


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

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int maxn = 2000;

int n, x;
int a[maxn + 5], b[maxn + 5];

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	LL ans = LLONG_MAX;
	scanf("%d%d", &n, &x);
	REP(i, 0, n) scanf("%d", a + i);
	memset(b, oo, sizeof b);
	REP(i, 0, n)
	{
		REP(j, 0, n) chkmin(b[j], a[(j + i) % n]);
		LL tmp = (LL)i * x;
		REP(j, 0, n) tmp += b[j];
		chkmin(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256