akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    a=a+b;
    if(a%2==0){
        a=a/2;
        printf("%d",a);

    }
    else if(a%2!=0){
        a=(a/2)+1;
        printf("%d",a);
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define SZ(x) ((int)(x.size()))
#define FOR(i,s,n) for (ll i = (s); (i) < (n); ++i)
#define FORD(i,s,l) for (ll i = (s); (i) >= l; --i)
#define F first
#define S second
#define TC int __tc; cin >> __tc; FOR(case_num,1,__tc+1)
#define TEST(x,i) ((x)&(1ll<<(i)))
#define SET(x,i) ((x)|(1ll<<(i)))
#define FLIP(x,i) ((x)^(1ll<<(i)))
#define CLEAR(x,i) ((x)&~(1ll<<(i)))


const double pi = 4*atan(1);
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;
const int MAXN = 200005;

int num[MAXN];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	FOR(i,0,n){
		cin >> num[i];
	}

	map<int,int> cnt1;
	map<int,int> cnt2;

	for(int i = 0; i < n; i+=2){
		cnt1[num[i]]++;
	}

	for(int i = 1; i < n; i+=2){
		cnt2[num[i]]++;
	}

	vector<pair<int,int>> c1;
	vector<pair<int,int>> c2;

	for (auto &p : cnt1){
		c1.push_back({-p.S,p.F});
		sort(c1.begin(),c1.end());
		while(c1.size() > 2) {
			c1.pop_back();
		}
	}

	for (auto &p : cnt2){
		c2.push_back({-p.S,p.F});
		sort(c2.begin(),c2.end());
		while(c2.size() > 2) {
			c2.pop_back();
		}
	}

	c1.pb({0,-1});
	c2.pb({0,-2});

	int best = 1000000;

	for (auto &p : c1){
		for(auto &p2 : c2){
			if (p.S != p2.S){
				best=min(best,n+p.F+p2.F);
			}
		}
	}

	cout << best << "\n";

}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define print(x) cout << x << endl;
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;

int val[201010];

void dfs(const Graph &G, int v, int p = -1) {
    for (auto nv : G.at(v)) {
        if (p != nv) {
            val[nv] += val[v];
            dfs(G, nv, v);
        }
    }
}

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

    Graph G(N);
    rep(i, N - 1) {
        cin >> a >> b;
        a--; b--;
        G.at(a).push_back(b);
        G.at(b).push_back(a);
    }

    for (int i = 0; i < Q; i++) {
        int p, x;
        cin >> p >> x;
        p--;
        val[p] += x;
    }

    dfs(G, 0);

    rep(i, N) {
        if (i) cout << " ";
        cout << val[i];
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 26624
// ※※※ 解答不能(long long型, int型 の 差分でも, AC／WA が 分かれるので注意(自戒)) ※※※
// TangentDay氏.
// https://atcoder.jp/contests/abc149/submissions/9216415
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VL = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define ALL(c) (c).begin(), (c).end()

int main(){
    LL n, m;
    scanf("%lld %lld", &n, &m);
    VL a(n);
    rep(i, n) scanf("%d", &a[i]);
    sort(ALL(a));
    reverse(ALL(a));
    LL ok = 0, ng = 1e6;
    while(ng - ok > 1){
        LL x = (ok + ng) / 2;
        LL s = 0;
        int j = n - 1;
        rep(i, n){
            while(j >= 0 && a[i] + a[j] < x) j--;
            s += j + 1;
        }
        if(s >= m) ok = x;
        else       ng = x;
    }
    VL s(n + 1);
    rep(i, n) s[i + 1] = s[i] + a[i];
    LL c = 0, ans = 0;
    int j = n - 1;
    rep(i, n){
        while(j >= 0 && a[i] + a[j] < ok) j--;
        ans += (j + 1) * a[i] + s[j + 1];
        c += j + 1;
    }
    ans -= (c - m) * ok;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 1792
#!/usr/bin/env python3
import sys


def solve(a: int, b: int):
    print(sum([i for i in range(b-a)]) - a)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(a, b)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}

#[allow(unused)]
use std::cmp::{max, min};
#[allow(unused)]
use std::collections::HashMap;

#[allow(unused)]
fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}

#[allow(unused)]
fn lcm(x: i64, y: i64) -> i64 {
    x * y / gcd(x, y)
}

fn main() {
    input! {
        // usize
        // n: usize,
        // vec
        // v: [i64; n],
        a: f64,
        b: i64,
        t: f64,
    }

    if a > t {
        println!("0");
    } else {
        let ans = ((t + 0.5) / a) as i64;
        println!("{}", ans * b);
    }
}


Measured memory_bytes: 4352
use std::io;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::f64::consts::PI;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

fn func(l: usize, r: usize, vs: &Vec<i64>, k: usize) -> i64 {
    let n = vs.len();
    if l + n - r > k {
        return 0;
    }
    let mut que = BinaryHeap::new();
    let mut res = 0;
    for i in 0..l {
        if vs[i] >= 0 {
            res += vs[i];
        } else {
            que.push(-vs[i]);
        }
    }

    for i in r..n {
        if vs[i] >= 0 {
            res += vs[i];
        } else {
            que.push(-vs[i]);
        }
    }

    let mut count = k - l - (n - r);
    while count > 0 && !que.is_empty() {
        que.pop();
        count -= 1;
    }
    while !que.is_empty() {
        res -= que.pop().unwrap();
    }

    res
}


