akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
//#include <cfenv>
//#define _GNU_SOURCE 1
#define square(x) ((x)*(x))
using namespace std;
const double INF = 1000.0;
 
/*static void attribute((constructor)) trapfpe()
{
feenableexcept(FE_INVALID|FE_DIVBYZERO|FE_OVERFLOW);
}
*/ //何かの痕跡
int n,a;
double dis[100][101];
double dis2[100][101];
double fdis[100][101];
double touch[100][101];
double geo[100][5];
double mincost[101];
bool used[101];
int par[101];
int rank[101];
//struct edge{ int to,from,cost; };
vector<int> set[100],set2[100],fset[100];
 
void init(int n);
int find(int x);
void unite(int x,int y);
bool same(int x,int y);
double prim();


int main()
{
  while(cin >> n,n){
    init(n);
    
    for(int i=0;i<n;i++){
      //cin >> ((double)geo[i][0]) >> ((double)geo[i][1]) >> ((double)geo[i][2]) >> ((double)geo[i][3]); 
      //cout << square(geo[i][3]) << endl;
      scanf("%lf %lf %lf %lf", &geo[i][0], &geo[i][1], &geo[i][2], &geo[i][3]);
    }
    
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(i==j)continue;
	dis[i][j] = (double)sqrt((double)square(geo[i][0]-geo[j][0]) + (double)square(geo[i][1]-geo[j][1]) + (double)square(geo[i][2]-geo[j][2]));
	touch[i][j] = geo[i][3]+geo[j][3];
	dis2[i][j] = dis[i][j] - touch[i][j]; //cout <<dis2[i][j] << endl;
	if(touch[i][j]>dis[i][j]) unite(i,j);
      }
    }
    
    int p;
    for(int i=0;i<n;i++){
      p = find(i);
      set[p].push_back(i);
    }
    a = 0;
    for(int i=0;i<n;i++){
      if(set[i].empty()) continue;
      set2[a] = set[i];
      a++;
    }
    
    for(int i=0;i<a;i++){
      for(int j=0;j<a;j++){
	if(i==j)continue;
	double dmin = INF;
	for(int k=0;k<set2[i].size();k++){
	  for(int l=0;l<set2[j].size();l++){
	    dmin = min(dmin,dis2[set2[i][k]][set2[j][l]]);
	  }
	}
	fdis[i][j] = dmin; //cout<< dmin << endl;
	dmin = INF;
      }
    }
    
    printf("%.3f\n",prim());
    
    for(int i=0;i<n;i++) set[i].clear();
    for(int i=0;i<a;i++) set2[i].clear();
    
  }
  
}

void init(int n)
{
  for(int i=0;i<n;i++){
    par[i] = i;
    rank[i] = 0;
  }
}

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

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

bool same(int x,int y)
{
  return find(x)==find(y);
}

double prim()
{
  for(int i=0;i<a;i++){
    mincost[i] = INF;
    used[i] = false;
  }
  
  mincost[0] = 0;
  double res = 0.0;
  
  while(true){
    int v = -1;
    for(int i=0;i<a;i++){
      if(!used[i] && (v==-1 || mincost[i]<mincost[v])) v = i;
    }
    
    if(v == -1) break;
    used[v] = true;
    res += mincost[v]; //cout << mincost[v] << ' ' << res << endl;
    
    for(int i=0;i<a;i++){
      mincost[i] = min(mincost[i],fdis[v][i]);
    }
  }
  return res;
}

Measured memory_bytes: 1636
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define debug(x) cerr << #x << ":" << x << "\n"
using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>;

int main() {
    int H, A;
    cin >> H >> A;
    int ans = (H + A - 1) / A;    
    cout << ans << endl;
}

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

using namespace std;

#define fore(i, s, e) for(int i = s; i < e; i++)
#define pb push_back
#define fst first
#define snd second

typedef long long ll;

const int N = 2e5 + 10;
const int M = 1e9 + 7;

int h, w, n;

vector<pair<int, int>> v;

ll fact[N], inv[N];

ll expmod(ll a, ll b) {
    ll r = 1;
    while(b) {
        if(b & 1) r = (a * r) % M;
        b >>= 1;
        a = (a * a) % M;
    }
    return r;
}

void init() {
    fact[0] = 1, inv[0] = 1;
    fore(i, 1, N) {
        fact[i] = (fact[i - 1] * i) % M;
        inv[i] = expmod(fact[i], M - 2);
    }
}

ll get(ll x, ll y) {
    int r = fact[x];
    r = (r * inv[y]) % M;
    r = (r * inv[x - y]) % M;
    return r;
}

ll dp[N];

ll solve() {
    init();

    fore(i, 0, n + 1) {
        dp[i] = get(v[i].fst + v[i].snd, v[i].fst);
        fore(j, 0, i) if(v[j].fst <= v[i].fst && v[j].snd <= v[i].snd) {
            ll p = get(v[i].fst + v[i].snd - v[j].fst - v[j].snd, v[i].fst - v[j].fst);
            p = (p * dp[j]) % M;
            dp[i] = (dp[i] - p + M) % M;
        }
        // cout << dp[i] << endl;
    }
    return dp[n];
}

int main() {
    cin >> h >> w >> n;
    fore(i, 0, n) {
        int r, c; cin >> r >> c; r--, c--;
        v.pb({r, c});
    }
    v.pb({h - 1, w - 1});
    sort(v.begin(), v.end());
    cout << solve() << endl;
}

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

