akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,-1,1,0};
const int dy[]={0,1,0,-1,1,1,-1,-1,0};
const int INF = 1e9+101;
const long long LINF = 1e18;
const double EPS = 1e-8;
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define reps(i,j,k) for(ll i = (j); i < (k); ++i)
#define rep(i,j) reps(i,0,j)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> Pii;
typedef pair<Pii,int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
template<class T>
ostream& operator<<(ostream &out, const vector<T> &v){
	out << "{";
	rep(i,v.size()){
		out << v[i] <<", ";
	}
	return out << "}" << endl;
}
int  N,M;
int memo[20][20];
int p[20];
int ans = 0;
void solve(int depth, vector<int> a) {
    if(depth == N){
        bool flg = false;
        rep(i,M){
            int s = 0;
            rep(j,N){
                if(memo[i][j] == 1 && a[j] == 1){
                    s++;
                }
            }
            if(s%2 != p[i]){
                flg = true;
                break;
            }
        }
        if(!flg){
            ans++;
        }
        return ;
    }
    vector<int> s = a;
    s.pb(1);
    solve(depth+1, s);
    a.pb(0);
    solve(depth+1, a);
}
int main() {
    cin >> N >> M;
    rep(i, M){
        int k;
        cin >> k;
        rep(j,k){
            int t;
            cin >> t;
            --t;
            memo[i][t] = 1;
        }
    }
    rep(i, M){
        cin >> p[i];
    }
    vector<int> clr;
    solve(0, clr);
    cout <<ans << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  string flg="No";
  int N;
  cin >> N;
  REP(i,9){
    REP(j,9){
      if((i+1)*(j+1) == N) flg = "Yes";
    }
  }
  cout << flg << endl;
}

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

int main() {
  int n = 5;
  int a[n];
  for(int i=0;i<n;i++) {
    cin >> a[i];
  }
  sort(a,a+n);
  for(int i=n-1;i>=0;i--) {
    cout << a[i] << (i == 0 ? "\n" : " ");
  }
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define hii cout << "hii" << endl
#define int ll
#define endl '\n'
#define all(s) s.begin(), s.end()
 
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; } 
 
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE
 
 
const int N = 5e5 + 5;
const int MAXN = 1e5 + 5;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e15;
const int LG = 21;
const long double PI = acos(-1);

int arr[N];

void solve() 
{
	int r;
	cin >> r;
	cout << fixed << setprecision(15);
	r *= 2;
	long double ret = PI * r;
	cout << ret << endl;
}

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

	    int t = 1;
	    // cin >> t;
	while(t--)solve();
	return 0;
}

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

int main(){
	long long val; cin >> val; int sum = 0; bool flg = 1;
	while(val / 10){flg &= val % 10 == 9; sum += 9; val /= 10;}
	sum += val % 10 - !flg; cout << sum; return 0;
}


Measured memory_bytes: 256
N = int(input())
L = [int(_n) for _n in input().split()]
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i] == L[j] or L[j] == L[k] or L[k] == L[i]:
                continue
            if abs(L[j]-L[k]) < L[i] < abs(L[j] + L[k]):
                cnt+=1
print(cnt)

Measured memory_bytes: 68500
#include <bits/stdc++.h>
#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 _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;

void solve() {
    ll n; cin >> n;
    map<string, ll> m;
    rep(i, 0, n){
        string s; cin >> s;
        sort(ALL(s));
        m[s]++;
    }
    ll ans = 0;
    for(auto p : m){
        auto v = p.second;
        // //
        // auto k = p.first;
        // cout << k << " " << v << endl;
        // //
        while(v--){
            ans += v;
        }
    }
    cout << ans << endl;
}

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

    solve();
    return 0;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,x,ans=1,d=0,num=0;cin >> n >> x;
  vector<int> l(n,100000);
  for(int i=0;i<n;i++) cin >> l[i];
  int i=0;
  while(i!=n){
    d=num+l[i];
    if(d<=x) ans++;
    num = d;
    i++;
  }

  cout << ans << endl;
}


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

using namespace std;

const int MAXN = (int) 1e5 + 10;

int n, t[4*MAXN];

void build(vector<int> &a, int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = __gcd(t[v*2], t[v*2+1]);
    }
}

int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return __gcd(sum(v*2, tl, tm, l, min(r, tm)), sum(v*2+1, tm+1, tr, max(l, tm+1), r));
}

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

		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];
		build(a, 1, 0, n - 1);
		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				ans = max(ans, sum(1, 0, n - 1, i + 1, n - 1));
			} else if (i == n - 1) {
				ans = max(ans, sum(1, 0, n - 1, 0, n - 2));
			} else {
				ans = max(ans, __gcd(sum(1, 0, n - 1, 0, i - 1), sum(1, 0, n - 1, i + 1, n - 1)));
			}
		}
		cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int n,a[N];
int main() {
    cin>>n;n<<=1;
    for(int i=1;i<=n;i++) a[i]=gi();
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=1;i<=n;i+=2) ans+=a[i];
    printf("%d\n",ans);
    return 0;
}
//orzgzy
//鸡贼明年进队超稳