fn main() {
    let line: Vec<usize> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let n = line[0];
    let k = line[1];
    let vs: Vec<i64> = read_line().split_whitespace().map(|s| s.parse().unwrap()).collect();

    let mut ans = 0;
    for i in 0..n+1 {
        for j in (i..n+1).rev() {
            ans = cmp::max(ans, func(i, j, &vs, k));
        }
    }

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


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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

int main() {
	llong N, K;
	cin >> N >> K;
	if (K == 1)
		cout << 0 << endl;
	else
		cout << N- K << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	long x = sc.nextLong();
	long[] a = new long[N];
	for(int i = 0; i<N; i++) {
	    a[i] = sc.nextInt();
	}
	long ans = 0;
	for(int i = 1; i<N; i++) {
	    long sum = a[i]+a[i-1];
	    if(sum>x) {
		ans += sum-x;
		a[i] = Math.max(0, a[i]-(sum-x));
	    }
	}
	System.out.println(ans);
    }
}

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

int main(void){
	int n,c,i,o,r,p=0;
	int b[100][100]={0};
	scanf("%d%d",&n,&c);
	int *a;
	int memo[100]={0};
	a = calloc(c,sizeof(int));
	for(i=0;i<c;i++)
		scanf("%d",&a[i]);
	for(i=0;i<c;i++){
		for(o=0;o<n;o++){
			scanf("%d",&b[i][o]);
		}
		for(r=0;r<n;r++){
			if(a[i] == b[i][r]){
				memo[r]++;
				p++;
			}
		}
		memo[a[i]-1]+=n-p;
		p=0;

	}
	for(i=0;i<n;i++)
		printf("%d\n",memo[i]);
	return 0;
}

Measured memory_bytes: 648
import itertools
N = int(input())
F =[ list(input().split()) for i in range(N)]
P =[ list(input().split()) for i in range(N)]
set01 = list(itertools.product('01',repeat = 10))
counter = []
ans = -10**9
for s01 in set01:
    if s01 != ("0","0","0","0","0","0","0","0","0","0"):
        prof = 0
        for i in range(N):
            counter = 0
            for j in range(10):
                if s01[j] =="1" and F[i][j] == "1":
                    counter += 1
            prof += int(P[i][counter])
        ans = max(ans,prof)
print(ans)

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

typedef priority_queue<int> maxHeap;
typedef priority_queue<int, vector<int>, greater<int>> minHeap;
#define endl "\n"
#define int long long
#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
#define max(x, y) ((x > y) ? x : y)
#define min(x, y) ((x < y) ? x : y)
#define mid(s, e) ((s + (e - s) / 2))

bool test_cases;

void init(bool k) {
    test_cases = k;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

struct precompute {
    void compute() {
    }
};

int dp[101][100001];

struct test_cases {
    static int solvemax(int *wt, int *val, int i, int n, int wtleft) {
        if (i == n) {
            return 0;
        }

        if (dp[i][wtleft] != -1) return dp[i][wtleft];

        if (wtleft >= wt[i]) {
            int a1 = solvemax(wt, val, i + 1, n, wtleft);
            int a2 = val[i] + solvemax(wt, val, i + 1, n, wtleft - wt[i]);
            return dp[i][wtleft] = max(a1, a2);
        } else {
            int a1 = solvemax(wt, val, i + 1, n, wtleft);
            return dp[i][wtleft] = a1;
        }
    }

    void test_case() {
        int n, w;
        cin >> n >> w;
        memset(dp, -1, sizeof(dp));
        int val[n], wt[n];
        for (int i = 0; i < n; i++) {
            cin >> wt[i] >> val[i];
        }

        cout << solvemax(wt, val, 0, n, w) << endl;
    }
};

int32_t main() {
    init(false);
    int tc;
    if (test_cases) {
        cin >> tc;
    } else {
        tc = 1;
    }
    struct precompute l;
    l.compute();
    for (int i = 0; i < tc; i++) {
        struct test_cases o;
        o.test_case();
    }
    return 0;
};

Measured memory_bytes: 82564
#include<iostream>
#include<string.h>
#include<math.h>
#include<vector>
#include<algorithm>
#define lli long long int

using namespace std;
 
int main(){

for(int i=1;i<=5;i++)
{
	int x;
	cin>>x;
	if(x==0)
	{
		cout<<i;
		break;
	}
}
}






Measured memory_bytes: 3596
import java.util.Scanner;

public class Main{
    public static void main(String[]args){
        Scanner scn = new Scanner(System.in);
        
        int n = scn.nextInt();
        int m = scn.nextInt();
        int l = scn.nextInt();
        
        long [][]A = new long[n][m];
        long [][]B = new long[m][l];
        long [][]C = new long[n][l];
        
        read(n,m,A,scn);
        read(m,l,B,scn);
        
        
        for(int i=0;i<n;i++){
            for(int j=0;j<l;j++){
                for(int k=0;k<m;k++){
                    C[i][j]+=A[i][k]*B[k][j];
                }
            }
        }
        

        for(int i=0;i<n;i++){
            for(int j=0;j<l;j++){
                if(j==l-1){
                    System.out.print(C[i][j]+"\n");
                }else{
                    System.out.print(C[i][j]+" ");
                }                               
            }
        }        
        
    }
    
    private static void read(int a, int b, long[][] Ar,Scanner scn) {
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                Ar[i][j]=scn.nextInt();
            }
        }
    }
        
}

