akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653
#define INF 100000000000000

int main(){
    ll k; cin >> k;
    string s; cin >> s;
    if (s.size()<=k){
        cout << s << endl;
    }
    else{
        string t;
        REP(i,k) t+=s[i];
        REP(i,3) t+='.';
        cout << t << endl;
    }
}

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

ll modpow(ll a, ll N) {
  ll ans = 1;
  ll tmp = a;
  while(N > 0) {
    if(N % 2 == 1) {
      ans *= tmp;
      ans %= mod;
    }
    N /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  return ans;
}
ll modinv(ll a, ll m=mod) {
  ll b = m, u = 1, v = 0;
  while(b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if(u < 0) u += m;
  return u;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<ll> C(N);
  rep(i, N) cin >> C[i];
  sort(all(C), greater<ll>());
  ll ans = 0;
  rep(i, N) {
    (ans += C[i] * modpow(4, N-1) % mod * (i+2) % mod) %= mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;

int main(){
    int n ; 
    cin >> n ;
    for(int i=0;i<n;i++){
    	char x ; 
    	cin >> x ; 
    	debug() << imie(x) ; 
    	if ( x == 'Y' ) {
    		cout << "Four" << endl;
    		return 0 ; 
    	}
    }
    cout << "Three" << endl;
    return 0 ;
}


Measured memory_bytes: 256
inline fun <T> T.also(block: (T) -> Unit): T { block(this); return this }

fun Int.divCeil(a: Int) = (this + a - 1) / a

fun main(args: Array<String>) {
    val (N, H) = readLine()!!.split(" ").map{ it.toInt() }
    val damages = (1..N).map { readLine()!!.split(" ").map{ it.toInt() }.let{ Pair(it[0], it[1])} }

    val maxNormal = damages
            .map { it.first }.max()!!
    val sortedSpecial = damages
            .map { it.second }
            .filter { it > maxNormal }
            .sortedDescending()
    val specialSum = sortedSpecial.sum()


    print(if (specialSum < H) {
        sortedSpecial.size + (H - specialSum).divCeil(maxNormal)
    } else {
        var partSum = 0
        sortedSpecial.takeWhile { b ->
            (partSum < H).also {
                partSum += b
            }
        }.size
    })
}

Measured memory_bytes: 64244
def calc_before(x, s) :
    ans = []
    for i in range(1, s) :
        i_tax = int(i + i*x/100) 
        for j in range(1, s) :
            j_tax = int(j + j*x/100)
            if i_tax + j_tax > s :
                break
            if i_tax + j_tax == s :
                ans.append([i, j])
    return ans

def calc_after(i, j, y) :
    ans = int(i + i*y/100) + int(j + j*y/100)
    return ans

while True :
    x, y, s = map(int, input().split())
    if x == 0 and y == 0 :
        break
    
    lst = calc_before(x, s)
    max_price = 0
    for i in range(len(lst)) :
        price = calc_after(lst[i][0], lst[i][1], y)
        max_price = max(price, max_price)
    print(max_price)
            


Measured memory_bytes: 5792
from collections import deque

N=int(input())
AB=[list(map(int,input().split())) for i in range(N)]
CD=[list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x:x[1], reverse=True)
CD.sort()
CD=deque(CD)
cc=0

while len(CD)>0:
    p=CD.popleft()
    c,d=p[0],p[1]
    for i in range(len(AB)):
        if AB[i][0]<c and AB[i][1]<d:
            AB=AB[:i]+AB[i+1:]
            cc+=1
            break

print(cc)

Measured memory_bytes: 3436
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i < e; ++i)
#define sort_(a) sort(a.begin(), a.end())
#define rsort(a) sort(a.rbegin(), a.rend())
#define sum(a) accumulate(a.begin(), a.end(), 0LL)
#define __lcm(a, b) std::__detail::__lcm(a, b)
typedef long long ll;
const long mod = 1e9 + 7;

int main(void) {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
#endif

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

  int H, W;
  cin >> H >> W;
  vector<string> A(H);
  rep(i, 0, H+2) {
    cin >> A[i];
  }
  cout << string(W + 2, '#') << endl;
  rep(i, 0, H) {
    cout << '#' << A[i] << '#' << endl;
  }
  cout << string(W + 2, '#') << endl;
  return 0;
}


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

#define int long long int
#define ll long long
#define quickie ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rep1(i, a, b) for(int i=a; i<=b; i++)
#define repp(i, a, b) for(int i=b-1; i>=a; i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define db double
#define mi map<int, int>
#define vi vector<int>
#define qi queue<int>
#define MI(x) power(x, mod-2)
#define test int t; cin >> t;
#define all(a) a.begin(),a.end()
#define mod 1000000007
#define pi 3.141592653589
#define fact(n) rep(i, 1, n+1)ft.pb((ft[i-1]*i)%mod) ;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
// template<typename T>
// using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
//(*****FOR USING ORDERED SET CHANGE INT*******)


signed main() {
    quickie
    int n ;
    cin >> n ;
    int a[n] ;
    int val[n] ;
    rep(i, 0, n) cin >> a[i] ;
    val[n-1] = 0 ;
    val[n-2] = abs(a[n-1]-a[n-2]) ;
    for(int i=n-3; i>=0; i--) {
        val[i] = min(abs(a[i]-a[i+1])+val[i+1], abs(a[i]-a[i+2])+val[i+2]) ;
    }
    cout << val[0] << "\n" ;
}

int power(int x, int y) {
    int res = 1; x %= mod;
    while (y > 0) {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res%mod;
}

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

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

struct Point{ double x, y; };

Point set_p(double a, double b)
{
    Point p;
    p.x = a; p.y = b;
    return p;
}

struct Vector{ double vx, vy; };

Vector set_v(const Point &p1, const Point &p2)
{
    Vector v;
    v.vx = p2.x - p1.x;
    v.vy = p2.y - p1.y;
    return v;
}

double dot(const Vector &v1, const Vector &v2)
{
    return (v1.vx * v2.vx) + (v1.vy * v2.vy);
}

double cross(const Vector &v1, const Vector &v2)
{
    return (v1.vx * v2.vy) - (v1.vy * v2.vx);
}

double cross0(const Point &P0, const Point &P1)
{
	return (P0.x * P1.y) - (P1.x * P0.y);
}

double onenorm(const Vector &v)
{
    return abs(v.vx) + abs(v.vy);
}

int ccw(const Point &P0, const Point &P1, const Point &P2)
{
    Vector V1 = set_v(P0, P1);
    Vector V2 = set_v(P0, P2);
    double c = cross(V1, V2);
    if(c > 0){ return 1; }else if(c < 0){ return -1; }
    if(dot(V1, V2) < 0){ return -2; }
    if(onenorm(V1) < onenorm(V2)){ return 2; }
    return 0;
}

int intersect(const Point &P0, const Point &P1, const Point &P2, const Point &P3)
{
    if(ccw(P0, P1, P2) * ccw(P0, P1, P3) <= 0 && ccw(P2, P3, P0) * ccw(P2, P3, P1) <= 0){
        return 1;
    }else{
        return 0;
    }
}

int main()
{
    int q;
    double x0, y0, x1, y1, x2, y2, x3, y3;
    Vector V01, V23;
    Point P0, P1, P2, P3;
    double Area, a, b;
    double isx, isy;
    scanf("%d", &q);

    for(int i = 0; i < q; i++){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x0, &y0, &x1, &y1, &x2, &y2, &x3, &y3);
        P0 = set_p(x0, y0), P1 = set_p(x1, y1), P2 = set_p(x2, y2), P3 = set_p(x3, y3);
        V01 = set_v(P0, P1), V23 = set_v(P2, P3);
        Area = cross(V01, V23);
        a = cross0(P2, P3) / Area, b = cross0(P0, P1) / Area;
        isx = a * (x1 - x0) - b * (x3 - x2);
        isy = a * (y1 - y0) - b * (y3 - y2);
        printf("%.12f %.12f\n", isx, isy);
    }
    return 0;
}

Measured memory_bytes: 1252
#include <stdio.h>

#define N 100003
#define INF 1 << 29

int enqueue(long *queue, long data, int *head, int *tail){
	if(*head % N != (*tail+1) % N) {
		queue[(*tail)++ % N] = data;
		return *tail - *head;
	}else{
		return INF;
	}
}

long dequeue(long *queue, int *head, int * tail){
	if(*head != *tail) {
		return queue[(*head)++ % N];
	}else{
		return INF;
	}
}

void initQueue(long *queue, int *head, int *tail){
	for(long i=1; i <= 9; i++)
		enqueue(queue, i, head, tail);
}

int main(void){
	long queue[N], x;
	int k, head = 0, tail = 0;

	scanf("%d", &k);

	initQueue(queue, &head, &tail);
	for(int i=0; i < k; i++) {
		if(k <= tail-head) {
			for(int j=i; j < k-1; j++)
				dequeue(queue, &head, &tail);
			printf("%ld", dequeue(queue, &head, &tail));
			return 0;
		}
		if((x = dequeue(queue, &head, &tail)) == INF) {
			return 1;
		}else{
			for(int j=-1; j <= 1; j++) {
				int d = x%10 + j;
				if(d < 0 || d > 9) continue;
				if(enqueue(queue, 10*x+d, &head, &tail) == INF)
					return 1;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 896
n=gets.to_i
a=gets.split.map(&:to_i).sort
c=(a.inject(:+).to_f/n).round
s=a[0]
m=a[-1]
x=1000000
y=1000000
c.upto(m){|i|w=a.map{|i|(i-c)**2}.inject(:+)
  if x>w
    x=w
  else
    break
  end
  }
c.downto(s){|i|w=a.map{|i|(i-c)**2}.inject(:+)
  if y>w
    y=w
  else
    break
  end
  }
puts [x,y].min

Measured memory_bytes: 1788
from itertools import combinations
import numpy as np

N, M, X = map(int, input().split())

C = []
A = []
for _ in range(N):
    l = list(map(int, input().split()))
    C.append(l[0])
    A.append(l[1:])
A = np.array(A)

ans = sum(C)
flag = False

for i in range(1, N+1):
    for c in combinations(range(N), i):
        k = np.zeros(M)
        cost = 0
        for n in c:
            k += A[n]
            cost += C[n]
        if np.all(k >= X):
            flag = True
            ans = min(ans, cost)

if flag:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 27236
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

/* exchange */
#define chmin(a, b) (a) = min((ll)(a), (ll)(b))
#define chmax(a, b) (a) = max((ll)(a), (ll)(b))

/* output */
#define I(x) cin >> x;
#define D(x) cerr << (x) << " ";
#define BR cerr << "\n";
#define P(x) cout << (x) << endl;
#define FIX cout << fixed << setprecision(10);

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll ret = 0;

struct City {
  ll id;
  string name;
  ll score;
};

bool operator< (City s, City t) {
  if (s.name != t.name) {
    return s.name < t.name;
  } else {
    return s.score > t.score;
  }
}

vector<City> v;

int main(void){
  
  I(N);
  string s;
  ll p;
  FOR(i, 1, N+1) {
    I(s);
    I(p);
    City c = {i, s, p};
    v.pb(c);
  }

  sort(ALL(v));
  REP(i, N) {
    P(v[i].id);
  }

}


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

int a[101];

int main()
{
	int n,s=0;
	cin>>n;
	
	for(int i=1; i<=n; i++)
	{
		int x;
		cin>>x;
		a[x]=1;
	}
	
	for(int i=1; i<=100; i++)
	{
		if(a[i]==1){
			s++;
		}
	}
	
	cout<<s<<endl;
	return 0;
 } 

Measured memory_bytes: 256
N, A , B = map(int,input().split())
S = input()

count_b = 0
count_total = 0
ans = ["No"] * N

for i in range(N):
    if count_total >= A+B:
        break

    if S[i] == "c":
        continue
    if S[i] == "a":
        count_total += 1
        ans[i] = "Yes"
    if S[i] == "b":
        count_b += 1
        if count_b <= B:
            count_total += 1
            ans[i] = "Yes"
    

for i in range(N):
    print(ans[i])

Measured memory_bytes: 4784
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = 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")
}

fn main() {
    let a: Vec<char> = read::<String>().chars().collect();
    let b: Vec<char> = read::<String>().chars().collect();
    let c: Vec<char> = read::<String>().chars().collect();
    println!("{}", if a[a.len() - 1] == b[0] && b[b.len() - 1] == c[0]
             { "YES" } else { "NO" });
}

Measured memory_bytes: 4352
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define INIT    \
    cin.tie(0); \
    ios::sync_with_stdio(false);

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

ll const INF = 1LL << 60;
ll const MOD = 1000000007;

int main() {
    INIT;

    ll N, X;
    cin >> N >> X;

    vector<ll> m(N);
    ll sum = 0;
    rep(i, N) {
        cin >> m[i];
        sum += m[i];
    }
    sort(ALL(m));

    ll ans = N;
    X -= sum;
    ans += (X / m[0]);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3628
K = int(input())
ans_list = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
nex = ans_list.copy()


def resp(n):
    if n == "0":
        return ["0", "1"]
    elif n == "9":
        return ["8", "9"]
    else:
        n_tmp = int(n)
        return [n, str(n_tmp + 1), str(n_tmp - 1)]


for j in range(1000):
    tmp = nex.copy()
    nex = []
    for i in tmp:
        nex += [i + x for x in resp(i[-1])]
    ans_list += nex
    if len(ans_list) > 10 ** 5:
        break

ans_list = list(map(int, ans_list))
ans_list.sort()
print(ans_list[K - 1])


Measured memory_bytes: 26696
#include <bits/stdc++.h>
#define maxn 2005
#define maxl 1000000000

using namespace std;

#define st first
#define nd second
#define ALL(x) (x).begin(), (x).end()

template <class T>
void mini(T& l, T r) {
  l = min(l, r);
}
template <class T>
void maxi(T& l, T r) {
  l = max(l, r);
}

using LL = long long;
using LD = long double;
using ULL = unsigned long long;
const int dx[] = {0, -1, 1, 0, -1, -1, 1, 1},
          dy[] = {-1, 0, 0, 1, -1, 1, -1, 1};
const int INF = 1e9;
const LL MOD = 1e9 + 7;

int t, T;

void Solve() {
  // TODO
  int n, k;
  cin >> n >> k;
  int r, s, p;
  cin >> r >> s >> p;
  string t;
  cin >> t;
  long long res = 0;
  map<char, int> m{{'r', p}, {'s', r}, {'p', s}};
  for (int i = 0; i < k; i++) {
    for (int j = i; j < n; j += k) {
      if (j >= k && t[j] == t[j - k]) {
        t[j] = ' ';
      } else {
        res += m[t[j]];
      }
    }
  }
  cout << res << '\n';
  return;
}

void Prepare() {
  // TODO
  return;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  // Prepare();
  // cin >> T;
  // for (t = 1; t <= T; t++) {
  //   printf("Case #%d: ", t);
  Solve();
  //}
  return 0;
}


Measured memory_bytes: 512
n = gets.to_i
a = gets.split.map(&:to_i)

b = Hash.new(0)
a.each do |ai|
  b[ai] += 1
end

ans = 0
b.each do |k, v|
  if k > v
    ans += v
  else v < k
    ans += v - k
  end
end

puts ans


Measured memory_bytes: 14468
#include<cstdio>
#include<cstring> 
using namespace std;
char a[200005];
int main(){
	int n,ans=0;
	scanf("%s",a);
	n=strlen(a);
	for(int i=0;i<n;i++){
		ans+=a[i]-48;
	}
	if(ans%9==0){
		printf("Yes");
	}
	else{
		printf("No");
	} 
	return 0;
}


Measured memory_bytes: 1868
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i=1;;i++) {
            int x = sc.nextInt();
            if(x==0) {
                break;
            }
            System.out.println("Case " + i + ": " + x);
        }
        sc.close();
    }
}


Measured memory_bytes: 41404
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll * pos,ll val){*pos=max(*pos,val);}//Max(&dp[i][j],dp[i-1][j]);
void Min(ll * pos,ll val){*pos=min(*pos,val);}
void Add(ll * pos,ll val){*pos=mod(*pos+val);}
const long double EPS=1E-8;
////////////////////////////////////////


int main() {
    string s;cin>>s;
    rep(i,0,2){
        if(s[i]=='1')s[i]='9';
        else  if(s[i]=='9')s[i]='1';
    }
    cout<<s<<endl;
    return 0;
}


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

int n;

int main(){
  cin >> n;
  int res = 0;
  if(n >= 195) res = 5;
  else if(n >= 189) res = 4;
  else if(n >= 165) res = 3;
  else if(n >= 135) res = 2;
  else if(n >= 105) res = 1;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    int flag1 = 0, flag2 = 0;
    cin>>s;

    for(int i=0;i<s.length();i++)
    {
        if(s[i] == 'A')
        flag1++;

        else if(s[i] == 'B')
        flag2++;
    }

    if(flag1 > 0 && flag2 > 0)
    cout<<"Yes\n";

    else 
    cout<<"No\n";
	return 0; 
} 


Measured memory_bytes: 256
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
ab=[0,0]
ans=0
cnt=0
for i in range(len(s)):
    if s[i]=="A":
        ab[0]+=pow(3,cnt,mod)
    elif s[i]=="B":
        ab[1]+=ab[0]
    elif s[i]=="C":
        ans+=ab[1]
    else:
        ans=ab[1]+3*ans
        ab[1]=ab[0]+3*ab[1]
        ab[0]=pow(3,cnt,mod)+3*ab[0]
        cnt+=1
    ab[0]%=mod
    ab[1]%=mod
    ans%=mod
print(ans%mod)


Measured memory_bytes: 40688
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));

console.log(main());
function main(){
  var n = o.a();
  var h = o.a();
  var w = o.a();
  return (n-h+1) * (n-w+1);
}

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

int countWays(int n, int x) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int k = x - (i + j);
            if (k > j && k <= n) {
                res++;
            }
        }
    }
    return res;
}