Measured memory_bytes: 256
n = gets.chomp.to_i
arr = gets.chomp.split.map(&:to_i).sort
table = {}
arr.each do |ai|
  if table.has_key?(ai)
    table[ai] += 1
  else
    table[ai] = 1
  end
end
# 最頻値の+-1の数とそのtable[+-1]の数を調べる。
# ↑間違い 2 2 2 4 4 5 5 6 6 7 7とか
# なので、出てきたやつを試していく
max_count = 1

table.keys.each do |ai|
  temp = 0
  [-1, 0, 1].each do |i|
    if table.has_key?(ai+i)
      temp+=table[ai+i]
    end
  end
  max_count = [max_count, temp].max
end
puts max_count

Measured memory_bytes: 16624
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9+7

def nCr(n, r, mod=MOD):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

n, a, b = map(int, (input().split()))

ans = pow(2, n, MOD) - 1 - nCr(n, a) - nCr(n, b)
ans += MOD * 2
ans %= MOD
print(ans)


Measured memory_bytes: 3064
from bisect import bisect_left

X = int(input())


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


p = sieve_of_eratosthenes(2 * 10 ** 5)

print(p[bisect_left(p, X)])


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

vector<int> to_code(string s) {
    vector<int> ret = {0};
    if(s[0] == '0') {
        ret.push_back(0);
    }
    s += "$";
    int pos = 0;
    while(pos+1 < s.size()) {
        int cnt = 1;
        while(pos+1 < s.size() && s[pos] == s[pos+1]) pos++,cnt++;
        ret.push_back(cnt);
        pos++;
    }
    if(s[s.size()-2] == '0') {
        ret.push_back(0);
    }
    for(int i=1;i<ret.size();++i) {
        ret[i] += ret[i-1];
    }
    return ret;
}

int solve(string s,int k) {
    vector<int> codes = to_code(s);
    //cout<<codes.size()<<endl;
    if(2*k+1 >= codes.size()) {
        return codes.back();
    }
    int head = 0;
    int ans = 0;
    for(int i=2*k+1;i<codes.size();i+=2,head+=2) {
        ans = max(ans,codes[i] - codes[head]);
    }
    return ans;
}
int main() {
    int n,k;
    string s;
    cin>>n>>k>>s;
    cout<<solve(s,k)<<endl;;
}

Measured memory_bytes: 1152
#include<iostream>
using namespace std;
int n,x,m;
int l[10],r[10],s[10];
int t[6],ans[6],maxm;
int u[6];
void check(){
  int i,j;
  u[0]=t[0];
  for(int i=1;i<n;i++){
    u[i]=u[i-1]+t[i];
  }
  if(u[n-1]<=maxm)return;
  
  for(i=0;i<m;i++){
    if(u[r[i]]-u[l[i]]+t[l[i]]!=s[i]){
      break;
    }
  }
  if(i==m){
    maxm=u[n-1];
    for(j=0;j<n;j++)ans[j]=t[j];
  }
}

void compute(int y){
  if(y==n)check();
  else{
    for(int i=0;i<=x;i++){
      t[y]=i;
      compute(y+1);
    }
  }
}


int main(){
  cin>>n>>x>>m;
  for(int i=0;i<m;i++){
    cin>>l[i]>>r[i]>>s[i];
    l[i]--;
    r[i]--;
  }
  maxm=-1;
  compute(0);
  if(maxm==-1){
    cout<<-1<<endl;
    return 0;
  }
  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<ans[i];
  }
  cout<<endl;
  return 0;
}

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

int main(){
  int A, B, C, D;
  cin>>A>>B>>C>>D;
  bool suzuki=true;
  bool takahashi=true;
  while(suzuki || takahashi){
    C-=B;
    if(C<=0) {
      suzuki=false;
      break;
    }
    A-=D;
    if(A<=0){
      takahashi=false;
      break;
    }
  }
  if(takahashi) cout<<"Yes"<<endl;
  if(suzuki) cout<<"No"<<endl;
}
 

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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int a = in.ni(), b = in.ni(), h = in.ni();
        out.println((a+b)*h/2);
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 21076
using System;

class Program
{
  static void Main(string[] args)
  {
    string s1 = Console.ReadLine();
    string s2 = Console.ReadLine();
    
    if(s1[0] == s2[2] && s1[1] == s2[1] && s1[2] == s2[0]) Console.WriteLine("YES");
    else Console.WriteLine("NO");
  }
}

Measured memory_bytes: 11092
use std::io::*;

fn main() {
    let stdin = stdin();
    let mut lock = stdin.lock();
    let mut str1 = String::new();
    lock.read_line(&mut str1).unwrap();
    let vec:Vec<_> = str1.trim().split_whitespace().
    next().unwrap().bytes().collect();
    let mut sanjo = vec.len() as usize;
    for (i, j) in vec.iter().enumerate() {
        //        println!(": {}, {}, {}", i, j, vec[0])
        if i == 0 {
            continue;
        }
        if *j != vec[i-1] {
            if i < vec.len() - i && vec.len() - i < sanjo {
                sanjo = vec.len() - i;
            } else if i < sanjo {
                sanjo = i;
            }
        }
    }
    println!("{}", sanjo);
}

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