Measured memory_bytes: 47208
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		String S = sc.nextLine();

		char c = S.charAt(0);
		int N = S.length();
		List<Integer> bw = new ArrayList<>();
		int temp=0;
		for(int i=0;i<N;i++) {
			if(c == S.charAt(i)) {
				temp++;
			}else {
				bw.add(temp);
				temp=1;
				c = S.charAt(i);
			}
		}
		bw.add(temp);

		System.out.println(bw.size()-1);
	}
}


Measured memory_bytes: 26180
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int k,x;

int main(){
    cin>>k>>x;
    for(int i=-200000;i<=200000;i++){
        if(x-i+1<=k&&i-x+1<=k){
            printf("%d ",i);
        }
    }

}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 2019
#define test ll tx; cin>>tx; while(tx--)
typedef long long int ll;
int main() {
    FIO;
    //test
    {
      // Multiple of 2019
      string s;
      cin>>s;
      ll n,i,power_of_ten=1,sum=0,ans=0;
      n=s.length();
      map<ll,ll>mp;
      mp[0]=1;
      for(i=n-1;i>=0;i--){
         sum=(power_of_ten*(s[i]-'0') + sum)%mod;
         power_of_ten=(power_of_ten*10)%mod;
         ans+=mp[sum];
         mp[sum]++;
      }
      cout<<ans<<endl;
    }
	return 0;
}


Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define ll long long
#define PB push_back
#define MP make_pair

#define REP(i, n) for(int i=0;i<(int)(n);++i)
#define FOR(i,l,h) for(int i=(int)(l);i<=(int)(h);++i)
#define FORD(i,h,l) for(int i=(int)(h);i>=(int)(l);--i)

//#define max(a,b) a>b?a:b
//#define min(a,b) a>b?b:a

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

#define dump(x)  cerr << #x << " = " << (x) << endl
#define ALL(t) (t).begin(),(t).end()

using namespace std;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

int sum() { return 0; }

template<typename T, typename... Args>
T sum(T a, Args... args) { return a + sum(args...); }



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int temp;cin>>temp;
    if(temp >= 30) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define N 1111116
#define mod 1000000007

int n,a[N],d[N],h[N],g[N];
long long ans,f[N];
queue<int> q;

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();ans=1;
	for (int i=1;i<=n;i++) a[i]=read(),d[a[i]]++;
	for (int i=1;i<=n;i++) if (!d[i]) q.push(i);
	while (!q.empty()){
		int t=q.front();q.pop();
		if (h[a[t]]) ans=0;h[a[t]]=h[t]+1;
		if (--d[a[t]]==0) q.push(a[t]);
	}
	for (int i=1;i<=n;i++)
		if (d[i]){
			int t=i;vector<int> q;
			while (a[t]!=i&&!h[t]) t=a[t];
			while (d[t]){
				q.push_back(h[t]);
				d[t]=0;t=a[t];
			}
			if (!q[0]) g[q.size()]++;
			else {
				q.push_back(q[0]);
				for (int i=1,j=0;i<(int)q.size();i++)
					if (q[i]){
						if (q[i]<i-j) ans=ans*2%mod;
						if (q[i]>i-j) ans=0;
						j=i;
					}
			}
		}
	for (int i=1;i<=n;i++){
		f[0]=1;f[1]=(i>1&&i%2)+1;
		for (int j=2;j<=g[i];j++)
			f[j]=(f[j-1]*f[1]+f[j-2]*(j-1)*i)%mod;
		ans=(ans*f[g[i]])%mod;
	}
	printf("%lld\n",ans);return 0;
}

Measured memory_bytes: 9120
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

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

int table[510][510];
int sum[510][510];
int main(){
    int N,M,Q;
    cin >> N >> M >> Q;
    int l,r;
    int p,q;

    rep(i,M){
        cin >> l >> r;
        table[l][r]++;
    }
    rep(i,510){
        sum[i][0] = table[i][0]; 
        reps(j,1,510){
            sum[i][j] = sum[i][j-1] + table[i][j];
        }
    }

    ll tot;
    rep(i,Q){
        tot = 0;
        cin >> p >> q;
        reps(j,p,q+1){
            tot += (sum[j][q] - sum[j][p-1]);
        }
        cout << tot << endl;
    }

    return 0;
}

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

