akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int a,b,c; cin>>a>>b>>c;
    if(a+b==c||b+c==a||c+a==b)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
from sys import stdin


def main():
    h, w = map(int, input().split())
    a = [next_str() for _ in range(h)]

    ans = []
    for i in range(h + 2):
        ans += ["#"]
        if i == 0 or i == h + 1:
            ans[i] += "#" * w
        else:
            ans[i] += a[i - 1]
        ans[i] += "#"

    print("\n".join(ans))


def next_int() -> int:
    return int(next_str())


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
typedef long long llong;

int main(){
    llong N, A, B;
    cin >> N >> A >> B;
    llong res = N % (A + B);
    llong num = N / (A + B);
    llong ans;
    if(A < res) ans = A;
    else ans = res;
    ans += A * num;
    cout << ans << endl; 
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<pair<pair<int, int>, int>> v;
    vector<int> used(2 * n, 0);
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        
        v.push_back({{x, y}, 1});
    }
    
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        
        v.push_back({{x, y}, 2});
    }
    
    sort(v.begin(), v.end());
    int ans = 0;
    for (int f = 0; f < 2 * n; ++f) {
        for (int i = 0; i < 2 * n; ++i) {
            if (v[i].first.second == f && v[i].second == 2) {
                for (int j = i - 1; j >= 0; --j) {
                    if (v[j].first.second < f && v[j].second == 1 && used[j] == 0) {
                        used[j] = 1;
                        ans++;
                        break;
                    }
                }
                break;
            }
        }
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

char S[101010];

bool hoge(int a, int x)
{
	return a == x || a == x + 1;
}

bool test(int a, int b, int c)
{
	int mn = min(a, min(b, c));
	return hoge(a, mn) && hoge(b, mn) && hoge(c, mn);
}

int main()
{
	scanf("%s", S);
	int a = 0, b = 0, c = 0;
	for (int i = 0; S[i]; ++i) {
		if (S[i] == 'a') ++a;
		else if (S[i] == 'b') ++b;
		else ++c;
	}
	puts(test(a, b, c) ? "YES" : "NO");

	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};

int main() {
    int a, b; cin >> a >> b;
    vector<int> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(a - 1);
    v.push_back(b - 1);
    sort(v.begin(), v.end());
    cout << v[3] + v[2] << endl;
}
    


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
E = []
for i in range(M):
    L, R, C = map(int, input().split())
    E.append([L-1, R-1, C])

E = sorted(E, key=lambda X: X[1])

# N_はN以上の2べき数
N_ = 2**(len(bin(N))-2)
INF = 10**15 # 10**10 
seg = [INF] * (2*N_-1)

# k番目(0index)をaに更新
def update(k, a):
    k += N_-1
    seg[k] = a

    while k > 0:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1], seg[k*2+2])

# 開区間！！！[a, b)の最小値を求める
def query(a, b, k, l, r):
    if r <= a or b <= l:
        return INF
    if a <= l and r <= b:
        return seg[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return min(vl, vr)



# 初期化
update(0, 0)

for i in range(M):
    new = query(E[i][0], E[i][1], 0, 0, N_) + E[i][2]
    if new < seg[E[i][1] + N_-1]:
        update(E[i][1], new)

if seg[N-1+N_-1] == INF:
    print(-1)
else:
    print(seg[N-1+N_-1])

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

int main(){
   int N;
   std::cin >> N;
   std::vector<std::vector<int>> A(2, std::vector<int> (N));
   for (int i=0; i<2; i++){
      for (int j=0; j<N; j++){
         std::cin >> A.at(i).at(j);
      }
   }
   int max = 0;
   for (int i=0; i<N; i++){
      int sum0 = 0;
      int sum1 = 0;
      for (int j=i; j<N; j++){
         sum1 = sum1 + A.at(1).at(j);
      }
      for (int j=0; j<=i; j++){
         sum0 = sum0 + A.at(0).at(j);
      }
      if (sum0 + sum1 > max){
         max = sum0 + sum1;
      }
   }
   std::cout << max << std::endl;

}



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
const int INF = 1000000007;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    int N, X;
    cin >> N >> X;
    vector<int> A(N+1, 0);
    for(int i = 1; i <= N; i++) cin >> A[i];
    
    ll ans = 0;
    rep(i, N){
        int a = A[i] + A[i + 1];
        if(a > X){
            ans += a - X;
            A[i + 1] -= a - X;
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
  while(1){
    int ans=0;
    vector<int>vec[109];
    int n;
    int h[109];
    int a[109];
    cin>>n;
    if(n==0)break;
    n++;
    for(int i=0;i<n;i++){
      cin>>h[i];
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(i!=j)vec[i].push_back(h[j]);
      }
      /*for(int j=0;j<n-1;j++){
	cout<<vec[i][j]<<' ';
	}*/
      //cout<<endl;
    }
    for(int i=0;i<n;i++){
      int cnt=0;
      for(int j=0;j<n-3;j++){
	if(vec[i][j+1]-vec[i][j]!=vec[i][j+2]-vec[i][j+1])cnt++;
      }
      if(cnt==0)ans=h[i];
    }
    cout<<ans<<endl;
  }
  return(0);
}




Measured memory_bytes: 3164
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        //var n = int.Parse(Console.ReadLine());
        long[] np = Console.ReadLine().Split().Select(long.Parse).ToArray();
        var n = np[0];
        var p = np[1];
        long ans = 1;

        var dic = prime_factorize(p);
        foreach (var item in dic)
        {
            for (int j = 0; j < item.Value / n; j++)
            {
                ans *= item.Key;
            }
        }


        // 出力
        Console.WriteLine(ans);
    }


    //素因数分解(ペア作成)
    public static Dictionary<long, long> prime_factorize(long n)
    {
        var res = new Dictionary<long, long>();
        for (long p = 2; p * p <= n; p++)
        {
            if (n % p != 0) continue;
            long num = 0;
            while (n % p == 0)
            {
                num++;
                n /= p;
            }
            res.Add(p, num);
        }
        if (n != 1) res.Add(n, 1);
        return res;
    }
}

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

