akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(){
    vector<string> v(3) ;
    cin>>v[0]>>v[1]>>v[2];
    for(ll i=0,j=0;v[i]!="";){
        i=v[i][0]-'a';
        v[j].erase(v[j].begin());
        j=i;
        if(v[i]==""){
            cout<<(char)(i+'A')<<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){

    int a, b;
    
    scanf("%d",&a);
    scanf("%d",&b);
    
    if(a>b){
        printf("a > b\n");
    }else if(a == b){
        printf("a == b\n");
    }else{
        printf("a < b\n");
    }
    
    return 0;
}

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

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

    if (a < b)
    {
        cout << "a < b" << endl;
    }
    else if (a == b)
    {
        cout << "a == b" << endl;
    }
    else
    {
        cout << "a > b" << endl;
    }

}



Measured memory_bytes: 3108
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

A,B,C,X,Y = map(int,readline().split())
L = []
L.append(A*X+B*Y)
for i in range(1, min(X,Y)+1):
    sum = A*(X-i)+B*(Y-i)+C*2*i
    L.append(sum)
ans = min(L)
if max(X,Y)*2*C<ans:
    ans = max(X,Y)*2*C
print(ans)

Measured memory_bytes: 7048
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//ll MOD=1000000007LL;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;
//const ll MAX_V=114514LL;
//const ll MAX = 500010LL;
const ll mod=MOD;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={0,0,1,-1};
vl dy={1,-1,0,0};

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll modpow(ll a, ll n, ll mod) {
  
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll N=2000010;
vl arr(N);
void Eratosthenes(){
	for(ll i = 0; i < N; i++){
		arr[i] = 1;
	}
        arr[1]=0;
	for(ll i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(ll j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}
}
//素数判定O(√n)
bool is_prime(ll n){
  for(ll i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return n!=1;
}


int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(10);
  /*--------------------------------*/
  ll n;cin>>n;
  ll k;cin>>k;
  vl a(n);
  rep(i,n)cin>>a[i];
  ll ng=0;
  ll ok=INF;
  while(ok-ng>1){
    ll mid=(ok+ng)/2;
    ll cnt=0;
    rep(i,n){
      cnt+=(a[i]-1)/mid;
    }
    if(cnt<=k)ok=mid;
    else ng=mid;
  }
  cout<<ok<<endl;
}

Measured memory_bytes: 20368
#include <iostream>
#include <vector>
#include<set>
#include<algorithm>
#include <queue>

using ll =  long long;
#define rep(i,n) for(int i= 0; i< (n); i++)
using namespace std;
using Graph = vector<vector<int>>;

int main(){

    int a, b, k;
    cin >> a >> b >> k;
    int cnt=0;
    for(int i=100; i>=1; i--){
        if(a%i==0 && b%i==0){
             cnt++;
            if(cnt==k){
                cout << i << endl;
                return 0;
            }
        }
    }
    
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val A = readLine()!!.split(" ").map(String::toInt)
    A.mapIndexed { i, e -> i + 1 to e }.sortedBy { it.second }.joinToString(" ") { it.first.toString() }.let(::println)

}

Measured memory_bytes: 83148
import           Control.Monad
import qualified Control.Monad.ST            as ST
import qualified Data.ByteString.Char8       as BS
import           Data.List
import           Data.Maybe
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [n, m] <- getIntList

  acs <- VM.new n -- ACs
  was <- VM.new n -- WAs
  VM.set acs (0::Int)
  VM.set was (0::Int)

  forM_ [1..m] $ \_ -> do
    [t, s] <- words <$> getLine
    let i = read t - (1::Int)
    ac <- VM.read acs i
    if s == "AC"
      then VM.write acs i 1
      else when (ac == 0) $ do wa <- VM.read was i
                               VM.write was i (wa+1)

  ans <- VM.new 2
  VM.set ans (0::Int)

  forM_ [0..(n-1)] $ \i -> do
    ac <- VM.read acs i
    wa <- VM.read was i
    when (ac > 0) $ do a0 <- VM.read ans 0 -- ACs
                       a1 <- VM.read ans 1 -- WAs
                       VM.write ans 0 (a0+1)
                       VM.write ans 1 (a1+wa)

  a0 <- VM.read ans 0
  a1 <- VM.read ans 1

  putStrLn $ show a0 ++ " " ++ show a1

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

typedef long long int ll;
typedef long double ld;

//****************************************************                
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll> 
#define vpll vector<pll>
#define all(X) X.begin(),X.end()
#define endl "\n" //comment it for interactive questions
#define trace1(a) cerr << #a << ": " << a << endl;
#define trace2(a,b) cerr << #a << ": " << a << " " << #b << ": " << b << endl;
#define trace3(a,b,c) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << endl;
#define trace4(a,b,c,d) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << #d << ": " << d << endl;
#define OC freopen("input.txt" , "r", stdin); freopen("output.txt" , "w", stdout) 
#define MOD (ll)1e9+7; //change it for other mods
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
        //*******************************************************
//Some Functions

ll powmod(ll a,ll b)
{
   ll res = 1;
   while(b > 0) {
      if(b & 1) res = (res * a) % MOD;
      a = (a*a)%MOD;
      b = b >> 1; 
  }
  return res % MOD;
}

void solve()
{
    ll a,b;
    cin >> a >> b;
    if(a > 9 || b > 9) {
    	cout << "-1\n";
    	return;
    }
    cout << a*b << "\n";
}

int main()
{
    FAST_IO;
    // #ifndef ONLINE_JUDGE 
      // OC;
    // #endif
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (x, y, z) = readLine()!!.split(" ").map { it.toInt() }
    var l = (mutableListOf(0L) + readLine()!!.split(" ").map { it.toLong() }).toMutableList()
    var l2 = (mutableListOf(0L) + readLine()!!.split(" ").map { it.toLong() }).toMutableList()
    var a = 0
    for (i in 0 until x) {
        l[i + 1] = l[i] + l[i + 1]
    }
    for (i in 0 until y) {
        l2[i + 1] = l2[i] + l2[i + 1]
    }

    for (i in 0..x) {
        if (l[i] > z) break
        val j = l2.binarySearch(z - l[i])
        if (j < 0) {
            a = Math.max(i - (j + 1) - 1, a)
        } else {
            a = Math.max(i + j, a)
        }
    }
    println(a)
}


Measured memory_bytes: 91024
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

#define int long long

const int MAX_V = 805;

class Edge{
	public:
		int to, dis;
		Edge(){}
		Edge(int to, int dis): to(to), dis(dis)  {}
};

vector<Edge> g[MAX_V];
int dis[MAX_V];

void bfs(int s, int n){
	queue<int> q;

	rep(i,n) dis[i] = INF;
	dis[s] = 0;
	q.push(s);

	int u;
	while(not q.empty()){
		u = q.front(); q.pop();
		rep(i,g[u].size()){
			Edge e = g[u][i];
			if(dis[e.to] == INF){
				dis[e.to] = dis[u] + e.dis;
				q.push(e.to);
			}
		}
	}
}

int solve(int n, int s){
	int maxi = 0;
	int tgt = 0; //?????????s?????????????????????

	bfs(s, n);
	rep(i,n){
		if(dis[i] == INF) continue;
		if(maxi < dis[i]){
			maxi  = dis[i];
			tgt = i;
		}
	}

	bfs(tgt, n);
	maxi = 0; //tgt????????????????????\???????????¢maxi
	rep(i,n){
		if(dis[i] == INF) continue;
		maxi = max(maxi, dis[i]);
	}

	return maxi;
}

signed main(){
	int n;
	while(cin >> n,n){
		rep(i,MAX_V) g[i].clear();
		memset(dis, 0, sizeof(dis));

		vector<int> a(n), c(n);
		rep(i,n - 1) cin >> a[i];
		rep(i,n - 1) cin >> c[i];

		rep(i,n - 1){
			g[i + 1].emplace_back(Edge{a[i] - 1, c[i]});
			g[a[i] - 1].emplace_back(Edge{i + 1, c[i]});
		}

		vector<int> leves;
		int s = -1;
		rep(cur,n){
			if(g[cur].size() == 1){
				leves.emplace_back(cur);
			}else{
				s = cur;
			}
		}

		int leaf = 0;
		for(auto i : leves){
			leaf += g[i].back().dis;

			int to = g[i].back().to;
			g[i].clear();
			for(auto it = g[to].begin(); true; it++){
				if((*it).to == i){
					g[to].erase(it);
					break;
				}
			}
		}

		//for(auto i : g[1]){ cout << i.to << endl; }
		//for(auto i : g[2]){ cout << i.to << endl; }

		int sum = accumulate(all(c), 0);
		//cout << sum << ' ' << leaf << ' ' << solve(n,s) << endl;
		cout << sum * 3 - 2 * leaf - solve(n,s) << endl;
	}
}

Measured memory_bytes: 3276
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, a, b = MAP()

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod
ans = power(2, n) - 1
    
a_max = 2 * 10 ** 5
# a, bの最大値+2
fact = [1] * (a_max + 2)
# 逆元
for i in range(1, a_max + 1):
    fact[i] = (fact[i-1] * i) % mod
# combination
def C(n, a):
    tmp = 1
    for i in range(n, n-a, -1):
        tmp = (tmp * i) % mod
    return tmp * power(fact[a], mod - 2)

print((ans - C(n, a) - C(n, b)) % mod)


Measured memory_bytes: 13012
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def primeFactor(N):  # return prime factors of N as dictionary {prime p:power of p}
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

def PrimeNumSet(N):  # return the list of prime numbers in [2,N], using eratosthenes sieve
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList and seachList[0] <= Max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

def LCM(b,mo=10**9+7):  # retrun LCM of numbers in list b
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True


ans=0

n=I()
a=LI()

m=LCM(a)

x=0
for i in a:
    x+=m*pow(i,mo-2,mo)
    x%=mo

print(x)


Measured memory_bytes: 134724
#include <iostream>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;
    int n;
    int x;
    cin >> n >> x;
    int m[n];
    for (int i = 0; i < n; i++) {
        cin >> m[i];
    }
    int sum = accumulate(m, m + n, 0);
    int min = *min_element(m, m + n);
    x -= sum;
    int r = n + x / min;
    cout << r << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class B
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var ss = new int[n].Select(_ => Console.ReadLine()).OrderBy(s => s.Length).ToArray();

		var r = 0L;
		var root = new Node();

		foreach (var s in ss)
		{
			var node = root;
			for (int i = s.Length - 1; i >= 0; i--)
			{
				if (i == 0)
					node.Ends[s[i] - 'a']++;
				else
					for (int j = 0; j < 26; j++)
					{
						if (node.Ends[j] == 0) continue;
						var c = (char)('a' + j);
						if (s.IndexOf(c, 0, i + 1) >= 0)
							r += node.Ends[j];
					}

				if (!node.Nexts.ContainsKey(s[i]))
					node.Nexts[s[i]] = new Node();
				node = node.Nexts[s[i]];
			}
		}
		Console.WriteLine(r);
	}
}

class Node
{
	public int[] Ends = new int[26];
	public Dictionary<char, Node> Nexts = new Dictionary<char, Node>();
}


Measured memory_bytes: 393296
D, N = map(int, input().split())


def func(x):
    cnt = 0
    while x > 0:
        if x % 100 == 0:
            cnt += 1
        x = x // 100
    return cnt


i = 0
cnt = 0
while True:
    i += 100 ** D
    if func(i) == D:
        cnt += 1

    if cnt == N:
        print(i)
        break


Measured memory_bytes: 2940
a = list( map(int, input().split()) )

cnt = 0
while not a[0] == a[1] == a[2]:
    arr = a.sort()
    cnt += 1
    if a[0] == a[1] :
        a[0] += 1
        a[1] += 1
        continue
    if a[1] == a[2] :
        a[0] += 2
        continue
    else:
        min_id = a.index(min(a))
        a[min_id] += 2
        continue
print(cnt)

Measured memory_bytes: 3064
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}

