akhauriyash/Code-Regression huggingface dataset:
(defparameter *dx-dy*
  '((-1 . -1)
    (-1 . 0)
    (-1 . 1)
    (0 . -1)
    (0 . 1)
    (1 . -1)
    (1 . 0)
    (1 . 1)))



(defun solve (h w board)
  (labels ((count-mine (y x board &optional (cnt 0))
             (dotimes (d 8 cnt)
               (let ((nx (+ x (first (nth d *dx-dy*))))
                     (ny (+ y (rest (nth d *dx-dy*)))))
                 (when (and (<= 0 nx (1- w))
                            (<= 0 ny (1- h))
                            (char-equal (aref (aref board ny) nx) #\#))
                   (incf cnt))))))
    (dotimes (i h)
      (dotimes (j w)
        (unless (char-equal (aref (aref board i) j) #\#)
          (setf (aref (aref board i) j) (digit-char (count-mine i j board))))))
    board))

(defun main ()
  (let* ((h (read))
         (w (read))
         (board (make-array h :initial-element "")))
    (dotimes (i h)
      (setf (aref board i) (read-line)))
    (let ((ans (solve h w board)))
      (dotimes (i h)
        (fresh-line)
        (princ (aref ans i))))
    (fresh-line)))

(main)


Measured memory_bytes: 24552
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int flag = -1, p, la, lb, lc, pa, pb, pc, i;
    string sa, sb, sc;
    cin >> sa >> sb >> sc;
    pa = 0;
    pb = 0;
    pc = 0;
    la = sa.size();
    lb = sb.size();
    lc = sc.size();
    p = pa;
    char c = sa[0];
    while (pa != la || pb != lb || pc != lc)
    {
        if (c == 'a')
        {
            pa++;
            flag = 0;
            if (pa == la)
            {
                break;
            }
            c = sa[pa];
        }
        else if (c == 'b')
        {
            c = sb[pb];
            flag = 1;
            if(pb == lb)
            break;
            pb++;
        }
        else if (c == 'c')
        {
            flag = 2;
            c = sc[pc];
            if(pc == lc)
            break;
            pc++;
        }
    }
    if(flag == 0)
    cout << "A";
    else if(flag == 1)
    cout << "B";
    else
    cout << "C";
    // cout << "\n";
    return 0;
}

Measured memory_bytes: 3608
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[][] directions8= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	static int[][] directions4= {{-1,0},{1,0},{0,-1},{0,1}};
	static long  ans;
	static int[] parent;//union-find用
	static int[] rank;//union-find用
	static int mod = 1000000007;

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

		Scanner sc = new Scanner(System.in);
		long N = sc.nextInt();
		long all = 1;
		long no09 = 1;
		long no0 = 1;
		for(long i = 0;i<N ; i++) {
			all*=10;
			no0 *= 9;
			no09*=8;
			all%=1000000007;
			no0 %= 1000000007;
			no09%=1000000007;
		}
		no0 = (no0*2)%1000000007;
		ans = all - no0+no09;
		ans %=mod;
		ans=(ans+mod)%mod;

		System.out.println(ans);
	}

	//素数判定
	public static boolean isPrime(long num) {
		if (num < 2) return false;
		else if (num == 2) return true;
		else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

		double sqrtNum = Math.sqrt(num);
		for (int i = 3; i <= sqrtNum; i += 2)
		{
			if (num % i == 0)
			{
				// 素数ではない
				return false;
			}
		}

		// 素数である
		return true;
	}

	//BFS用に二つの配列を足し算する
	static int[] addArrayElms(int[] a, int[] b) {
		int[] c = new int[a.length];
		for(int i = 0; i < a.length; i++) {
			c[i] = a[i] + b[i];
		}
		return c;
	}

	//	//二分探索
	//k <= num となる最小の配列要素kのインデックスを返す
	static private int binarySearch(long num, long[] orderedArray){
		int lowerBorder = -1;
		int upperBorder = orderedArray.length;
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedArray[mid]<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//二分探索
	//k <= num となる最小のList要素kのインデックスを返す
	static private int binarySearch(long num, ArrayList<Long> orderedList){
		int lowerBorder = -1;
		int upperBorder = orderedList.size();
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedList.get(mid)<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//aとbの最小公倍数を求める
	public static int gcd(int a, int b) {
		return b == 0 ? a: gcd(b, a % b);
	}
	public static long gcd(long a, long b) {
		return b == 0 ? a: gcd(b, a % b);
	}

	//Union-Find用の配列を要素数nで初期化
	static void ufInit(int n){
		parent = new int[n];
		rank = new int[n];
	}

	//Union-Findの要素の最上位の親（グループ名）を返す
	static int ufFind(int a) {
		if(parent[a]==a) {
			return a;
		}else {
			return ufFind(parent[a]);
		}
	}

	//Union-Find木を連結する
	static void ufUnite(int a, int b) {
		a = parent[a];
		b = parent[b];

		if(a==b) {
			return;
		}
		if(rank[a] > rank[b]){
			parent[b]=a;
		}else {
			parent[a]=b;
			if(rank[a]==rank[b]) {
				rank[b]++;
			}
		}
	}

	static boolean ufSame(int a, int b) {
		return ufFind(a)==ufFind(b);
	}
}


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

long long dp[2030][680];

int main() {
  long long s;
  cin >> s;

  for (int i = 0; i < 2030; i++) dp[i][0] = (i>1) ? 1 : 0;
  int hi = s / 3;
  for (int i = 1; i < hi; i++) {
    dp[(i+1)*3 - 1][i] = 1;
    for ( int j = (i+1)*3; j < s; j++)  {
      dp[j][i] = (dp[j-3][i-1] + dp[j-1][i]) % 1000000007;
    }
  }
  int ans = 0;
  for (int i = 0; i < hi; i++) {
    ans = (ans + dp[s-1][i]) % 1000000007;
  }
  cout << ans << endl;
}


Measured memory_bytes: 13976
'use strict'
const main = arg => {
	const input = arg.trim().split("\n");
	let H = Number(input[0].split(' '))
	let W = Number(input[1].split(' '))
	let N = Number(input[2].split(' '))
	let paintedRow = 0
	let paintedColumn = 0
	let paintedCell = 0
	while(1) {
		if(W >= H) {
			paintedCell += W - paintedColumn
			paintedRow++
		} else {
			paintedCell += H - paintedRow
			paintedColumn++
		}
		if(paintedCell >= N) break
	}
	console.log(paintedColumn + paintedRow)
}   
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 22080
#include <bits/stdc++.h>
using namespace std;
#define Ds 1
#define Dt 2
#define Db 3

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int S = int(3e3)+10;
const ll MOD = ll(1e9)+7;

string s, t;
int dp[S][S], mv[S][S];


int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> s >> t;
	int n = sz(s);
	int m = sz(t);
	rep(i, 1, n+1) 
		rep(j, 1, m+1) {
			mv[i][j] = Ds;
			if(dp[i][j] < dp[i-1][j]) {
				dp[i][j] = dp[i-1][j];
				mv[i][j] = Ds;
			}
			if(dp[i][j] < dp[i][j-1]) {
				dp[i][j] = dp[i][j-1];
				mv[i][j] = Dt;
			}
			if(s[i-1] == t[j-1] && dp[i][j] < dp[i-1][j-1]+1) {
				dp[i][j] = dp[i-1][j-1]+1;
				mv[i][j] = Db;
			}
		}
	int ci = n, cj = m;
	string res;
	while(ci > 0 && cj > 0) {
		if(mv[ci][cj] == Ds)
			ci--;
		else if(mv[ci][cj] == Dt)
			cj--;
		else {
			res.push_back(s[ci-1]);
			ci--; cj--;
		}
	}
	reverse(all(res));
	cout << res << endl;

	
	return 0;
}

Measured memory_bytes: 70912
#include<stdio.h>
#define N 100001
int Partition(int,int);
int A[N];
main(){
  int a,i,n;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  a=Partition(0,n-1);
  for(i=0;i<n;i++){
    if(i==a) printf("[%d]",A[i]);
    else printf("%d",A[i]);   
    if(i==n-1) printf("\n");
    else printf(" ");
}
  return 0;
}

int Partition(int p,int r){
  int x,R=0,L=0,i,j;
  x=A[r];
  i=p-1;
  for(j=p;j<=r-1;j++){
    if(A[j]<=x){ 
      i=i+1;
      R=A[i];
      A[i]=A[j];
      A[j]=R;
    }
  }
    L=A[i+1];
    A[i+1]=A[r];
    A[r]=L;
    return i+1;
}

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

int main() {
	int n,ma=0;
	cin>>n;
	string s[n];
	int a[n];
	map<string, int> m;
	vector<string> v;
	map<string , int>::iterator itr;
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
		itr=m.find(s[i]);
		if(itr==m.end())
		m.insert({s[i],1});
		else
		itr->second++;
	}
	for(itr=m.begin();itr!=m.end();itr++)
	{
		// cout<<itr->first<<" "<<itr->second<<"\n";
		ma=max(ma,itr->second);
	}
	for(itr=m.begin();itr!=m.end();itr++)
	{
		if(ma==itr->second)
		{
			v.push_back(itr->first);
		}
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++)
	cout<<v[i]<<"\n";
	return 0;
}