ll pow(ll d){
ll k= 1;
for(int i=0;i<d;i++)k*=100;
return k;
}

int main() {
    ll d;ll n;
    cin>>d>>n;
    ll k = pow(d);
    if(n==100)cout<<k*101;
    else cout<<k*n;


 return 0;
}


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

#define MAXN 524288
#define MAXC 1048576
#define NO_VALUE -1

#define LEFT(x) ( 2*(x) )
#define RIGHT(x) ( 2*(x)+1 )

int A, B, C, M;

int r() {
    A = 36969 * (A & M) + (A >> 16);
    B = 18000 * (B & M) + (B >> 16);
    return (C & ((A << 16) + B)) % 1000000;
}

int x[MAXN], y[MAXN], z[MAXN], ox[MAXN], val[MAXN], used[MAXC], stack[MAXN], ymap[MAXC], Y;

bool cmp_x(const int &a, const int &b) {
    if (x[a] != x[b]) return x[a] < x[b];
    else if (y[a] != y[b]) return y[a] < y[b];
    else return z[a] < z[b];
}

map<int, int> bit[MAXC];

int answer(int idx, int th) {
    map<int, int>::iterator it = bit[idx].lower_bound(th);
    if (it != bit[idx].begin()) return (--it)->second;
    else return NO_VALUE;
}

int query(int idx, int th) {
    int res = NO_VALUE;
    while (idx > 0) {
        res = max(res, answer(idx, th));
        idx &= idx-1;
    }
    return res;
}

void update(int idx, int th, int v) {
    map<int,int>::iterator it1, it2;
    while (idx < Y) {
        it1 = it2 = bit[idx].upper_bound(th);
        while (it2 != bit[idx].end() && it2->second <= v) it2++;
        bit[idx].erase(it1, it2);
    
        it1 = bit[idx].upper_bound(th);
        if (it1 == bit[idx].begin() || (--it1)->second < v) bit[idx][th] = v;
        idx += idx&(-idx);
    }
}

int main() {
    int m, n, i, j, N, t = 1, STACK;

    while (scanf("%d %d %d %d", &m, &n, &A, &B) && (m || n || A || B)) {
        C = ~(1<<31); M = (1<<16)-1;
        for (i=0; i<m; i++) scanf("%d %d %d", &x[i], &y[i], &z[i]);
        for (i=m; i<m+n; i++) { x[i] = r(); y[i] = r(); z[i] = r(); }
        N = m+n;

        Y = 0;
        for (i=0; i<N; i++) {
            ox[i] = i;
            if (used[y[i]] < t) { used[y[i]] = t; stack[Y++] = y[i]; }
        }
        sort(ox, ox+N, cmp_x);
        sort(stack, stack+Y);
        for (i=0; i<Y; i++) ymap[stack[i]] = i+1;
        for (i=0; i<N; i++) y[i] = ymap[y[i]];
        t++; Y++;

        for (i=0; i<Y; i++) bit[i].clear();

        i = 0;
        do {
            for (j=i; j<N && x[ox[j]]==x[ox[i]]; j++) val[ox[j]] = max(1, query(y[ox[j]]-1, z[ox[j]])+1);
            for (; i<j; i++) update(y[ox[i]], z[ox[i]], val[ox[i]]);
        } while (i < N);
        printf("%d\n", query(Y-1, MAXC));
    }

    return 0;
}

Measured memory_bytes: 111904
#include <bits/stdc++.h>
#define ll long long
#define ar array
#define nl '\n'
#define AC ios_base::sync_with_stdio(0); cin.tie(NULL);
using namespace std;
const int M = 1e9+7;
const int N = 2*1e5;

int cur_pos[N+5]; 
int tele[N+5];
ll pred[N+5];


int main(){
    AC
    int n;
    ll k;
    cin>>n>>k;
    for(int i=0; i<n; i++){
        cin>>tele[i];
        tele[i]--;
    }
    memset(pred, -1, sizeof(pred));

    cur_pos[0] = 0;
    pred[0] = 0;
    for(ll i = 1; i<=k; i++){
        cur_pos[i] = tele[cur_pos[i-1]];
        if(pred[cur_pos[i]]!=-1){
            // city already visited
            ll cycle_len = i-pred[cur_pos[i]];
            ll last_steps = (k-i)%cycle_len;
            ll last_pos = cur_pos[pred[cur_pos[i]]+last_steps];
            cout<<last_pos+1<<endl;
            return 0;
        }
        else
            pred[cur_pos[i]] = i;
    }
    cout<<cur_pos[k]+1<<endl;
}

Measured memory_bytes: 6528
import java.util.*;
import java.lang.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        for(int i = 0;i<s.length();i++){
            char a = s.charAt(i);
            if(a == 'U' || a == 'D'){
                continue;
            }else if(a == 'R' && i % 2 == 0){
                continue;
            }else if(a == 'L' && i % 2 == 1){
                continue;
            }else{
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
        sc.close();
    }
}

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

int n,m;// n price, m ticket