int main(){
  int n;  cin >> n;
  vector<int> p(n), q(n), a(n);
  for(int i=0; i<n; i++)  cin >> p[i];
  for(int i=0; i<n; i++){
    cin >> q[i];
    a[i] = i + 1;
  }
    
  map<vector<int>, int> mp;
  do{
    mp[a] = mp.size();
  }while(next_permutation(a.begin(), a.end()));
  
  cout << abs(mp[p] - mp[q]) << endl;

  return 0;
}
  


Measured memory_bytes: 8600
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,ans=0;string S,T;cin>>N>>S>>T;
  for(int i=N-1;i>=0;i--){
    if(S.substr(N-i-1)==T.substr(0,i+1)){
      ans=N*2-i-1;
      break;
    }
  }
  if(ans==0)ans=2*N;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys

A, B = map(int, input().split())
if B == 1:
	print(0)
	sys.exit()

cond = True
tmp = 0
cnt = 0
while cond:
	cnt += 1
	tmp += A
	if tmp >= B:
		cond = False
	else:
		tmp -= 1
print(cnt)

Measured memory_bytes: 3060
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));
		String str = br.readLine();
		String strArray[] = str.split(" ");
		int a = Integer.parseInt(strArray[0]);
		int b = Integer.parseInt(strArray[1]);
		int c = Integer.parseInt(strArray[2]);
		int count = 0;
		int i =a;
		while(i<=b){
			if(c%i==0){
				count +=1;
			}else{}
			i += 1;
			}
		System.out.println(count);
	}
}

Measured memory_bytes: 24268
S = input()
count = 0


def calculate(isPlus):
    #print(isPlus)
    ans = 0
    start = 0
    for i in range(len(isPlus)):
        if isPlus[i]:
            #print('i=', i, 'ans+=', S[start:i+1])
            ans += int(S[start:i+1])
            start = i+1
        if i == len(isPlus)-1:
            #print('i=', i, 'ans+=', S[start:])
            ans += int(S[start:])

    return ans


def recursion(depth, isPlus):
    global count
    if depth == len(S)-1:
        count += calculate(isPlus)
    else:
        recursion(depth=depth+1, isPlus=isPlus+[False])
        recursion(depth=depth+1, isPlus=isPlus+[True])


if len(S) == 1:
    print(S)
else:
    recursion(depth=0, isPlus=[])
    print(count)


Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

int main() {
        string s;
        cin >> s;
        int ans = 0;
        for (int i = 0; i < s.size(); i ++) {
                ans += s[i] == '1';
        }
        printf("%d\n", ans);
        return 0;
}



Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#include <bits/stdc++.h>
//~ #include <atcoder/all>
using namespace std;
using ll = long long;
//~ using P = pair<int, int>;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
//~ int A = (1<<2) | (1<<3) | (1<<5) | (1<<7);
//~ for (int bit=A; ; bit=(bit-1)&A){
//~ if (!bit) break;
//~ }
int next_combination(int sub)
{
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}
//~ int n=5;
//~ int k=3; // nCkの組み合わせ、ただしk=0には対応してない
//~ int bit=(1<<k)-1; // 1000 -> 0111
//~ for(; bit < (1<<n); bit=nex_combination(bit){
//~ }
bool isPrime(int a)
{
    if (a == 2)
        return true;
    if (a <= 1 || a % 2 == 0)
        return false;

    for (int i = 3; i * i <= a; i += 2)
    {
        if (a % i == 0)
            return false;
    }
    return true;
}
//~ vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};
vector<int> aaa;
// index が条件を満たすかどうか
bool isOK(int index, int key)
{
    if (aaa[index] >= key)
        return true;
    else
        return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key)
{
    int ng = -1;              //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok = (int)aaa.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1)
    {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}

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

//~ int v[100100];
//~ int INF = 1 << 30;
//~ vector<vector<int>> dp(310, vector<int>(310));
//~ ll dp[110][100100];
//~ vector<int> dp(100100, 0));

//~ int seen[110];
//~ int ans[110][2];
//~ ll MOD = 1e9 + 7;

vector<vector<int>> v =
    {
        {0, 1, 2},
        {3, 4, 5},
        {6, 7, 8},
        {0, 3, 6},
        {1, 4, 7},
        {2, 5, 8},
        {0, 4, 8},
        {2, 4, 6}};

int main()
{
    int a[9];
    rep(i, 9) cin >> a[i];

    int n;
    cin >> n;

    bool exist[9];
    rep(i, 9) exist[i] = false;

    while (n--)
    {
        int b;
        cin >> b;
        rep(i, 9) if (a[i] == b) exist[i] = true;
    }

    for (auto r : v)
    {
        bool yn = true;
        for (auto e : r)
        {
            if (exist[e] == false)
                yn = false;
        }
        if (yn == true)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}


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

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

  if (n % 2 == 0) {
    cout << 0.5 << endl;
  } else {
    double a = (n/2) + 1;
    cout << a / n << endl;
  }

}

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

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7



//メイン関数
int main()
{
	ll N;
	cin >> N;
	vector<ld> p(N);
	REP(i, N)cin >> p[i];

	vector<vector<ld>> dp(N + 1, vector<ld>(N + 1, 0));
	dp[0][0] = 1;
	// i 枚投げて、j枚が表だとする
	REP(i, N)REP(j, i + 1)
	{
		// 表が出る場合
		dp[i + 1][j + 1] += p[i] * dp[i][j];
		// 裏
		dp[i + 1][j] += (1 - p[i])*dp[i][j];
	}
	ld res = 0;
	REP(i, N + 1)
	{
		if(i <= N - i)continue;
		res += dp.back()[i];
	}
	cout << fixed << setprecision(12) << res << endl;
	cin >> N;
	return 0;
}


Measured memory_bytes: 141056
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
	int n, m;
	while(scanf("%d %d", &m, &n) != EOF) {
		if(n == 0 && m == 0) break;
		const int Max = 7368791+10;
		// set<int> st;
		// REP(i, m , Max) st.insert(i);
		// rep(i, n) {
		// 	int t = *st.begin();
		// 	for(int j = t; j < Max; j += t) {
		// 		if(st.count(j)) st.erase(j);
		// 	}
		// }
		// cout << *st.begin() << endl;
		vi v(Max, 0);
		int cnt = 0;
		REP(i, m, Max) {
			if(v[i]) continue;
			if(cnt == n) {
				printf("%d\n", i);
				break;
			}
			cnt++;
			for(int j = i; j < Max; j += i) v[j] = 1;
		}
	}	
}

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