int a[5][5];
map<int,bool>mp;
int main()
{
    int n,val;

    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
            cin>>a[i][j];
    }
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>val,mp[val]=true;

    if(mp[a[1][1]] && mp[a[1][2]] && mp[a[1][3]])
        puts("Yes");
    else if(mp[a[2][1]] && mp[a[2][2]] && mp[a[2][3]])
        puts("Yes");
    else if(mp[a[3][1]] && mp[a[3][2]] && mp[a[3][3]])
        puts("Yes");
    else if(mp[a[1][1]] && mp[a[2][1]] && mp[a[3][1]])
        puts("Yes");
    else if(mp[a[1][2]] && mp[a[2][2]] && mp[a[3][2]])
        puts("Yes");
    else if(mp[a[1][3]] && mp[a[2][3]] && mp[a[3][3]])
        puts("Yes");
    else if(mp[a[1][1]] && mp[a[2][2]] && mp[a[3][3]])
        puts("Yes");
    else if(mp[a[1][3]] && mp[a[2][2]] && mp[a[3][1]])
        puts("Yes");
    else
        puts("No");
}


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

using namespace std;
using ll = long long;

int main() {
    int ans = 0;
    int now = 0;
    int N;
    string S;
    cin >> N >> S;

    for(int i = 0; i < N; i++) {
        if(S.at(i) == 'I') {
            now++;
        } else {
            now--;
        }
        ans = max(ans,now);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3616
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < n; ++i)

char s[100001];

int main() {
	scanf("%s", s);
	int n = strlen(s);
	n += s[0] == s[n - 1];
	printf("%s\n", n & 1 ? "First" : "Second");
}

Measured memory_bytes: 384
import math

S = int(input())
mod = 10**9 + 7
dp = [0] * (S + 1)
dp[0] = 1

for i in range(1,S+1):
    if i < 3:continue
    for j in range(i-2):
        dp[i] += dp[j]
        dp[i] %= mod

print(dp[S])

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

int main() {
  string S, T;
  cin >> S >> T;
  
  int judge1 = 0;
  int judge2 = 0;
   
  if(S.size() + 1 != T.size()){
  judge1 = 1;
  }
  
  for(int i = 0; i < S.size(); i++){
    if(S.at(i) != T.at(i)){
    judge2 = 1;
    break;
    }
  }
  
    
  if (judge1 + judge2 == 0) {
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3604
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>

using namespace std;
long long a[100000];
int main(){
    int N;
    long long L;
    cin >> N >> L;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }

    int length_L_index = -1;
    for(int i = 0; i < N - 1; i++){
        if(a[i] + a[i + 1] >= L){
            length_L_index = i;
            break;
        }
    }
    if(length_L_index < 0){
        cout << "Impossible" << endl;
        return 0;
    }

    cout << "Possible" << endl;
    for(int i = 0; i < length_L_index; i++){
        cout << i + 1 << endl;
    }
    for(int i = N - 2; i >= length_L_index; i --){
        cout << i + 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 1536
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main{
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int s = n%60;
    int h = n/3600;
    int m = (n-h*3600)/60;
    System.out.println(h+":"+m+":"+s);
  }
}

Measured memory_bytes: 24208
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////
const double PI=acos(-1.0);
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    double a,b,c,d;
    cin >> a >> b >> c >> d;
    print(sqrt(a*a+b*b-2*a*b*cos(2*PI*((c+d/60.0)/12.0-d/60.0))));
    return 0;
}

Measured memory_bytes: 4296
#include<stdio.h>

int main()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	if (a == b || a == c || b == c)
		if (a == b && b == c)
			printf("No");
		else
			printf("Yes");
	else
		printf("No");

		
}

Measured memory_bytes: 128
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include<map>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define rpe(i,r,l) for(int i=(r);i>=(l);--i)
#define rpp(i,x,e,head) for(int i=head[x];~i;i=e[i].next)
#define dyes cerr<<"yes"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define pts puts("")
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1LL;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
template <class T> inline void chmax(T &a,T b){if(a<b) a=b;}
template <class T> inline void chmin(T &a,T b){if(a>b) a=b;}
inline void swap(int &a,int &b){int c=a;a=b;b=c;}
using namespace std;
#define mst(a,val) memset(a,val,sizeof(a))
#define pii pair<int,int>
#define piii pair<int,pair<int,int> >
#define mp(i,j) make_pair(i,j)
#define fi first
#define sc second
#define inf (0x3f3f3f3f)
#define id(i,j) ((i-1)*m+j)
const int N=233;
int dp[3][N],a[3][N];
int n;
int main(){
    n=read();
    rep(i,1,2) rep(j,1,n) a[i][j]=read();
    dp[1][1]=a[1][1];
    rep(i,1,2){
        rep(j,1,n){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
        }
    }
    printf("%d\n",dp[2][n]);
    return 0;
}


Measured memory_bytes: 256
d=[]
while True:    
   a=input().split(" ")
   if a[0]=='0' and a[1]=='0':
      break
   d.append(int(a[0]))
   d.append(int(a[1]))
for i in range(0,len(d),2):
    if d[i]>d[i+1]:
      print(d[i+1],d[i])
    else:
      print(d[i],d[i+1])



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

using namespace std;

/*
const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;*/

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define LSOne(S) (S & (-S))
#define isBitSet(S, i) ((S >> i) & 1)

void printV(vi v) {
    for (int i = 0; i<v.size(); ++i) cout << v.at(i) << " ";
    cout << "\n";
}

//g++ -std=c++11 -O2 -Wall c.cpp

void solve() {
    string s; cin >> s;
    if (s[s.length()-1] ==  's') {
        cout << s << "es" << '\n';
    } else {
        cout << s << "s" << "\n";
    }

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    solve();


    /**
     * ALGORITHME DE TRI ET EN LEVER LES DUPLICATES
     * set<int> s( v.begin(), v.end() );
     * v.assign( s.begin(), s.end() );
     * */
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*int n;
ll a;
vector<int> arr;
ll dp[51][2501][51];
ll answer(int cnt, int curr, int total){
    if(cnt == n){
        if(total == 0) return 0;
        ll k = (ll)curr / total;
        if(k * total == curr && k == a) return 1;
        else return 0;
    }
    if(curr > total * a) return 0;
    /*if(total != 0){
        double avg = curr / total;
        if(avg > (double)a && avg <= arr[curr]) return 0;
    }
    if(dp[cnt][curr][total] != 0) return dp[cnt][curr][total];
    //if(total != 0 && curr / total < a) return;
    return dp[cnt][curr][total] = answer(cnt+1, curr, total) + answer(cnt+1, curr+arr[cnt],  total+1);
}
*/
int main() {
	// your code goes here
    //int n, a;
   /* cin >> n >> a;
    arr.resize(n);
    for(int i=0; i<n; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());
    ll ans = answer(0, 0, 0);
    cout << ans << endl;*/
    int n;
    ll x; cin >> n >> x;
    ll arr[n];
    for(int i=0; i<n; i++) cin >> arr[i];
    ll cnt = 0;
    for(int i=1; i<n; i++){
        ll sub = arr[i] + arr[i-1];
        if(sub > x){
            ll exc = sub - x;
            if(exc > arr[i]) {arr[i] = 0;}
            else arr[i] = arr[i] - exc;
            cnt += exc;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=998244353;
int main(){
    ll r;cin>>r;
    cout<<r*r<<endl;
}

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

#define     fast()              ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define     ll                  long long int
#define     test()              ll t; cin>>t; while(t--) 
#define     lp0(i,begin,end)    for(ll i=begin;i<end;i++)
#define     lp1(i,begin,end)    for(ll i=begin;i<=end;i++)
#define     rlp(i,begin,end)    for(ll i=end;i>=begin;i--)
#define     prec(n)             fixed<<setprecision(n)
#define     initial(a,i)        memset(a,i,sizeof(a))
#define     pb                  push_back
#define     PI                  3.1415926535897932384626433832795
#define     MOD                 1000000007
#define     F                   first
#define     S                   second
#define     all(a)              (a).begin(),(a).end()
#define     BPC(x)              __builtin_popcountll(x)
#define     gcd(a,b)            __gcd(a,b)

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

ll power(ll x,ll n)
{
    ll result = 1;
    while (n)
    {
        if (n & 1)
            result = result * x;
        n = n / 2;
        x = x * x;
    }
    return result;
}


// Solution Function
void solution(ll compte)
{
    // cout<<compte<<"\n";
    ll a, b;
    cin >> a >> b;
    cout << (6-a-b);
}
// Driver Function
int main()
{
    ll compte = 1;
    //test()
    //{
        solution(compte);
        compte++;
    //}
    return 0;
}


Measured memory_bytes: 3512
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

while True:
    H = int(input())
    if H == 0:
        break
    B = [0] * H
    for i in range(H):
        B[i] = list(map(int, input().split()))
    W = len(B[i])

    score = 0
    while True:
        # erase step
        for i in range(H):
            start = 0
            while start < W:
                count = 1
                while start + count < W and B[i][start] == B[i][start + count]:
                    count += 1
                if count >= 3:
                    score += B[i][start] * count
                    for j in range(start, start + count):
                        B[i][j] = 0
                start += count
        # drop step
        updated = False
        for i in range(H - 1, -1, -1):
            for j in range(W - 1, -1, -1):
                if B[i][j] != 0:
                    continue
                new_col = []
                for k in range(i, -1, -1):
                    if B[k][j] == 0:
                        continue
                    new_col.append(B[k][j])
                l = 0
                for k in range(i, -1, -1):
                    if l >= len(new_col):
                        B[k][j] = 0
                    else:
                        B[k][j] = new_col[l]
                        updated = True
                    l += 1
        if not updated:
            break
    print(score)






Measured memory_bytes: 6100
def diff(a):
    m = min(a)
    return sum(map(lambda x: x - m, a))

a, b, c = map(int, input().split())
cnt = 0
while a != b or b != c:
    next = []
    next.append([a + 2, b, c])
    next.append([a, b + 2, c])
    next.append([a, b, c + 2])
    next.append([a + 1, b + 1, c])
    next.append([a + 1, b, c + 1])
    next.append([a, b + 1, c + 1])
    d = list(map(lambda x: diff(x), next))
    m = min(d)
    i = d.index(m)
    a, b, c = tuple(next[i])
    # print(a, b, c)
    cnt += 1
    # if m == 0:
    #     break
print(cnt)

Measured memory_bytes: 3064
fn solve() {
    let (mut l, mut r): (usize, usize) = (read::<usize>(), read::<usize>());
    let mut res = 2019;
    if l >= r || l + 2019 <= r {
        res = 0;
    } else {
        l %= 2019;
        r %= 2019;
        for i in l..r + 1 {
            for j in i + 1..r + 1 {
                res = min(res, i * j % 2019);
            }
        }
    }
    println!("{}", res);
}

fn main() {
    let stack_size = 104_857_600;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min, Reverse};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========


Measured memory_bytes: 2220
n = int(input())
ac = 0
wa = 0
tle = 0
re = 0
for i in range(n):
  s = input()
  if s == "AC":
    ac += 1
  elif s == "WA":
    wa += 1
  elif s == "TLE":
    tle += 1
  else:
    re += 1
print("AC x",ac)
print("WA x", wa)
print("TLE x", tle)
print("RE x", re)


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

#define fi first
#define se second
#define pb push_back

typedef long long LL;
typedef long double LD;

const LL INF = (1LL << 60);

typedef pair<LL,LL> PL;
LL knapsack_01(vector<PL>& items, int n, LL w);

int main() {

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

  int n; LL w;
  cin >> n >> w;

  vector<PL> items; items.assign(n, {0, 0});
  for (int i = 0; i < n; i++) {
    cin >> items[i].fi >> items[i].se;
  }

  LL ans = knapsack_01(items, n, w);

  cout << ans << endl;

  return 0;
}

LL dp[105][100005];
LL solve(vector<PL>& items, int n, LL w) {
  if (w < 0) {
    return -INF;
  } else if (n == 0 || w == 0) {
    return 0;
  } else if (dp[n][w] != -1) {
    return dp[n][w];
  } else {
    return dp[n][w] = max(solve(items, n - 1, w),
                          solve(items, n - 1, w - items[n - 1].se) + items[n - 1].fi);
  }
}

LL knapsack_01(vector<PL>& items, int n, LL w) {
  memset(dp, -1, sizeof(dp));
  return solve(items, n, w);
}


Measured memory_bytes: 85228
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N,W;
int nowv, noww;
int wgt[110];
int val[110];
int dp[110][350][110];//枚举第first个物品，容量second，一共选了third的物品
int main()
{
    scanf("%d %d", &N, &W);
    for(int i = 1; i <= N; i++)
    {
        scanf("%d %d", &wgt[i], &val[i]);
    }
    int ans = 0;
    int minn = min(N,W/(wgt[1]+3));
    int maxn = min(N,W/wgt[1]);
    if(minn == N){
        for(int i = 1; i <= N; i++)ans+=val[i];
        printf("%d\n", ans);
        return 0;
    }
    int MW = 3*maxn;
        for(int j = 1; j <= N; j++)
        {
            for(int k = 1; k <= j; k++)
            {
                if(k < j)for(int l = 0; l < wgt[j]-wgt[1]; l++)
                {
                    dp[j][l][k] = dp[j-1][l][k];
                }
                for(int l = wgt[j]-wgt[1]; l <= MW; l++)
                {
                    if(l > 0)dp[j][l][k] = max(dp[j][l][k],dp[j][l-1][k]);
                    dp[j][l][k] = max(dp[j-1][l-wgt[j]+wgt[1]][k-1] + val[j], dp[j-1][l][k]);
                }

            }
        }
        for(int i = minn; i <= N; i++)
        {
            for(int j = minn; j <= maxn; j++)
            {
                for(int l = 0; l <= min(MW,W-wgt[1]*j); l++)
                {
                    ans = max(ans,dp[i][l][j]);
                }
            }
        }

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


    return 0;
}


Measured memory_bytes: 16128
import java.util.Scanner;

public class Main {
	
	public static void main(String []args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		
		
		int ans1= 0;
		int ans2 = 0;
		int ans3 = 0;
		
	for(int i = 1 ; i <= 3500 ; i++) {
		for(int j = 1 ; j <= 3500 ; j++) {
			long temp = (long)i * j * n;
			long temp1 = (long)(4 * i * j) - n * (i + j);
			if(temp1 <= 0) continue;
			if(temp % temp1 == 0 ) {
				ans1 = i;
				ans2 = j ;
				ans3 = (int)(temp/temp1);
			}
		}
	}
		System.out.println(ans1+" "+ans2+" "+ans3);
		
		}	
	}



Measured memory_bytes: 24020
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;
const int MAXN = 200000 + 10;

int n, q;
int query[MAXN][2];

char input[MAXN];

inline bool check(int x){
    for(register int i=1; i<=q; i++){
        if(query[i][0] == input[x] - 'A'){
            x += query[i][1];

            if(x <= 0)
                return true;
            
            if(x > n)
                return false;
        }
    }

    return false;
}

inline bool check2(int x){
    for(register int i=1; i<=q; i++){
        if(query[i][0] == input[x] - 'A'){
            x += query[i][1];

            if(x > n)
                return true;
            
            if(x <= 0)
                return false;
        }
    }

    return false;
}

/*
int main(){
    scanf("%d%d", &n, &q);
    scanf("%s", input + 1);

    for(register int i=1; i<=q; i++){
        char A, B;
        scanf(" %c %c", &A, &B);

        query[i][0] = A - 'A';
        query[i][1] = (B == 'L' ? -1 : 1);
    }

    int lL = 1, lR = n;
    int rL = 1, rR = n;

    int ansl = 0, ansr = n + 1;

    while(lL <= lR){
        int mid = (lL + lR) >> 1;

        if(check(mid)){
            lL = mid + 1;
            ansl = mid;
        }else{
            lR = mid - 1;
        }
    }

    while(rL <= rR){
        int mid = (rL + rR) >> 1;

        if(check2(mid)){
            rR = mid - 1;
            ansr = mid;
        }else{
            rL = mid + 1;
        }
    }

    printf("%d\n", (ansr - ansl + 1));
    return 0;
}
*/

int main(){
    scanf("%d%d", &n, &q);
    scanf("%s", input + 1);

    for(register int i=1; i<=q; i++){
        char A, B;
        scanf(" %c %c", &A, &B);

        query[i][0] = A - 'A';
        query[i][1] = (B == 'L' ? -1 : 1);
    }

	int l=1,r=n,ansl=0,ansr=n+1;

	while (l<=r){
		int mid=(l+r)>>1;
		if (check(mid)) {ansl=mid;l=mid+1;}
		else r=mid-1;
	}

	l=1;
    r=n;

	while (l<=r){
		int mid=(l+r)>>1;
		if (check2(mid)) {ansr=mid;r=mid-1;}
		else l=mid+1;
	}

	printf("%d",n-ansl-(n-ansr+1));
	return 0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long Q, H, S, D, N;
	cin >> Q >> H >> S >> D >> N;
	H = min(H, 2*Q);
	S = min(S, 2*H);
	D = min(D, 2*S);
	cout << (N / 2) * D + (N % 2) * S << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int linarSearch(int *A, int n, int key ) {
  int i = 0;
  
  A[n] = key;
  while(A[i] != key) {
    i++;
  }
  if(i == n) return 0;
  return 1;
  
}

int main () {
  int i, n, q, S[10000], T[500], m = 0;

  scanf("%d", &n);
  for(i = 0; i < n; i++) scanf("%d", &S[i]);
  scanf("%d", &q);
  for(i = 0; i < q; i++) scanf("%d", &T[i]);

  for(i = 0; i < q; i++) {
    m += linarSearch(S, n, T[i]);
  }

  printf("%d\n", m);
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
  int y,m,d;

  scanf("%d/%d/%d",&y,&m,&d);

  if(m <= 4){
    cout << "Heisei" << endl;
  } else {
    cout << "TBD" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;

int main(){
    ll a,b;cin>>a>>b;
    ll c=b-a;
    c=c*(c+1)/2;
    cout<<c-b<<endl;
    return 0;
}


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

const long long INF = 5e18;

void solve() {
    int N;
    cin >> N;
    vector<double> t(N + 1), v(N);
    for (int i = 0; i < N; i++) {
        cin >> t.at(i + 1);
        t.at(i + 1) += t.at(i);
    }
    for (int i = 0; i < N; i++) cin >> v.at(i);
    double ans = 0, l, r;
    for (double i = 0; i < t.at(N); i += 0.5) {
        l = min(i, t.at(N) - i);
        r = min(i + 0.5, t.at(N) - 0.5 - i);
        for (int j = 0; j < N; j++) {
            if (i + 0.5 <= t.at(j)) {
                l = min(l, v.at(j) + (t.at(j) - i));
                r = min(r, v.at(j) + (t.at(j) - 0.5 - i));
            } else if (i >= t.at(j + 1)) {
                l = min(l, v.at(j) + (i - t.at(j + 1)));
                r = min(r, v.at(j) + (i + 0.5 - t.at(j + 1)));
            } else {
                l = min(l, v.at(j));
                r = min(r, v.at(j));
            }
        }
        ans += (l + r) * 0.25;
    }
    cout << fixed << ans << endl;
    return;
}

int main() {
    solve();
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007


ans, cnt = 1, [0, 0, 0]
for i in a:
    ans = ans * cnt.count(i) % mod
    for j in range(3):
        if cnt[j] == i:
            cnt[j] += 1
            break
print(ans)


Measured memory_bytes: 83864
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))
x = 1000
b_list = []
start_a = a_list[n - 1]
a = start_a
flag = 0
for i in range(2, len(a_list) + 1):
    if a_list[n - i] <= a:
        flag = 1
        a = a_list[n - i]
        if n - i == 0:
            b_list.append(start_a)
            b_list.append(a)
    else:
        if flag == 0:
            a = a_list[n - i]
            start_a = a
        else:
            b_list.append(start_a)
            b_list.append(a)
            a = a_list[n - i]
            start_a = a
b_list.reverse()
for i in range(len(b_list) // 2):
    c = x // b_list[2 * i]
    x -= b_list[2 * i] * c
    x += b_list[2 * i + 1] * c

print(x)



Measured memory_bytes: 9220
#include "stdio.h"
typedef long long ll;
ll gcd(ll a,ll b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
int main()
{
	ll a,b;
	while(scanf("%lld%lld",&a,&b)!=EOF)
	{
		printf("%lld %lld\n",gcd(a,b),a*b/gcd(a,b));
	}
	return 0;
}

Measured memory_bytes: 596
/**
 * Created By: Anonyman637
 * Created On: 4/19/2020 6:13:49 PM
 */

/* =============================================================================
   ================================== HEADERS ==================================
   ========================================================================== */

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

/* =============================================================================
   ================================= TYPEDEFS ==================================
   ========================================================================== */

typedef char i8;
typedef short i16;
typedef int i32;
typedef long long i64;

typedef unsigned char ui8;
typedef unsigned short ui16;
typedef unsigned int ui32;
typedef unsigned long long ui64;

typedef double db;
typedef long double ldb;

using namespace std;

/* =============================================================================
   ================================== MACROS ===================================
   ========================================================================== */

#ifdef DEBUG
#define debug(format, ...) printf(format, __VA_ARGS__)
#else
#define debug(format, ...) 
#endif

#define NOCSYNCIOS 1

#define FOREACH(it, cont) for (const auto& it : (cont)) 

#define ALL(cont) (cont).begin(), (cont).end()
#define RALL(cont) (cont).end(), (cont).begin()
#define SP(x) fixed << setprecision(x)

#define MP make_pair
#define PB push_back
#define fi first
#define se second

#define EPS 1e-9
#define MOD 1000000007

/* =============================================================================
   ================================== GLOBALS ==================================
   ========================================================================== */

const double pi=acos(-1.0);

/* =============================================================================
   =================================== SETUP ===================================
   ========================================================================== */

i32 setup() {

#if NOCSYNCIOS
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#endif

#if FILEIO
	#define FILEI
	if(freopen(OUTFILE, "w", stdout) == NULL) return 402;
#endif

#ifdef FILEI
	if(freopen(INFILE, "r", stdin) == NULL) return 401;
#endif

	return 0;
}


/* =============================================================================
   ================================= FUNCTIONS =================================
   ========================================================================== */

i32 main() {

	i32 errorInSetup = setup();
	if (errorInSetup) exit(errorInSetup);

	i32 i, t;
	i32 r;

	cin >> r;
	cout << 2 * 3.14159 * r;
	
	return 0;
}


Measured memory_bytes: 3800
#include <stdio.h>

int main(void)
{
	int a,b,d,r;
	double f;
	scanf("%d %d",&a,&b);
	d=a/b;
	r=a%b;
	f=(1.0*a)/(1.0*b);
	printf("%d %d %.5lf\n",d,r,f);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define itn int
#define gI gi

using namespace std;

typedef long long ll;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline ll gl()
{
	ll f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

int ans, n, m, a[200003], minn = 200003;
char s[100003];

int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = gi();
	for (int i = 1; i <= n; i+=1) a[i] = gi();
	for (int i = 1; i <= n; i+=1)
	{
		minn = min(minn, a[i]);
		if (minn == a[i]) ++ans;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <limits>
#include <sstream>

using namespace std;

int main (void)
{
	long a[5],b[5];

	for (int i = 0; i < 4; i++)
	{
		cin >> a[i] >> b[i];
	}

	for (int i = 0; i < 4; i++)
	{
		if (a[i] == 1)
		{
			cout << b[i] * 6000 << endl;
		}
		else if (a[i] == 2)
		{
			cout << b[i] * 4000 << endl;
		}
		else if (a[i] == 3)
		{
			cout << b[i] * 3000 << endl;
		}
		else
		{
			cout << b[i] * 2000 << endl;
		}
	}
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
string s;
int len,y=0,x=0,ans=0;
int main(){
	cin>>s;
	len=s.length();
	for(register int i=0;i<len;i++){
		if(x==y){
			x++;
			if(s[i]=='p')ans--;
		}
		else{
			y++;
			if(s[i]=='g')ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(void)
{
    int n, h[20], highest;
    int count = 0;

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

    highest = h[0];
    for (int i=0; i<n; i++) {
        if (h[i] >= highest) {
            count += 1;
            highest = h[i];
        }
    }

    cout << count << endl;

    return 0;
}

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

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;


static const long long mod = 1000000007;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

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

  vll as(n);
  rep(i,n) {
    cin >> as[i];
    as[i]--;
  }

  ll cur = 0;
  map<ll, ll> vsd;
  map<ll, ll> rvsd;
  dqll path;
  ll sti, eni;
  rep(i, n + 5){
    if(i == k) {
      cout << cur + 1 << endl;
      return 0;
    }

    if(vsd.count(cur) != 0) {
      eni = i;
      sti = vsd[cur];
      break;
    }
    vsd[cur] = i;
    rvsd[i] = cur;
    path.push_back(cur);
    cur = as[cur];
  }

  k -= sti;
  ll len = eni - sti;
  ll ansi = k%len + sti;
  cout << rvsd[ansi] + 1 << endl;

  return 0;
}


Measured memory_bytes: 26204
#include <cstdio>           // printf(), scanf()
#include <vector>
#include <queue>
#include <algorithm>        // max()

using namespace std;

static const int MAX_N = 100000;
static const int INFTY = 1 << 30;

class edge
{
public:
	int t, w;
	edge() {}
	edge(int t, int w): t(t), w(w) {}
};

vector<edge> G[MAX_N];
int n;
int d[MAX_N];

bool vis[MAX_N];
int count;

void
bfs(int s)
{
	for (int i = 0; i < n; ++i)
		d[i] = INFTY;

	queue<int> Q;
	Q.push(s);
	d[s] = 0;
	while(!Q.empty())
	{
		int u = Q.front(); Q.pop();
		for (unsigned int i = 0; i < G[u].size(); ++i)
		{
			edge e = G[u][i];
			if (d[e.t] == INFTY)
			{
				d[e.t] = d[u] + e.w;
				Q.push(e.t);
			}
		}
	}
}

int
solve()
{
	// ??????????????? s ???????????????????????? tgt ????±???????
	bfs(0);
	int maxv = 0;
	int tgt = 0;
	for (int i = 0; i < n; ++i)
	{
		if (d[i] != INFTY && d[i] > maxv)
		{
			maxv = d[i];
			tgt = i;
		}
	}

	// tgt ????????????????????????????????¢ maxv ????±???????
	bfs(tgt);
	maxv = 0;
	for (int i = 0; i < n; ++i)
	{
		if (d[i] != INFTY)
			maxv = max(maxv, d[i]);
	}

	return maxv;
}

int
main(int argc, char** argv)
{
	int s, t, w;

	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i)
	{
		scanf("%d %d %d", &s, &t, &w);
		G[s].push_back(edge(t, w));
		G[t].push_back(edge(s, w));
	}

	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 9528
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

bool isPrime(int n){
    for(int i = 2; i*i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

int dp[100010];

int main(){
   int Q; cin >> Q;
   dp[1] = 0;
   repr(i,1,100000){
       if((i+1)%2 == 1 && isPrime(i+1) && isPrime((i+2)/2)) dp[i+1] = dp[i]+1;
       else dp[i+1] = dp[i];
   }
   while(Q--){
       int l,r; cin >> l >> r;
       int ans = dp[r] - dp[l-1];
       cout << ans << endl;
   }
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
	int n, jsum = 0;
	double inp, bsum = 0;
	cin >> n;
	string s;
	REP(i, n){
		cin >> inp >> s;
		if(s == "JPY") jsum += inp;
		else bsum += inp;
	}

	double ans = jsum + 380000* bsum;

	cout << ans << endl;
}


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

using namespace std;

int main(){

    int n;
    string s, t;

    cin >> n >> s >> t;

    for(int i = 0; i < n; i++){
        bool flag = true;
        for(int j = 0; j < n - i; j++){
            if(s[i + j] != t[j]){
                flag = false;
            }
        }
        if(flag){
            cout << n + i << endl;
            return 0;
        }
    }

    cout << 2 * n << endl;


}

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

using Pair = std::array<double, 2>;

double dist(const Pair& p1, const Pair& p2) {
	const double dx = p1[0] - p2[0];
	const double dy = p1[1] - p2[1];

	return std::sqrt(dx * dx + dy * dy);
}

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

	std::vector<Pair> town(n);
	for (auto&& t : town)
		std::cin >> t[0] >> t[1];

	std::vector<int> perm(n);
	for (int i = 0; i < n; ++i)
		perm[i] = i;

	double ans = 0;
	do {
		for (int i = 1; i < n; ++i)
			ans += dist(town[perm[i - 1]], town[perm[i]]);
	} while (std::next_permutation(perm.begin(), perm.end()));

	for (int i = 2; i <= n; ++i)
		ans /= i;

	std::cout << std::setprecision(10) << std::fixed <<  ans << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

class BIT{
public:
  ll n,bit[555555];
  BIT(){fill(bit,bit+555555,0);}
  void add(ll i,ll x){
    while(i<=n){
      bit[i]+=x;
      i+=i&-i;
    }
  }
  ll sum(ll i){
    ll s=0;
    while(i>0){
      s+=bit[i];
      i-=i&-i;
    }
    return s;
  }
};

BIT b=BIT(),b2=BIT();

void Main() {
  ll T;
  R T;
  b.n=b2.n=T+1;
  PP p[T];
  rep(i,T) {
    R p[i].F;
    if(p[i].F==1) cin >> p[i].S.F >> p[i].S.S;
  }
  vector<P> v;
  ll e[T];
  rep(i,T) {
    if(p[i].F==1) v.pb(P(p[i].S.F,i));
  }
  sort(all(v));
  rep(i,v.size()) e[v[i].S]=i+1;
  ll n=0,s=0;;
  rep(i,T) {
    if(p[i].F==1) {
      b.add(e[i],p[i].S.F);
      b2.add(e[i],1);
      s+=p[i].S.S;
      n++;
    } else {
      ll l=0,r=T;
      while(l+1<r) {
        ll m=(l+r)/2;
        if(b2.sum(m)<(n+1)/2) l=m;
        else r=m;
      }
      ll ans=0;
      ll x=b.sum(r);
      ll y=b.sum(T)-b.sum(r);
      ll x2=b2.sum(r);
      ll y2=b2.sum(T)-b2.sum(r);
      ll d=b.sum(r)-b.sum(r-1);
      pr(d,y-y2*d+x2*d-x+s);
    }
  }
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 19824
#include<bits/stdc++.h>
#define mod LLONG_MAX
#define mod1 998244353
#define Mmax 1000005
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long int li;
typedef unsigned long long int ull;
using namespace std;
bool sortbysec(const pair<li,li>&a,const pair<li,li>&b)
{
    return (a.second<b.second);
}
bool comp(pair<li,pair<li,li>>a,pair<li,pair<li,li>>b)
{
  if(a.first<b.first)
  return 1;
  else if(a.first>b.first)
  return 0;
  else
  {
    return a.second.first<b.second.first;
  }
}
li mpow(li x,li y)
{
  li ans=1;
  while(y)
  {
    if(y%2!=0)
    ans=(ans%mod)*(x%mod)%mod;
    y/=2;
    x=((x%mod)*(x%mod))%mod;
  }
  return ans;
}
li modInverse(li n)
{
    return mpow(n, mod-2);
}

li nCrModPFermat(li n, li r,li x,li y,li z)
{
   // Base case
   if (r==0)
      return 1;
    // li fac[n+1];
    // fac[0] = 1;
    // for (int i=1 ; i<=n; i++)
    //     fac[i] = fac[i-1]*i%mod;
    return (x* modInverse(y) % mod *modInverse(z) % mod) % mod;
}
void bfs(vector<li>v[],li visit[],li s,li ans[])
{
  deque<li>q;
  q.push_back(s);
  visit[s]=1;
  while(!q.empty())
  {
    li x=q.front();
    q.pop_front();
    for(auto i=v[x].begin();i!=v[x].end();i++)
    {
      if(!visit[*i])
      {
        q.push_back(*i);
        visit[*i]=1;
      }
    }
  }
}
void buildtree(int*tree,int*arr,int start,int end,int treeNode)
{
  if(start<end)
  {
    int mid=start+(end-start)/2;
    buildtree(tree,arr,start,mid,2*treeNode);
    buildtree(tree,arr,mid+1,end,2*treeNode+1);
    tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
  }
}
void update(int*tree,int*arr,int start,int end,int pos,int val,int treeNode)
{
  if(start==end)
  tree[treeNode]=val;
  else
  {
    int mid=start+(end-start)/2;
    if(pos<=mid)
    update(tree,arr,start,mid,pos,val,2*treeNode);
    else
    update(tree,arr,mid+1,end,pos,val,2*treeNode+1);
    tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
  }
}

void dfs(vector<li>v[],li visit[],li s,li c[],li ans[],map<li,li>*m,li pred[])
{
    visit[s]=1;
     (*m)[c[s]]++;
    for(auto i=v[s].begin();i!=v[s].end();i++)
      {
        if(!visit[*i])
        {pred[*i]=s;
           dfs(v,visit,*i,c,ans,m,pred);
        }
      }
      if((*m)[c[pred[s]]]==1)
    ans[s]=(*m).size()-1;
    else
    ans[s]=(*m).size();
}
vector<li>factor(li n)
{
  vector<li>v;
  if(n%2==0)
  {
    while(n%2==0)
    {n/=2;
    v.push_back(2);
    }
  }
  for(li i=3;i<=sqrt(n);i+=2)
  {
    if(n%i==0)
    {
      while(n%i==0)
      {n/=i;
      v.push_back(i);
      }
    }
  }
  if(n>1)
  v.push_back(n);
  return v;
}
int main()
{
// li t,i,j;
// cin>>t;
// while(t--)
// {
//
//   cout<<endl;
// }
li a,b,c,k;
cin>>a>>b>>c>>k;
if(k<=a)
cout<<k;
else if(k>a&&k<=a+b)
cout<<a;
else
cout<<2*a+b-k;
return 0;
}


Measured memory_bytes: 3728
#include<stdio.h>
#define N 110
int main(){
  int n,a[N],b[N];
  scanf("%d",&n);
  for(int i = 0;i < n; i++){
    scanf("%d",&a[i]);
    b[(n-1)-i]=a[i];
  }

  for(int i = 0;i < n; i++){
    printf("%d",b[i]);
    if(i+1!=n){
      putchar(' ');
    }
  }
  putchar('\n');


}



Measured memory_bytes: 2072
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

template <typename Abelian>
struct BIT0based {
  BIT0based(int n, const Abelian UNITY = 0) : n(n), UNITY(UNITY), dat(n, UNITY) {}

  void add(int idx, Abelian val) {
    while (idx < n) {
      dat[idx] += val;
      idx |= idx + 1;
    }
  }

  Abelian sum(int idx) {
    Abelian res = UNITY;
    --idx;
    while (idx >= 0) {
      res += dat[idx];
      idx = (idx & (idx + 1)) - 1;
    }
    return res;
  }

  Abelian sum(int left, int right) {
    if (right <= left) return UNITY;
    return sum(right) - sum(left);
  }

  Abelian operator[](const int idx) { return sum(idx, idx + 1); }

  int lower_bound(Abelian val) {
    if (val <= UNITY) return 0;
    int res = 0, exponent = 1;
    while (exponent <= n) exponent <<= 1;
    for (int mask = exponent >> 1; mask > 0; mask >>= 1) {
      if (res + mask - 1 < n && dat[res + mask - 1] < val) {
        val -= dat[res + mask - 1];
        res += mask;
      }
    }
    return res;
  }

private:
  int n;
  const Abelian UNITY;
  vector<Abelian> dat;
};

int main() {
  int n, m; cin >> n >> m;
  vector<pair<pair<int, int>, int>> seg;
  REP(_, n) {
    int l, r; cin >> l >> r;
    seg.emplace_back(make_pair(r + 1, l), 0);
  }
  FOR(d, 2, m + 1) {
    for (int sta = d; sta <= m; sta += d) {
      seg.emplace_back(make_pair(sta, INF + sta - d + 1), d);
      if (sta < m && sta + d > m) seg.emplace_back(make_pair(m + 1, INF + sta + 1), d);
    }
  }
  sort(ALL(seg));
  vector<int> ans(m + 1, n);
  BIT0based<int> bit(m + 1);
  for (auto e : seg) {
    int l, r; tie(r, l) = e.first;
    if (e.second == 0) {
      // cout << '[' << l << ',' << r << "] " << e.second << '\n';
      bit.add(l, 1);
    } else {
      // cout << '[' << l - INF << ',' << r << "] " << e.second << '\n';
      ans[e.second] -= bit.sum(l - INF, r);
      // cout << bit.sum(l - INF, r) << '\n';
    }
    // REP(i, m + 1) cout << bit[i] << " \n"[i == m];
  }
  FOR(d, 1, m + 1) cout << ans[d] << '\n';
  return 0;
}


Measured memory_bytes: 26728