ll gcd(ll(a), ll(b)) {
	ll k = a;
	ll l = b;
	ll j = 0;
	while (l != 0) {
		j = k % l;
		k = l;
		l = j;
	}
	return k;
}



int main() {
	ll N,x;
	cin >> N>>x;
	
	vector<ll> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec.at(i);
	}
	ll an=0;
	if (vec.at(0) > x) {
		an += vec.at(0) - x;
		vec.at(0) = x;
	}
	for (int i = 1; i < N; i++) {
		if (vec.at(i - 1) + vec.at(i) > x) {
			an += vec.at(i - 1) + vec.at(i) - x;
			vec.at(i) = x - vec.at(i - 1);
		}
		
	}
	cout << an << endl;;

	
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque> 
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype> 
using namespace std;

int main(){
    int N;
    cin >> N;
    int ans=1;
    if (N==1) {
        cout << ans << endl;
        return 0;
    }
    for (int i=0; i<8; i++) {
        ans*=2;
        if (ans*2>N) {
            cout << ans << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 888
#include<stdio.h>

int main()
{
	int n,a,b,i,j;
	long long c=0,d=0;
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		
		if(a>=c&&b>=d){
			c=a;d=b;
		}
		else{
			if((c-1)/a>(d-1)/b){
				c=(((c-1)/a)+1)*a;
				d=(((c-1)/a)+1)*b;
			}
			else{
				c=(((d-1)/b)+1)*a;
				d=(((d-1)/b)+1)*b;
			}
		}
		
//		printf("            %lld %lld\n",c,d);
	}
	printf("%lld",c+d);
}

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

int main(){
    int n;
    cin >> n;
    int p_tarou = 0, p_hanako = 0;
    for(int i=0; i<n; i++){
        string animal_tarou, animal_hanako;
        cin >> animal_tarou >> animal_hanako;
        if (animal_hanako == animal_tarou) {
            p_tarou +=1;
            p_hanako += 1;
            }
        else if (animal_tarou > animal_hanako) p_tarou += 3;
        else p_hanako += 3;
    }
    cout << p_tarou << ' ' << p_hanako << endl;
}


Measured memory_bytes: 3152
"""
yieldを使った全探索
"""
import sys
input = sys.stdin.buffer.readline


S = input()[:-1]

def F(S):
    yield int(S)
    for i in range(len(S)-1):
        left = S[:i+1]
        right = S[i+1:]
        x = int(left)
        for y in F(right):
            yield x + y

answer = sum(F(S))
print(answer)

Measured memory_bytes: 39916
N,M = map(int,input().split(" "))
fact = {}
for i in range(2,M):
    while (M%i == 0):
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
        M //= i
    if (M == 1):
        break


MOD = 10**9+7

def nCr_mod(n,r,mod): #nCrmod
    r = min(n-r,r)
    v = 1
    for i in range(r):
        v = (v * ((n-i)%mod) * pow((i+1),mod-2,mod)) % mod
    return v

ans = 1
for key,item in fact.items():
    ans *= nCr_mod((item + (N) - 1),N-1,MOD)
    ans %= MOD
print(ans)

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

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

using namespace std;
using lint=long long;

class union_find{
	int n;
	vector<int> p;
public:
	union_find(int n):n(n),p(n,-1){}
	int find(int u){ return p[u]<0?u:p[u]=find(p[u]); }
	void unite(int u,int v){
		u=find(u); v=find(v);
		if(u!=v){
			if(p[v]<p[u]) swap(u,v);
			p[u]+=p[v]; p[v]=u; n--;
		}
	}
	bool is_same(int u,int v){ return find(u)==find(v); }
	int size()const{ return n; }
	int size(int u){ return -p[find(u)]; }
};

int main(){
	int n,q;
	lint m; scanf("%d%lld%d",&n,&m,&q);
	vector<pair<int,int>> E1,E2;
	rep(i,q){
		int u,v,c; scanf("%d%d%d",&u,&v,&c);
		if(c==0) E1.emplace_back(u,v);
		else     E2.emplace_back(u,v);
	}

	union_find U(n);
	for(auto e:E1){
		int u,v; tie(u,v)=e;
		U.unite(u,v);
	}

	map<int,int> f;
	rep(u,n) if(f.count(U.find(u))==0) f.emplace(U.find(u),f.size());

	union_find V(U.size());
	for(auto e:E2){
		int u,v; tie(u,v)=e;
		if(U.is_same(u,v)) return puts("No"),0;
		V.unite(f[U.find(u)],f[U.find(v)]);
	}

	if(U.size()==2 && V.size()==1) return puts("No"),0;

	lint k=U.size();
	lint mn,mx=k*(k-1)/2;
	if(E2.empty()) mn=k-1; // spanning tree
	else           mn=k;   // cycle

	if((n-k)+mn<=m && m<=(n-k)+mx) puts("Yes");
	else                           puts("No");

	return 0;
}


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

const int N=2e5+20;

int n;
long long ans;
map <int,int> m;

int main()
{
    
	scanf("%d",&n);
    vector<int>a(n+1);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		ans+=m[i-a[i]];
		m[a[i]+i]++;
	}

	cout<<ans;
}


Measured memory_bytes: 21124
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	string a,b; cin>>a>>b;
	ll ans=INT_MAX;
	for(int i=0;i<=(int)a.length()-(int)b.length();i++)
	{
		ll c=0;
	
			int k=i;
			for(int j=0;j<b.length();j++)
			{
				if(k<a.length() && a[k]!=b[j])
				{
					c++;
				}
				k++;
			}
			//cout<<c<<" ";
			ans=min(ans,c);
		
	
	}
	cout<<ans;
}
	

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