using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vp vector<pair<int, int>>
#define vll vector<long long>
#define inf 1000000100
#define infll 1LL << 50

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a/g * b; //prevent overflow
}

/////////////////////////  END OF TEMPLATE /////////////////////////////////////////

vp adj[100001];

bool visited[100001];
vll dist(100001);
void dfs(int k)
{
    visited[k] = 1;
    for(auto u : adj[k])
    {
        if(!visited[u.first])
        {
            dist[u.first] = dist[k] + u.second;
            dfs(u.first);
        }

    }

}


int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n-1; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }

    int q, k;
    cin >> q >> k;
    dfs(k);
    while(q--)
    {
        int x, y;
        cin >> x >> y;
        cout << dist[x] + dist[y] << endl;
    }
}

Measured memory_bytes: 11264
n,m=map(int, input().split())
# 好きな種類の全食べ物の番号を含む配列Sを作成する
S=set(range(1, m+1))
# Forループを作成する
for i in range(n):
    # Kと、Aをアンパックしながら配列へ入力する
    K,*A=map(int,input().split())
    # Aリストの中から重複を取り除き、SとのANDをとる　
    S&=set(A)
# 最終的の残ったリスト2つどうしでANDをとる
print(len(S))

Measured memory_bytes: 38512
N, M = map(int, input().split())
L = []
R = []
LR_and = []
sum_list = []

for i in range(M):
    LR = input().split()
    L.append(int(LR[0]))
    R.append(int(LR[1]))

max_L = max(L)
min_R = min(R)

if max_L <= min_R:
    print(min_R - max_L + 1)
else:
    print(0)

Measured memory_bytes: 10996
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

#define MOD 1000000007;//1e9+7

int counter(int x) {
    if (x == 0)return 0;
    return counter(x >> 1) + (x & 1);
}

int main() {
    int N;
    cin >> N;
    vector<int>A(N + 1);
    vector<vector<int>>x(N + 1, vector<int>(N + 1));
    vector<vector<int>>y(N + 1, vector<int>(N + 1));

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        for (int j = 1; j <= A[i]; j++) {
            cin >> x[i][j] >> y[i][j];
        }
    }

    int ans = 0;
    for (int bit = 0; bit < (1<<N); bit++){
        bool ok = true;
        for (int i = 1; i <= N; i++){
            if (!(bit&(1 << (i - 1))))continue;
            for (int j = 1; j <= A[i]; j++) {
                if ((((bit >> (x[i][j]) - 1)) & 1) ^ y[i][j])ok = false;
            }
        }
        if (ok)ans = max(ans, counter(bit));
    }

    cout << ans;
}

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

