akhauriyash/Code-Regression huggingface dataset:
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include<bitset>
#include <iomanip>

using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;



#define ll long long




/*
class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d, e, H, W, L;
ll A[200005] = {};
ll B[200005] = {};
ll C[200005] = {};
bool f, ff;
string S[2];
set <long long>sll;
pl bufpl;
vector <long long>vl[3];
vector <pl>vpl;
vector <string> vs;
set<ll> llset;

/*struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}



ll minn, maxx;
double ansa;
int fl[40];
char ch;


int main() {

	cin >> S[0];
	
	for (int i = 0; i < S[0].size(); i++) {
		fl[S[0][i] - 'a']++;
	}

	ch = 'a';
	for (int i = 0; i < 26; i++) {
		if (fl[i] == 0) {
			cout<<ch<<endl;
			break;
		}
		if (i == 25) {
			cout << "None" << endl;
		}
		ch++;
	}

	return 0;

}


Measured memory_bytes: 512
use std::io;
use std::collections::VecDeque;

fn main() {
    println!("{}", solve());
}

fn solve() -> String {
    let mut input = Input::new();
    let n: usize = input.next();
    let mut a: Vec<usize> = (0..n).map(|_| input.next()).collect();
    a.sort();
    if n > 3 && a[0] == a[2] {
        return String::from("Impossible");
    }
    let m = a[0];
    let x = m - if m < a[1] { 0 } else { 1 };
    let mut c = vec![0; n];
    for v in a {
        c[v] += 1;
    }
    for i in 0..n {
        if i == m {
            continue;
        }
        if (i < m || m + x < i) && c[i] > 0 {
            return String::from("Impossible");
        }
        if !(i < m || m + x < i) && c[i] < 2 {
            return String::from("Impossible");
        }
    }
    String::from("Possible")
}

struct Input {
    queue: VecDeque<String>,
}

impl Input {
    fn new() -> Input {
        Input { queue: VecDeque::new() }
    }

    fn next<T>(&mut self) -> T
        where T: std::str::FromStr,
              T::Err: std::fmt::Debug
    {
        if self.queue.is_empty() {
            let mut line = String::new();
            let _ = io::stdin().read_line(&mut line);
            for x in line.split_whitespace() {
                self.queue.push_back(String::from(x));
            }
        }
        return self.queue.pop_front().unwrap().parse::<T>().unwrap();
    }
}



Measured memory_bytes: 4352
#include <stdio.h>
#define min(a, b) ((a)>(b) ? (b) : (a))

int main(){
  int dish[5];
  int minv = 10;
  int ans = 0;
  for(int i=0; i<5; i++){
    scanf("%d", &dish[i]);
    if(dish[i] % 10){
      minv = min(minv, dish[i]%10);
      ans = ans + dish[i] + (10-dish[i]%10);
    }else{
      ans = ans + dish[i];
    }
  }
  printf("%d", ans - 10 + minv);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (long long  i=a;i<n;i++)
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;

void solve() {
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	while (b <= a&&k) {
		b *= 2;
		k--;
	}
	while (c <= b&&k) {
		c *= 2;
		k--;
	}
	if (a < b&&b < c) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T_ = 1;
	//cin >> T_;
	for (int i = 0; i < T_; i++)solve();
	return 0;
}



Measured memory_bytes: 3652
import math

N = int(input())
P = input().split()
Q = input().split()
X = [i+1 for i in range(N)]
Y = [i+1 for i in range(N)]

n = 1
for i in range(N):
    for j in range(N-i):
        if int(P[i]) == X[j]:
                l = j
    X.remove(int(P[i]))
    n += l*math.factorial(N-i-1)
m = 1
for i in range(N):
    for j in range(N-i):
        if int(Q[i]) == Y[j]:
                l = j
    Y.remove(int(Q[i]))
    m += l*math.factorial(N-i-1)
print(abs(m-n))

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <deque>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

bool cmp(const pii &a, const pii &b) {
     if (a.second == b.second) return a.first < b.first;
     else return a.second < b.second;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<pii> req;
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        req.push_back(make_pair(a, b));
    }
    sort(req.begin(), req.end(), cmp);
    int ans = 0, prev = 0;
    for (auto i : req) {
        if (prev >= i.first && prev < i.second) continue;
        ans++;
        prev = i.second - 1;
    }
    printf("%d\n", ans);
    return 0;
}


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

static const int MAX_V = 210;
const int INF = 1e9;

int d[MAX_V][MAX_V];
int V;

void warshall_floyde(){
    for(int k = 0; k < V; k++){
        for(int i = 0; i < V; i++){
            for(int j = 0; j < V; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

int R;
bool visited[210];
vector<int> r;
/* 
int dfs(int v, int p = -1, int length = 0, int depth = 1){
    if(depth == R) return length;
    
    int ans = INF;
    rep(i, R){
        int nv = r[i];
        if(visited[nv] || nv == p) continue;
        visited[nv] = true;
        ans = min(ans, dfs(nv, v, length + d[v][nv], depth + 1));
        visited[nv] = false;
    }
    return ans;
} */