int main () {
    string S;
    cin >> S;
    int n = S.length();

    long long res = 0;
    for(int i = 0; i < (1 << (n - 1)); i++) {
        long long tmp = 0;
        for(int j = 0; j<n; j++) {
            tmp = tmp * 10 + S[j] - '0';
            if(i & (1 << j)) {
                res += tmp;
                tmp = 0;
            }
        }
        res += tmp;
    }
    printf("%ld", res);
}

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

int count(int n, int x){
  int cnt = 0;
  for (int i = 1; i <= n-2; i++) {
     for (int j = i+1; j <= n-1; j++) {
       for (int k = j+1; k <= n; k++) {
         if (i < j && j < k && i + j + k == x) cnt++;
       }
     }
  }
  return cnt;
}

int main(){
  while(1){
    int n, x;
    cin >> n >> x;
    if (n == 0 && x == 0) break;
    cout <<  count(n, x) << endl;
  }
return 0;
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define int long long

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)a, i##_len=(b); i<i##_len; i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

#define all(box) box.begin(), box.end()

using namespace std;

using P = pair<int,int>;
using ll = long long;

const long long INF = LLONG_MAX/3;

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

struct UnionFind{
	std::vector<int> par,siz;
	void init(int n){
		par.resize(n);
		for(int i=0;i<n;i++)par[i]=i;
		siz.resize(n,1);
	}
	UnionFind(int n){
		init(n);
	}
	int root(int n){
		if(par[n]==n)return n;
		else return par[n]=root(par[n]);
	}
	bool issame(int x,int y){
		return (root(x)==root(y));
	}
	bool marge(int a,int b){
		if(issame(a,b))return false;
		else{
			a=root(a),b=root(b);
			if(siz[a]<siz[b])swap(a,b);
			siz[b]+=siz[a];
			par[a]=par[b];
			return true;
		}
	}
	int size(int n){
		return siz[root(n)];
	}
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}
long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}

const int MOD=998244353;
long long fac[510000], finv[510000], inv[510000];
long long MAX=510000;
bool COMinited=false;
long long COM(int n, int k){
	if(COMinited==false){
		fac[0] = fac[1] = 1;
    	finv[0] = finv[1] = 1;
    	inv[1] = 1;
    	for (int 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;
    	}
		COMinited=true;
	}
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}
template< typename T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
signed main(){
	string s;
	cin>>s;
	int n=s.size();
	string a=s.substr(0,(n-1)/2);
	string b=a;
	reverse(a.begin(),a.end());
	string c=s.substr((n+3)/2-1,n-(n+3)/2+1);
	string d=c;
	reverse(c.begin(),c.end());
	string t=s;
	reverse(s.begin(),s.end());
	if(a==b&&c==d&&s==t)puts("Yes");
	else puts("No");
}


Measured memory_bytes: 256
// B.

#include <iostream>
#include <sstream>

using namespace std;

int main(int argc, char *argv[])
{
	char cnt[256] = {};
	string s;
	cin >> s;
	for (char c : s) {
		++cnt[c];
	}
	bool ans = true;
	for (int c = 'a'; c <= 'z'; ++c) {
		if (cnt[c] % 2) {
			ans = false;
		}
	}
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}


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

using namespace std;


typedef long long ll;

const ll mdl = 1e9 + 7;



int main() {

	ll n, k;
	cin >> n >> k;

	ll ans[n + 1][k + 1];
	ll a[n];
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i <= k; i++) {
		ans[1][i] = (i <= a[0]) ? 1 : 0;
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			if (j == 0)
				ans[i][j] = ans[i - 1][j];
			else {
				ans[i][j] = (mdl + ans[i][j - 1] + ans[i - 1][j] - ((j - 1 - a[i - 1] >= 0) ? ans[i - 1][j - 1 - a[i - 1]] : 0 )) % mdl;
			}
		}
	}

	cout << (ans[n][k] % mdl) << endl;

	return 0;

}


Measured memory_bytes: 81720
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,a,b = inm()
c = a+b
k = n//c
r = n%c
print(k*a + min(r,a))


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

int main() {
	int N, K; cin >> N >> K;
	int x[100010];
	for(int i=0; i<N; ++i) cin >> x[i];
	int S=314159265;
	for(int i=0; i<=N-K; ++i){
	    if(x[i]<0 && x[i+K-1]>0) S=min(S, x[i+K-1]-x[i]+min(abs(x[i]), x[i+K-1]));
	    else S=min(S, max(abs(x[i]), abs(x[i+K-1])));
	}
	cout << S << endl;
	return 0;
}


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


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

  vector<int> left(N);
  vector<int> right(N);
 
  for(int i = 0; i < N - 1; i++) {
     if(A[i] < left[i]) left[i + 1] = left[i];
     else left[i + 1] = A[i];
  }

  for(int i = N - 2; i >= 0; i--) {
    if(A[i + 1] < right[i + 1]) right[i] = right[i + 1];
    else right[i] = A[i + 1];
  }

  for(int i = 0; i < N; i++) {
    cout << max(left[i], right[i]) << endl;
  }

  return 0;
}