long long solve(){
    cin>>n>>m;
    
    #define ms multiset < int , greater < int > >
    ms s;
    for(int i=0;i<n;++i){
        int x;cin>>x;
        s.insert(x);
    }
    for(int i=0;i<m;++i){
        int p=*s.begin();
        s.erase(s.begin());
        s.insert(p>>1);
    }
    long long ans=0;
    for(auto i=s.begin();i!=s.end();++i){
        ans+=*i;
    }
    return ans;
}

int main(){
    cout<<solve()<<endl;
    return 0;
}


Measured memory_bytes: 6912
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;

////////////////////////// templates

template<class U>
void PRINT(std::vector<U> &x) {
    for (int i=0;i<x.size();++i) {
        cout << x[i];
    }
}

template<class U>
void PRINTLN(std::vector<U> &x) {
    PRINT<U>(x);
    cout << endl;
}

////////////////////////// functions

////////////////////////// main

int main() {
    ll N;
    string S;
    cin >> N >> S;
    int ans = 0;
    for (int i=0;i<N-2;++i) {
        if(S[i]=='A' && S[i+1]=='B' && S[i+2]=='C') ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef long long LL;
const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,
               5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};
const int pr[12]={2,3,5,7,11,13,17,19,23,29,31,37};
const LL UnUseMethod=4759123141;
LL count[2]={0};
LL IN(void)
{
  LL x=0;short f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
LL GCD(LL a,const LL b){return !b?a:GCD(b,a%b);}
LL Mult(LL x,LL y,const LL mod){LL z=x*y-(LL)((long double)x/mod*y+1e-8)*mod;return z<0?z+mod:z;}
LL BinaryModularPower(LL base,LL pow,const LL mod)
{
  LL x=1;
  while(pow){if(pow&1){x=Mult(x,base,mod);}base=Mult(base,base,mod);pow>>=1;}
  return x;
}
void Exp(LL x,const LL y){count[1]=0;while(!(x%y)){count[1]++;x/=y;}count[0]=x;return;}
int MillerRabin(const LL a)
{
  if(a==2)return 1;
  if(a%2==0||a==1)return 0;
  LL u=a-1,t=0,p=1;
  while(!(u&1)){u>>=1;t++;}
  for(int i=0;i<12;++i)
  {
    p=pr[i]%a;
    if(!p)return 1;
    LL x=BinaryModularPower(p,u,a);
    if(x==1)continue;
    for(int j=0;x!=a-1&&j<t;j++)
    {
      x=Mult(x,x,a);
      if(x==1)return 0;
    }
    if(x==a-1)continue;
    return 0;
  }
  return 1;
}
LL PollardRho(const LL n,LL a)
{
  LL x=rand()%n,y=x,gcd=1,i=1,k=0;
  while(gcd==1)
  {
    k++;
    x=Mult(x,x,n)+a;if(x>=n)x-=n;
    gcd=GCD(x>y?x-y:y-x,n);
    if(k==i){y=x;i<<=1;}
  }
  if(gcd==n)return PollardRho(n,a+1);
  return gcd;
}
signed main(void)
{
  srand((unsigned int)time(NULL));
  LL a=0,p=1,q=-1,N=IN();
  if(N<=1)return puts("0"),0;
  Exp(N,2);a=e[count[1]];N=count[0];
  Exp(N,3);a+=e[count[1]];N=count[0];
  while(q*q<=UnUseMethod)
  {
    p+=6,q+=6;
    Exp(N,p);a+=e[count[1]];N=count[0];
    Exp(N,q);a+=e[count[1]];N=count[0];
  }
  if(N<=UnUseMethod){if(N>1){a++;}return printf("%lld\n",a),0;}
  if(MillerRabin(N)){a++;return printf("%lld\n",a),0;}
  while(N>=UnUseMethod)
  {
    p=PollardRho(N,0);
    while(!MillerRabin(p))p=PollardRho(p,p);
    Exp(N,p);a+=e[count[1]];N=count[0];
  }
  if(MillerRabin(N)){a++;}return printf("%lld\n",a),0;
}

Measured memory_bytes: 1608
def f(w, n, k, v):
    # how many things in list w of length n can fill in k cars with capacity v?
    i = 0
    space = 0
    while i < n:
        if space >= w[i]:
            space -= w[i]
            i += 1
        else:
            # space < w[i]
            if k == 0:
                break
            k -= 1
            space = v
    return i


if __name__ == '__main__':
    n, k = map(int, raw_input().split())
    w = []
    maxv = -1
    for i in range(n):
        x = int(raw_input())
        w.append(x)
        maxv = max(maxv, x)

    left = 0
    right = n * maxv

    # range: (left, right]
    # loop until left + 1 = right, then right is the answer
    # why? because right works, but right - 1 doesn't work
    # so right is the smallest capacity
    while right - left > 1:
        mid = (left + right) / 2
        v = f(w, n, k, mid)
        if v >= n:
            # range: (left, mid]
            # in fact, v cannot > n
            right = mid
        else:
            # range: (mid, right]
            left = mid
    print right


Measured memory_bytes: 10880
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  ll N = 0;
  cin >> N;
  vector<ll>A(N);
  rep(i,N){
    cin >> A[i];
  }
  sort(A.begin(), A.end()); //小さい順
  ll ans = 0;
  rep(i,N-1){
    ans += A[i];
  }
  if(ans > A[N-1]){
    cout << "Yes";
  }
  else{
    cout << "No";
  }
}
      

Measured memory_bytes: 3608
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only


def main():
    n = ii()
    print(n**3)
    return


if __name__ == '__main__':
    main()



Measured memory_bytes: 6880
#include<stdio.h>
int main(){
  double r;
  double s,l;

  while(1){
    scanf("%lf",&r);
    if(0<r && r<10000) break;
  }

  s = r*r*3.14159265359;
  l = r*2*3.14159265359;

  printf("%.6f %.6f\n",s,l);
  return 0;
}

Measured memory_bytes: 652
use std::io;

fn main() {
    let mut buf = String::new();
    let stdin = io::stdin();
    stdin.read_line(&mut buf).unwrap();
    buf.clear();
    stdin.read_line(&mut buf).unwrap();
    let c = buf.trim_end();
    let red = c.chars().filter(|&c| c == 'R').count();
    let ans = c[0..red].chars().filter(|&c| c == 'W').count();
    println!("{}", ans);
}


Measured memory_bytes: 2292
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define mod 1000000007
#define limit 200001
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(i = 0; i < n; i++)
#define max(a,b) {if(a>b){return a;}return b;}
#define min(a,b) {if(a<b){return a;}return b;}
int up_int(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_int(const void *a, const void *b){return *(int*)b - *(int*)a;}

typedef struct {
    ll a;
    ll b;
} data_t;

int kozotai_upint(const void * n1, const void * n2)
{
    if (((data_t *)n1)->a > ((data_t *)n2)->a)
    {
        return 1;
    }
    else if (((data_t *)n1)->a < ((data_t *)n2)->a)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

int main(){
    ll n,m,x,sum=0;
    int i,j;
    data_t price[200001];
    
    scanf("%lld %lld",&n,&m);
    rep(i,n) scanf("%lld %lld",&price[i].a,&price[i].b);
    qsort(price,n,sizeof *price,kozotai_upint);
//    rep(i,n) printf("%lld %lld\n",price[i].a,price[i].b);
    
    rep(i,n){
        if(m-price[i].b > 0){
            sum += (price[i].a * price[i].b);
            m -= price[i].b;
        }else{
            sum += (price[i].a * m);
            break;
        }
    }
    
    printf("%lld\n",sum);
    return 0;
}


Measured memory_bytes: 4348
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<math.h>
#define ll long long 
#define d double
using namespace std;

int main()
{
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,m;
    cin>>n>>m;
    
    n-=1;
    m-=1;
    
    int s1= n*(n+1)/2;
    int s2= m*(m+1)/2;
    
    cout<<s1+s2<<endl;
    
    return 0;
    
}
    

Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std ;
int main()
{
   int n;
   cin >> n;
   int a[n];
   for(int i=0 ; i<n; i++)
   {
       cin>> a[i];
   }
   sort(a,a+n);
   cout << abs(a[0]-a[n-1]);


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

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


ll f[2110000];
void cominit() {
	f[0] = 1;
	REP(i, 2100000)f[i + 1] = f[i] * (i + 1) % MOD;
}

ll com(ll n, ll r) {
	return f[n] * powmod(f[r] * f[n - r], MOD - 2) % MOD;
}

ll perm(ll n, ll r) {
	return f[n] * powmod(f[n - r], MOD - 2) % MOD;
}

ll x, y, a, b;
int main(){
    cominit();
  cin >> x >> y;
  if(x < y) swap(x,y);
  ll c = x - y;
  x -= 2 * c;
  y -= c;
  a += c;
  if(x >= 0 and x % 3 == 0){
      a += x / 3;
      b += x / 3;
      cout << com(a + b, a) << endl;
  }
  else cout << 0 << endl;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
using ll = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;

int main() {
  string s; cin >> s;
  if (s == "SSS") {
    cout << 0;
  } else if (s == "SSR") {
    cout << 1;
  } else if (s == "SRR") {
    cout << 2;
  } else if (s == "RRR") {
    cout << 3;
  } else if (s == "SRS") {
    cout << 1;
  } else if (s == "RRR") {
    cout << 2;
  } else if (s == "RRS") {
    cout << 2;
  } else if (s == "RSR") {
    cout << 1;
  } else if (s == "RSS") {
    cout << 1;
  }
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[1000];
    int a,n,i,l;
    cin>>s;
    if(s[2]==s[3] && s[4]==s[5])
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
program atcoder
    implicit none
    integer :: i,n
    integer,allocatable,dimension(:) :: a,dp
    read*,n
    allocate(a(0:n))
    allocate(dp(0:n+3))
    read(*,*)(a(i),i=1,n)
    dp = 1000000007
    dp(1) = 0
    do i = 1,n
        dp(i+1) = min( dp(i+1) , dp(i)+abs(a(i+1)-a(i)))
        dp(i+2) = min( dp(i+2) , dp(i)+abs(a(i+2)-a(i)))
    end do
    write(*,'(I0)')dp(n)
    stop 
!---------------------------------------
contains

end program atcoder


Measured memory_bytes: 1536
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
constexpr int mo = 1000000007;
constexpr int  mod = mo;
constexpr ll inf = 1ll<<62;
int main(){
    int n;
    cin>>n;
    vector<int> p10(10);
    p10[0] = 1;
    for(int i=0;i<=5;++i)p10[i+1] = p10[i] * 10;
    int i;
    for(i=5;i>=0;--i){
        if(p10[i] <= n)break;
    }
    int ret = 0;
    if(i%2 == 0){
        ret += (n-p10[i]+1);
        i--;
    }
    for(;i>=0;--i){
        if(i%2 == 0)ret += 9*p10[i];  
    }
    cout << ret << endl;
    return 0;
}



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

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

    int count = 0, nowMax = 0;
    for (int i = 0; i < n; ++i)
    {
        int input;
        cin >> input;

        if (input >= nowMax)
        {
            ++count;
        }

        nowMax = max(nowMax, input);
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

char map[110][110];
int s_x,s_y,loop;

void serch(int x,int y)
{
	if(map[x][y]=='1')
	{
		loop=1;
		return ;
	}
	if(map[x][y]=='.')
	{
		s_x=x;
		s_y=y;
		return ;
	}
	if(map[x][y]=='>')
	{
//		cout << "x:" << x << " y:" << y <<" nowmap:" << map[x][y] << endl;
		map[x][y]='1';
		serch(x,y+1);
	}
	else if(map[x][y]=='<')
	{
//		cout << "x:" << x << " y:" << y <<" nowmap:" << map[x][y] << endl;
		map[x][y]='1';
		serch(x,y-1);
	}
	else if(map[x][y]=='v')
	{
//		cout << "x:" << x << " y:" << y <<" nowmap:" << map[x][y] << endl;
		map[x][y]='1';
		serch(x+1,y);
	}
	else if(map[x][y]=='^')
	{
//		cout << "x:" << x << " y:" << y <<" nowmap:" << map[x][y] << endl;
		map[x][y]='1';
		serch(x-1,y);
	}
	return ;
}

int main()
{
	int w,h;
	int i,j;
	
	for(;;)
	{
		loop=0;
		cin >> w >> h ;
		if(w==0 && h==0)
			break;
		for(i=0;i<w;i++)
		{
			for(j=0;j<h;j++)
			{
				cin >> map[i][j] ;
			}
		}
		
		serch(0,0);
		
		if(loop==1)
			cout << "LOOP" << endl;
		else
			cout << s_y << " " << s_x << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << "\n"
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
template<class T> void chmax(T &a, const T &b){if(a<b) a=b;}
template<class T> void chmin(T &a, const T &b){if(b<a) a=b;}
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
int main() {
	int n; cin >> n;
    vi dp(n + 1, INT_MAX);
    int a;
    rep(i, 0, n) {
        cin >> a;
        *lower_bound(dp.begin(), dp.begin() + n, a) = a;
    }
    P(lower_bound(all(dp), INT_MAX) - dp.begin());
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef long  l;
typedef pair<int,int> pl;
const ll INF=100000000000000001;
const double PI=3.141592653589;


int main(){
  int n;cin>>n;
  vector<int> d(n);
  rep(i,n){
    cin>>d[i];
  }
  ll ans=0;
  for(int i;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      ans+=(d[i]*d[j]);
      // cout<<ans<<endl;
    }
  }

  cout<<ans<<endl;
  return 0;
}


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

int N;
int b[200001];

main(){
	cin>>N;
	for(int i=1;i<=N;++i){
		int a;
		scanf("%d",&a);
		b[a]=i;
	}
	set<int>s;
	s.insert(0);
	s.insert(N+1);
	long long x=0;
	for(long long i=1;i<=N;++i){
		auto it=s.upper_bound(b[i]);
		x+=i*(*it-b[i])*(b[i]-*--it);
		s.insert(b[i]);
	}
	cout<<x;
}


Measured memory_bytes: 10368
def resolve():
    S = input()
    T = input()
    Min = 1000
    for i in range(len(S) - len(T) + 1):
        C = 0
        for j in range(len(T)):
            if S[i+j] != T[j]:
                C += 1
        Min = min(Min, C)
    print(Min)
    
resolve()    

Measured memory_bytes: 8880
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String[] params = in.nextLine().split(" ");
        int h = Integer.parseInt(params[0]);
        int w = Integer.parseInt(params[1]);
        String[][] ss = new String[h][w];
        for (int i = 0; i < h; i++) {
            params = in.nextLine().split("");
            for (int j = 0; j < w; j++) {
                ss[i][j] = params[j];
            }
        }

        // 全ての場所をスタート地点として最長距離を回答とする
        int maxDistance = 0;
        String[][] copy = new String[h][];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                maxDistance = Math.max( maxDistance , getMaxDistanceWithBfs( ss , i , j ) );
            }
        }

        System.out.println(maxDistance);

    }

    /**
     * 幅優先探索で最長距離を返す
     * @param ss 迷路の配列
     * @param startY スタート地点のY座標
     * @param startX スタート地点のX座標
     * @return 最長距離
     */
    private static int getMaxDistanceWithBfs( String[][] ss , int startY , int startX ) {

        int[][] distances = new int[ss.length][ss[0].length];
        Queue<Integer> queue = new ArrayDeque<>();

        // 四方の定義 順に左上右下
        int[] dx = { -1 , 0 , 1 , 0 };
        int[] dy = { 0 , 1 , 0 , -1 };

        int maxDistance = 0;

        // スタート位置をキューに追加しておく
        queue.add( startX );
        queue.add( startY );

        // キューが空になった時 = 探索できる場所がなくなった時
        // ループ回数 = スタート位置からの距離
        while( !queue.isEmpty()  ) {

            int x = queue.remove();
            int y = queue.remove();

            // 今いる場所が壁の場合処理しない
            if( "#".equals( ss[y][x] ) ){
                continue;
            }

            maxDistance = Math.max( maxDistance , distances[y][x] );

            // 四方を確認
            for( int i = 0 ; i < 4 ; i++ ){

                // 確認先の座標
                int xx = x + dx[i];
                int yy = y + dy[i];

                // 確認先の座標が配列外にいないこと
                if( !( 0 <= yy && yy < ss.length && 0 <= xx && xx < ss[0].length ) ) {
                    continue;
                }

                // 確認先の座標が壁でないこと
                if( !".".equals( ss[yy][xx] ) ) {
                    continue;
                }

                // 既に通った道でないこと
                if( distances[yy][xx] != 0 ){
                    continue;
                }

                // スタート地点でないこと
                if( xx == startX && yy == startY ){
                    continue;
                }

                queue.add( xx );
                queue.add( yy );
                distances[yy][xx] = distances[y][x] + 1;

            }

        }

        return maxDistance;

    }

}


Measured memory_bytes: 25396
N = int(input())
S = input()
left = 0
right = S.count("E")
ans = False
for i in range(N):
    if i > 0:
        left += 1 if S[i - 1] == "W" else 0
    right -= 1 if S[i] == "E" else 0
    if ans is not False:
        ans = min(ans, left + right)
    else:
        ans = left + right
print(ans)

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

const int inf = 1000000037;
const int maxn = 200005;

int n, from, to;
int a[maxn], lis[maxn], ans[maxn];
vector < int > g[maxn];

void dfs (int u, int p = -1) {
	int j = lower_bound(lis, lis + n, a[u]) - lis;
	int w = lis[j];
	lis[j] = a[u], ans[u] = int(lower_bound(lis, lis + n + 1, inf) - lis) - 1;
	for (int v: g[u]) {
		if (v != p)
			dfs(v, u);
	}
	lis[j] = w;
}

signed main () {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	lis[0] = -inf;
	for (int i = 1; i <= n + 1; ++i)
		lis[i] = inf;
	for (int i = 1; i < n; ++i) {
		scanf("%d %d", &from, &to);
		g[from].push_back(to);
		g[to].push_back(from);
	}
	dfs(1);
	for (int i = 1; i <= n; ++i)
		printf("%d\n", ans[i]);
}


Measured memory_bytes: 31388
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def main():
    K, A, B = MI()
    if B - A <= 2:
        return K + 1
    if K <= A:
        return K + 1
    b = A
    K -= A-1
    b += K // 2 * (B - A)
    b += K % 2
    return b


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


Measured memory_bytes: 5388
#include<bits/stdc++.h>
// C++ program to count common subsequence in two strings
using namespace std; 
const int MOD=1e9+7;
// return the number of common subsequence in two strings
int Count_Commom_Subsequences(int *s,int *t,int n1,int n2)
{ 
    int dp[n1+1][n2+1]; 
  
    for(int i=0;i<=n1;i++){
        for(int j=0;j<=n2;j++){
            dp[i][j] = 0;
        }
    }
  
    // for each character of S 
    for(int i=1;i<=n1;i++){
        // for each charcater in T
        for(int j=1;j<=n2;j++){
            // if character are same in both
            // the string
            if(s[i-1]==t[j-1]){
                dp[i][j]=1+dp[i][j-1]+dp[i-1][j];
              dp[i][j]%=MOD;
            }
            else {
                dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
              dp[i][j]=(dp[i][j]%MOD+MOD)%MOD;
            }
        }
    }
    return dp[n1][n2];
}
  
// Driver Program 
int main(){
  int n,m;
  cin>>n>>m;
  int s[n],t[m];
  for(int i=0;i<n;i++)cin>>s[i];
  for(int i=0;i<m;i++)cin>>t[i];
    cout<<Count_Commom_Subsequences(s,t,n,m)+1<<endl;
    return 0; 
} 



Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int INT_INF = 1e9;
const ll MOD = 1e9 + 7;
const int INT_MOD=1e9+7;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 0; i <= n; i++)
#define rrep(i,n) for(int i=n;i>0;i--)
#define RREP(i,n) for(int i=n;i>=0;i--)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
signed main(){
    int a,b;cin>>a>>b;
    if(a>2*b) cout<<a-2*b<<endl;
    else cout<<"0"<<endl;
    return 0;
}

Measured memory_bytes: 256
N, X = map(int, input().split())
L = list(map(int, input().split()))

ans = 1
D = [0] * (N+1)
for i in range(1, N+1):
    D[i] = D[i-1] + L[i-1]
    if D[i] <= X:
        ans += 1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int mod =1e9+7;
const int N = (int)2e5 + 5;



void solve(){
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	if(a>=k){
		cout<<k;
		return;
	}
	if(a+b>=k){
		cout<<a;
		return;
	}
	ll mx=a*1ll;
	ll d=k*1ll-(a+b)*1ll;
	cout<<a*1ll-d*1ll;
}

int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;} 
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        cin >> N;
        vll A(N);
        rep(i, 0, N) cin >> A[i];

        A.push_back(-inf);
        ll std = A[0];
        vll tmp;
        ll money = 1000;
        ll now = 0;
        ll g = -1;
        rep(i, 0, N+1) {
                if (A[i] < std) {
                        ll s = g + 1;
                        g = i - 1;
                        ll buy = money / A[s];
                        money -= buy * A[s];
                        now += buy;

                        money += now * A[g];
                        now = 0;
                }
                std = A[i];
                
        }

        // if (A.back() > std) {
        //                 ll s = g + 1;
        //                 g = N - 1;
        //                 ll buy = money / A[s];
        //                 money -= buy * A[s];
        //                 now += buy;

        //                 money += now * A[g];
        //                 now = 0;

        //                 cout << s << ' ' << g << endl;
        // }
        
        cout << money << endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
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; }

int main(){
  ll n, m;
  cin >> n >> m;
  ll ans = 0;
  vi h(n);
  rep(i,n){
    cin >> h[i];
  }
  vi a(m);
  vi b(m);
  vector<bool> s(n, true);
  rep(i, m){
    cin >> a[i] >> b[i];
    if(h[a[i]-1]>h[b[i]-1]){
      s[b[i] - 1] = false;
    }
    else if(h[a[i]-1]<h[b[i]-1]){
      s[a[i] - 1] = false;
    }
    else {
      s[a[i] - 1] = false;
      s[b[i] - 1] = false;
    }
  }
  rep(i,n){
    if(s[i]==true){
      ans++;
    }
  }
  print(ans);
}

Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 1; i <= n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
#define MP make_pair
#define FI first
#define SE second
#define VI vector<int>
#define CLR(x) memset(x, 0, sizeof(x))
#define SZ(x) (x.size())
#ifdef QWERTIER
#define err(x) cerr<<x<<endl;
#else
#define err(x)
#endif

typedef long long LL;

#define N 100010
LL dp[N];
int x[N];
int n, p, q;
int main() {
#ifdef QWERTIER
  freopen("in.txt", "r", stdin);
#endif
  scanf("%d%d%d", &n, &p, &q);
  LL mind = 0x3f3f3f3f3f3f3f3fll;
  FOR (i, n) {
    scanf("%d", &x[i]);
    mind = min(mind, dp[i-1] + q - x[i]*(LL)p);
    dp[i] = x[i]*(LL)p + mind;
    //cout << i << ':' << dp[i] << endl;
  }
  cout << dp[n] - q;
  return 0;
}


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

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

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;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
char a[5];
int main(){
	ios::sync_with_stdio(false);
	cin>>a+1;
	for(int i=1;i<=3;i++){
		if(a[i]==a[i+1])return cout<<"Bad\n",0;
	}
	cout<<"Good";
	return 0;
}

Measured memory_bytes: 764
import sys
S = input()
if S[0:1] != "A":
    print("WA")
    sys.exit()
s2 = S[2:]
s2 = s2[:-1]
if s2.count("C") != 1:
    print("WA")
    sys.exit()
s3 = S.replace("A", "")
s3 = s3.replace("C", "")
s4 = s3.lower()
if (s3 != s4):
    print("WA")
else:
    print("AC")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll a[n];
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a, a+n);
    multiset<ll> ms;
    reverse(a,a+n);
    ll ans = 0;
    ms.insert(a[0]);
    for(int i=1;i<n;i++){
    	auto itr = ms.end();
    	itr--;
        ans += *itr;
        ms.erase(itr);
        ms.insert(a[i]);
        ms.insert(a[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 14584
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1e9;

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

    vector<vector<int>> dp(n/2+1, vector<int>(2, inf));
    dp[1][0] = 0;
    for(int i=0; i<n-1; i++){
        vector<vector<int>> ndp(n/2+1, vector<int>(2, inf));
        for(int j=0; j<=n/2-1; j++){
            ndp[j+1][0] = min(ndp[j+1][0], min(dp[j][0], dp[j][1]+t[i]));
        }
        for(int j=0; j<=n/2; j++){
            ndp[j][1] = min(ndp[j][1], min(dp[j][0]+t[i], dp[j][1]));
        }
        dp = move(ndp);
    }
    cout << min(dp[n/2][0], dp[n/2][1]) << endl;
    return 0;
}



Measured memory_bytes: 3472