int main()
{
    int a,b;

    scanf("%d %d",&a, &b);

    if(b/10 == 0){
        a=a*10;
    }
    else if(b/100==0){
        a=a*100;
    }
    else{
        a=a*1000;
    }

    if(ceil(sqrt(a+b))==sqrt(a+b)){
        printf("Yes");
    }

    else{
        printf("No");
    }



}


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


int main()
{
	int N, M;
	cin >> N >> M;
	int K[30];
	int A[30][30];
	int count[30];
	for (int i = 0; i < 30; i++)
		count[i] = 0;

	for (int i = 0; i < N; i++)
	{
		cin >> K[i];
		for (int j = 0; j < K[i]; j++)
		{
			cin >> A[i][j];
			count[A[i][j] - 1]++;
		}
	}
	int ans = 0;
	for (int i = 0; i < 30; i++)
	{
		if (count[i] == N)
			ans++;
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define MAX 100001
using namespace std;

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

  int d_a = x - a > 0 ? x - a : a - x;
  int d_b = x-b >0 ? x-b:b-x;

  if(d_a<d_b){
    cout<<"A"<<endl;
  }
  else{
    cout<<"B"<<endl;
  }
}


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

using namespace std;

int main()
{
    int a,b,c,d;cin>>a>>b>>c>>d;
    
    for(int i=0;i<100;++i){
        c-=b;
        if(c<=0){cout<<"Yes"<<endl;return 0;}
        a-=d;
        if(a<=0){cout<<"No"<<endl;return 0;}
    }
    
    return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
#define EPS (1e-10)
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int a,b; cin>>a>>b;
	int c[4] = {300000,200000,100000,0};
	int ans = 0;
	ans+=c[min(a-1,3)];
	ans+=c[min(b-1,3)];
	if(a==b&&a==1) ans+=400000;
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

int main(void) {
    string s, t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;
    if (s == u) {
        a--;
    } else {
        b--;
    }
    cout << a << " " << b << endl;
    return 0;
}

Measured memory_bytes: 3636
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const ll MOD = 1e9 + 7;
const int INF = 1LL << 62;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

signed main() {
    int N, K;
    cin >> N >> K;

    int x[N];
    int y[N];
    for (int i = 0; i < N; i++) cin >> x[i] >> y[i];

    int ret = INF;

    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            for (int k = 0; k < N; k++) {
                for (int l = k+1; l < N; l++) {
                    int max_x = max(x[i], max(x[j], max(x[k], x[l])));
                    int min_x = min(x[i], min(x[j], min(x[k], x[l])));
                    int max_y = max(y[i], max(y[j], max(y[k], y[l])));
                    int min_y = min(y[i], min(y[j], min(y[k], y[l])));
                    int s = (max_x - min_x) * (max_y - min_y);

                    int cnt = 0;

                    for (int m = 0; m < N; m++) {
                        if (x[m] >= min_x && x[m] <= max_x && y[m] >= min_y && y[m] <= max_y) cnt++;
                    }

                    if (cnt >= K) ret = min(ret, s);
                }
            }
        }
    }

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
  ll a,b,x; cin>>a>>b>>x;
  b = b/x+1;
  if(a) a = (a-1)/x+1;
  else a = 0;
  cout << b-a << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに実装したソースコード
 */
public class Main {

	private static final long MOD = 998_244_353;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), m = scanner.nextInt(), k = scanner.nextInt();
			// n-1_C_i のmod結果を格納する配列
			long[] c = new long[n];
			c[n - 1] = c[0] = 1;
			IntStream.rangeClosed(1, (n - 1) / 2)
					.forEach(i -> c[n - 1 - i] = c[i] = c[i - 1] * (n - i) % MOD * modpow(i, MOD - 2) % MOD);
			// (m-1)^i のmod結果を格納する配列
			long[] mp = new long[n];
			mp[0] = 1;
			IntStream.range(1, n).forEach(i -> mp[i] = mp[i - 1] * (m - 1) % MOD);
			long result = 0L;
			for (int i = 0; i <= k; i++) {
				result = (result + m * c[i] % MOD * mp[n - 1 - i] % MOD) % MOD;
			}
			System.out.println(result);
		}
	}

	/**
	 * nのmべき乗 mod MOD を計算する
	 * 
	 * @param n
	 * @param m
	 * @return nのmべき乗 mod MOD
	 */
	private static long modpow(long n, long m) {
		long result = 1L;
		while (m > 0) {
			if (1 == (m & 1)) {
				result = result * n % MOD;
			}
			n = n * n % MOD;
			m >>= 1;
		}
		return result;
	}
}


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