int main(){
    int M; cin >> V >> M >> R;
    r.resize(R);
    rep(i,R) {cin >> r[i]; r[i]--;}
    rep(i, V) rep(j, V){
        if(i != j) d[i][j] = INF;
        else d[i][j] = 0;
    }
    rep(i, M){
        int a, b, c; cin >> a >> b >> c;
        a--, b--;
        d[a][b] = c;
        d[b][a] = c;
    }
    warshall_floyde();
    int ans = INF;
    sort(r.begin(), r.end());
    do{
        int cnt = 0;
        rep(i, R - 1){
            cnt += d[r[i+1]][r[i]];
        }
        ans = min(ans, cnt);
    }while(next_permutation(r.begin(),r.end()));
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <utility> // pair make_pair
using std::swap; // c++11
using std::pair;
using std::make_pair;
#include <tuple> // tuple(c++11) make_tuple(c++11)
using std::tuple; // get<address>(variable)
using std::make_tuple;
#include <string> // string stoi(c++11) stoll(c++11) to_string(c++11)
using std::string;
using std::stoi;
using std::stoll;
using std::to_string;
#include <queue> // queue priority_queue
using std::queue;
using std::priority_queue;
#include <stack> // stack
using std::stack;
#include <vector> // vector
using std::vector;
#include <map> // map
using std::map;
#include <set> // set
using std::set; // insert erase find count
#include <algorithm> // min max
using std::sort;
using std::lower_bound; // iterator,  >=
using std::upper_bound; // iterator,  >
using std::min;
using std::max;
using std::min_element; // iterator
using std::max_element; // iterator
#include <complex> // complex
using std::complex; // real imag
#include <iostream> // cin cout
using std::cin;
using std::cout;
using std::endl;
#include <iomanip> // setprecision fixed(manipulator)
using std::setprecision;
using std::fixed;
#include <cmath>
#include <cstdio>

#define lli long long int
#define INF (int)1e09
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define EFOR(i, m, n) for (int i = m; i <= n; i++)
#define RFOR(i, m, n) for (int i = m; i > n; i--)
#define REFOR(i, m, n) for (int i = m; i >= n; i--)
#define VSORT(v) sort((v).begin(), (v).end()) // sort vector
typedef pair<int, int> PI;
typedef tuple<int, int, int> TI;
template <typename T> using Vec = vector<T>; // c++11

int main(void) {
    string s;
    cin >> s;
    int first = stoi(s);
    int second = 0;
    FOR (i, 0, (int)s.length()) {
        second += (s[i] - '0');
    }
    if (first % second == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
int tests;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a,p;
	cin>>a>>p;
	cout<<(a*3+p)/2;
	return 0;
}

Measured memory_bytes: 3588
n = int(input())
s = input()

def ROTN(tmp, n):
    tmp = ord(tmp) + n
    if tmp > 0x5a:
        tmp -= 26
    return chr(tmp)


ans = []
for i in range(len(s)):
    tmp = s[i]
    ans.append(ROTN(tmp, n))

for i in range(len(ans)):
    print(ans[i], end="")

Measured memory_bytes: 9200
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int hp = Integer.parseInt(sc.next());
        int attack = Integer.parseInt(sc.next());
        if(hp % attack != 0){
            System.out.println(hp / attack + 1);
        }else{
            System.out.println(hp / attack);
        }
    }
}

Measured memory_bytes: 21716
# coding:utf-8
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    n,m = map(int, input().split())
    diff = m * n
    print(int(combinations_count(n+m, 2)) - diff )

if __name__ == '__main__' :
    main()

Measured memory_bytes: 3060
import math

n=int(input())

t=int(input())
mint=t
t1=int(input())
mint = min(t, t1)
maxtt=t1-t


for i in range(2,n):
    t=int(input())
 
    maxtt = max(t-mint, maxtt)
    mint = min(t, mint)
    # if t-mint>maxtt: maxtt=t-mint
    # if t<mint: mint=t
    
print(int(maxtt))   


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

using namespace std;

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

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    int h;
    cin >> h;
    if (h >= K) cnt++;
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m = (int(x) for x in input().split())

if n<=1:
  if m<=1:
    print(0)
  else:
    print(comb(m, 2))
elif m<=1:
  print(comb(n, 2))
else:
  print(comb(n, 2)+comb(m, 2))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
long long f(long long a){
  long long ans = 0;
  for (long long i = a / 4 * 4; i <= a; i++){
    ans ^= i;
  }
  return ans;
}
int main(){
  long long A, B;
  cin >> A >> B;
  A--;
  long long ans = f(A) ^ f(B);
  cout << ans << endl;
}

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