int main() {
    while (true) {
        int n, x;
        cin >> n >> x;
        if (n == 0 && x == 0) {
            return 0;
        }

        cout << countWays(n, x) << endl;
    }
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

int main() {
  int k,s,ans=0; cin>>k>>s;
  REP(x,k+1) { REP(y,k+1) { int z = s-(x+y); if (0<=z && z<=k) ans++; } }
  cout << ans << endl;
}

Measured memory_bytes: 256
# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
L = []
for i in range(N):
    L.append(int(input()))
L.sort()
ans = 10**9
for i in range(N - K+1):
    ans = min(ans, L[i+K-1]-L[i])
print(ans)


Measured memory_bytes: 13224
import bisect

N = int(input())
S = input()

changes = []

wests = [i for i in range(N) if S[i] == 'W']
# print(wests)
easts = [i for i in range(N) if S[i] == 'E']
# print(easts)

for leader in range(N):
    change = 0
    change += bisect.bisect_left(wests, leader)
    change += len(easts) - bisect.bisect_right(easts, leader)
    changes.append(change)

print(min(changes))

Measured memory_bytes: 27656
// #include<bits/stdc++.h>
// using namespace std;
 
// const int N = 100000, MAXI = 3, D = 1000;
 
// int main() {
//     freopen("output.txt", "r", stdin);
//     freopen("input.txt", "w", stdout);
//     srand(time(nullptr));
//     int tc = 10000, flag = 1;
//     cout << tc << "\n";
//     int n = 1;
//     while (tc--)
//     {
//     	n = rand()%N + 1;

//     	cout << n << "\n~\n";

//     }
 
//     return 0;
// }
 
 
 
 
 
 
 
 
//---------------------------------------------//
 
 
 
/*
#define int long long 
#define mod (int)(1e9+9)
#define endl '\n'
#define MAXI (int)(3e17+10)
#define N 200005
 */ 
 
 
 
 

//  /* while(!cin.eof()) */
 
#include<bits/stdc++.h>
using namespace std; 
#define int long long
#define mod (int)(1e9+7)
#define MAXI (int)(3e17+10)
#define N 105
#define M 100005

int dp[M];

int n, k, a[N];



// Driver code to test above functions
int32_t main()
{
   
     
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    
    cin >> n >> k;
    for(int i=0;i<n;i++)
    	cin >> a[i];

   	dp[0] = 0;

    for(int i=1;i<=k;i++)
    {
    	dp[i] = 0;
    	for(int j=0;j<n;j++)
    	{
    		if(i-a[j]>=0){
    			if(!dp[i-a[j]]){
    				dp[i] = 1;
    				break;
    			}
    		}
    	}
    }

    if(dp[k])
    	cout << "First";
    else
    	cout << "Second";

    return 0;
 
} 

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

int main(){
    string S;
    cin>>S;
    sort(S.begin(),S.end());
    bool flag = true;
    for(int i=0;i<S.size()-1;i++){
        if(S.at(i)==S.at(i+1)){
            flag = false;
        }
    }
    
    if(flag){
        cout<<"yes"<<endl;
    }else{
        cout<<"no"<<endl;
    }
}


Measured memory_bytes: 256
#include <string>
#include <bits/stdc++.h>
#include <stdlib.h>
#include <iostream>
#include <deque>
#define  N 100005
#define  ul unsigned long long
#define  ll long long int
#define  loop0(i,a,b) for(int i = a;i<b;++i)
#define  loop1(i,a,b) for(int i = a;i<=b;++i)
#define  ini0(i,b) for(int i = b;i>=0;--i)
#define  ini1(i,b) for(int i = b-1;i>=0;--i)
#define  pl pair<ll,ll>
#define  pi pair<int,int>
#define  ff first
#define  ss second
#define  bg begin()
#define  ed end()

#define  READ freopen("input.txt","r",stdin);
#define  WRITE freopen("output.txt","w",stdout);

#define  test1(x) cout<<#x<<" : "<<x<<endl;   
#define  test2(x,y) cout<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<endl;
#define  test3(x,y,z) cout<<#x<<" : "<<x<<"   "<<#y<<" : "<<y<<"  "<<#z<<" : "<<z<<endl;


int bgval(int n, int a)
{
	int rt = n / a;
	if (n%a != 0) rt++;
	return rt;
}


using namespace std;

map<string, int> mp;

ll phi(ll n)
{
	ll result = n; // Initialize result as n 

	// Consider all prime factors of n and subtract their 
	// multiples from result 
	for (ll p = 2; p * p <= n; ++p) {

		// Check if p is a prime factor. 
		if (n % p == 0) {

			// If yes, then update n and result 
			while (n % p == 0)
				n /= p;
			result -= result / p;
		}
	}

	// If n has a prime factor greater than sqrt(n) 
	// (There can be at-most one such prime factor) 
	if (n > 1)
		result -= result / n;
	return result;
}

bool isprime(ll n) {
	for (ll i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);

	int t=1;
	//cin >> t;
	while (t--)
	{
		int n,k=0;
		cin >> n>>k;
		vector<ll> vc(n,0), dp(n,INT_MAX);
		for (auto &it : vc) cin >> it;
		dp[0] = 0;
		for (int i = 1;i<n;i++)
		{
			dp[i] = dp[i - 1] + abs(vc[i] - vc[i-1]);
			for (int j = 2;j <= k;j++)
			{
				if (i - j >= 0)
				{
					dp[i] = min(dp[i], dp[i - j] + abs(vc[i] - vc[i - j]));
				}
			}
		}
		cout << dp[n - 1] << endl;
	
	}


	return 0;
}


Measured memory_bytes: 1792
H, N = map(int, input().split())
INF = float('inf')
dp = [INF]*(H+1) #モンスターの体力をi減らすために消耗する魔力の最小値
ans = 0
for n in range(N):
    a,b = map(int, input().split())
    for h in range(1, H + 1):
        if a >= h:
            dp[h] = min(dp[h], b)
        else:
            dp[h] = min(dp[h], dp[h-a] + b)

print(dp[H])

Measured memory_bytes: 75032
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}
public class Main {
	static FastScanner stdIn=new FastScanner();
	public static void main(String[] args) {
		int N=stdIn.nextInt();
		long minA=1000000005,minB=1000000005,maxA=0,maxB=0;
		long ans=0;
		for(int i=0;i<N;i++){
			int a=stdIn.nextInt();
			int b=stdIn.nextInt();
			if(minA>a){
				minA=a;minB=b;
			}
			if(maxA<a){
				maxA=a;maxB=b;
			}
		}
		ans+=maxA;
		ans+=maxB;
		System.out.println(ans);
	}
}


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