int main(){
    string S, T;
    std::cin >> S >> T;
    int n, count = 0, min_c = 1000;

    n = S.size() - T.size() + 1;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < T.size(); j ++){
            if(S[i+j] != T[j]){
                count++;
            }
        }
        if(count < min_c){
            min_c = count;
        }
        count = 0;
    }

    std::cout << min_c;

}

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


int cnt;
int m; /*間隔Gの添字*/



void inserctionSort(vector<int>& A,int n,int g){
  int v,j;

  for(int i=g; i<n; i++){
    v = A[i];
    j = i-g;
    while(j >= 0 && A[j] > v){
      A[j+g] = A[j];
      j = j-g;
      cnt++;
    }
    A[j+g] = v;
  }
}


/*間隔G,回数cntを出力する関数*/
void Print_G_cnt(vector<int> &G){

  cout<<G.size()<<endl;

  for(int i=G.size()-1; i>=0; i--) cout<<G[i]<<" ";
  cout<<endl;

  cout<<cnt<<endl;
}



void shellSort(vector<int>& A,int n){
  cnt =0;
  int v;
  vector<int> G;
  G.push_back(1);

  for( m=1; 3*G[m-1]+1<n; m++){
    G.push_back(3*G[m-1]+1);
  }
 
  for(int i=m-1; i>=0; i--)inserctionSort(A,n,G[i]);

  Print_G_cnt(G);
  
}


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

  shellSort(A,n);
  
  for(int i=0; i<n; i++) cout<<A[i]<<endl;
  

  return 0;
}