Measured memory_bytes: 4736
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	// table[i]: iで何回割り切れるか
	table := make([]int, n+1)

	for i := 2; i <= n; i++ {
		num := i
		for j := 2; j <= n; j++ {
			for num%j == 0 {
				num /= j
				table[j]++
			}
		}
	}

	ans := 1
	for _, v := range table {
		if v == 0 {
			continue
		}
		ans = (ans * (v + 1)) % 1000000007
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
    auto s = readln().split();
    assert(s.length == t.length);
    foreach(ref ti; t) {
        ti = s[0].to!(typeof(ti));
        s = s[1..$];
    }
}

class UnionFindTree {
public:
    this(size_t n) {
        parent = iota(n).array();
        rank = new size_t[](n);
    }
    size_t find(size_t n) {
        if(n == parent[n]) {
            return n;
        } else {
            parent[n] = find(parent[n]);
            return parent[n];
        }
    }
    void unite(size_t n, size_t m) {
        auto p1 = find(n);
        auto p2 = find(m);
        if(n == m) {
            return;
        }
        if(rank[p1] < rank[p2]) {
            swap(p1, p2);
        }
        if(rank[p1] == rank[p2]) {
            ++rank[p1];
        }
        parent[p2] = p1;
    }
private:
    size_t[] parent;
    size_t[] rank;
}
unittest {
    auto uft = new UnionFindTree(10);
    foreach(i; iota(10)) {
        assert(uft.find(i) == i);
    }
    foreach(i; iota(10).filter!(a => a%3 == 0).drop(1)) {
        uft.unite(i, i-3);
    }
    foreach(i; iota(10).filter!(a => a%3 == 0)) {
        assert(uft.find(0) == uft.find(i));
    }
    foreach(i; iota(10).filter!(a => a%3 != 0)) {
        assert(uft.find(0) != uft.find(i));
    }
}

const real eps = 1e-10;

const long p = 1_000_000_000 + 7;

void main(){
    auto s = readln().chomp();
    while(!s.empty()) {
        if(s.startsWith("dream")) {
            if(s.startsWith("dreamer")) {
                if(s.startsWith("dreamera")) {
                    s = s[5..$];
                } else {
                    s = s[7..$];
                }
                continue;
            } else {
                s = s[5..$];
                continue;
            }
        }
        if(s.startsWith("erase")) {
            if(s.startsWith("eraser")) {
                if(s.startsWith("erasera")) {
                    s = s[5..$];
                } else {
                    s = s[6..$];
                }
                continue;
            } else {
                s = s[5..$];
                continue;
            }
        }
        writeln("NO");
        return;
    }
    writeln("YES");
}



Measured memory_bytes: 2556
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define ff first
#define ss second
#define file_se_input  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define pp long long int
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define mp make_pair
#define pi 3.141592653589793238
#define eb emplace_back
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define zip(i,a,b) for(int i=a;i<b;i++)
#define rzip(i,a,b) for(int i=a;i>=b;i--)
#define ll unsigned long long int
#define test int t;cin>>t; while(t--)
#define um unordered_map
#define en '\n'
#define us unordered_set
typedef pair<int, int>     pii;
typedef pair<char, int>    pci;
typedef pair<char, char>   pcc;
typedef vector<pii>       vii;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define INF (1e18+5)
#define inf (1e9+5)
#define mod 1000000007


bool check_prime(long long n)
{
	int flag = 0;
	for (long long i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			flag = 1;
			break;
		}
	}
	if (n == 1)
		return false;
	else if (flag == 0 || n == 2 || n == 3)
	{
		return true;
	}
	else
	{
		return false;
	}

}

int BE(int x, int n, int m) //function to calculate x raise to power n modulo m
{
	int result = 1;
	while (n > 0)
	{
		if (n % 2 == 1)
			result = result * x % m;
		x = x * x % m;
		n = n / 2;
	}
	return result;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	if (fopen("input.txt", "r"))
	{
		freopen ("input.txt" , "r" , stdin);
		freopen ("output.txt" , "w" , stdout);
	}
#endif
	//_______________________________-code starts-_______________________________________________


	int n, k;
	cin >> n >> k;
	int a[n];
	zip(i, 0, n)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	int ans = 0;
	zip(i, 0, k)
	{
		ans += a[i];
	}

	cout << ans << en;
	return 0;
}



Measured memory_bytes: 3596
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

ll A, B, C;
ll K;

void solve() {
    ll ab = pow(-1, K) * (pow(-2, K - 1) * (-2 / 3) - 1 / 3);
    ll aa = K % 2 == 0 ? ab + 1 : ab - 1;
    ll tscore = aa * A + ab * B + ab * C;
    ll nscore = aa * B + ab * C + ab * A;
    cout << tscore - nscore << endl;
}

int main() {
    cin >> A >> B >> C >> K;
    solve();
    return 0;
}

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