int main(){
  int n,k;
  cin >> n >> k;
  int ans=0;
  int x;
  for(int i=0;i<n;i++){
	cin >> x;
    ans+=(x>=k);
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  
  int max_dist=0,min_dist,K,N;
  cin >> K >> N;
  
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  
  for(int i=0;i<N-1;i++){
    if(A.at(i+1)-A.at(i) >= max_dist){
      max_dist = A.at(i+1)-A.at(i);
    }
  }
  
  //0とN-1の間の距離
  int dist = K - A.at(N-1) + A.at(0);
  if(dist >= max_dist){
    max_dist = dist;
  }

  min_dist = K - max_dist;
  cout << min_dist << endl;
  
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iomanip>
#include<limits>
#include<queue>
#include<set>
#include<cstdio>
#include<climits>
#include<cstring>

using namespace std;

int main(){
	
    int A,B;
    cin >> A >> B;
    
    if(A <= 8 && B <=8){
    	cout << "Yay!" << endl;
    }else{
    	cout << ":(" << endl;
    }
	
    return 0;
}


Measured memory_bytes: 256
////////////////////////////////////////////////////////////////////
// This source code is for Visual Studio
////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <stack>
#include <functional>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <math.h>
#include <assert.h>

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF		UINT64_MAX
#define Rep(i,n) for(int i = 0; i < (n); ++i )

using namespace std;

typedef vector< vector<int> > MAT;
typedef pair<int, int> PINT;
typedef long long ll;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t s32;
typedef int64_t s64;

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int main()
{
	ll c[3][3];
	string ans = "No";

	Rep(i, 3) {
		Rep(j, 3) {
			cin >> c[i][j];
		}
 	}

	if (c[1][1] - c[1][0] == c[0][1] - c[0][0]) {
		if (c[1][1] - c[1][0] == c[2][1] - c[2][0]) {
			if (c[1][2] - c[1][0] == c[0][2] - c[0][0]) {
				if (c[1][2] - c[1][0] == c[2][2] - c[2][0]) {
					ans = "Yes";
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


struct MaxDeque {
  using T = lint;
  static T op(const T& lhs, const T& rhs) { return max(lhs, rhs); }
  static constexpr T e() { return -1e18; }

  T get() {
    return op(get_l(), get_r());
  }
  void push_front(const T& x) {
    l.emplace_back(x, op(get_l(), x));
  }
  void push_back(const T& x) {
    r.emplace_back(x, op(get_r(), x));
  }
  void pop_front() {
    if (l.empty()) {
      assert(!r.empty());
      int n = r.size(), m = 1 + (n - 1) / 2;
      l.resize(m - 1);
      copy(begin(r) + 1, begin(r) + m, rbegin(l));
      copy(begin(r) + m, end(r), begin(r));
      r.resize(n - m);
      update();
    } else {
      l.pop_back();
    }
  }
  void pop_back() {
    if (r.empty()) {
      assert(!l.empty());
      int n = l.size(), m = 1 + (n - 1) / 2;
      r.resize(m - 1);
      copy(begin(l) + 1, begin(l) + m, rbegin(r));
      copy(begin(l) + m, end(l), begin(l));
      l.resize(n - m);
      update();
    } else {
      r.pop_back();
    }
  }
private:
  V< pair<T, T> > l, r;
  T get_l() {
    return l.empty() ? e() : l.back().second;
  }
  T get_r() {
    return r.empty() ? e() : r.back().second;
  }
  void update() {
    int nl = l.size(), nr = r.size();
    for (int i = 0; i < nl; ++i) {
      l[i].second = op(i > 0 ? l[i - 1].second : e(), l[i].first);
    }
    for (int i = 0; i < nr; ++i) {
      r[i].second = op(i > 0 ? r[i - 1].second : e(), r[i].first);
    }
  }
};

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, m, k; cin >> n >> m >> k;
  V<> a(n); for (int i = 0; i < n; ++i) cin >> a[i];
  VV<lint> dp; assign(dp, k + 1, n, 0);
  for (int i = 0; i < n; ++i) {
    dp[1][i] = a[i];
  }
  for (int j = 1; j < k; ++j) {
    MaxDeque deq;
    for (int i = 0; i < n; ++i) {
      dp[j + 1][i] = deq.get() + (lint) (j + 1) * a[i];
      deq.push_back(dp[j][i]);
      if (i >= m) deq.pop_front();
    }
  }
  cout << *max_element(begin(dp[k]), end(dp[k])) << '\n';
}

Measured memory_bytes: 240892
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input().strip()
def mi():return map(int,input().split())
def li():return list(mi())
mod=1000000007

n=ii()
s=si()

    
l=0
r=n-1
ans=0
while(l<r):
    f=0
    for i in range(l,n):
        if s[i]=='W':
            l=i
            f=1
            break
    f1=0
    for i in range(r,-1,-1):
        if s[i]=='R':
            r=i
            f1=1
            break
    if(l>=r or f==0 or f1==0):
        break
    ans+=1
    l+=1
    r-=1

print(ans)










Measured memory_bytes: 68648
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Array;
using static AtCoder.Tool;

namespace AtCoder
{
    class AC
    {
        const int MOD = 1000000007;
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 2;
        const double EPS = 1e-8;
        static readonly int[] dx = { 0, 1, 0, -1 };
        static readonly int[] dy = { 1, 0, -1, 0 };

        

        static void Main(string[] args)
        {
            //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            //Console.SetOut(sw);
            var cin = new Scanner();


            int N = int.Parse(Console.ReadLine());
            List<Tuple<int, int>> LR = new List<Tuple<int, int>>();
            long difmax = 0;
            for(var i = 0; i < N; i++)
            {
                var p = cin.SplitRead();
                LR.Add(new Tuple<int, int>(p[0], p[1]));
                difmax = Max(difmax, p[1] - p[0] + 1);
            }
            LR.Sort((x, y) => (x.Item1 - y.Item1));

            int Lmax = LR[N - 1].Item1;
            var Rmin1 = new int[N];
            Rmin1[0] = LR[0].Item2;
            var Rmin2 = new int[N];
            Rmin2[N - 1] = LR[N - 1].Item2;
            for(var i = 1; i < N; i++)
            {
                Rmin1[i] = Min(Rmin1[i - 1], LR[i].Item2);
                Rmin2[N - 1 - i] = Min(Rmin2[N - i], LR[N - i - 1].Item2);
            }
            /*foreach (var t in LR) Console.WriteLine(t);
            for (var i = 0; i < N; i++) Console.WriteLine($"{Rmin1[i]} {Rmin2[i]}");*/
            long ans1 = difmax + Max(0, Rmin1[N - 1] - Lmax + 1);
            long ans2 = 0;
            for(var i = 0; i < N - 1; i++)
            {
                ans2 = Max(ans2, Max(0, Rmin1[i] - LR[i].Item1 + 1) + Max(0, Rmin2[i + 1] - Lmax + 1));
            }

            Console.WriteLine(Max(ans1, ans2));


           
            //Console.Out.Flush();

        }
    }


    public class Scanner
    {
        public int[] SplitRead()
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return array;
        }
        public long[] SplitReadL()
        {
            long[] array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return array;
        }
    }
    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            for (var i = 0; i < array.Length; i++)
            {
                array[i] = initialvalue;
            }
        }
    }

}


Measured memory_bytes: 24116
#include <bits/stdc++.h>
using namespace std;
int main() {
	vector<int> x (3);
	cin >> x.at(0) >> x.at(1) >> x.at(2);
	sort(x.begin(),x.end());
	if(x.at(0) == x.at(1)){
		cout << x.at(2) << endl;
	}
	else{
		cout << x.at(0) << endl;
	}
	return 0;
}

Measured memory_bytes: 256
(* 配列版素集合データ構造 *)
module RawUnionFind : sig
  type t
  type class_

  (* n要素の素集合データ構造を作る *)
  val make : int -> t
  (* 要素がどの集合に属するか調べる *)
  (* 要素は0からn-1の整数である必要がある *)
  val find : t -> int -> class_
  (* 与えられた要素が属する集合同士を合併する *)
  val unite : t -> int -> int -> unit

  val compare_class : class_ -> class_ -> int
end = struct
  type t = { rank : int array; parent : int array }
  type class_ = int

  let make n =
    { rank = Array.make n 0;
      parent = Array.init n (fun c -> c) }

  let rec find uf x =
    if x = uf.parent.(x) then x
    else begin
      let y = find uf uf.parent.(x) in
      uf.parent.(x) <- y; y
    end

  let unite uf i j =
    let x = find uf i in
    let y = find uf j in
    if x <> y then begin
      if uf.rank.(x) < uf.rank.(y) then uf.parent.(x) <- y
      else begin
        uf.parent.(y) <- x;
        if uf.rank.(x) = uf.rank.(y) then
          uf.rank.(x) <- 1 + uf.rank.(x)
      end
    end

  let compare_class = compare
end

let rec select acc trace = function
  | [] -> acc
  | x :: xs -> select ((trace, x, xs) :: acc) (x :: trace) xs
let select xs = select [] [] xs

let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let abs = Array.init m @@ fun _ ->
    Scanf.scanf "%d %d\n" @@ fun a b -> a, b in
  Array.to_list abs
  |> select
  |> List.filter (fun (prev, (a, b), post) ->
      let uf = RawUnionFind.make n in
      List.iter (fun (a, b) ->
        RawUnionFind.unite uf (a - 1) (b - 1)) (prev @ post);
      RawUnionFind.find uf (a - 1) <> RawUnionFind.find uf (b - 1))
  |> List.length
  |> Printf.printf "%d\n"



Measured memory_bytes: 512
H, W = gets.split.map(&:to_i)
c = []
H.times{c<< gets.chomp.split}
c.each_with_index do |row, i|
  row.each_with_index do |col, j|
    puts "#{(65 + j).chr}#{i+1}" if col == 'snuke'
  end
end

Measured memory_bytes: 14276
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
	int a, b;
	char op;
	int ans;

	while(1){
		cin >> a >> op >> b;
		if (op == '?')
			break;
		switch(op){
			case '+': ans = a + b; break;
			case '-': ans = a - b; break;
			case '*': ans = a * b; break;
			case '/': ans = a / b; break;
		}
		cout << ans << endl;
	}

	return 0;
}




Measured memory_bytes: 3084
import heapq
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
for i in range(n):
  a[i] *= -1

heapq.heapify(a)
for i in range(m):
    heapq.heapreplace(a, int(a[0] / 2))

print(sum(a)*-1)

Measured memory_bytes: 14168
s = input()
z = int(input())
list = [chr(i) for i in range(97,97+26)]
d = []
for j in list:
  indexes = [i for i,x in enumerate(s) if x==j]
  if len(indexes)==0:
    continue
  for k in indexes:
    for l in range(len(s)-k):
      d.append(s[k:l+k+1])
      if len(s[k:l+k+1])==z:
        break
print(sorted(set(d))[z-1])

Measured memory_bytes: 5052
#include <iostream>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

ll a, b, c, k;

int main(int argc, char const *argv[]) {
    cin >> a >> b >> c >> k;
    int ans = 0;
    int takeNum = k;
    if (a >= takeNum) {
        ans += k;
        cout << ans << endl;
        return 0;
    } else {
        ans = a;
        takeNum -= a;
    }

    if (b >= takeNum) {
        cout << ans << endl;
        return 0;
    } else {
        takeNum -= b;
    }

    ans -= takeNum;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3180
#include<bits/stdc++.h>
#define For(i,m,n) for(int i=m;i<n;i++)
#define FOR(i,n) for(int i=0;i<n;i++)
#define ll long long
#define ull unsigned long long
#define lli long long int
#define pb push_back
#define all(x) x.begin(),x.end()
ll mob=1000000007;
using namespace std;
int main()
{ 
int n;
cin>>n;
ll a[n];
FOR(i,n)cin>>a[i];
ll sumh[n];
ll sump[n];
map<ll,ll> g;

FOR(i,n)
{
    sumh[i]=a[i]+i;
    g[sumh[i]]++;
    
    
}
FOR(i,n)
{
    sump[i]=i-a[i];
}
ll r=0;
for(int i=n-1;i>0;i--)
{ if(sump>0)
{
    if(g.find(sump[i])!=g.end())
    {
        r+=g[sump[i]];
    }
}
    
}
cout<<r;

return 0;
}











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


int main(){
  char b; cin >> b;
  if(b == 'A'){
    cout << 'T' << endl;
  }else if(b == 'T'){
    cout << 'A' << endl;
  }else if(b == 'G'){
    cout << 'C' << endl;
  }else{
    cout << 'G' << endl;
  }
}


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

int zeinukiMuximum(int zeikomi, int zeiritsu) {
double min1 = zeikomi * 100.0 / (100.0 + zeiritsu);
double max1 = (zeikomi + 1.0) * 100.0 / (100.0 + zeiritsu);
int min2 = (int)floor(min1);
int max2 = (int)ceil(max1);
int i;
for (i = max2; i >= min2; i--) {
if (i*(100+zeiritsu)/100 == zeikomi)
return i;
}
return 0;
}

int main(void){
int x,y,s,ans;
int p1max,p2max;
int q1max,q2max;
int i;
while(1){
scanf("%d %d %d",&x,&y,&s);
ans=0;
if(x==0&&y==0&&s==0) break;
for(i=1;i<s;i++){
p1max=zeinukiMuximum(i, x);
p2max=zeinukiMuximum(s-i, x);
if (p1max == 0 || p2max == 0) continue;
q1max=p1max*(100+y)/100;
q2max=p2max*(100+y)/100;
if(ans<(q1max+q2max)) ans=q1max+q2max;
}
printf("%d\n",ans);
}
return 0;
}


Measured memory_bytes: 2684
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; ++i)
#define all(x) begin(x), end(x)
#define gets(s) fgets(s,size(s),stdin)
using namespace std;
typedef long long ll;
typedef string str;
template<typename T>
using vec=vector<T>;
template<typename T>
using uset=unordered_set<T>;
template<typename T,typename S>
using umap=unordered_map<T,S>;

const int mod=1000000007;
const double pi=3.1415926535;

int a[5];

int main() {
	rep(i,5) {
		scanf("%d",a+i);
		if(!a[i]) printf("%d",i+1);
	}
	return 0;
}


Measured memory_bytes: 3704
#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 FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> a(m);
  rep(i, m) cin >> a[i];

  int l = 0, r = 0;
  rep(i, m) {
    if (a[i] < x) l++;
    else r++;
  }
  cout << min(l, r) << endl;


  
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var N, A, max, min int
	fmt.Scan(&N)

	for i := 0; i < N; i++ {
		fmt.Scan(&A)
		if i == 0 {
			max = A
			min = A
		} else {
			if max < A {
				max = A
			}
			if min > A {
				min = A
			}
		}
	}
	fmt.Print(max - min)
}

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

vector<long long> ans;

void func(string s){
    long long x = stoll(s);
    if (x <= 3234566667){
        ans.push_back(x);
        if(x%10 != 0) func(s+to_string(x%10-1));
        func(s+to_string(x%10));
        if(x%10 != 9) func(s+to_string(x%10+1));
    }
}

int main(){
    int K;
    cin >> K;
    for(int i=1;i<=9;i++) func(to_string(i));
    sort(ans.begin(), ans.end());
    cout << ans[K-1] << endl;
}

Measured memory_bytes: 1400
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC139A
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string T = Console.ReadLine();
            int ans = 0;
            for(int i = 0; i < 3; i++)
            {
                if (S[i] == T[i])
                {
                    ans += 1;
                }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 25880
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			int q = scanner.nextInt();
			scanner.nextLine();
			long[] s = new long[a];
			for (int i = 0; i < a; i++) {
				s[i] = scanner.nextLong();
				scanner.nextLine();
			}
			long[] t = new long[b];
			for (int i = 0; i < b; i++) {
				t[i] = scanner.nextLong();
				scanner.nextLine();
			}
			long[] result = new long[q];
			for (int i = 0; i < q; i++) {
				long x = scanner.nextLong();
				result[i] = nearest(x, s, t);
			}
			Arrays.stream(result).forEach(System.out::println);
		}
	}

	private static long nearest(long x, long[] s, long[] t) {
		long s1, s2, t1, t2;
		int sIndex = Arrays.binarySearch(s, x);
		int tIndex = Arrays.binarySearch(t, x);
		if (sIndex >= 0) {
			s1 = s2 = s[sIndex];
		} else {
			if (sIndex == -1) {
				s1 = s2 = s[0];
			} else if (sIndex == -s.length - 1) {
				s1 = s2 = s[s.length - 1];
			} else {
				s1 = s[-sIndex - 2];
				s2 = s[-sIndex - 1];
			}
		}
		if (tIndex >= 0) {
			t1 = t2 = t[tIndex];
		} else {
			if (tIndex == -1) {
				t1 = t2 = t[0];
			} else if (tIndex == -t.length - 1) {
				t1 = t2 = t[t.length - 1];
			} else {
				t1 = t[-tIndex - 2];
				t2 = t[-tIndex - 1];
			}
		}
		return min(distance(x, s1, t1), distance(x, s1, t2), distance(x, s2, t1), distance(x, s2, t2));
	}

	private static long distance(long x, long s1, long t1) {
		return Math.abs(s1 - t1) + min(Math.abs(s1 - x), Math.abs(t1 - x));
	}

	private static long min(long... x) {
		long min = Long.MAX_VALUE;
		for (long number : x) {
			min = Math.min(min, number);
		}
		return min;
	}
}

Measured memory_bytes: 279388