Measured memory_bytes: 6708
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vp;
typedef map<ll, ll> mll;
typedef map<string, ll> mstrll;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define indent() cout << '\n'
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
const ll N = 200005;
const ll M = 100005;
ll n, m, x, y, z, w, h, ans, cnt, mx, mn;
string s, t, alphabet = "abcdefghijklmnopqrstuvwxyz";
ll a[N] = {}, b[N] = {}, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
vll v;
//vll dx = {-1, 0, 1, -1, 1, -1, 0, 1}, dy = {-1, -1, -1, 0, 0, 1, 1, 1};

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n >> m){
        rep(i, m){
            cin >> a[i];
        }
        rep(i, 1, 100000){
            if(i >= n){
                bool flag = true;
                rep(j, m){
                    if(to_string(i).find(to_string(a[j])) != string::npos){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    print(i);
                    break;
                }
            }
        }
    }
}


Measured memory_bytes: 256
n, m, c = map(int,input().split())
b_list = list(map(int,input().split()))
a_list = []
for i in range(n):
    a_list.append(list(map(int,input().split())))
count = 0

for i in range(n):
    sum = 0
    for j in range(m):
        sum += a_list[i][j] * b_list[j]
    if sum + c > 0:
        count += 1

print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(c) (c).begin(),(c).end()
int main(){
	while(true){
		int n,ans=1;
		cin >> n;
		if(!n) break;
		vector<int> a,ac(3);
		rep1(i,3) a.push_back(i);
		rep(i,n){
			string s;
			cin >> s;
			if(s[0]=='N'){
				ac[0]=a[1];
				ac[1]=7-a[0];
				ac[2]=a[2];
			}
			if(s[0]=='E'){
				ac[0]=7-a[2];
				ac[1]=a[1];
				ac[2]=a[0];
			}
			if(s[0]=='W'){
				ac[0]=a[2];
				ac[1]=a[1];
				ac[2]=7-a[0];
			}
			if(s[0]=='S'){
				ac[0]=7-a[1];
				ac[1]=a[0];
				ac[2]=a[2];
			}
			if(s[0]=='R'){
				ac[0]=a[0];
				ac[1]=a[2];
				ac[2]=7-a[1];
			}
			if(s[0]=='L'){
				ac[0]=a[0];
				ac[1]=7-a[2];
				ac[2]=a[1];
			}
			a=ac;
			ans+=a[0];
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1228
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        Scanner scanner = new Scanner(System.in);
        int A = scanner.nextInt();// taka kou
        int B = scanner.nextInt();
        int C = scanner.nextInt();// ao kou
        int D = scanner.nextInt();
        while(true){
            C -= B;
            if(C <= 0 ){
                System.out.println("Yes");
                return;
            }
            A -= D;
            if(A <= 0 ){
                System.out.println("No");
                return;
            }
        }
    }
}


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

using namespace std;

const int MOD = 1e9+7;

string k;
int d;

vector<int> digits;
int dp[(int)1e4+10][110][2];

int solve(int idx, int sum, int tight){
    // cout << idx << " " << sum << " " << tight << '\n';
    if(idx == -1) 
        return sum % d == 0;

    if(dp[idx][sum][tight] != -1 and tight != 1)
        return dp[idx][sum][tight];

    int ret = 0;

    int j = (tight) ? digits[idx] : 9;

    for(int i=0;i<=j;++i){
        int newTight = (digits[idx] == i) ? tight : 0;
        ret = (ret + solve(idx - 1, (sum + i) % d, newTight)) % MOD;
    }

    if(!tight)
        dp[idx][sum][tight] = ret;

    return ret;
}

int main(){

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

    memset(dp, -1, sizeof(dp));

    cin >> k >> d;

    digits = vector<int>(k.size());
    for(int i=0;i<k.size();++i)
        digits[i] = k[i] - '0';
    reverse(digits.begin(), digits.end());


    cout << (solve(k.size()-1, 0, 1) - 1 + MOD)%MOD << '\n';

    return 0;
}

Measured memory_bytes: 9856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(int i = a; i < b; i++)

int main(){
    ll N; cin >> N;
    vector<ll> A(N+1), S(N+1);
    rep(i, 1, N+1){
        cin >> A[i];
        A[i] *= 2;
    }
    S[0] = 0;
    rep(i, 1, N + 1) S[i] = S[i-1] + A[i];
    for(auto t: S) cerr << t << " ";
    cerr << endl;
    ll left = 2, right = 3;
    ll ans = 1e18;

    rep(mid, 3, N){
        ll pq = S[mid-1], rs = S[N] - S[mid-1];
        while(llabs(pq/2 - S[left-1]) > llabs(pq/2 - S[left]) && left < mid-1) left++;
        if(right <= mid) right = mid + 1;
        while( right < N && llabs(rs/2 - (S[right-1] - S[mid-1])) > llabs(rs/2 - (S[right] - S[mid-1]) )) right++;
        ll t[4];
        t[0] = S[left-1];
        t[1] = pq - t[0];
        t[2] = S[right-1] - (t[1] + t[0]);
        t[3] = S[N] - (t[2] + t[1] + t[0]);
        cerr << "left, mid, right " << left << " " <<  mid << " " << right << endl;
        for(auto e: t) cerr << e << " ";
        cerr << endl;
        sort(t, t + 4);
        //cerr << t[3] << t[0] << endl;
        ans = min(ans, t[3] - t[0]);
        cerr << ans << endl;
    }
    cout << ans / 2 << endl;
}


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

struct BIT
{
    int N;
    vector<int> bit;

    BIT(int n):N(n)
    {
        bit.assign(N+1,0);
    }

    void add(int k,int x)
    {
        for(int i=k; i<=N; i+=i&-i)
        {
            bit[i] += x;
        }
    }

    int sum(int k)
    {
        int ret = 0;

        for(int i=k; i>0; i-=i&-i)
        {
            ret += bit[i];
        }

        return ret;
    }
};

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

    BIT bit(N);

    for(int i=0; i<Q; i++)
    {
        int c,x,y;
        cin >> c >> x >> y;

        if(c){
            int s1 = bit.sum(y),
                s2 = x==1 ? 0 : bit.sum(x-1);

            cout << s1 - s2 << endl;
        }else{
            bit.add(x,y);
        }
    }
}