int main() {
	int n;
	cin>>n;
	string s[n];
	for(int i=0;i<n;i++) cin>>s[i];
	bool k=1;
	for(int i=1;i<n;i++) {
		for(int j=0;j<i;j++) {
			if(s[j]==s[i]) {
				k=0;
				break;
			}
		}
		int l=s[i-1].length();l--;
		if(s[i-1][l]!=s[i][0]) {
			k=0;
			break;
		}
	}
	
	if(k) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
ans = [0] * (N+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n <= N:
                ans[n] += 1
print(*ans[1:], sep='\n')

Measured memory_bytes: 9508
{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE FlexibleContexts    #-}
{-# LANGUAGE RankNTypes          #-}
{-# LANGUAGE ScopedTypeVariables #-}
import           Control.Monad
import           Control.Monad.State
import qualified Data.ByteString.Char8        as BS
import           Data.Char
import qualified Data.Vector.Unboxing         as VU
import qualified Data.Vector.Unboxing.Mutable as VUM

main :: IO ()
main = do
  n <- readLn :: IO Int
  avec <- readLnAsUVecWith unconsInt n
  let setwise = VU.foldl1' gcd avec

  putStrLn $ if VU.null $ VU.filter (>1) $ solve avec
             then "pairwise coprime"
             else if setwise == 1 then "setwise coprime" else "not coprime"

solve :: VU.Vector Int -> VU.Vector Int
solve avec = VU.create $ do
  let sv = sieve (10^6+5)
  counts <- VUM.replicate (10^6+5) 0
  VU.forM_ avec $ \a -> do
    let ps = map fst $ factorize sv a
    forM_ ps $ \p -> do
      c <- VUM.read counts p
      VUM.write counts p (c+1)

  return counts

-- 添字の数字の最初の素因数（Smallest Prime Factor, SPF）を格納した配列を作る(Eratosthenesの篩)
-- もし添字の数字と格納されている数が等しければ、素数
sieve :: Int -> VU.Vector Int
sieve n = VU.create $ do
  vec <- VUM.replicate (n+1) 0
  VUM.write vec 1 1
  forM_ [2..n] $ \i -> do
    b <- VUM.read vec i
    when (b == 0) $ do
      VUM.write vec i i
      forM_ [i*i,(i+1)*i..n] $ \j -> do
        c <- VUM.read vec j
        when (c == 0) $ VUM.write vec j i
  return vec


type Prime = Int
type Factor = Int

-- 予め作っておいたSPF配列を渡して、素因数分解を行う
factorize :: VU.Vector Int -> Int -> [(Prime,Factor)]
factorize sv n = go 1 (sv VU.! n) (n `div` sv VU.! n)
  where go _ 0 _ = []
        go _ 1 _ = []
        go a p m
          | m == 1 = [(p,a)]
          | otherwise = let m' = sv VU.! m
                        in if p == m'
                           then go (a+1) p (m`div`m')
                           else (p, a) : go 1 m' (m`div`m')


unconsInt :: StateT BS.ByteString Maybe Int
unconsInt = StateT $ BS.readInt . BS.dropWhile isSpace

readLnAsUVecWith :: VU.Unboxable a => StateT BS.ByteString Maybe a -> Int -> IO (VU.Vector a)
readLnAsUVecWith !st !n = VU.unfoldrN n (runStateT st) <$> BS.getLine


Measured memory_bytes: 48572
n = int(input())
As = list(map(int, input().split()))

if n%2 == 0:
    inds = list(range(n-1,0,-2)) + list(range(0,n,2))
else:
    inds = list(range(n-1,-1,-2)) + list(range(1,n,2)) 

Bs = [As[i] for i in inds]
print(*Bs)

Measured memory_bytes: 26744
#include <stdio.h>

int main(void)
{
	int i, n;
	int a, b, c;
	scanf("%d", &n);

	for(i=0; i<n; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		     if(a*a + b*b == c*c)puts("YES");
		else if(a*a + c*c == b*b)puts("YES");
		else if(b*b + c*c == a*a)puts("YES");
		else puts("NO");
	}
	return 0;
}

Measured memory_bytes: 580
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
if(0 in a):
  print(0)
  exit()
  
for i in range(1, n):
  ans *= a[i]
  if(ans > 1000000000000000000):
    print(-1)
    exit()
  
print(ans)



Measured memory_bytes: 21636
Module _20191116

    Sub Main()
        'https://atcoder.jp/contests/abc108/tasks/abc108_a

        Dim iNumber As Integer = Console.ReadLine()

        Dim iKisuuCount As Integer = 0
        Dim iGusuuCount As Integer = 0

        For i As Integer = 1 To iNumber

            If i Mod 2 = 0 Then
                iGusuuCount += 1
            Else
                iKisuuCount += 1
            End If

        Next

        Console.WriteLine(iGusuuCount * iKisuuCount)

    End Sub

End Module

Measured memory_bytes: 11220
program atcoder
    implicit none
    integer :: N, i00, i01, counter, devide
    integer, allocatable :: a(:)

    read *, N
    allocate(a(N))
    read *, (a(i00), i00 = 1, N )
    counter = 0

    do i00 = 1, 1000
        devide = 0
        do i01 = 1, N
            if(mod(a(i01), 2) == 0) then
                devide = devide + 1
            end if
        end do
        if(devide == N) then
            counter = counter + 1
            do i01 = 1, N
                a(i01) = a(i01)/2
            end do
        else
            exit
        end if
    end do

    print '(i0)', counter
    deallocate(a)


end program atcoder


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long

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

signed main() {
  int n, k;
  cin >> n >> k;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int maxi = 0;
  for (int i = 0; i < n; i++) {
    maxi = max(maxi, a[i]);
  }
  if (k > maxi) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  if (n == 1) {
    if (a[0] == k) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  int g = gcd(a[0], a[1]);
  for (int i = 2; i < n; i++) {
    g = gcd(g, a[i]);
  }
  if (k % g == 0) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define cst(x) cout<<fixed<<setprecision(x)
#define pi 3.14159265359
#define mod 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
using pint = pair<int,int>;

int main(){

    int n,m; cin >> n >> m;
    vector<int> ab(n);
    rep(i,m){
        int a,b; cin >> a >> b;
        --a;--b;
        ++ab.at(a);++ab.at(b);
    }
    rep(i,n){
        if(ab.at(i)%2){
            cno;
            return 0;
        }
    }
    cyes;
    return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr ll INF = 1ll << 55;

template <typename T> inline constexpr bool chmin(T &a, T b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> inline constexpr bool chmax(T &a, T b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}
template <typename ite>
void print_ite(ite start, ite end, char sp = ' ', char en = '\n') {
  for (auto i = start; i != end; i++)
    cout << *i << sp;
  cout << en;
}
template <typename ite> void scan_ite(ite start, ite end) {
  for (auto i = start; i != end; i++)
    cin >> (*i);
}
inline void Yes(bool condition) { cout << (condition ? "Yes\n" : "No\n"); }

struct Edge {
  int to;
  ll time;
  ll cost;
};

int main() {
  int n, m;
  ll s;
  cin >> n >> m >> s;
  vector<Edge> Graph[n];
  for (int i = 0; i < m; i++) {
    int u, v, a;
    ll b;
    cin >> u >> v >> a >> b;
    u--, v--;
    Graph[u].push_back(Edge{v, b, -a});
    Graph[v].push_back(Edge{u, b, -a});
  }
  for (int i = 0; i < n; i++) {
    ll c, d;
    cin >> c >> d;
    Graph[i].push_back(Edge{i, d, c});
  }
  // cerr << "Input OK\n";
  vector<vector<ll>> dp(n, vector<ll>(2600, INF));
  priority_queue<tuple<ll, ll, int>, vector<tuple<ll, ll, int>>,
                 greater<tuple<ll, ll, int>>>
      pq;
  pq.push(make_tuple(0, min(s, 2510ll), 0));
  while (!pq.empty()) {
    auto t = pq.top();
    pq.pop();
    ll time = get<0>(t);
    ll coin = get<1>(t);
    int idx = get<2>(t);
    // cerr << time << ' ' << coin << ' ' << idx << '\n';
    if (coin > 2510) {
      pq.push(make_tuple(time, 2510, idx));
      continue;
    }
    if (dp[idx][coin] <= time) {
      continue;
    }
    dp[idx][coin] = time;
    for (auto e : Graph[idx]) {
      if (coin + e.cost >= 0) {
        pq.push(make_tuple(time + e.time, coin + e.cost, e.to));
      }
    }
  }
  for (int i = 1; i < n; i++) {
    ll ans = INF;
    for (auto j : dp[i])
      chmin(ans, j);
    cout << ans << '\n';
  }
}


Measured memory_bytes: 16192
#include<stdio.h>
int main(void)
{
  int n,x,count,i,j,k;

  scanf("%d %d",&n,&x);

  while(n!=0 || x!=0){
    count=0;

    for(i=1;i<=n-2;i++)
    for(j=i+1;j<=n-1;j++)
    for(k=j+1;k<=n;k++)
      if(i+j+k == x)count++;

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

    scanf("%d %d",&n,&x);
  }

  return 0;
}

Measured memory_bytes: 1812
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
using namespace std;

int main() {
    int n;
    string s[100];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    bool flag = 1;
    for (int i = 1; i < n; i++) {
        if (s[i][0] != s[i-1][s[i-1].size() - 1]) flag = 0;
        for (int j = 0; j < i; j++) {
            if (s[i] == s[j]) flag = 0;
        }
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}
    


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);  
	cin.tie(NULL);
	string s,t;
	cin>>s>>t;
	int n = s.length();
	int ans=0;
	for(int i=0;i<n;i++){
		if(s[i]!=t[i]){
			ans++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3820
def main():
    s = input()
    lst = ["AKIHABARA",
           "KIHABARA", "AKIHBARA", "AKIHABRA", "AKIHABAR",
           "KIHBARA", "KIHABRA", "KIHABAR", "AKIHBRA", "AKIHBAR", "AKIHABR",
           "KIHBRA", "KIHBAR", "KIHABR", "AKIHBR",
           "KIHBR"]

    if s in lst:
        print("YES")
    else:
        print("NO")


if __name__ == "__main__":
    main()


Measured memory_bytes: 61764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
#include <numeric>
#include <queue>
#include <map>
#include <cstdint>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long int ll;
typedef pair<ll, ll> P;
const vector<int> di = { -1, 0, 1, 0 };
const vector<int> dj = { 0, 1, 0, -1 };
const double PI = 3.14159265358979323846;

int main() {

	ll n;
	cin >> n;
	vector<ll> a(n);
	deque<ll> b;
	if (n % 2 == 0) {
		rep(i, n) {
			cin >> a.at(i);
			if (i == 0) {
				b.push_back(a.at(i));
			}
			else if (i % 2 == 0) {
				b.push_back(a.at(i));
			}
			else if (i % 2 != 0) {
				b.push_front(a.at(i));
			}
		}
	}
	else if (n % 2 != 0) {
		rep(i, n) {
			cin >> a.at(i);
			if (i == 0) {
				b.push_back(a.at(i));
			}
			else if (i % 2 == 0) {
				b.push_front(a.at(i));
			}
			else if (i % 2 != 0) {
				b.push_back(a.at(i));
			}
		}
	}
	

	rep(i, n) {
		cout << b.at(i) << ' ' ;
	}

   
	return 0;
	
}



Measured memory_bytes: 5376
/*
このコード、と～おれ!
Be accepted!
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printfin(a) printf(a ? "possible\n" : "inposible\n")
#define all(x) (x).begin(), (x).end()
using ll = long long;

//マクロとかここまで

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

int main() {
	
	char str[100001];
	bool alpha['z' - 'a' + 1] = {};
	scanf("%s", str);
	string s = str, ans = "None";
	rep(i, s.length()) {
		alpha[s[i] - 'a'] = true;
	}
	rep(i, 'z' - 'a' + 1) {
		if (alpha[i] == false) {
			ans = char(i + 'a');
			break;
		}
	}
	printf("%s\n", ans.c_str());
	


	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,T;
  cin >> N >> T;
  vector<pair<int,int>> v;
  for (int i=0;i<N;i++){
    int x,y;
    cin >> x >> y;
    v.push_back(make_pair(y,x));
  }
  sort(v.begin(),v.end());
  int ans=1010;
  for (int i=0;v[i].first<=T&&i<N;i++){
    ans=min(ans,v[i].second);
  }
  if (ans<=1000){ 
    cout << ans << endl;
  }
  else {
    cout << "TLE" << endl;
  }
}

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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  int Ans;
  if (K <= A) {
    Ans = K;
    cout << Ans << endl;
  }
  else if (A < K && K <= A+B) {
    Ans = A;
    cout << Ans << endl;
  }
  else if (A+B < K && K <= A+B+C) {
    Ans = A - (K-A-B);
    cout << Ans << endl;
  }
}


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

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		double xa, ya, ra, xb, yb, rb;
		cin >> xa >> ya >> ra >> xb >> yb >> rb;
		double d = sqrt((xb - xa) * (xb - xa) + (yb - ya) * (yb - ya));
		if (rb > ra && d < rb - ra){
			cout << -2 << endl;
		}
		else if (ra > rb && d < ra - rb){
			cout << 2 << endl;
		}
		else if (d > ra + rb){
			cout << 0 << endl;
		}
		else{
			cout << 1 << endl;
		}
	}
	return 0;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e19;
//const int INF=(1<<30);

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

  vector<int> x(N),y(N);
  vector<int> xaxis(N),yaxis(N);


  REP(i,N){
    cin >> x[i] >> y[i];
    xaxis[i] = x[i];
    yaxis[i] = y[i];
  }

  sort(ALL(xaxis));
  sort(ALL(yaxis));

  ll ans = INF;

  REP(xi,N)REP(xj,N)REP(yi,N)REP(yj,N){
    int lx,rx,ly,ry;
    lx=xaxis[xi]; rx=xaxis[xj];
    ly=yaxis[yi]; ry=yaxis[yj];

    int cnt=0;
      REP(i,N){
        if(lx <= x[i] && x[i] <= rx && ly <= y[i] && y[i] <= ry)cnt++;
      }
      if(cnt >= K){
        ans = min(ans, 1LL*(rx-lx)*(ry-ly));
      }
  }

  cout << ans << endl;

}



Measured memory_bytes: 384
H,W=[int(c) for c in input().split()];
a=[H*(W//3),(H//2)*(W-W//3),(H-H//2)*(W-W//3)];
b=[W*(H//3),(W//2)*(H-H//3),(W-W//2)*(H-H//3)];
c=[W*((H+2)//3),(W//2)*(H*2//3),(W-W//2)*(H*2//3)];
d=[H*((W+2)//3),(H//2)*(W*2//3),(H-H//2)*(W*2//3)];
print(min((H%3!=0)*W,(W*3!=0)*H, max(a)-min(a),max(b)-min(b),max(c)-min(c),max(d)-min(d)));



Measured memory_bytes: 3064
#include <iostream>      // cout, endl, cin
#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;

int main()
{
  long long a, b, c;
  cin >> a >> b >> c;
  if(c-a-b>0 && 4*a*b<(c-a-b)*(c-a-b)){
    cout << "Yes";
  
  }
  else
    cout << "No";
}


Measured memory_bytes: 3640
#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<set<int>>in(n+1), out(n+1);
  for(int i=0; i<n+m-1; i++){
    int a, b;
    cin >> a >> b;
    in[b].insert(a);
    out[a].insert(b);
  }
  vector<int>ret(n+1, 0);
  for(int i=1; i<=n; i++){
    if(in[i].size()==0){
      out[0].insert(i);
      in[i].insert(0);
      ret[i]=0;
      break;
    }
  }
  queue<int>Q;
  Q.push(0);
  while(!Q.empty()){
    int p=Q.front();
    Q.pop();
    for(int i: out[p]){
      in[i].erase(p);
      if(in[i].size()==0){
        ret[i]=p;
        Q.push(i);
      }
    }
  }
  for(int i=1; i<=n; i++)cout << ret[i] << endl;
  return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    A.at(a-1)++;
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  int cnt = 0, ans = 0;
  for (int i = 0; i < N; i++) {
    if (cnt < K && A.at(i) != 0) {
      cnt++;
      continue;
    }
    if (A.at(i) != 0) ans += A.at(i);
  }
  cout << ans << endl;
}

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

# define mp make_pair
# define pb push_back
# define PI acos(-1)
# define ff first 
# define ss second 
# define endl '\n'
# define vt vector
# define all(c) (c).begin(), (c).end()
# define REP(i,a,b) for(int i = a ; i <= b ; ++i) 
# define Rep(i,a,b) for(int i = a ; i < b ; ++i) 
# define Rrep(i,a,b) for(int i = b ; i >= a ; --i) 
# define FOR(i,b) for(int i = 0 ; i <= b ; ++i)
# define For(i,b) for(int i = 0 ; i < b ; ++i)
# define Rfor(i,b) for(int i = b ; i >= 0 ; --i)

typedef long long ll ; 
typedef long double ld ; 
typedef pair<int,int> pii ; 
typedef pair<ll,ll> pll ;

const ll inf = 1e18 ; 
const int MxN = 200005; 
const int mod = 1e9+7 ; 

void pe(int a) { cout << a << "\n" ; }
void pe(ll a) {	cout << a << "\n" ; }
void pe(string a) {	cout << a << "\n" ; }
void ps(int a) {	cout << a << ' ' ; }
void umax(int &a,int &b) { a = max(a,b); } ; 
void umax(ll &a , ll &b) {a = max(a,b);} ; 
void umin(int &a,int &b) { a = min(a,b);} ; 
void umin(ll &a , ll &b) {a = min(a,b);} ; 

ll nCr(ll n,ll r){
	ll res=1;
	if(r>n) return 0;
	if(r>n-r) r=n-r;
	for(ll i=0;i<r;i++) {
		res*=(n-i);
		res/=(i+1);
	}
	return res;
}




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

	string s ; 
	cin >> s; 
	int cnt = 0 ; 
	int ans = 0; 
	For(i,s.size()) {
		if(s[i]=='R') 
			++cnt ; 
		else {
			ans = max(ans,cnt) ;
			cnt = 0 ; 
		}
	}
	pe(max(ans,cnt)) ; 
	return 0 ; 	
}




Measured memory_bytes: 3612
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n = int(input())
    p = sieve_of_eratosthenes(55555)
    res = []
    for i in p:
        if i % 5 == 3:
            res.append(i)
    print(*res[:n],sep = " ")
if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 5688
#include<stdio.h>

int main(){

    int i, j, W, H;

    while(1){
	    scanf("%d %d", &W, &H);
	    if ((W == 0) && (H == 0)) {
	    	break;
	    }
	    for ( i = 0 ; i < W ; i++ ) {
	    	for ( j = 0 ; j < H ; j++ ) {
	    		if ((i + j)%2 == 0) {
		    		printf("#");
	    		} else {
	    			printf(".");
	    		}
	    	}
		    printf("\n");
	    }
	    printf("\n");
	}
    return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
int main() {
    int n;
    cin >> n;
    unordered_map<ll, ll> mp;
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        mp[x]++;
        ans += x;
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        ll b, c;
        cin >> b >> c;
        ll tmp = mp[b];
        mp[b] = 0;
        mp[c] += tmp;
        ans -= tmp * b;
        ans += tmp * c;
        cout << ans << endl;
    }
}

Measured memory_bytes: 7104
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define inf  1000000000
#define mod  1e9+1
#pragma GCC optimization ("O3")
using namespace std;
const long long int N = 6999999;
#define all(x) begin(x),end(x)
int main()
{
 
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n,c =0;
  cin >> n;
  vector <int> v(n),sv(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> v[i];
    sv[i] = v[i];
  }
  sort(sv.begin(),sv.end());
  for (int i = 0; i < n; ++i)
  {
    if(v[i] != sv[i])
    {
      c++;
    }
  }
  if(c > 2)
    cout << "NO";
  else
    cout << "YES";
  return 0;
} 


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
	int a, b, c, d, s;
	cin >> s;
	a = s / 1000;
	b = s % 1000; b /= 100;
	c = s % 100; c /= 10;
	d = s % 10;
	if (a + b - c - d == 7)cout << a << '+' << b << '-' << c << '-' << d << "=7" << endl;
	else if (a - b + c - d == 7)cout << a << '-' << b << '+' << c << '-' << d << "=7" << endl;
	else if (a - b - c + d == 7)cout << a << '-' << b << '-' << c << '+' << d << "=7" << endl;
	else if (a + b + c - d == 7)cout << a << '+' << b << '+' << c << '-' << d << "=7" << endl;
	else if (a - b + c + d == 7)cout << a << '-' << b << '+' << c << '+' << d << "=7" << endl;
	else if (a + b - c + d == 7)cout << a << '+' << b << '-' << c << '+' << d << "=7" << endl;
	else if (a + b + c + d == 7)cout << a << '+' << b << '+' << c << '+' << d << "=7" << endl;
	else cout << a << '-' << b << '-' << c << '-' << d << "=7" << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	private void doit() {
		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int [] freq = new int[10];
			while(n-- > 0){
				freq[sc.nextInt()]++;
			}
			for(int i = 0; i < 10; i++){
				if(freq[i] == 0){
					System.out.println("-");
				}
				else{
					for(int j = 0; j < freq[i]; j++){
						System.out.print("*");
					}
					System.out.println();
				}
			}
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

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

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> c(m);
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
    }
    const int INF = 1 << 30;
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            if (j + c[i] <= n) dp[i + 1][j + c[i]] = min(dp[i + 1][j + c[i]], dp[i + 1][j] + 1);
        }
    }
    cout << dp[m][n] << endl;
}


Measured memory_bytes: 7044
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x, y, a, b, c ;
  cin >> x >> y >> a >> b >> c ;
  vector<ll> r(a);
  vector<ll> g(b);
  vector<ll> m(c);
  REP(i,a){
    cin >> r[i] ;
  }
  REP(i,b){
    cin >> g[i] ;
  }
  REP(i,c){
    cin >> m[i] ;
  }
  ll ans = 0 ;
  sort(ALL(r)) ;
  sort(ALL(g)) ;
  sort(ALL(m)) ;
  reverse(ALL(r)) ;
  reverse(ALL(g)) ;
  priority_queue<ll, vector<ll>, greater<ll>> eat;
  REP(i,x){
    eat.push(r[i]) ;
  }
  REP(i,y){
    eat.push(g[i]) ;
  }
  REP(i,c){
    ll k ;
    k = eat.top() ;
    if(m[i]>=k){
      eat.pop() ;
      eat.push(m[i]) ;
    }
  }
  REP(i,x+y){
    ll a ;
    a = eat.top() ;
    ans += a ;
    eat.pop() ;
  }
  cout << ans <<endl ;
      
      

  
  return 0 ;
}



Measured memory_bytes: 4852
#include <iostream>
using namespace std;
int main(void){
    int h1, h2; //浩(hiroshi)が釣ったイワナとヤマメの数
    int k1, k2; //健次郎が釣ったイワナとヤマメの数
    int a, b, c, d; //得点：a点/匹、b点/匹、c点/10匹、d点/10匹

    cin >> h1 >> h2;
    cin >> k1 >> k2;
    cin >> a >> b >> c >> d;

    int h_score, k_score; //浩と健次郎の得点
    h_score = a * h1 + b * h2 + c * (h1 / 10) + d * (h2 / 20);
    k_score = a * k1 + b * k2 + c * (k1 / 10) + d * (k2 / 20);

    if(h_score > k_score) 
        cout << "hiroshi" << endl;
    else if(h_score < k_score) 
        cout << "kenjiro" << endl;
    else    
        cout << "even" << endl;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int a,b,c,k;
	cin >> a >>b >>c >>k;
	
	ll mx = max({a,b,c});
	ll zn = a+b+c-mx;
	rep(i,k) mx *=2;
	cout << mx + zn<<"\n";
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;

struct Cards{
    string card;
    char suit;
    int value;
    int num;
};

void bubbleSort(Cards c[], int n){
    for(int i=0; i<n; i++){
        for(int j=n-1; j>i; j--){
            if(c[j].value<c[j-1].value) swap(c[j],c[j-1]);
        }
    }

    for(int i=0; i<n; i++){
        cout<<c[i].card;
        if(i!=n-1) cout<<" ";
    }
    cout<<endl;
    cout<<"Stable"<<endl;
}

void selectionSort(Cards c[], int n){
    for(int i=0; i<n; i++){
        int minj = i;
        for(int j=i; j<n; j++){
            if(c[j].value<c[minj].value) minj=j;
        }
        swap(c[i],c[minj]);
    }
    int flag=0;
    for(int i=0; i<n-1; i++){
        if(c[i].value==c[i+1].value){
            if(c[i].num>c[i+1].num){
                flag=1;
                break;
            }
        }
    }
    for(int i=0; i<n; i++){
        cout<<c[i].card;
        if(i!=n-1) cout<<" ";
    }
    cout<<endl;
    if(flag==0){
        cout<<"Stable"<<endl;
    }else{
        cout<<"Not stable"<<endl;
    }
}

int main(){
    int n;
    cin>>n;
    Cards a[n],b[n];
    for(int i=0; i<n; i++){
        cin>>a[i].card;
        a[i].suit=a[i].card[0];
        a[i].value=(unsigned char)(a[i].card[1]-'0');
        a[i].num=i;
        b[i]=a[i];
    }
    bubbleSort(a,n);
    selectionSort(b,n);
    return 0;
}


Measured memory_bytes: 3228
#include <stdio.h>

int main(void) {
	int d_num,d_cur;
	int card_num[3][10];
	int nums[9];
	char colors[9][4];
	int i;
	int ok;
	scanf("%d",&d_num);
	for(d_cur=0;d_cur<d_num;d_cur++) {
		for(i=0;i<9;i++)scanf("%d",&nums[i]);
		for(i=0;i<9;i++)scanf("%s",colors[i]);
		for(i=0;i<10;i++) {
			card_num[0][i]=card_num[1][i]=card_num[2][i]=0;
		}
		for(i=0;i<9;i++) {
			card_num[colors[i][0]=='R'?0:colors[i][0]=='G'?1:2][nums[i]]++;
		}
		for(i=2;i<10;i++) {
			while(card_num[0][i-2] && card_num[0][i-1] && card_num[0][i]) {
				card_num[0][i-2]--;card_num[0][i-1]--;card_num[0][i]--;
			}
			while(card_num[1][i-2] && card_num[1][i-1] && card_num[1][i]) {
				card_num[1][i-2]--;card_num[1][i-1]--;card_num[1][i]--;
			}
			while(card_num[2][i-2] && card_num[2][i-1] && card_num[2][i]) {
				card_num[2][i-2]--;card_num[2][i-1]--;card_num[2][i]--;
			}
		}
		for(i=0;i<10;i++) {
			card_num[0][i]%=3;
			card_num[1][i]%=3;
			card_num[2][i]%=3;
		}
		ok=1;
		for(i=0;i<10;i++) {
			if(card_num[0][i])ok=0;
			if(card_num[1][i])ok=0;
			if(card_num[2][i])ok=0;
		}
		printf("%d\n",ok);
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define Would
#define you
#define please

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

	int A, B;
	cin >> A >> B;
	int black = 0;
	if (A > B) black = 1;

	int amime = min(A, B) - 1;
	int tenten = abs(A - B);

	int grid[100][100] = {};

	rep(i, 88) grid[78][i] = 1;
	rep(i, 44) grid[77][2 * i] = 1;

	for (int ii = 76; ii > 0; ii--) {
		if (ii % 2 == 0) {
			rep(i, ii / 2) {
				if (amime) {
					grid[ii][2 * i + 1] = 1;
					amime--;
				}
			}
		}
		else {
			rep(i, ii / 2 + 1) {
				if (amime) {
					grid[ii][2 * i] = 1;
					amime--;
				}
			}
		}
	}
	for (int ii = 1; ii < 78; ii += 2) {
		rep(i, 88 - ii) {
			if (amime) {
				grid[i][i + ii] = 1;
				amime--;
			}
		}
	}

	for (int ii = 81; ii < 100; ii += 2) {
		for (int i = 0; i < 100; i += 2) {
			if (tenten) {
				grid[ii][i] = 1;
				tenten--;
			}
		}
	}
	
	cosp(100);
	co(100);
	rep(i, 100) {
		rep(ii, 100) {
			if ((black + grid[ii][i]) % 2) {
				cout << "#";
			}
			else {
				cout << ".";
			}
		}
		cout << "\n";
	}
	Would you please return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n; cin >> n;
  cout << (n-1)/2 << "\n";
  return 0;
}


Measured memory_bytes: 3648
# coding: utf-8

class Proc:
    def __init__(self):
        (n, m) = [int(i) for i in input().rstrip().split(" ")]
        self.switch_count = n
        self.light_count = m
        self.light_connect = [[int(i) - 1 for i in input().rstrip().split(" ")][1:] for j in range(m)]
        self.light_setting = [int(i) for i in input().rstrip().split(" ")]

    def get_ans(self, index: int, subtotal: int):
        if index >= self.switch_count:
            light_connect_count = [0 for i in range(self.light_count)]
            for i in range(0, self.switch_count):
                if ((1 << i) & subtotal) == 0:
                    continue
                for j in range(self.light_count):
                    if i in self.light_connect[j]:
                        light_connect_count[j] += 1
            if all([light_connect_count[i] % 2 == self.light_setting[i] for i in range(self.light_count)]):
                return 1
            else:
                return 0

        ret = self.get_ans(index + 1, subtotal) + self.get_ans(index + 1, subtotal + (1 << index))
        return ret


print(Proc().get_ans(0, 0))


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,K;
string S;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	
	char mi=*min_element(ALL(S));
	
	string R="{";
	FOR(i,N) if(S[i]==mi) {
		int cnt=0;
		FOR(cnt,N) if(i+cnt==N || S[i+cnt]!=mi) break;
		
		string T=S.substr(i,cnt);
		if(i+cnt==N) {
			FOR(j,K) {
				T=T+T;
				if(T.size()>=N) break;
			}
			x=i-1;
			while(T.size()<N) {
				if(x>=0) T+=S[x];
				else T+=S[-x+1];
				x--;
			}
		}
		else {
			FOR(j,K-1) {
				T=T+T;
				if(T.size()>=N) break;
			}
			x=i+cnt;
			while(T.size()<N) {
				if(x<N) T+=S[x];
				else T+=S[2*N-1-x];
				x++;
			}
		}
		if(T.size()>N) T.resize(N);
		R=min(R,T);
		
	}
	
	
	
	cout<<R<<endl;
	
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <chrono>
#include <random>
#include <unordered_map>
#include <cassert>
#pragma GCC optimize("O3")
#pragma comment(linker, "STACK:36777216")
using namespace std;
using i64 = int64_t;
constexpr i64 MOD = 1e9 + 7;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
using vi = vector<i64>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ii = pair<i64, i64>;

vi a[3] = {{1,3,5,7,8,10,12}, {4,6,9,11}, {2}};

int find(int k) {
    for (int i = 0; i < 3; i++) {
        for (auto j: a[i]) {
            if (j == k) return i;
        }
    }
    exit(1);
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << (find(x) == find(y) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 384
N,K=map(int, raw_input().split())
 
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1,N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

can_zero_num=min(N-1,K)
ans=0
for zero_num in range(can_zero_num+1):
    ans+=ncr(N,zero_num)*ncr(N-1,N-zero_num-1)

print ans%mod

Measured memory_bytes: 63772