int main()
{
    long long n, m;
    cin >> n >> m;
    if(n == 2 || m == 2) cout << 0;
    else if(min(n, m) == 1){
        int maximum = max(n, m);
        cout << (maximum == 1 ? 1 : maximum - 2);
    } else 
        cout << (m-2)*(n-2);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(b>0){
        c-=b;
        if(c<=0){
            cout<<"Yes"<<endl;
            return 0;
        }
        a-=d;
        if(a<=0){
            cout<<"No"<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3580
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_set>

#define REP(i, s, e) for (ll i = s; i < e; ++i)

using namespace std;
using ll = long long;
using ld = long double;

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

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    cout << y1 + x2 - y2 << " " << x2 + y2 - x1 << " " << x1 + y1 - y2 << " " << y1 + x2 - x1 << endl;

    return 0;
}


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

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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;


bool start[200010];
bool goal[200010];

int main(){
	

	int n,m;
	cin>>n>>m;

	for (int i = 0; i < m; i++){
		int c,d;
		cin>>c>>d;
		if(c==1)start[d]=true;
		if(d==n)goal[c]=true;
	}

	for (int i = 1; i < n ; i++){
		if(start[i]&&goal[i]){
			cout<<"POSSIBLE"<<endl;
			return 0;
		}
	}

	cout<<"IMPOSSIBLE"<<endl;

	return 0;
}

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi 1
#define LL long long
#define ULL unsigned long long
#define LD long double

using namespace std;

#define MAX_N 200005
#define MAX_M 200005

int N, M;
vector<int> Edge[MAX_N];
int dist[MAX_N];

int main()
{
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b; a--; b--;
    Edge[a].push_back(b);
    Edge[b].push_back(a);
  }

  for (int i = 0; i < Edge[0].size(); i++) {
    dist[Edge[0][i]] |= 1;
  }

  for (int i = 0; i < Edge[N-1].size(); i++) {
    dist[Edge[N-1][i]] |= 2;
  }

  for (int i = 0; i < N; i++) {
    if(dist[i] == 3){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }

  cout << "IMPOSSIBLE" << endl;

  return 0;
}


Measured memory_bytes: 12784
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int N,K,X,Y;
    cin >>N>>K>>X>>Y;
    
    cout << min(N,K)*X+max(0,N-K)*Y << endl;




}


Measured memory_bytes: 256
N,M = (int(x) for x in input().split())
X = [int(x) for x in input().split()]

X.sort()
dis = []
for i in range(len(X)-1):
    dis.append(X[i+1] - X[i])
ans=0
dis.sort()
for i in range(len(dis)-N+1):
    ans += dis[i]

print(ans)

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

int main(){
  int N,x; cin>>N>>x;
  int a[N];
  for(int i=0;i<N;i++) cin>>a[i];
  sort(a,a+N);
  int ans=0;
  for(int i=0;i<N;i++){
    if(x>=a[i]){
      x-=a[i];
      ans++;
    }
    else{
      break;
    }
    if(i==N-1) if(x!=0) ans--;
  }
  cout<<ans<<endl;
  
  
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> l(n);
    int max = 0;
    int sum = 0;
    for(int i=0;i<n;i++){cin >> l[i];}
    for(int j=0;j<n;j++){
        if(l[j] > max) max = l[j];
        sum += l[j];
    }
    if(max < sum-max) {cout << "Yes" << endl;}
    else {cout << "No" << endl;}

    return 0;

}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  int rst;
  if(a < b) {
    int tmp = a;
    a = b;
    b = tmp;
  }
  if( a < c){
    int tmp = a;
    a = c;
    c = tmp;
  }
  rst = b + c;
  
  for( int i = 0 ; i < k; i++){
    a = 2 * a;
  }
  rst += a;
  cout << rst << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C, D, N, ans=0;
    vector<int> V(3);
    char tmp;
    string S;
    cin >> V[0] >>V[1] >>V[2];
    tmp = V[0]*100+V[1]*10+V[2]*1;
    if(tmp%4==0)
	puts("YES");
    else
	puts("NO");
    
    // cout <<ans<<endl;
    

    // string S;
    // cin >>S;
    // cout << S + "pp"<<endl;
    // if(A+B==C || B+C==A || C+A==B)
    // 	puts("Yes");
    // else
    // 	puts("No");
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		double A = a;
		double B = b;

		System.out.println(a/b + " " + a%b + " " + String.format("%.5f", A/B));


	}
}



Measured memory_bytes: 26476
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long n,n1=0,n2=0,g1,s1,b1,g2,s2,b2;
  cin >> n >> g1 >> s1 >> b1 >> g2 >> s2 >> b2;
  
  for(long i=0;i*g1<=n;i++) {
    for(long j=0;i*g1+j*s1<=n;j++) {
      n1=max(n1,i*g2+j*s2+(n-i*g1-j*s1));
      n1=max(n1,i*g2+j*s2+(n-i*g1-j*s1)/b1*b2+(n-i*g1-j*s1)%b1);
    }
  }
  vector<long> v2,v1;
  if(g2<g1) {
    v2.push_back(g2);
    v1.push_back(g1);
  }
  if(s2<s1) {
    v2.push_back(s2);
    v1.push_back(s1);
  }
  if(b2<b1) {
    v2.push_back(b2);
    v1.push_back(b1);
  }
  if(v2.size()==0) n2=n1;
  if(v2.size()==1) n2=n1/v2[0]*v1[0]+n1%v2[0];
  if(v2.size()==2) {
    for(long i=0;i*v2[0]<=n1;i++) {
      n2=max(n2,i*v1[0]+(n1-i*v1[0]));
      n2=max(n2,i*v1[0]+(n1-i*v2[0])/v2[1]*v1[1]+(n1-i*v2[0])%v2[1]);
    }
  }
  if(v2.size()==3) {
    for(long i=0;i*g2<=n1;i++) {
      for(long j=0;i*g2+j*s2<=n1;j++) {
        n2=max(n2,i*g1+j*s1+(n1-i*g2-j*s2));
        n2=max(n2,i*g1+j*s1+(n1-i*g2-j*s2)/b2*b1+(n1-i*g2-j*s2)%b2);
      }
    }
  }
  cout << n2 << endl;
}