Measured memory_bytes: 1532
import scala.io.StdIn.readInt

object Main {
  def fib(a:Int, b:Int, c:Int, n:Int):Int = {
    n match {
      case 0 => a
      case n => fib(a+b, a, b, n-1)
    }
  }

  def main(args: Array[String]) = {
    val n = readInt()
    println(fib(1, 0, 0, n))
  }
}

Measured memory_bytes: 43736
from fractions import gcd
def solve(a):
    n = len(a)
    s = [(x + 1) & 1 for x in a]
    ss = sum(s)
    if ss == n:
        a[0] -= 1
    elif ss == n - 1:
        for i in xrange(n):
            if s[i] == 0 and a[i] > 1:
                a[i] -= 1
                break
        else:
            return ss & 1
    else:
        return ss & 1
    g = reduce(gcd, a)
    return not solve([x / g for x in a])

def main():
    n = int(raw_input())
    a = map(int, raw_input().split())
    print "First" if solve(a) else "Second"
main()


Measured memory_bytes: 92056
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<class T>
bool chmax(T &a, T b){if(a < b){a = b; return true;} return false;}
template<class T>
bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    ll mon = 1000;
    vector<ll> a(n+2);
    a[0] = 1000;
    for(int i = 0; i < n; i++) cin >> a[i+1];
    ll num = 0;
    rep(i,1,n+1){
        if(a[i-1] >= a[i] && a[i] <= a[i+1]){
            ll t = mon / a[i];
            num += t;
            mon -= t * a[i];

        }

        if(a[i-1] <= a[i] && a[i] >= a[i+1]){
            mon += num * a[i];
            num = 0;
        }

        debug(i, mon, num);
    }
    if(num)mon += num * a[n];

    cout << mon << "\n";
}