Measured memory_bytes: 28404
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[h,w]=i2()
s=[]
for i in range(h):
 s.append(input())
y=[[-1,0],[1,0],[0,1],[0,-1]]
ss="Yes"
for i in range(h):
 for j in range(w):
   if s[i][j]=="#":
     f=0
     for kx,ky in y:
       if 0<=i+kx<h and 0<=j+ky<w:
          if s[i+kx][j+ky]=="#":
               f=1
     if f==0:
        ss="No"
print(ss)

Measured memory_bytes: 40048
#!/usr/bin/env python3

import math


def solve(n):
    dmax = 0
    for d in range(1, int(math.sqrt(n)) + 1):
        if n % d == 0:
            dmax = max(dmax, d)
    cmax = n // dmax
    res = (cmax - 1) + (dmax - 1)
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int minus = 0;
    rep(i, n) {
        cin >> a[i];
        if (a[i] < 0) {
            minus++;
            a[i] *= -1;
        }
    }
    ll sum = 0;
    auto min_itr = min_element(a.begin(), a.end());
    for (auto it = a.begin(); it != a.end(); it++) {
        if (it == min_itr && minus % 2)
            sum += *it * -1;
        else
            sum += *it;
    }
    cout << sum << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using ll = long long int;

int main(){
    ll N, K; cin >> N >> K;
    string S; cin >> S;
    ll m = 0;
    for(int i=0; i<N; i++){
        if(S[i] == 'L'){
            if(i != 0){
                if(S[i-1] == 'L'){m++;}
            }
        }else{
            if(i != N-1){
                if(S[i+1] == 'R'){m++;}
            }
        }
    }
    ll t = 0;
    for(int i=1; i<N; i++){
        if(S[i]!=S[i-1]){t++;}
    }
    if(t/2 >= K){
        cout << m + 2*K;
    }else{
        if(t%2==0){cout << m + 2*(t/2);}
        else{cout << m + 2*(t/2) + 1;}
    }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N,M; cin>>N>>M;
  vii A(N,vi(M));
  rep(i,0,N){
    rep(j,0,M) cin>>A[i][j];
  }
  int ans=N;
  vector<bool> F(M,1);
  rep(i,0,M){
    vi C(M);
    rep(j,0,N){
      rep(k,0,M){
        if(F[A[j][k]-1]){
          C[A[j][k]-1]++;
          break;
        }
      }
    }
    int sum=-1,memo=-1;
    rep(j,0,M){
      if(F[j]&&sum<C[j]){
        sum=C[j];
        memo=j;
      }
    }
    F[memo]=0;
    ans=min(ans,sum);
  }
  cout<<ans<<endl;
  }



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //  repマクロ
#define leng(n) (int)(log10(n)+1)  //  桁数
using namespace std;