Measured memory_bytes: 3632
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int,int>;
using PLL = pair<LL, LL>;
const int INF = 1e9;
const int MXN = 0;
const int MXV = 0;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FOR(i, L, R) for(int i = L; i != (int)R; ++i)
#define FORD(i, L, R) for(int i = L; i != (int)R; --i)
#define IOS cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);

int main()
{
    IOS;
    LL n, a, b;
    cin >> n >> a >> b;
    LL ans = n / (a + b) * a;
    n %= (a + b);
    ans += min(a, n);
    cout << ans << '\n';
}


Measured memory_bytes: 764
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<vector<int>,int>P;
typedef pair<int,int>P2;
typedef pair<P2,P2>P3;
int a[4][4],o;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
vector<int>vp(16),tmp(16);
set<vector<int> >s;
vector<int> get(vector<int> &v,int y,int x){
	r(i,16)a[i/4][i%4]=v[i];
	a[y][x]++;
	if(a[y][x]==5){
	  int now=0;
	  queue<P3>q;
	  a[y][x]=0;
	  r(i,4)q.push(P3(P2(y,x),P2(i,0)));
	  while(!q.empty()){L:;
	  	P3 p;
	  	if(q.size()){p=q.front();q.pop();}
	  	else p=P3(P2(-1,0),P2(0,now+1));
	  	if(now!=p.second.second){
	  		r(i,4)r(j,4)if(a[i][j]>=5){
	  			a[i][j]=0;
	  		  r(k,4)q.push(P3(P2(i,j),P2(k,p.second.second)));
	  		}
	  		 now=p.second.second;
	  	}
	  	if(p.first.first==-1)continue;
	  	y=p.first.first+dy[p.second.first];
	  	x=p.first.second+dx[p.second.first];
	  	if(y<0||x<0||y>=4||x>=4)continue;
	  	if(a[y][x])a[y][x]++;
	  	else q.push(P3(P2(y,x),P2(p.second.first,p.second.second+1)));
	  }
	  r(i,4)r(j,4)if(a[i][j]>=5)goto L;
	}
	r(i,4)r(j,4)tmp[i*4+j]=a[i][j];
	return tmp;
}
bool ch(vector<int> &v){
	r(i,16)if(v[i])return 0;
	return 1;
}
int main(){
	r(i,16)cin>>vp[i];
	queue<P>q;
	q.push(P(vp,0));
	s.insert(vp);
	if(ch(vp))cout<<0<<endl;
	else while(!q.empty()){
		P p=q.front();q.pop();o=p.second;
		if(p.second==5){
			cout<< -1 <<endl;
			return 0;
		}
		vector<int>v=p.first;
		r(i,4)r(j,4){
			vector<int>t=get(v,i,j);
			if(ch(t)){
				cout<<p.second+1<<endl;
				return 0;
			}
			if(!s.count(t)){
				s.insert(t);
				q.push(P(t,p.second+1));
			}
		}
	}
}

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
//    cout << fixed << setprecision(15);

    i32 a,b,c,k; cin >> a >> b >> c >>k;

    i64 ans = max<i64>({a,b,c});
    rep(i,k) ans *= 2;

    ans += a+b+c - max<i64>({a,b,c});

    cout << ans << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
long long int cache[10005][10005];
long long int mod=1000000007;
long int numWays(int H,int W)
{
	if(cache[H][W]!=-1)
	return cache[H][W];
if(a[H][W]=='#')
return cache[H][W]=0;
if(H==1&&W==1)
return 1;
if(H==1)
return cache[H][W]=numWays(H,W-1);
else if(W==1)
return cache[H][W]=numWays(H-1,W);
return cache[H][W]=(numWays(H-1,W)%mod+numWays(H,W-1)%mod)%mod;
}
int main()
{
	memset(cache,-1,sizeof(cache));
	int H,W;
	cin>>H>>W;
	int i,j;
	for(i=1;i<=H;i++)
	{
		for(j=1;j<=W;j++)
		cin>>a[i][j];
			}
long int x=numWays(H,W);
cout<<x;
}

Measured memory_bytes: 783488
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
#include<functional>
using namespace std;