Measured memory_bytes: 3656
//agc003_b.cpp
//Sat Jul 27 15:24:47 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	ll ans = 0; 
	ll prevnum = 0;
	for (int i=0;i<n;i++){
		ll a;
		cin >> a;
		if (prevnum ==1 && a>0){
			a--;
			ans++;
		}
		ans += a/2;
		prevnum = a%2;
	}

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 384
/*----------------by syr----------------*/
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<deque>
#include<fstream>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<limits>
#include<list>
#include<map>
#include<math.h>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<sstream>
#include<string>
#include<time.h>
#include<utility>
#include<vector>

using namespace std;

const int INF=1e9+7;

int n,m,c;
int dis[1000005],iter[100005];
int vis[100005];
vector<int> have[1000005],g[1000005];
vector<pair<int,int> > ve[100005];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		ve[u].push_back(make_pair(w,v));
		ve[v].push_back(make_pair(w,u));
		have[w].push_back(u);
		have[w].push_back(v);
		c=max(c,w);
	}
	for(int i=1;i<=n;i++) sort(ve[i].begin(),ve[i].end());
	for(int i=1;i<=c;i++){
		if(!have[i].size()) continue;
		sort(have[i].begin(),have[i].end());
		have[i].erase(unique(have[i].begin(),have[i].end()),have[i].end());
	}
	int nn=n;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=c;i++){
		for(int j=0;j<have[i].size();j++){
			int s=have[i][j];
			if(vis[s]==c) continue;
			queue<int> q;
			vector<int> vec;
			q.push(s);
			vis[s]=i;
			while(!q.empty()){
				int u=q.front();q.pop();
				vec.push_back(u);
				for(int &k=iter[u];k<ve[u].size()&&ve[u][k].first==i;k++){
					int v=ve[u][k].second;
					if(vis[v]==i) continue;
					vis[v]=i;
					q.push(v);
				}
			}
			nn++;
//			printf("%d\n",i);
			for(int k=0;k<vec.size();k++){
//				printf("%d ",vec[k]);
				g[vec[k]].push_back(nn);
				g[nn].push_back(vec[k]);
			}
//			puts("");
		}
//		puts("OK");
	}