signed main() {
  string A, B;
  cin >> A;
  B ="";
  for (int i = 0; i < A.size(); i++) {
    if (A[i]=='A') B += 'T';
    if (A[i]=='T') B += 'A';
    if (A[i]=='G') B += 'C';
    if (A[i]=='C') B += 'G';
  }
  cout << B << endl;
}

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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    ll a;
    cin >> a;
    cout <<  (a+(a*a)+(a*a*a)) << endl;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 3620
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/


int main(){
int N,M;
cin>>N>>M;
int ans;
ans = (1800*M+100*N)*(int)pow(2,M);
cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 4036
# include <bits/stdc++.h>
using namespace std;
int n, m, a[308][308], vis[308], go[308];
bool check(int x)
{
    memset(go, 0, sizeof(go));
    for(int i=1; i<=n; ++i) a[i][0] = 1;
    while(1)
    {
        memset(vis, 0, sizeof(vis));
        bool flag = true;
        for(int i=1; i<=n; ++i)
        {
            while(a[i][0] <= m && go[a[i][a[i][0]]]) ++a[i][0];
            if(++vis[a[i][a[i][0]]] > x) {go[a[i][a[i][0]]]=1; flag =false;}
            if(a[i][0] > m) return false;
        }
        if(flag) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
    {
        a[i][0] = 1;
        for(int j=1; j<=m; ++j)
        scanf("%d",&a[i][j]);
    }
    int l=1, r=n;
    while(l<r)
    {
        int m = l+r>>1;
        if(check(m)) r = m;
        else l=m+1;
    }
    printf("%d\n",r);
    return 0;
}




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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=1e9+7;

int main(){
    int N; cin >> N;
    vector<pair<ll, ll>> range(N);
    for(int i=0; i<N; i++){
        ll X, L;
        cin >> X >> L;
        range[i]={X+L, X-L};
    }
    sort(all(range));
    ll ans=0, cur=-1e9-5;
    for(int i=0; i<N; i++){
        if(cur <= range[i].second){
            cur=range[i].first;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4756
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;

struct nd{
    vector< ll > ady;
}G[100010];

ll n,m,s,t,a,b;
queue< pair<ll,ll> > c;
pair<ll,ll> p,h;
bool use[ 100010 ][ 4 ];

int main()
{

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

    cin >> n >> m;
    for(ll i=0; i<m; i++) cin >> a >> b , G[a].ady.pb( b );
    cin >> s >> t;


    use[s][0] = true;
    c.push( {s,0} );

    while( !c.empty() ){
        p = c.front();
        c.pop();

        if( p.fi == t && p.se%3==0 ){
            cout << p.se/3;
            return 0;
        }

        h = p;
        h.se++;
        for(auto p1:G[p.fi].ady){
            if(use[p1][h.se%3]) continue;
            h.fi = p1;
            use[p1][h.se%3]=true;
            c.push( h );
        }
    }

    cout << -1;

    return 0;
}


Measured memory_bytes: 6144
n = int(input())
A = list(map(int, input().split()))

Aone = A[0]
counter = 0

for i in range (0, n):
	if A[i] == Aone:
		counter+=1
	else:
		break

if counter == n:
	print(int(n/2))
	exit()

k = int(len(A)/2)
maxA = max(A)

Odd = []
Even = []

for i in range (0, k):
	Odd.append(A[2*i])
	Even.append(A[2*i+1])

Oddcount = [0]*maxA
Evencount = [0]*maxA

for i in range (0, k):
	Oddcount[Odd[i]-1]+=1
	Evencount[Even[i]-1]+=1

Oddcount2 = sorted(Oddcount.copy())
Evencount2 = sorted(Evencount.copy())

if Oddcount.index(Oddcount2[-1]) != Evencount.index(Evencount2[-1]):
	print(2*k-Oddcount2[-1]-Evencount2[-1])
elif Oddcount2[-2] >= Evencount2[-2]:
	print(2*k-Oddcount2[-2]-Evencount2[-1])
else:
	print(2*k-Oddcount2[-1]-Evencount2[-2])

Measured memory_bytes: 14008
// problem: "https://atcoder.jp/contests/abc146/tasks/abc146_e"

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll numSeq(vector<ll>&V,ll n,ll k)
{
    ll i;
    for(i=1;i!=n+1;i++)
        V[i] += V[i-1];

    for(i=0;i!=n+1;i++)
    {
        V[i] -= i;
        V[i] %= k;
    }

    ll j,c;
    unordered_map<ll,ll>M;
    M[0] = 1;
    i = 0;
    c = 0;

    for(j=1;j!=n+1;j++)
    {
        if(j-i >= k)
        {
            M[V[i]]--;
            i++;
        }

        if(M.count(V[j]))
        {
            c += M[V[j]];
            M[V[j]]++;
        }
        else
        {
            M[V[j]] = 1;
        }
    }

    return c;
}

int main()
{
    ll n,k;
    cin>>n>>k;

    vector<ll>V={0};
    ll x,i;

    for(i=0;i!=n;i++)
    {
        cin>>x;
        V.push_back(x);
    }

    cout<<numSeq(V,n,k);        // define

    return 0;
}


Measured memory_bytes: 10096
/// hi_im_manh :D
#include <bits/stdc++.h>
#define reset(a,n) memset(a,0,(n+1)*sizeof(int))
#define endl "\n"
#define llmin LLONG_MIN
#define llmax LLONG_MAX
#define intmax INT_MAX
#define intmin INT_MIN
#define ll long long
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define time cout << "\nTime: " << clock()/(double) 1000 <<"s"
#define pb push_back
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const ll oo = 0x3f3f3f3f3f3f3f3f;

#define duckman "task"

#define input freopen(duckman".inp", "r", stdin);
#define output freopen(duckman".out", "w", stdout);

#define nmax 22000
using namespace std;


int main() {
    fast;
//    input;
//    output;

    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    ll ans = max((ll)0, min(a, k));
    k -= ans + b;
    if (k > 0) {
        ans -= min(k, c);
    }
    cout << ans;
	return 0;
}
/*

*/


Measured memory_bytes: 3648
module Main where

import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8         as BS
import           Data.List
import           Data.Char
import           Control.Monad
import           Data.Bits
import           Data.Function
import           Debug.Trace

ub = 1145141919

main :: IO ()
main = do
  [n, m] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  keys   <- replicateM m $ do
    [a, b] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    cs     <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    let bits = foldl' setBit zeroBits $ map pred cs
    return (a, bits)
  let full = bit n - 1
  let ans = solve full keys VU.! full
  print $ if ans == ub then -1 else ans

solve :: Int -> [(Int, Int)] -> VU.Vector Int
solve full keys = VU.create $ do
  dp <- VUM.replicate (full + 1) ub
  VUM.write dp 0 0
  forM_ [0 .. full - 1] $ \j ->
    forM_ keys $ \(ai, di) -> do
      let j_or_di = j .|. di
      candidate1 <- VUM.read dp j_or_di
      candidate2 <- VUM.read dp j
      let candidate2' = candidate2 + ai
      when (candidate1 > candidate2') $ 
        VUM.write dp j_or_di candidate2'
  return dp
      


Measured memory_bytes: 1404
#include <stdio.h>
#include <string.h>
int main () {
  char s[100001];
  scanf ("%s",s);
  int x;
  x = strlen(s);
  int n;
  int y = x;  //y = x/2
  y = (x+(x%2))/2;
  for (n=0;n<y;n++) {
    if (s[n] == 'b' && s[x-n-1] != 'd' || s[n] == 'd' && s[x-n-1] != 'b' || s[n] == 'p' && s[x-n-1] != 'q' || s[n] == 'q' && s[x-n-1] != 'p') {
      printf ("No\n");
      break;
    }
  }
  if (n == y) printf ("Yes\n");
  
  return 0;
}


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

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

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

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

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

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

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


int main(){
    int n , m, k;
    cin >> n >> m >> k;

    vector<vector<int> > fre(n);
    UnionFind uf(n);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        uf.merge(a, b);
        fre[a].push_back(b);
        fre[b].push_back(a);
    }

    vector<vector<int> > bro(n);
    for(int i = 0; i < k; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        bro[a].push_back(b);
        bro[b].push_back(a);
    }

    int cou = 0;

    for(int i = 0; i < n; i++){
        cou = uf.size(i);
        cou -= fre[i].size();
        for(int j = 0; j < bro[i].size(); j++){
            if(uf.issame(i, bro[i][j])){
                cou--;
            }
        }

        cou--;

        if(i != n - 1){
            cout << cou << " ";
        }else{
            cout << cou << endl;
        }
    }

}

Measured memory_bytes: 15764
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  if (a == b)
    printf("%d\n", c);
  if (b == c)
    printf("%d\n", a);
  if (c == a)
    printf("%d\n", b);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF 1e18
#define dump(x) cerr<<#x<<"="<<x<<endl
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }
template <class T> void chmax(T & a, T const & b) { if (b > a) a = b; }
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
using ll = long long;
const ll mod = LLONG_MAX;


int h,ma,ans;
int a[110];
int main(){
    cin>>h;
    rep(i,h){
        if(i>0)ma=max(ma,a[i-1]);
        cin>>a[i];
        
        if(a[i]>=ma)ans++;
    }
    cout<<ans<<endl;
}


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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

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

  ll a, b, c;
  cin >> a >> b >> c;

  cout << (a + b >= c ? "Yes" : "No") << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

typedef pair<int,int> pint;
typedef pair<int,pint> ppint;
const int INF=1e9;
struct edge{int to,cost;};
int N,M,L;

vector<int> solve(int s,vector<vector<edge>>& G)
{
    vector<int> mincnt(N,INF),dp(N,-1);
    mincnt[s]=0;
    dp[0]=L;
    priority_queue<ppint,vector<ppint>,greater<ppint>> Q;
    Q.push({0,{s,L}}); 

    while(!Q.empty()){
        ppint p=Q.top(); Q.pop();
        int cnt=p.first;
        int v=p.second.first;
        int rest=p.second.second;
        if(cnt>mincnt[v]) continue;
        if(rest<dp[v]) continue;

        // cout<<v+1<<' '<<cnt<<' '<<dp[v]<<endl;
        for(edge e:G[v]){
            if(rest>=e.cost){
                if(mincnt[e.to]>cnt){
                    mincnt[e.to]=cnt;
                    dp[e.to]=rest-e.cost;
                    Q.push({mincnt[e.to],{e.to,dp[e.to]}});
                }else if(mincnt[e.to]==cnt){
                    if(rest-e.cost>dp[e.to]){
                        dp[e.to]=rest-e.cost;
                        Q.push({mincnt[e.to],{e.to,dp[e.to]}});
                    }
                }
            }
            int nxtcnt=cnt+1;
            if(mincnt[e.to]>nxtcnt){
                mincnt[e.to]=nxtcnt;
                dp[e.to]=L-e.cost;
                Q.push({mincnt[e.to],{e.to,dp[e.to]}});
            }else if(mincnt[e.to]==nxtcnt){
                if(L-e.cost>dp[e.to]){
                    dp[e.to]=L-e.cost;
                    Q.push({mincnt[e.to],{e.to,dp[e.to]}});
                }
            }
        }
    }
    for(int i=0;i<N;i++) if(mincnt[i]==INF) mincnt[i]=-1;
    // for(int i=0;i<N;i++) cout<<mincnt[i]<<' '; cout<<endl;
    // for(int i=0;i<N;i++) cout<<dp[i]<<' '; cout<<endl;
    return mincnt;
};

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

    cin>>N>>M>>L;
    vector<vector<edge>> G(N);
    for(int i=0;i<M;i++){
        int a,b,c; cin>>a>>b>>c;
        a--; b--;
        if(c>L) continue;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    vector<vector<int>> ans(N);
    for(int i=0;i<N;i++){
        ans[i]=solve(i,G);
    }
    int Q; cin>>Q;
    while(Q--){
        int s,t; cin>>s>>t;
        s--; t--;
        cout<<ans[s][t]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3584
#include<stdio.h>
int main(void)
{
    int i,j,k,n,aisu[10],hanbai,kazu[10];
    for(i=0;i<10;i++){
        aisu[i]=i;
        kazu[i]=0;
    }
    for(;;){
    scanf("%d",&n);
    if(n==0)break;
    for(i=0;i<n;i++){
        scanf("%d",&hanbai);
        for(j=0;j<10;j++){
            if(aisu[j]==hanbai){
                kazu[j]++;
            }
        }
    }
    for(i=0;i<10;i++){
        for(j=0;j<kazu[i];j++){
            if(kazu[i]>0){
                printf("*");
            }
        }
        if(kazu[i]==0){
            printf("-");
        }
        printf("\n");
    }
    for(i=0;i<10;i++){
     kazu[i]=0;
    }
    }
    return 0;
}

Measured memory_bytes: 572
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    int a[26];
    memset(a,0,sizeof(a));
    char c;
    while(cin >> c)
    {
        a[c - 'a']++;
    }
    for(int i = 0;i < 26;i++)
    {
        if(a[i] > 1)
        {
            cout << "no\n";
            return 0;
        }
    }
    cout << "yes\n";
    return 0;
}

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

using namespace std;
typedef long long ll;

int main(){
    string s;
    const string cmpDate = "2019/04/30";
    cin >> s;

    if(s>cmpDate){
        cout << "TBD" << endl;
    }else{
        cout << "Heisei" << endl;
    }

    return 0;
}

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

using namespace std;

int main(void) {
  int n;
  cin >> n;
  vector <int> v(n);
  for(int i = 0; i < n; i++) {
    cin >> v[i];
  }

  map <int, int> odd, even;
  for(int i = 0; i < n; i++) {
    if(i % 2 == 0) {
      even[v[i]]++;
    }
    else {
      odd[v[i]]++;
    }
  }

  int ans = 0;
  int mx_odd = 0;
  int ki_odd = -1;
  for(auto i : odd) {
    if(mx_odd < i.second) {
      mx_odd = i.second;
      ki_odd = i.first;
    }
  }

  int mx_even = 0;
  int ki_even = -1;
  for(auto i : even) {
    if(mx_even < i.second) {
      mx_even = i.second;
      ki_even = i.first;
    }
  }

  //  cout << ki_odd << ", " << ki_even << endl;
  if(ki_odd == ki_even) {
    int mx_o2 = 0;
    int ki_o2 = -1;
    for(auto i : odd) {
      if(mx_o2 < i.second && i.first != ki_odd) {
	mx_o2 = i.second;
	ki_o2 = i.first;
      }
    }

    int mx_e2 = 0;
    int ki_e2 = -1;
    for(auto i : even) {
      if(mx_e2 < i.second && i.first != ki_even) {
	mx_e2 = i.second;
	ki_e2 = i.first;
      }
    }

    if(mx_odd - mx_o2 < mx_even - mx_e2) {
      mx_odd = mx_o2;
      ki_odd = ki_o2;
    }
    else {
      mx_even = mx_e2;
      ki_even = ki_e2;
    }
  }

  ans += n - mx_odd - mx_even;
  cout << ans << endl;
}

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

    int main() {
        int W,H,x,y,r;
        cin >> W >> H >> x >> y >> r ;

        if(x - r >= 0 && x + r <= W && y - r >= 0 && y + r <= H){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
        return 0;
    }


Measured memory_bytes: 3104
/*
	ex3_2
	ruuu0048
*/
#include <stdio.h>
#include <math.h>
#define PI 3.14159265359 //πを定義
 
double radian_distance_cos(int hour,int minute); //時針と分針の間の角度の余弦を返す関数
 
int main(void){
 
 
    int hour_length,minute_length; //時針と分針の変数を宣言
    int hour,minute; //時間Hと分Mの変数を宣言
    double distance; //求める距離の変数を宣言
 
    scanf("%d %d %d %d",&hour_length,&minute_length,&hour,&minute); //それぞれ入力
    
    distance = sqrt(pow(hour_length,2) + pow(minute_length,2) - 2 * hour_length * minute_length * radian_distance_cos(hour,minute)); //余弦定理を使う
 
    printf("%.16f\n",distance); //答えを出力
 
    return 0; 
}
 
double radian_distance_cos(int hour,int minute){
 
    double hour_radian,minute_radian; //時針と分針の0時からの角度の変数を宣言
 
    hour_radian = ((double)hour + (double)minute / 60) / 12 * (2 * PI); //ラジアンに変換
 
    minute_radian = (double)minute / 60 * (2 * PI); //ラジアンに変換
 
    return cos(hour_radian - minute_radian); //差の予言を返す
 
};


Measured memory_bytes: 2520
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
 
int main() {
  ll n,m;
  cin >> n >> m;
  ll ans;
  m /= 2;
  if (n > m) ans = m;
  else {
    ans = (n+m) / 2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll a[4];
ll read() {
	char ch = getchar();
	ll x = 0, f = 1;
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9') x = x*10 + ch - 48, ch = getchar();
	return x * f;
}
int main() {
	for(int i=1; i<=3; i++)
		a[i]=read();
	sort(a+1,a+3+1);
	if((a[1]==a[2]&&a[2]!=a[3])||(a[2]==a[3]&&a[1]!=a[2]))
		cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(void) {
    //char a, b, c, d, e;
    int a[5];
    for(int i = 0; i < 5; i++) {
        cin >> a[i];
    }
    int x;
    for(int i = 0; i < 5; i++) {
        if(a[i] ==0) x = i+1;
    }

    cout << (x) << endl;

    return 0;
}


Measured memory_bytes: 3588
#include<cstdio>
using namespace std;
const long long N=1e9+7;
const int M=2005;
long long finv[500000],fac[500000],dp[5000][5000],a[500000],b[500000];
long long ksm(long long n,long long k)
{
	long long ret=1;
	while (k)
	{
		if (k%2) ret=ret*n%N;
		n=n*n%N;
		k/=2;
	}
	return ret;
}
void init()
{
	for (int i=1;i<=4010;i++)
	{
		for (int j=1;j<=4010;j++)
		dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i][j-1])%N;
	}
}
void invd()
{
	fac[1]=1;
	for (int i=2;i<=100000;i++) fac[i]=i*fac[i-1]%N;
	finv[100000]=ksm(fac[100000],N-2);
	for (int i=100000;i>=1;i--) finv[i-1]=finv[i]*i%N;
}
long long C(long long n,long long m)
{
	return fac[n]%N*finv[m]%N*finv[n-m]%N;
}
int main()
{
	invd();
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	scanf("%lld%lld",&a[i],&b[i]);
	for (int i=1;i<=n;i++) dp[M-a[i]][M-b[i]]++;
	init();
	long long ans=0;
	for (int i=1;i<=n;i++) ans=(ans+dp[a[i]+M][b[i]+M])%N;
	for (int i=1;i<=n;i++) ans=(ans-C(a[i]*2+b[i]*2,2*a[i])+N)%N;
	printf("%lld\n",ans*finv[2]%N);
	return 0; 
}

Measured memory_bytes: 169600
N, M = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for a in A:
	ans[a] = -1

for i in range(len(ans)):
	if ans[i] == -1:
		continue
	if(i+1 < len(ans) and ans[i+1] != -1):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and ans[i+2] != -1):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])

Measured memory_bytes: 50136
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const double PI  = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const LL INF  = 0x3f3f3f3f3f3f;
const int N=3e5+10;
const int M=1e6+10;
const int mod=1e9+7;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
inline LL lcm(LL a, LL b) { return a * b / gcd(a, b); }
inline LL read(){LL x=0,f=1;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 x*f;}
inline LL qpow(LL x,LL k=mod-2,LL m=mod){LL res=1;while(k){if(k&1) res=res*x%m;x=x*x%m;k>>=1;}return res;}
/*=================================================================================================================*/


int main(){
    int x;cin>>x;
    cout<<(!x)<<endl;
    
    return 0;
}

Measured memory_bytes: 3592
#include <stdio.h>
#include <algorithm>


char st[200];

int main()
{
    scanf("%s",st+1);
    int flag=1;
    for (int i=1;st[i];i++)
    {
        if (st[i]=='U' || st[i]=='D') continue;
        if (st[i]=='R')
            if (i%2==0)
                flag=0;
        if (st[i]=='L')
            if (i%2)
                flag=0;
    }
    if (flag) printf("Yes\n");
    else printf("No\n");
}


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

int main() {
  int N, M, A;
  cin >> N >> M >> A;
  if(N == M && M == A){
      cout << "No" << endl;
  }
  else if(N != M && M != A && N != A){
      cout << "No" << endl;
  }
  else cout << "Yes" << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        List<int> list = new List<int>();
        for (int i = 0; i < n; i++)
            list.Add(int.Parse(Console.ReadLine()));
        list.Sort();
        if (n == 1)
        {
            Console.WriteLine(1);
        }
        else
        {
            int ans = 0;
            int tmp = list[0];
            bool even = false;
            for (int i = 1; i < n; i++)
            {
                if (i == n - 1)
                {
                    if (tmp == list[i])
                    {
                        if (even) ans++;
                    }
                    else if (even) ans++;
                    else ans += 2;
                }
                else
                {
                    if (tmp == list[i])
                    {
                        even = !even;
                    }
                    else
                    {
                        if (even) even = false;
                        else ans++;
                        tmp = list[i];
                    }

                }
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 16092
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

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

    int H, W, D;
    cin >> H >> W >> D;

    int N = H * W;

    vvi A(H, vi(W));
    rep(i, H)
    {
        rep(j, W)
        {
            cin >> A[i][j];
            A[i][j]--;
        }
    }

    vector<pair<int, int>> pos(N);
    rep(i, H)
    {
        rep(j, W)
        {
            pos[A[i][j]] = make_pair(i, j);
        }
    }

    //コストを累積和で計算
    vvll cost(D, vll(N / D + 1));
    rep(d, D)
    {
        for (int c = 0; c < N; c++)
        {
            int next = (c + 1) * D + d;
            if (next >= N) break;
            auto p = pos[next - D];
            auto q = pos[next];
            cost[d][c + 1] = cost[d][c] + (abs(p.first - q.first) + abs(p.second - q.second));
        }
    }

    int Q;
    cin >> Q;

    rep(i, Q)
    {
        int L, R;
        cin >> L >> R;
        L--;
        R--;

        int d = L % D;
        int l = L / D;
        int r = R / D;

        cout << cost[d][r] - cost[d][l] << endl;
    }

    return 0;
}

Measured memory_bytes: 9224
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


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

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
	int n;
	cin>>n;
	vector<pair<ll,pll>> v(n);
	rep(i,n){
		cin>>v[i].se.se>>v[i].se.fi;
		v[i].fi = v[i].se.fi + v[i].se.se;
	}
	sort(ALL(v));
	vll dp(n+2,INFL);
	dp[0] = 0;
	rep(i,n){
		ll H = v[i].se.se;
		ll P = v[i].se.fi;
		for(int j=n+1; j>=0; j--){
			if(dp[j] > H) continue;
			if(dp[j]+P < dp[j+1]) dp[j+1] = dp[j]+P;
		}
	}
	int ans = 0;
	rep(i,n+2) if(dp[i]<INFL) ans = i;
	cout<<ans<<endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

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

int main(){

  int n,*a,kaisu=0,temp;
  int i,j;

  scanf("%d",&n);

  a=(int *)malloc(sizeof(int)*n);

  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }

  for(i=0;i<n-1;i++){
    for(j=n-1;j>i;j--){
      if(a[j]<a[j-1]){
	temp=a[j];
	a[j]=a[j-1];
	a[j-1]=temp;
	kaisu++;
      }
    }
  }

  for(i=0;i<n;i++){
    printf("%d",a[i]);
    if(i!=n-1)printf(" ");
  }
  printf("\n%d\n",kaisu);

  free(a);

  return 0;

}

Measured memory_bytes: 604
/* Simplicity and Goodness */

#include <bits/stdc++.h>
using namespace std;
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define deb(x) cout << #x << ' ' << x << '\n'
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define per(i,ini) for(int i=ini;i>=0;i--)
#define tc int tt; scn(tt); while(tt --)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 998244353;
const int N = 2e5+2;


int main()
{
    ll x;
    lscn(x);
    
    ll a, b;
    
    for(ll i=-1002; i<=1002; i++)
    {
        ll here = pow(i, 5);
        
        double total = here + x;
        
        ll temp = pow(total, 1.0/5);
        
        ll req = pow(temp, 5);
        
        if(req - here == x)
        {
            a = temp;
            b = i;
            break;
        }
    }
    
    lpri(a); lprin(b);
    
    return 0;
}

Measured memory_bytes: 4260
#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

int a[500][500];

vector<tuple<int, int, int, int>> operations;

int main()
{
    int H, W;

    cin >> H >> W;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
        {
            cin >> a[i][j];
        }

    int currX = 0;
    int currY = 0;
    int dirX = 1;
    for (int i = 0; i < H * W - 1; i++)
    {
        bool stayX = currX + dirX < 0 || currX + dirX >= H;
        int nextX = stayX ? currX : currX + dirX;
        int nextY = stayX ? currY + 1 : currY;

        if (a[currX][currY] % 2 == 1)
        {
            operations.push_back(make_tuple(currX, currY, nextX, nextY));
            a[currX][currY]--;
            a[nextX][nextY]++;
        }

        dirX *= stayX ? -1 : 1;
        currX = nextX;
        currY = nextY;
    }

    cout << operations.size() << endl;
    for (const auto &op : operations)
    {
        cout << get<0>(op) + 1 << " " << get<1>(op) + 1 << " " << get<2>(op) + 1 << " " << get<3>(op) + 1 << endl;
    }
}

Measured memory_bytes: 5104
import sys
import collections

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = nm()
    uf = UnionFind(M)
    lang_spoken = set()
    for i in range(N):
        k, *lang = nm()
        assert len(lang) == k
        roots = {uf.find(l - 1) for l in lang}
        lang_spoken |= roots
        roots = list(roots)
        x = roots[0]
        for y in roots[1:]:
            uf.union(x, y)
    lang1 = next(iter(lang_spoken))
    return uf.size(lang1) == len(lang_spoken)


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self._root_table) if x == i]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


print(["NO", "YES"][solve()])


Measured memory_bytes: 12728
using System;

namespace E___Sum_Equals_Xor
{
    class Program
    {
        static void Main(string[] args)
        {
            var L = Console.ReadLine();
            var dp = new long[L.Length + 1, 2];
            dp[0, 1] = 1;
            long MOD = 1000000007;

            for (int i = 1; i < L.Length + 1; i++)
            {
                dp[i, 0] += (dp[i - 1, 0] * 3) % MOD;

                if (L[i - 1] == '1')
                {
                    dp[i, 1] += (dp[i - 1, 1] * 2) % MOD;
                    dp[i, 0] += (dp[i - 1, 1]) % MOD;
                }
                else
                {
                    dp[i, 1] += dp[i - 1, 1] % MOD;
                }
            }
            var result = (dp[L.Length, 0] + dp[L.Length, 1]) % MOD;
            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 13140
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)

// github.com/EndlessCheng/codeforces-go
func run(_r io.Reader, _w io.Writer) {
	in := bufio.NewReader(_r)
	var n, k int
	Fscan(in, &n, &k)
	next := make([]int, n+1)
	for i := 1; i <= n; i++ {
		Fscan(in, &next[i])
	}

	beforeCycle := []int{}
	cycle := []int{}
	vis := make([]int8, n+1)
	for v := 1; vis[v] < 2; v = next[v] {
		if vis[v] == 1 {
			cycle = append(cycle, v)
		}
		vis[v]++
	}
	for v := 1; vis[v] == 1; v = next[v] {
		beforeCycle = append(beforeCycle, v)
	}
	if k < len(beforeCycle) {
		Fprint(_w, beforeCycle[k])
	} else {
		k -= len(beforeCycle)
		Fprint(_w, cycle[k%len(cycle)])
	}
}

func main() { run(os.Stdin, os.Stdout) }


Measured memory_bytes: 12616