int main(){
  int N;
  cin >> N;
  vector<double> A(N);
  double sum_A = 0;
  
  for(int i=0;i<N;i++){
    cin >> A.at(i);
    A.at(i) = 1/A.at(i);
    sum_A += A.at(i);
  }
  
  cout << 1/sum_A << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> P;
typedef pair<ll,ll> PLL;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//dpTable
int dp[100050];

int main(){
    int N;
    cin >> N;
    ll ans = 0;
    vector<int> A(N);
    rep (i,N) cin >> A.at(i);
    vector<int> cnt(100050,0);
    rep (i,N) {
        cnt.at(A.at(i))++;
        ans += A.at(i);
    }
    int Q;
    cin >> Q;
    vector<int> B(Q);
    vector<int> C(Q);
    rep (i,Q) {
        cin >> B.at(i) >> C.at(i);
        ans += (C.at(i) - B.at(i)) * cnt.at(B.at(i));
        cout << ans << endl;
        cnt.at(C.at(i)) += cnt.at(B.at(i));
        cnt.at(B.at(i)) = 0;
    }
    return 0;
}

Measured memory_bytes: 4848
from math import factorial

ball, blue_ball = map(int, input().split())
red_ball = ball - blue_ball
# i個所の青い領域を作る作り方。
# a:朱い領域はi-1個所、i個所、i+1個所作れる
# i個の正の数の振り分けが問題になる。つまり、Σα_k=K, 0<=k<i,a_k>0となるような数列a_kの通りが分かれば、あとはそれのかけ算三種類とかでなんとかなる.
divisor = 10**9+7
nCr = {}

def cmb(n,r):
    if(n < 0 or r < 0 or n < r):
        return 0
    if ((n,r) not in nCr):
        nCr[(n,r)] = factorial(n) // factorial(r) // factorial(n - r)
    return nCr[(n,r)]
for i in range(1, blue_ball+1):
    if(red_ball == 0 and i == 1):
        print(1)
        continue
    # 青=i領域、赤=i-1領域、i領域、i+1領域
    blue = cmb(blue_ball - 1, blue_ball - i)
    red_i_m = cmb(red_ball - 1,red_ball - (i-1)) % divisor
    red_i = cmb(red_ball - 1, red_ball -i) % divisor
    red_i_p = cmb(red_ball - 1, red_ball - (i+1)) % divisor
    print((blue * (red_i_m + red_i*2 + red_i_p)) % divisor)

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

#define Rep(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) Rep(i, 0, n)

template<class T> T read() {
	T t;
	cin >> t;
	return t;
}

int main(){
	int a[6];
	rep(i, 6) cin >> a[i];
	int b[6]={1,5,10,50,100,500};
	int sum = 0;
	rep(i,6) sum+=a[i]*b[i];
	if(sum>=1000) cout << 1 << endl;
	else          cout << 0 << endl;
}

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

int main(){
    int N;
    cin >> N;
    // x, y, 色(赤が0で青が1)
    vector<tuple<int, int, int>> pts;
    for(int c=0; c<2; c++) for(int i=0; i<N; i++){
        int x, y;
        cin >> x >> y;
        pts.emplace_back(x, y, c);
    }
    // x座標でソート
    sort(pts.begin(), pts.end());

    // Y[b]：ペア待ち点のy座標の集合にbが含まれているかどうか
    vector<bool> Y(2*N);
    int ans = 0;
    for(auto& [x, y, c] : pts){
        if(c == 0){
            Y[y] = 1;
        }else{
            for(int i=y-1; i>=0; i--) if(Y[i]){
                Y[i] = 0;
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define COUT(x) cout << #x << " = " << (x) << ", "
typedef long long ll;
using namespace std;
static const ll MOD = 1000000007;

int main(){
  int A,B,C;
  cin >> A >> B >> C;
  cout << C << " " << A << " " << B << endl;
}


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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b,c; cin>>a>>b>>c;
	cout << ((a+b>=c) ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String[] scores = new String[3];
        for (int i = 0; i < 3; i++) {
            scores[i] = sc.next();
        }
        Arrays.sort(scores, Comparator.reverseOrder());
        String big = scores[0] + scores[1];
        String small = scores[2];
        System.out.println(Integer.parseInt(big) + Integer.parseInt(small));
    }
}


Measured memory_bytes: 23892
#include <stdio.h>
struct cards {
  char suit;
  int  value;
};

void int_swap(int *, int *);
void char_swap(char *, char *);

int main() {
  int i,j,n,min;
  int stable = 1;

  scanf("%d", &n);

  struct cards card[n], bubble[n], selection[n];

  for (i = 0; i < n; i++) {
    scanf(" %c%d", &card[i].suit, &card[i].value);

    bubble[i].suit     = card[i].suit;
    bubble[i].value    = card[i].value;
    selection[i].suit  = card[i].suit;
    selection[i].value = card[i].value;
  }

  for (i = 0; i < n; i++){ 
    for (j = n - 1; j > i; j--){ 
      if (bubble[j].value < bubble[j - 1].value) {
	char_swap(&bubble[j].suit, &bubble[j - 1].suit);
	int_swap(&bubble[j].value, &bubble[j - 1].value);
      }
    }
  }
  

  for (i = 0; i < n; i++) {
    min = i;
    for (j = i; j < n; j++) 
      if (selection[j].value < selection[min].value) 
	min = j;
    if (min != i) {
      char_swap(&selection[i].suit, &selection[min].suit);
      int_swap(&selection[i].value, &selection[min].value);
    }
  }

  for (i = 0; i < n; i++) {
    if (bubble[i].suit != selection[i].suit) {
      stable = 0;
      break;
    }
  }

  for (i = 0; i < n - 1; i++) 
    printf("%c%d ", bubble[i].suit, bubble[i].value);
  printf("%c%d\n", bubble[n - 1].suit, bubble[n - 1].value);
  printf("Stable\n");
  for (i = 0; i < n - 1; i++) 
    printf("%c%d ", selection[i].suit, selection[i].value);
  printf("%c%d\n", selection[n - 1].suit, selection[n - 1].value);
  if (stable == 1) 
    printf("Stable\n");
  else 
    printf("Not stable\n");
  return 0;
}

void 
int_swap(int *x, int *y) {
  int tmp;
  tmp = *x;
  *x  = *y;
  *y  = tmp;
}

void char_swap(char *x, char *y) {
  char tmp;
  tmp = *x;
  *x  = *y;
  *y  = tmp;
}



Measured memory_bytes: 2048
/*
RAone00
Rohit sharma
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef vector < vector < ll > > matrix;
typedef vector < ll > vll;

#define pb push_back
#define debug(x) cout << (#x) << " is " << (x) << endl
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX;
const ll N = 1e5 + 10;

int main() {
    fast_io();
    int a, b;
    cin >> a >> b;
    int as = 1, cnt = 0;
    while (as < b) {
        cnt++;
        as--;
        as += a;
    }
    cout << cnt << "\n";
    return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sn = new Scanner(System.in);
		
		Integer N = Integer.parseInt(sn.nextLine());
		String[] PsStr = sn.nextLine().split(" ");
		Integer[] Ps = conv(PsStr, N);
		Integer[] sorted = Arrays.copyOf(Ps, N);
		Arrays.sort(sorted);
		
		if (comp(Ps, sorted) == 0) {
			System.out.println("YES");
			return;
		}
		
		int srcIndex = -1;
		int toIndex = -1;
		for (int i = 0; i < Ps.length; i++) {
			if (Ps[i].equals(sorted[i])) {
				continue;
			}
			srcIndex = i;
			toIndex = getToIndex(Ps[i], sorted);
			break;
		}
		
		int src = Ps[toIndex];
		int to = Ps[srcIndex];
		
		Ps[srcIndex] = src;
		Ps[toIndex] = to;
		
		System.out.println((comp(Ps, sorted) == 0 ? "YES" : "NO"));
	}
	
	private static Integer[] conv(String[] PsStr, int N) {
		Integer[] Ps = new Integer[N];
		for (int i = 0; i < PsStr.length; i++) {
			Ps[i] = Integer.parseInt(PsStr[i]);
		}
		return Ps;
	}
	private static int comp(Integer[] Ps, Integer[] sorted) {
		for (int i = 0; i < Ps.length; i++) {
			if (Ps[i] != sorted[i]) {
				return -1;
			}
		}
		return 0;
	}
	
	private static int getToIndex(Integer p, Integer[] sorted) {
		for (int i = 0; i < sorted.length; i++) {
			if (sorted[i] == p) {
				return i;
			}
		}
		return -1;
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) int((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;
typedef vector<int> V;
typedef vector<vector<int>> VV;
typedef pair<int, int> P;
typedef map<string, int> M;
typedef unordered_map<int, int> HM;
typedef set<int> S;
typedef queue<int> Q;

ll modpow(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    if (p % 2 == 0)
    {
        ll half = modpow(a, p / 2);
        return half * half;
    }
    else
    {
        return a * modpow(a, p - 1);
    }
}

ll ans = 0;
void solve(ll n, ll x){
    ll a = modpow(2, n+1) - 3;
    ll p = modpow(2, n) - 1;
    if(n == 0){
        ans++;
        return;
    }
    if(x <= 1){
        return;
    }
    else if(x <= a+1) solve(n-1, x-1);
    else if(x == a+2){
        ans += p+1;
        return;
    } 
    else if(x <= a*2+2){
        ans += p+1;
        solve(n-1, x-a-2);
    }
    else if(x == a*2+3){
        ans += p*2 +1;
        return;
    }
    return;
}

int main(){
    ll n,x; cin>>n>>x;
    solve(n, x);
    OUT(ans);
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, a, b, c, d = li()
a -= 1
b -= 1
s = ns()

no2_ac = not "##" in s[a:c]
no2_bd = not "##" in s[b:d]
yes3_bd = "..." in s[b-1:d+1]

if c < d:
    print("Yes" if no2_ac and no2_bd else "No")

else:
    print("Yes" if no2_ac and no2_bd and yes3_bd else "No")

Measured memory_bytes: 3572
#include<stdio.h>
#include<string.h>

int lcs(char *,char *);
int max(int, int);

int main()
{
  int i;
  int q, length;
  char x[1000], y[1000];

  scanf("%d", &q);
  for(i = 0; i < q; i++)
    {
      scanf("%s", x);
      scanf("%s", y);

      length = lcs(x, y);

      printf("%d\n" ,length);
    }

  return 0;
}

int lcs(char *x, char *y)
{
  int i, j, xlen, ylen, maxl = 0;
  int c[1001][1001];

  xlen = strlen(x);
  ylen = strlen(y);

  for(i = 0; i <= ylen; i++)
    {
      c[i][0] = 0;
    }
for(i = 0; i <= xlen; i++)
    {
      c[0][i] = 0;
    }

 for(i = 1; i <= ylen; i++)
   {
     for(j = 1; j <= xlen; j++)
       {
	 if(x[j-1] == y[i-1])
	   {
	     c[i][j] = c[i-1][j-1] + 1;
	   }
	 else c[i][j] = max(c[i][j-1],c[i-1][j]);
	  maxl = max(maxl, c[i][j]);
       }
    
   }
 
 return c[ylen][xlen];
}

int max(int a, int b)
{
  if(a < b)return b;
  return a;
}



Measured memory_bytes: 5704
import java.io.*;
import java.util.*;
import java.lang.*;


public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        PriorityQueue<Long> monsters = new PriorityQueue<>(Collections.reverseOrder());
        for(int n=0; n<N; n++) monsters.add(sc.nextLong());
        int k=0;
        long ans = 0;
        while(!monsters.isEmpty()){
            long m = monsters.poll();
            if(k<K){
                k++;
            }else{
                ans += m;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 90356
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define endl '\n'
#define PI 3.1415926535897932385
#define MOD 1000000007
typedef vector<ll> ve;



int main()
{ 
	ll n;
	cin>>n;
	cout<<fixed<<setprecision(2)<<2*PI*n<<endl;
	 return 0;

}    
	 		
	    


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

using namespace std;
main()
{
	int k,n; cin >> k >> n;
	int a[n];
	for(int i=0;i<n;i++) cin >> a[i];
	
	int maxi = INT_MIN;
	for(int i=0;i<n-1;i++)
	{
		maxi = max(maxi,a[i+1]-a[i]);
	}
		maxi = max(maxi,a[0]+(k-a[n-1]));
	
	if(n==1)
		cout << "0\n";
	else
		cout << k-maxi << endl;
	
}

Measured memory_bytes: 1024
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int R, C, N, ax, ay, bx, by;
int solve(int x, int y) {
	if (y == 0) return x;
	if (x == R) return R + y;
	if (y == C) return R + C + (R - x);
	if (x == 0) return R + C + R + (C - y);
	return -1;
}
int main() {
	ios::sync_with_stdio(false);
	cin >> R >> C >> N;
	vector<pair<int, int> > v;
	for (int i = 0; i < N; i++) {
		cin >> ax >> ay >> bx >> by;
		int ap = solve(ax, ay), bp = solve(bx, by);
		if (ap != -1 && bp != -1) {
			v.push_back(make_pair(ap, i));
			v.push_back(make_pair(bp, i));
		}
	}
	sort(v.begin(), v.end());
	vector<int> s, cnt(N); bool f = true;
	for (int i = 0; i < v.size(); i++) {
		if (cnt[v[i].second] == 0) {
			s.push_back(v[i].second);
			cnt[v[i].second] = 1;
		}
		else {
			if (s.back() != v[i].second) f = false;
			else s.pop_back();
		}
	}
	cout << (f ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 2672
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
const int INF = 1000000000;
const int MOD = 1000000007;
int main(){
	int n;
	cin >> n;
	cout << (n + 999) / 1000 * 1000 - n  << endl;
}


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

using namespace std;
#define lint long long
#define P pair<int, int>

int main() {
    int N, K;
    
    cin >> N >> K;
    
    if(K % 2 != 0){
        lint num = N / K;
        cout << num * num * num << endl;
    } else {
        lint num = N / K;
        lint num2 = N / (K / 2) - num;
        cout << num * num * num + num2 * num2 * num2 << endl;
    }
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl

const int INF = 1000000;
const int MAXK = 1000005;
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> A(m);
  rep(i, m) cin >> A[i];
  sort(all(A));
  vector<int> K = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
  vector<int> dp(MAXK, -INF);
  dp[0] = 0;
  for(int j = 0; j <= n; j++)
    rep(i, m) dp[j + K[A[i]]] =
      max(dp[j + K[A[i]]], dp[j] + 1);

  int rem = dp[n];
  string s;
  int j = n;
  while(j > 0) {
    for(int i = m - 1; i >= 0; i--) {
      if(j - K[A[i]] < 0) continue;
      if(dp[j - K[A[i]]] == rem - 1) {
        char c = '0' + A[i];
        s = s + c;
        j -= K[A[i]];
        rem--;
        break;
      }
    }
  }
  cout << s << endl;
  return 0;
}

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

int main(){
  int K, T; cin >> K >> T;
  int Cakes[T];
  for (int i = 0; i < T; i++) cin >> Cakes[i];
  sort(Cakes, Cakes + T);
  cout << max(0, 2*Cakes[T-1]-K-1) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int n, t; vector<pair<int, int> >v;
int f(int now, int time){
	if(now==n) return 0;
	if(time>=t) return 0;
	if(dp[now][time]!=-1) return dp[now][time];
	dp[now][time]=max(0, max(f(now+1, time), f(now+1, time+v[now].first)+v[now].second));
	return dp[now][time];
}
int main(){
	cin>>n>>t; v.resize(n);
	for(int i=0; i<n; i++){
		cin>>v[i].first>>v[i].second;
	}
	sort(v.begin(), v.end());
	memset(dp, -1, sizeof(dp));
	cout<<f(0, 0)<<endl;
	return 0;
}

Measured memory_bytes: 35712
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(bool b) { return to_string(int(b)); }
string to_string(char b) { return "'" + string(1, b) + "'"; }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v) {
	string res = "{";
	for (const auto& x : v) res += (res == "{" ? "" : ", ") + to_string(x);
	return res + "}";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug(T...);
}
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define db(...) 42
#endif
typedef long long ll;
typedef long double ld;
int main() {
	int n;
	scanf("%d", &n);
	vector<int> A(n), B(n), occ(n + 1);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &A[i]);
		occ[A[i]]++;
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &B[i]);
		occ[B[i]]++;
	}
	map<pair<int, int>, int> bs;
	for (int i = 0; i < n; ++i) {
		bs[{occ[B[i]], B[i]}]++;
	}
	auto update = [&](int x, int sub = 1) {
		if (!bs.count({occ[x], x})) return;
		int num = bs[{occ[x], x}];
		bs.erase({occ[x], x});
		--occ[x];
		if (num - sub > 0) bs[{occ[x], x}] = num - sub;
	};
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		auto it = prev(bs.end());
		int x = it->first.second;
		db(bs, ans, x);
		if (x != A[i]) {
			ans.push_back(x);
			update(x);
		} else {
			if (it == bs.begin()) {
				printf("No\n");
				return 0;
			}
			--it;
			x = it->first.second;
			db(x);
			ans.push_back(x);
			update(x);
		}
		update(A[i], 0);
	}
	printf("Yes\n");
	for (int x : ans) printf("%d ", x);
}


Measured memory_bytes: 17920
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
//#include <bits/stdc++.h>

#define ll long long int
#define pb push_back
#define llu unsigned long long int
#define fo(i,n) for(int i=0;i<n;i++)
#define eb emplace_back
#define M 1000000007
#define vi vector<int>
#define vlli vector<lli>
#define pi pair<int,int>
#define mp make_pair
#define mapi map<int,int>

using namespace std;
int min(int x,int y)
{
	if(x<y)
		return x;
	return y;
}
int max(int x,int y)
{
	if(x>y)
		return x;
	return y;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //cin.ignore(numeric_limits<streamsize>::max(),'\n');
    //const unsigned int M=1000000007;
	int test;
	cin >> test;
	int temp = test + test*test +test*test*test;
	cout << temp;
	return 0;
}



Measured memory_bytes: 3160
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var buff []byte

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextFloat64() float64 {
	sc.Scan()
	f, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func nextInts(n int) (r []int) {
	r = make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt64

func maxInt(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func minInt(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buff, bufio.MaxScanTokenSize*1024)
	log.SetFlags(log.Lshortfile)
}

func main() {
	N := nextInt()
	A := nextInts(N)
	money := 1000
	stock := 0
	for i := 0; i < N; i++ {
		if stock == 0 {
			if i+1 < N && A[i] < A[i+1] {
				n := money / A[i]
				money -= A[i] * n
				stock += n
			}
		} else {
			if (i == N-1) || (i+1 < N && A[i] > A[i+1]) {
				money += stock * A[i]
				stock = 0
			}
		}
		log.Println(i, money, stock)
	}
	fmt.Println(money)
}


Measured memory_bytes: 1880
def prod(n):
    x = 1
    for i in range(1, n+1):
        x *= i
        x %= (10 ** 9 + 7)
    return x


n, m = map(int, input().split())
n, m = min(n, m), max(n, m)
minusNM = abs(n-m)
ans = 0
if minusNM == 0:
    ans = 2 * prod(n) ** 2
elif minusNM == 1:
    ans = prod(n) ** 2 * m
print(ans % (10 ** 9 + 7))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n,d,h,x,c;
int main()
{
    cin>>n>>d>>x;
    for (int i=0;i<n;i++){
        cin>>h;
        c++;
        int q=1;
        while(q+h<=d)c++,q+=h;
    }
    cout<<c+x;
    return  0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] A = new int[n];
		int patern = 0;
		int count = 1;

		//格納
		for(int i=0; i<n; i++){
			A[i] = scan.nextInt();
		}

		for(int i=0; i<n-1; i++){
			if(patern==0){
				if(A[i]<A[i+1]){
					patern = 1;
				}
				else if(A[i]==A[i+1]){
					continue;
				}
				else if(A[i]>A[i+1]){
					patern = 2;
				}
			}
			else if(patern==1){
				if(A[i]<=A[i+1]){
					continue;
				}
				else{
					patern =0;
					count++;
				}
			}
			else if(patern==2){
				if(A[i]>=A[i+1]){
					continue;
				}
				else{
					patern = 0;
					count++;
				}
			}
		}
		System.out.println(count);
	}
}

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

int main(){
  int n,m;
  while(1){
  cin>>n>>m;
  if(!n&&!m)break;
  priority_queue <int> Q;
  for(int i=0,a;i<n;i++)cin>>a,Q.push(a);

  int ans=0,cnt=0,sum=0;
  while(!Q.empty()){
    int t=Q.top();Q.pop();
    cnt++;
    sum+=t;
    if(n&&cnt==m) ans+=sum-t,sum=cnt=0,n--;
  }
  ans+=sum;
  cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1228
X=int(input())
check=[False]*(X+1)
check[1]=True
for i in range(2,X+1):
  temp=i*i
  while temp<=X:
    check[temp]=True
    temp*=i
for i in range(X,0,-1):
    if check[i]==True:
      print(i)
      exit()


Measured memory_bytes: 3060
s=list(input())
al=list('abcdefghijklmnopqrstuvwxyz')

ki=[0]*26

for i in range(len(s)):
    for j in range(26):
        if s[i]==al[j]:
            ki[j]+=1
for i in range(26):
    if ki[i]==0:
        print(al[i])
        exit()
print('None')

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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, x, n) for(ll i=x; i<(ll)n; ++i)
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()

int main(){
    ll n;
    cin >> n;
    vll p(n);
    rep(i, n){
        cin >> p[i];
    }
    ll count = 0;
    REP(i, 1, n-1){
        if((p[i-1]<=p[i]&&p[i]<=p[i+1])||(p[i+1]<=p[i]&&p[i]<=p[i-1])){
            ++count;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
# Problem A - Kyu in AtCoder

# input
X = int(input())

# check
if X<=599:
    print(8)
elif X<=799:
    print(7)
elif X<=999:
    print(6)
elif X<=1199:
    print(5)
elif X<=1399:
    print(4)
elif X<=1599:
    print(3)
elif X<=1799:
    print(2)
elif X<=1999:
    print(1)
    


Measured memory_bytes: 9180
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)

typedef vector<int> vi;
typedef vector<vi> vvi;

void chmax(int& a,int b)
{
	a=max(a,b);
}

int main()
{
	for(int n,c;cin>>n>>c,n|c;){
		vi a(n),b(c);
		{
			int x;
			rep(i,n) rep(j,16) cin>>x,a[i]|=x<<j;
			rep(i,c) rep(j,16) cin>>x,b[i]|=x<<j;
		}
		
		vvi dp(n+1,vi(1<<16,-1));
		dp[0][0]=0;
		rep(i,n) rep(j,1<<16) if(dp[i][j]!=-1) rep(k,c)
			chmax(dp[i+1][(j|a[i])&~b[k]],dp[i][j]+__builtin_popcount((j|a[i])&b[k]));
		cout<<*max_element(begin(dp[n]),end(dp[n]))<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 9444
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#define MOD 1000000007
using namespace std;

int main()
{
	long long int n,m,ans;
	cin >> n>>m;
	if (2*n >= m){
		ans = m / 2;
	}
	else{
		ans = (2 * n + m) / 4;
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T>
struct Matrix {
    Matrix(int r, int c) : _r(r), _c(c), a(r * c) {}
    T* operator[](int row) { return row * _c + a.data(); }
    int _r, _c;
    vector<T> a;
};

int main()
{
    int n;
    cin >> n;
    vector<double> phead(n);
    for (double& p : phead) cin >> p;
    Matrix<double> dp(n + 1, n + 1);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i; ++j)
            dp[i][j] = dp[i - 1][j] * (1 - phead[i - 1]) + dp[i - 1][j - 1] * phead[i - 1];
    double res = 0;
    for (int i = n; i > n - i; --i) {
        res += dp[n][i];
//        cerr << i << ' ' << dp[n][i] << '\n';
    }
    cout << setprecision(9) << fixed << res;
    return 0;
}


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

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

int main(void) {
  double a, b, deg, rad, c, S, L, H;
  cin >> a >> b >> deg;

  rad = (deg / 180) * M_PI;

  S = (a*b)/2 * sin(rad);
  printf("%.15lf\n", S);

  c = pow(a, 2) + pow(b, 2) - (2*a*b)*cos(rad);
  c = sqrt(c);
  L = a + b + c;
  printf("%.15lf\n", L);

  H = 2*S / a;
  printf("%.15lf", H);
}



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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int gcd(int i, int j) {
	while (i && j) {
		if (i > j) i %= j;
		else j %= i;
	}
	return i + j;
}

#define MOD 1000000007
int main() {
	int h = ri() + 1, w = ri() + 1;
	int all = h * w;
	int res = (int64_t) all * (all - 1) * (all - 2) / 6 % MOD;
	
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (!i && !j) continue;
			res -= (int64_t) (h - i) * (w - j) % MOD * (gcd(i, j) - 1) * (i && j ? 2 : 1) % MOD;
			if (res < 0) res += MOD;
		}
	}
	for (int i = 0; i < all - 3; i++) res = res * 2 % MOD;
	std::cout << res << std::endl;
	return 0;
}



Measured memory_bytes: 3244
n,k = map(int,input().split(" "))
s = list(input())
a = [1]
for i in range(1,n):
    if s[i] != s[i-1]:
        a.append(i+1)
m = len(a)
ans = 1
i = 1
for i in range(m):
    if s[a[i]-1] == "1":
        if 2*k + i +1 < m:        
            ans = max(ans,a[2*k+i+1]-a[i])
        else:
            ans = max(ans,n+1- a[i])
    else:
        if 2*k+i< m:        
            ans = max(ans,a[2*k+i]-a[i])
        else:
            ans = max(ans,n+1-a[i])
print(ans)


Measured memory_bytes: 7848
open System

[<EntryPoint>]
let main argv =
    let readchararr () = Console.ReadLine().ToCharArray()
    let s,t = readchararr(), readchararr()
    s |> (t |> Array.fold2 (fun state a b -> if a = b then state + 1 else state) 0)
    |> Console.WriteLine
    0

Measured memory_bytes: 13268
h, w, d = map(int, input().split(' '))

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]

q = int(input())
lr = [map(int, input().split(' ')) for _ in range(q)]

dp = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    cnt = dp[i - d]
    cnt += abs(comp[i][0] - comp[i - d][0])
    cnt += abs(comp[i][1] - comp[i - d][1])    
    dp[i] = cnt
    

for l, r in lr:
    print(dp[r] - dp[l])

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

using namespace std;

#define sqr(x) ((x) * (x))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef vector<int> vi;
typedef long long ll;

void solve() {
  int N;
  cin >> N;
  vi A(N), B;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    if (N % 2 == 0) {
      if (i % 2 == 0) {
        B.push_back(A[i]);
      } else {
        B.insert(B.begin(), A[i]);
      }
    } else {
      if (i % 2 == 0) {
        B.insert(B.begin(), A[i]);
      } else {
        B.push_back(A[i]);
      }
    }
  }
  for (int i = 0; i < N; i++) {
    cout << B[i] << ' ';
  }
  cout << endl;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 3956