/*	for(int i=1;i<=nn;i++){
		for(int j=0;j<g[i].size();j++) printf("%d ",g[i][j]);
		puts("");
	}
*/	queue<int> q;
	memset(dis,-1,sizeof(dis));
	dis[1]=0;q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(dis[v]!=-1) continue;
			dis[v]=dis[u]+1;
			q.push(v);
		}
	}
	if(dis[n]==-1) puts("-1");
	else printf("%d\n",dis[n]/2);
	return 0;
}

Measured memory_bytes: 83456
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        String []s = br.readLine().split(" ");
        int []h = new int[N];
        for(int i=0; i < N; ++i)
            h[i] = Integer.parseInt(s[i]);

        int []dp = new int[N];

        dp[0] = 0;
        dp[1] = Math.abs(h[0] - h[1]);

        for(int i=2; i < N; ++i)
            dp[i] = Math.min(
                dp[i-1] + Math.abs(h[i] - h[i-1]),
                dp[i-2] + Math.abs(h[i] - h[i-2])
                );

        System.out.println(dp[N-1]);
    }
}

Measured memory_bytes: 35668
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b){
	if(b == 0) return a;
	return gcd(b,a%b);
}
ll n,ans;
ll t[105];
int main(){
	scanf("%lld",&n);
	for(int i = 1;i <= n;i++)
		scanf("%lld",&t[i]);
	ans = t[1];
	for(int i = 2;i <= n;i++){
		ll gg = gcd(ans,t[i]);
		ans = ans/gg*t[i];
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int par[200001];
int cnt[200000];
long long inv[200001];
long long fact[200001];
long long invfact[200001];
vector <int> v[200001];
map <int, int> mp[200000];

int find(int x) {
	if (par[x] == x) return x;
	return par[x] = find(par[x]);
}

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

void calc_inv(int n, int mod) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    
    fact[0] = invfact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    for (int i = 1; i <= n; i++) invfact[i] = invfact[i - 1] * inv[i] % mod;
}

int main() {
	int n, x, y, m = 1000000007, m1 = 1e9 + 1, c1 = -1, p1 = -1, m2 = 1e9 + 1, c2 = -1, p2 = -1, p = 0, i, j;
	long long ans = 1;
	map <int, int>::iterator it;
	
	calc_inv(200000, m);
	
	scanf("%d %d %d", &n, &x, &y);
	
	for (i = 0; i < n; i++) {
		int c, w;
		
		scanf("%d %d", &c, &w);
		
		v[c].push_back(w);
	}
	
	for (i = 1; i <= n; i++) {
		if (v[i].size() == 0) continue;
		
		sort(v[i].begin(), v[i].end());
		
		if (v[i][0] < m1) {
			m2 = m1;
			c2 = c1;
			p2 = p1;
			m1 = v[i][0];
			c1 = i;
			p1 = p;
		} else if (v[i][0] < m2) {
			m2 = v[i][0];
			c2 = i;
			p2 = p;
		}
		
		p += v[i].size();
	}
	
	for (i = 0; i < n; i++) par[i] = i;
	
	p = 0;
	
	for (i = 1; i <= n; i++) {
		for (j = 0; j < v[i].size(); j++) {
			if (v[i][j] + v[i][0] <= x) unite(p, p + j);
			if (c1 != i && m1 + v[i][j] <= y) unite(p1, p + j);
			if (c2 != i && m2 + v[i][j] <= y) unite(p2, p + j);
		}
		
		p += v[i].size();
	}
	
	p = 0;
	
	for (i = 1; i <= n; i++) {
		for (j = 0; j < v[i].size(); j++) {
			int x = find(p + j);
			
			cnt[x]++;
			mp[x][i]++;
		}
		
		p += v[i].size();
	}
	
	for (i = 0; i < n; i++) {
		if (cnt[i] == 0) continue;
		
		ans = ans * fact[cnt[i]] % m;
		
		for (it = mp[i].begin(); it != mp[i].end(); it++) ans = ans * invfact[it->second] % m;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}


Measured memory_bytes: 35072