int INF = 1e9 + 7;

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

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(begin(a), end(a), greater<int>());

	int i = 0;
	ll h = 0, w = 0, cnt = 0;
	while(i < n - 1) {
		if (a[i] == a[i + 1]) {
			if (cnt == 0) {
				h = a[i];
				cnt++;
				i++;
			}
			else {
				w = a[i];
				break;
			}
		}
		i++;
	}
	cout << h * w << endl;
}

Measured memory_bytes: 640
N = int(input())

xy = []
for i in range(N):
    xi, yi = map(int, input().split())
    xy.append((xi, yi))


vectors = []

x1, x2, y1, y2, xd, yd = 0, 0, 0, 0, 0, 0
for i in range(N):
    for j in range(i+1, N):
        x1, y1 = xy[i]
        x2, y2 = xy[j]

        vectors.append((x1-x2, y1-y2))
        vectors.append((x2-x1, y2-y1))

vectors.sort(key=lambda x: x[1])
vectors.sort()

frequencies_dic = {}
M = len(vectors)
for i in range(M):
    x, y = vectors[i]
    if (x, y) not in frequencies_dic:
        frequencies_dic[(x,y)] = 1
    else:
        frequencies_dic[(x,y)] += 1
if N == 1:
    print(1)
else:
    zeros = max(list(frequencies_dic.values()))
    ans = N - zeros
    print(ans)

Measured memory_bytes: 3700
n = int(input())
s = input()
ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    x = s.find(num[0])
    y = s.find(num[1], x+1)
    z = s.find(num[2], y+1)
    if x != -1 and y != -1 and z != -1:
            ans += 1
print(ans)

Measured memory_bytes: 3188
// ABC 151-D
// 2020.1.12 bal4u

#include <stdio.h>
#include <string.h>

#if 0
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

void ins(char *s) { // 文字列の入力　スペース以下の文字で入力終了
	do *s = gc();
	while (*s++ > ' ');
	*(s-1) = 0;
}

int H, W;
char map[25][25];
int ans;
char vis[25][25];

#define MAX 1000000
typedef struct { char r, c; int s; } Q;
Q q[MAX+5]; int top, end;
int mv[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

int bfs(int r0, int c0) {
	int i, r, c, s, rr, cc, ma;

	ma = 0;
	memset(vis, 0, sizeof(vis));
	top = 0, end = 1;
	q[0].r = r0, q[0].c = c0, q[0].s = 0;
	while (top != end) {
		r = q[top].r, c = q[top].c, s = q[top++].s;
		if (vis[r][c]) continue;
		vis[r][c] = 1;	
		if (s > ma) ma = s;
		for (i = 0; i < 4; ++i) {
			rr = r + mv[i][0], cc = c + mv[i][1];
			if (map[rr][cc] == '.' && rr >= 0 && rr < H && c >= 0 && c < W)
				q[end].r = rr, q[end].c = cc, q[end++].s = s+1;
		}
	}
//	printf("r0=%d, c0=%d, ma=%d\n", r0, c0, ma);
	return ma;
}

int main()
{
	int r, c;
	
	H = in(), W = in();
	for (r = 0; r < H; ++r) ins(map[r]);
	for (r = 0; r < H; ++r) for (c = 0; c < W; ++c) {
		if (map[r][c] == '.') {
			int x = bfs(r, c);
			if (x > ans) ans = x;
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
void chmax(LL& a, LL b) {
	a = max(a, b);
}
//////////////

void solve() {
	int A, B,K;
	cin >> A >> B>>K;
	vector<int> ans;
	for (int i = 1;i<=A+B; ++i) {
		if ((A % i) == 0 && (B % i) == 0) {
			ans.push_back(i);
		}
	}
	int N = ans.size();
	cout << ans[N-K] << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 256
//Structured Program I - Print a Frame
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String input;
		
		 while (!(input = in.readLine()).equals("0 0")) {

			 String[] HW = input.split(" ");

			 int H = Integer.parseInt(HW[0]);
			 int W = Integer.parseInt(HW[1]);

			 for(int i=0;i<H;i++){
				 for(int j=0;j<W;j++){
					 
					 if(i==0 || j ==0 || i==H-1 || j==W-1 ){
						 System.out.print("#");
					 }else{
						 System.out.print(".");						 
					 }
				 }
				 System.out.println();
			 }
			 System.out.println();
			 
		 }

	}
}

Measured memory_bytes: 24604
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>

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

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = 3.1415926535;

const int D = 60;
const int MAX_N = 200005;
int a[MAX_N];
int to[D][MAX_N];


int main()
{
    int n;
    ll k;
    cin >> n >> k;
    rep(i, n) {
        cin >> to[0][i];
        to[0][i]--;
    }

    // ダブリング表の作成
    rep(i, D-1) rep(j, n) {
        to[i + 1][j] = to[i][to[i][j]];
    }

    // 移動シミュレーション
    // ダブリング表を下から走査していき、
    // ビットが立っていたら移動を実施
    int pos = 0;  // 現在位置
    for (int i = D - 1; i >= 0; i--) {
        ll l = 1ll << i;  // llをつけないとオーバーフロー
        if (k & l) {
            pos = to[i][pos];
            k -= l;
        }
    }
    cout << pos + 1 << endl;
}

Measured memory_bytes: 50504