akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0xfff;
ll gcd(ll a, ll b)
{
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
ll a[1000005];
int main()
{
	ios::sync_with_stdio(false);
	ll a, b;
	cin >> a >> b;
	cout << a * b;
}


Measured memory_bytes: 3652
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse =True)
minimum = sum(A)/(4*M)
count = 0
for i in range(M):
    a = A.pop(0)
    if a < minimum:
        count = 1
if count == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 61936
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>

int calc_max(std::vector<int> &h, int n){
    int maxh = 0;
    for (int i=0; i < n; i++){
        if (h[i]>maxh) maxh = h[i];
    }
    return maxh;
}

void down_max(std::vector<int> &h, int maxh, int n){
    for (int i=0; i < n; i++){
        if(h[i]==maxh){
            for(int j = i; j < n; j++){
                if(h[j]==maxh){
                    h[j]--;
                }else{
                    return;
                }
            }
        }
    }
}

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

    for(int k=0; ;k++){
        int maxh = calc_max(h, n);
        // std::cout << "maxh="<<maxh<<"\n";
        if (maxh==0) {
            std::cout << k << std::endl;
            return 0;
        }
        down_max(h, maxh, n);
    }
	return 0;
}


Measured memory_bytes: 256
using System;

namespace ABC139_C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            var line = Console.ReadLine().Split();
            var lineInt = new int[n];
            for (int i = 0; i < n; i++)
            {
                lineInt[i] = int.Parse(line[i]);
            }

            int now = 0, count = 0, max = 0;

            for (int i = 0; i < n - 1; i++)
            {
                if (lineInt[i] >= lineInt[i+1])
                    count++;
                else
                    count = 0;
                if (count > max)
                    max = count;
            }

            Console.WriteLine(max);
        }
    }
}

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

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


 cout << b;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){

  int value = 0;
  int nextnum = 0;

  cin >> value;

  for(int i = 1; i <= value / 2 + 1; i++){

    nextnum = (i + 1) * (i + 1);

    if(nextnum > value){

      cout << i * i << endl;

      return 0 ;
 
    }

  }
  
  return 0;

}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b;
  scanf("%d%d",&a,&b);
  if(a<b){
    printf("a < b\n");
  }
  else if(a>b){
    printf("a > b\n");
  }
  else printf("a == b\n");
  return 0;
}


Measured memory_bytes: 2036
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
    using namespace std;
 
    int main(){
      int x,a,b;
      cin >> x >> a >> b;
      if(b<=a) cout << "delicious" << endl;
      else if(b-a<=x) cout << "safe" << endl;
      else if(b-a>x) cout << "dangerous" << endl;
      return 0;}

Measured memory_bytes: 256
line = input().split()
line2 = input().split()
lim = int(input())

apos = int(line[0])
aspeed = int(line[1])
bpos = int(line2[0])
bspeed = int(line2[1])

distance = abs(bpos - apos)
deltaspeed = aspeed - bspeed

if deltaspeed <= 0:
  print("NO")
if deltaspeed > 0:
  time = distance/deltaspeed
  if time <= lim:
    print("YES")
  else:
    print("NO")

Measured memory_bytes: 9208
def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    def getDistNexts(As):
        lenA = len(As)
        poss = dict()
        for i, A in enumerate(As):
            if A not in poss:
                poss[A] = i + lenA

        distNexts = [0]*(lenA)
        for i in reversed(range(lenA)):
            distNexts[i] = poss[As[i]] - i
            poss[As[i]] = i
        return distNexts

    distNexts = getDistNexts(As)

    NK = N*K
    maxD = (NK).bit_length() - 1

    dp = [[0]*(N) for _ in range(maxD+1)]
    for i in range(N):
        dp[0][i] = distNexts[i] + 1
    for d in range(1, maxD+1):
        for i in range(N):
            i2 = i + dp[d-1][i]
            dp[d][i] = i2 + dp[d-1][i2%N] - i

    iNow = 0
    dist = 0
    for d in reversed(range(maxD+1)):
        if dist+dp[d][iNow] < NK:
            dist += dp[d][iNow]
            iNow = dist%N

    Ss = []
    setS = set()
    for A in As[iNow:]:
        if A in setS:
            S = ''
            while S != A:
                S = Ss.pop()
                setS.remove(S)
        else:
            Ss.append(A)
            setS.add(A)

    if Ss:
        print(' '.join(map(str, Ss)))


solve()


Measured memory_bytes: 349640
N = int(input())
S = input()
cnt = 0
revS = []
for s in reversed(S):
    revS.append(s)
for s in S:
    if s == "(":
        cnt += 1
    else:
        if cnt <= 0:
            print("(", end="")
        if cnt > 0:
            cnt -= 1
print(S,end="")
cnt = 0
for s in revS:
    if s == ")":
        cnt += 1
    else:
        if cnt <= 0:
            print(")", end="")
        if cnt > 0:
            cnt -= 1


Measured memory_bytes: 3064
import java.io.*;

class Main {
	public static void main(String[] args) {
		BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
		try {
			int n = Integer.parseInt( kb.readLine() );
			String[] nums = kb.readLine().split( " " );
			int len = nums.length;
			int[] A = new int[ len ];
			int i, len2 = len-1;

			StringBuilder output = new StringBuilder( 100+1 );									
			for( i=0; i<len; i++ ) {
				A[i] = Integer.parseInt( nums[i] );
				output.append( i<(len2)? A[i]+" ": A[i]  );
			}
			System.out.println( output  );
			output.setLength( 0 );

			int key;
			int j, k;
 			for( i=1; i<len; i++ ) {
				key = A[i];
				j = i - 1;
				while( 0 <= j && key < A[j] ) {
					A[ j+1 ] = A[j];
					j--;
				}
				A[ j+1 ] = key;
				for( k=0; k<len; k++ ) {
					output.append( k<(len2)? A[k]+" ": A[k]  );
				}
				System.out.println( output  );
				output.setLength( 0 );
			}
			
 			kb.close();
		} catch( IOException e ) {
			System.err.println( e );
		}
	}
}

Measured memory_bytes: 24192
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <limits>
#include <sstream>
#include <typeinfo>
#include <cstdint>

using namespace std;

typedef long long ll;

int main() {
	int N;
	ll X;
	cin >> N >> X;
	vector<ll> a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	vector<vector<ll>> dp(N, vector<ll>(N));
	ll ans = 1LL << 62LL;
	ll tmp = 0;
	for (int i = 0; i < N; i++) {
		dp[i][0] = a[i];
		tmp += dp[i][0];
	}
	ans = min(ans, tmp);
	for (int k = 1; k < N; k++) {
		ll tmp = k*X;
		for (int i = 0; i < N; i++) {
			const int idx = (i + N - k) % N;
			dp[i][k] = min(dp[i][k - 1], a[idx]);
			tmp += dp[i][k];
		}
		ans = min(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 31616
#include <bits/stdc++.h>
using namespace std;
 
void chmax(int64_t& a, int64_t b){
    a = max(a, b);
}
 
const int M = 200001;
int L, N;
int64_t X[M], Y[M], Xs[M], Ys[M];
 
int main(){
    cin >> L >> N;
    for(int i=1; i<=N; i++){
        cin >> X[i];
        Y[N+1-i] = L - X[i];
    }
    for(int i=1; i<=N; i++){
        Xs[i] = Xs[i-1] + X[i];
        Ys[i] = Ys[i-1] + Y[i];
    }
 
    const int dx[2] = {1, 0};
    const int dy[2] = {0, 1};
    int64_t ans = 0;
    for(int d=0; d<=N; d++){
        int xt = d, yt = N-d;
        for(int k1=0; k1<2; k1++){
            for(int k2=0; k2<2; k2++){
                int cx = min(xt, yt + (- dy[k1] - dy[k2] + dx[k1] + dx[k2]) / 2);
                int cy = min(yt, xt + (- dx[k1] - dx[k2] + dy[k1] + dy[k2]) / 2);
                if(cx < 0 || cy < 0) continue;
 
                int64_t result = 0;
                result += (Xs[xt] - Xs[xt-cx]) * 2;
                result += (Ys[yt] - Ys[yt-cy]) * 2;
                result -= (k2 ? Y[yt] : X[xt]);
                chmax(ans, result);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6528
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

    f = int(S[:2])
    b = int(S[2:])
    if 1 <= f <= 12 and 1 <= b <= 12:
        print('AMBIGUOUS')
    elif 1 <= b <= 12:
        print('YYMM')
    elif 1 <= f <= 12:
        print('MMYY')
    else:
        print('NA')

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 10080
#include<bits/stdc++.h>
using namespace std;
bool isperfectsquare (long double x){
long double sr = sqrt(x);
return((sr-floor(sr))==0);
}
int main(){
int n;
cin>>n;
int f=0;
for(int i=n;i>=0;--i){
if(isperfectsquare(i)){
  cout<<i<<endl;
  break;
}
}
return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll func(ll n){
    if(n<=0)return 0;
    if(n%4==1)return 1;
    if(n%4==2)return n+1;
    if(n%4==3)return 0;
    if(n%4==0)return n;
}
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll a,b;cin>>a>>b;
    cout<<( func(b)^func(a-1) );
}


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

musics = [[] for i in range(N)]
for i in range(N):
    musics[i] = list(input().split())

X = input()

ans = 0
flg = False
for music in musics:
    if flg:
       ans += int(music[1])
    if music[0] == X:
        flg = True

print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#define INF 1000000000
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long int ll;
using namespace std;

int main() {

	int n; cin >> n;
	rep(i, n) {
		int num; cin >> num;
		if (num % 2 == 0 && num % 3 != 0 && num % 5 != 0) {
			cout << "DENIED" << endl;
			return 0;
		}
	}
	cout << "APPROVED" << endl;

	return 0;
}

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

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

int main(){
	int a;
	cin>>a;
	int b[3][a];
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < a; j++){
			if(i == 2 && j == a - 1)
				break;
			else
				cin>>b[i][j];
		}
	}
	int c = 0;
	for(int i = 0; i < a; i++){
		c += b[1][i];
		if(i < a - 1){
			if(b[0][i] == b[0][i + 1] - 1){
				c += b[2][b[0][i] - 1];
			}
		}
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned ll
using namespace std;
inline int read(){
	int s=0,t=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*t;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int n=read();
	int t=ceil(1.0*n/1000);
	cout<<t*1000-n;
	return 0;
}


Measured memory_bytes: 3632
import scala.io.StdIn

object Main extends App {
  val Array(a, b, k) = StdIn.readLine().trim.split(" ").map(_.toInt)
  val k1 = if(b - a <= k) b - a else k
  val result: Array[Int] = if(a != b) ((a until a + k1).map(i => i) ++ (b - k1 + 1 to b ).map(i => i)).toArray
  else Array(a)
  
  println(result.distinct.mkString(f"%n"))
}

Measured memory_bytes: 25536
#include <bits/stdc++.h>
#define maxn 100001
#define maxa 2000005
#define MOD  998244353 //1000000007
#define INF 1000000000000000000

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define piii pair<pii, ll>
#define ft first
#define sd second
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n-1; i >= 0; i--)
#define mem(a, b) memset(a, b, sizeof(a))
#define sort(v) sort(v.begin(), v.end())
#define edge(v, x, y) v[x].pb(y); v[y].pb(x);
#define popcount __builtin_popcount

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout << setprecision(10) << fixed;
}
ll ceil(ll a, ll b){ return (a+ b-1)/b; }
void flaged(bool flag){
    if(flag) cout << "Yes\n";
    else cout << "No\n";
}
// power and modulo inverse
ll power(ll a, ll b = MOD-2){
    if(b == 0) return 1;
    ll r = power(a, b/2);
    r = (r*r)%MOD;
    if(b%2 == 1) r = (r*a)%MOD;
    return r;
}
// factorial
ll fact[maxa], finv[maxa];
void calf(){
    fact[0] = finv[0] = 1;
    for(ll i = 1; i < maxa; i++){fact[i] = (fact[i-1]*i) %MOD;finv[i] = (finv[i-1]*power(i))%MOD;}
}
// nCr
ll ncr(ll N, ll R){ if(R > N) return 0; return (fact[N]*((finv[R]*finv[N-R])%MOD))%MOD;}

ll mn= 1000005,k=0;
bool prime[1000005];
vector<ll>vec;
ll seive(){
    ll i, j;
    memset(prime,  true, sizeof(prime));
    prime[0]= prime[1]= false;
    for(i=2; i*i<=mn;i++){
        if(prime[i]){
            //
            for(j = i*i;j<=mn; j+= i){
                prime[j] = false;
            }
        }
    }
    for(i=0; i<mn;i++){
        if(prime[i]) {vec.push_back(i); }
    }
}

void solve(){

    ll n, k; cin >> n >> k;
    ll a[n], ar[3];
    cin >> ar[0] >> ar[1] >> ar[2];
    string s; cin >> s;
    rep(i, n)
    {
        if(s[i] == 'r') a[i] = 0;
        else if(s[i] == 's') a[i] = 1;
        else a[i] = 2; //cout  << a[i] << " ";
    }

    ll ans = 0;
    rep(i, n)
    { //cout << ans << " ";
        if(i < k){
            ans += ar[(a[i]+2)%3];
        }
        else {
            if(a[i-k] == a[i] && a[i-k] != -1){
                a[i] = -1;
            }
            else{
                ans += ar[(a[i]+2)%3];
            }
        }
    }
    cout << ans;
}

int main()
{
    fast();
    ll t = 1;//cin >> t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 1232
import java.util.*;
public class Main{
  public static void main(String[]args){
      Scanner sc = new Scanner(System.in);

      String S = sc.nextLine();
      char[]  n = new char[3];
      for(int i =0;i<3;i++){
          n[i]=S.charAt(i);
        }

      for(int i =0;i<3;i++){
        if(n[i]=='1'){
          n[i]='9';
        }else{
          n[i]='1';
        }

      }
      System.out.print(n);
  }
}

Measured memory_bytes: 21716
#define _DEBUG 1
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#ifdef _DEBUG
#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z)                                                         \
  cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z     \
       << endl
#define check(s) cerr << s << endl
#else
#define dump(x)
#define dump2(x, y)
#define dump3(x, y, z)
#define check(s)
#endif

#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());

void solve(string S) {
  if (sz(S) == 1) {
    cout << stoll(S) << endl;
    return;
  }

  int upper = pow(2, sz(S) - 1);
  ll sum = 0;
  for (int tmp = 0; tmp < (1 << 9); tmp++) {
    bitset<9> s(tmp);
    if (s.to_ullong() >= upper) {
      break;
    }

    vector<ll> v;
    ll a = (ll)(S[0] - '0');
    for (int i = 1; i < sz(S); i++) {
      ll b = (ll)(S[i] - '0');
      if (s.test(sz(S) - 1 - i)) {
        v.push_back(a);
        a = b;
      } else {
        a = a * 10 + b;
      }
    }
    v.push_back(a);
    ll acc = accumulate(all(v), 0L);
    sum += acc;
  }
  cout << sum << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You
// use the default template now. You can remove this line by using your custom
// template)
int main() {
  string S;
  cin >> S;
  solve(S);
  return 0;
}


Measured memory_bytes: 256
use std::fs;
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let (n, k): (usize, usize) = parse!(it, 2);
    let a: Vec<usize> = parse!(it, n);
    let mut asum: Vec<usize> = vec![];
    for i in 0..n {
        for j in (i + 1)..(n + 1) {
            asum.push(a[i..j].iter().sum());
        }
    }
    let mut ret: usize = 0;
    for i in (0..40).rev() {
        let cur: usize = (1 << i) + ret;
        let mut count = 0;
        for i in 0..asum.len() {
            let a = asum[i];
            if cur & a == cur {
                count += 1;
            }
        }
        if count < k {
            continue;
        }
        ret = cur;
    }
    println!("{}", ret);
}

fn test() {
    let mut f = fs::File::open("foo.txt").unwrap();
    let mut s = String::new();
    f.read_to_string(&mut s).unwrap();
    solve(&s);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_main() {
        test();
    }
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 9464
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct Edge{
    ll to, weight;
    Edge(ll t, ll w) : to(t), weight(w){}
};
using graph = vector<vector<ll>>;
using Graph = vector<vector<Edge>>;


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

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

int main(){
    ll n, m;
    cin>>n>>m;
    vector<pair<ll, ll>> t(m);
    for(ll i=0;i<m;++i){
        cin>>t[i].second>>t[i].first;
    }
    sort(t.begin(), t.end());

    ll ans = 0;
    ll sum = 0;
    for(ll i=0;i<m;++i){
        if(t[i].second >= sum){
            sum = t[i].first;
            ans++;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define REP(i,a,n) for(int i = a ; i < n ; i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;

vector<int> solve(vector<int> v){
  map<int,int> cnt;
  rep(i,v.size()) cnt[v[i]]++;

  vector<int> res;
  rep(i,v.size()) res.push_back(cnt[v[i]]);
  return res;
}

int main(){
  int n;

  while(cin>>n,n){
    vector<int> v(n);
    rep(i,n) cin>>v[i];
    int cnt = 0;

    while(1){
      vector<int> next = solve(v);
      if(next == v){
        break;
      }
      v = next;
      cnt++;
    }

    cout<<cnt<<endl;
    rep(i,n){
      if(i != 0) cout<<" ";
      cout<<v[i];
    }
    cout<<endl;
  }
}

Measured memory_bytes: 0
//2018年  3月 23日 金曜日 23:37:25 JST
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
ll A[MAX_N];

bool ok(int m) {
	ll res = A[m];
	rep(i, 0, N) {
		if(i == m) continue;
		if(res * 2 < A[i]) return false;
		res += A[i];
	}
	return true;
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	sort(A, A + N);
	int lv = -1, rv = N - 1;
	while(rv - lv > 1) {
		int m = (lv + rv) / 2;
		if(ok(m)) rv = m;
		else lv = m;
	}
	cout << N - rv << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 1024
#include <map>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <tr1/unordered_map>
#define num(x) (x>='0' && x<='9')
typedef unsigned long long ull;
typedef long long ll;
using namespace std::tr1;
using namespace std;
int read(){
    int p=0, q=1;
    char ch=getchar();
    while (!num(ch))
        (ch=='-'?q=-1:0),
        ch=getchar();
    while (num(ch)) p=p*10+ch-'0', ch=getchar();
    return p*q;
}
#define N 55
#define M 25
#define ND 60000000
#define EDGE 90000000
int n, l[N], c[N], pre[N];
char s[N][M], res[N][M];
int nex[EDGE], nu[EDGE];
ll dist[ND], va[EDGE];
bool flag[ND];
int st, cnt;
ll INF=1ll*1999999999*1999999999;
struct node{
	int n;
	ll dist;
	node (int n, ll dist): n(n), dist(dist){}
	bool operator <(const node &o) const {return this->dist<o.dist;}
	bool operator >(const node &o) const {return this->dist>o.dist;} 
};
priority_queue<node, vector<node>, greater<node> > q;
void add(int u, int v, int w){
	nex[++cnt]=nex[u];nex[u]=cnt;nu[cnt]=v;va[cnt]=w;
}
void dijkstra(){
	for (int i=1;i<=st;i++) dist[i]=INF, flag[i]=0;
	dist[st]=0;
	q.push(node(st,0));
	while (!q.empty()){
		node curNode=q.top();
		q.pop();
		int u=curNode.n;
		flag[u]=1;
		for (int j=nex[u];j;j=nex[j]){
			int v=nu[j];
			if (!flag[v] && dist[u]+va[j]<dist[v])
				dist[v]=dist[u]+va[j],
				q.push(node(v,dist[v]));
		}
		while (!q.empty() && flag[q.top().n]) q.pop();
	}
}
int main(){
	n=read();
	for (int i=1;i<=n;i++){
		scanf("%s", &s[i]);
		c[i]=read();
		l[i]=strlen(s[i]);
		pre[i]=pre[i-1]+l[i];
		for (int j=0;j<l[i];j++) res[i][j]=s[i][l[i]-1-j];
	}
	#define get(i,j,x,y) (pre[i-1]+j+1)*1010+pre[x-1]+y+1
	ll ans=INF;
	for (int beg=1;beg<=n;beg++){
		st=1005*1010, cnt=st;
		for (int i=1;i<=cnt;i++) nex[i]=0;
		for (int x=beg;x<=beg;x++)
			for (int y=1;y<=n;y++)
				if (s[x][0]==res[y][0])
					add(st,get(x,0,y,0),c[x]+c[y]);
		for (int i=1;i<=n;i++)
			for (int j=0;j<l[i];j++)
				for (int k=1;k<=n;k++)
					for (int p=0;p<l[k];p++){
						int u=get(i,j,k,p);
						if (j<l[i]-1 && p<l[k]-1){
							if (s[i][j+1]==res[k][p+1])
								add(u,get(i,j+1,k,p+1),0);
						}
						else if (j<l[i]-1){
							for (int x=1;x<=n;x++)
								if (s[i][j+1]==res[x][0]) 
									add(u,get(i,j+1,x,0),c[x]);
						}
						else if (p<l[k]-1){
							for (int x=1;x<=n;x++)
								if (s[x][0]==res[k][p+1]) 
									add(u,get(x,0,k,p+1),c[x]);
						}
						else{
							//do nothing
							for (int x=1;x<=n;x++)
								for (int y=1;y<=n;y++)
									if (s[x][0]==res[y][0])
										add(u,get(x,0,y,0),c[x]+c[y]);
						}
					}
		dijkstra();
		ll res=INF;
		for (int x=1;x<=n;x++)
			for (int y=beg;y<=beg;y++)
				res=min(res,dist[get(x,l[x]-1,y,l[y]-1)]);
		ans=min(ans,res);
	}
	if (ans==INF) ans=-2;
	cout<<ans/2<<endl;
    return 0;
}

Measured memory_bytes: 41792
#include <stdio.h>
#include <stdlib.h>
#define max(a, b) ((a)>(b) ? (a) : (b))

int main(){
  int n, m;  scanf("%d %d", &n, &m);
  int to[100002] = {0};
  int **graph;
  graph = (int **)malloc(sizeof(int*)*(n+5));
  for(int i=0; i<=n+1; i++)  graph[i] = (int *)malloc(sizeof(int)*(n+5));
  for(int i=0; i<m; i++){
    int f, t;
    scanf("%d %d", &f, &t);
    graph[f][++graph[f][0]] = t;
    to[t]++;
  }
  int s[100002] = {0};
  int topo[100002] = {0};
  for(int i=1; i<=n; i++)
    if(to[i] == 0)
      s[++s[0]] = i;

  while(s[0] > 0){
    int tmp = s[s[0]--];
    for(int i=1; i<=graph[tmp][0]; i++){
      if(--to[graph[tmp][i]] == 0)
	s[++s[0]] = graph[tmp][i];
    }
    topo[++topo[0]] = tmp;
  }

  int dp[100003] = {0};
  int ans = 0;
  for(int i=1; i<=topo[0]; i++){
    for(int j=1; j<=graph[topo[i]][0]; j++){
      dp[graph[topo[i]][j]] = max(dp[graph[topo[i]][j]], dp[topo[i]] + 1);
      ans = max(ans, dp[graph[topo[i]][j]]);
    }
  }

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


Measured memory_bytes: 402560
#include <iostream>
#include <algorithm>
#include <numeric>
 
using namespace std;
 
int main(){
    int a[4], b[2];
    for(auto&& i : a){
        cin >> i;
    }
    for(auto&& j : b){
        cin >> j;
    }
    sort(rbegin(a), rend(a));
    sort(rbegin(b), rend(b));
    cout << accumulate(begin(a), begin(a) + 3, 0) + b[0] << "\n"; 
}


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

#define fastIO                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef long double ld;

int main()
{
    fastIO;
    string S, T;
    cin >> S >> T;
    int ans = INT_MAX;
    for (int i = 0; i <= S.length() - T.length(); i++)
    {
        int tmp = 0;
        for (int j = 0; j < T.length() ; j++)
        {
            tmp += ((S[i + j] == T[j])?0:1);
        }
        ans = min(ans, tmp);
    }
    cout << ans;
}

Measured memory_bytes: 3652
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<ctype.h>
int main()
{
    char a[1000];
    scanf("%s",&a);
    for(int i=0;i<strlen(a);i++){
        if((a[i]==a[i+1] && a[i]!=a[i+2])||(a[i]==a[i+2] && a[i]!=a[i+1])){
        printf("Yes");
        break;}
        else if(a[i]==a[i+1] && a[i]==a[i+2]){
            printf("No");
            break;}}
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int main()
{
    int n,cnt=0;
    ll x;
    cin>>n;
    int a[n+1]={0};
    ll v[n+1];
    for(int i=0; i<n; i++)
        cin>>v[i];
    for(int i=1; i<n; i++){
        if(v[i]<=v[i-1])
            a[cnt]++;
        else
            cnt++;
    }
    cnt++;
    int result = *max_element(a,a+cnt);
    cout<<result;
//    sort(a,a+cnt);
//    cout<<a[cnt-1];
//    int ans=0;
//    for(int i=0; i<n; i++){
//        if(v[i]>=v[i+1])cnt++;
//        else{
//            ans=max(ans,cnt);
//            cnt=0;
//        }
//    }
//    cout<<ans;
    return 0;
}


Measured memory_bytes: 1408
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000;
#define MAX_N 100000



int main()
{
	int X,Y;
	cin>>X>>Y;
	bool flag = false;
	for(int i = 0; i <= X; i++){
		int y = X - i;
		if( 2*i + 4*y == Y){
			flag = true;
			break;
		}
	}
	if(flag == true){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    char S;cin >> S;
    char tmp = (char)(S + 1);

    cout << tmp << endl;
}


Measured memory_bytes: 256
from itertools import product
import sys

sys.setrecursionlimit(10 ** 6)

def solve(H, W, C):
    def dfs(h, w):
        if h < 0 or h >= H or w < 0 or w >= W:
            return 0
        elif C[h][w] == 0:
            return 0
        else:
            C[h][w] = 0
            for dh, dw in product((1, 0, -1), repeat = 2):
                dfs(h+dh, w+dw)
            return 1
    
    cnt = 0

    for h in range(H):
        for w in range(W):
            cnt += dfs(h, w)

    print(cnt)

A = []
while True:
    W, H = [int(i) for i in input().split()]
    if W == 0 and H == 0:
        break
    else:
        C = [[int(i) for i in input().split()] for j in range(H)]
        A.append((H, W, C))

for a in A:
    solve(*a)


Measured memory_bytes: 9212
#include <vector>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <sstream>
#include <map>
#include <unordered_map>
#include <ctime>
#include <cassert>
#include <cstring>
#include <sys/time.h>
#include <stdlib.h>
using namespace std;

int main(int argc, char *argv[]){
  int n;
  cin >> n;
  string s;
  cin >> s;
  if(n%2==1){
    cout << "No" << endl;
  }else if(s.compare(n/2, n/2, s, 0, n/2)==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


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

ifstream fin("date.in");

int main() {
    char c;

    cin >> c;

    if (c <= 'Z' && c >= 'A')
        cout << 'A';
    else
        cout << 'a';


    return 0;
}


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


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

#define PB emplace_back

using namespace std;

const int N = 17;

long long int a[N][N], dp[1<<N];

int main () {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++ ) {
        for(int j = 0 ; j < n ; j++ ) {
            cin >> a[i][j];
        }
    }
    long long int ans = -1e18;
    for(int i = 1 ; i < (1 << n ) ; i++ ) {
        long long int mas = 0;
        vector<int>v;
        for(int j = 0 ; j < n ; j++ ) {
            if((1<<j)&i) v.PB(j);
        }
        for(int u: v) {
            for(int uu: v) {
                if(u <= uu)continue;
                mas += a[u][uu];
            }
        }
        for(int j = i ; j > 0 ; j = (j - 1) & i) {
            mas = max(mas, dp[j] + dp[i^j]);
        }
        if(ans < mas)ans = mas;
        dp[i] = mas;
    }
    cout << ans;
}


Measured memory_bytes: 4168
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A[3];
  cin >> A[0] >> A[1] >> A[2]; 
  sort(A,A+3);
  if(A[0] == A[1] && A[1] == A[2]){
  	cout << 1 << endl;
  }else if(A[0] == A[1] || A[1] == A[2]){
  	cout << 2 << endl;
  }else{
  	cout << 3 << endl;
  }
}

Measured memory_bytes: 256
import itertools
N=int(input())
P=list(map(str,input().split()))
Q=list(map(str,input().split()))
S=""
for i in range(1,N+1):
    S+=str(i)
pidx=-1
qidx=-1
for i,m in enumerate(itertools.permutations(S,N)):
    if P==list(m):
        pidx=i
    if Q==list(m):
        qidx=i
A=pidx-qidx if pidx-qidx > 0 else -(pidx-qidx )
print(A)


Measured memory_bytes: 41584
import java.util.*;

class Main {
        public static void main(String args[]) {
                try (Scanner sc = new Scanner(System.in)){
                        int H = sc.nextInt(), W = sc.nextInt();
                        for (int i = 0; i < H; i++) {
                                String S = sc.next();
                                System.out.println(S);
                                System.out.println(S);
                        }
                }
        }
}

Measured memory_bytes: 11464
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
#define N 500
#define C 30
int d[C+1][C+1];
int recolor_cost[3][C+1];
vector<int> klass[3];
int color(const vector<int>& c) {
    int ans = 0;
    for(int k = 0; k < 3; k++) {
        ans += recolor_cost[k][c[k]];
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, c;
    cin >> n >> c;
    for(int i = 1; i <= c; i++) {
        for(int j = 1; j <= c; j++) {
            cin >> d[i][j];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int cij;
            cin >> cij;
            klass[(i + j) % 3].push_back(cij);
        }
    }
    for(int k = 0; k < 3; k++) {
        for(int color = 1; color <= c; color++) {
            recolor_cost[k][color] = 0;
            for(int val : klass[k]) {
                recolor_cost[k][color] += d[val][color];
            }
        }
    }
    int cost = -1;
    for(int c0 = 1; c0 <= c; c0++) {
        for(int c1 = 1; c1 <= c; c1++) {
            for(int c2 = 1; c2 <= c; c2++) {
                if(c0 != c1 and c1 != c2 and c2 != c0) {
                    cost = cost == -1 ? color({c0, c1, c2}) : min(cost, color({c0, c1, c2}));
                }
            }
        }
    }
    cout << cost << endl;
    return 0;
}


Measured memory_bytes: 1520
package main

import (
	"fmt"
)

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func even(a int) bool {
	return a%2 == 0
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var a, b int
	fmt.Scanln(&a, &b)
	d := abs(a - b)
	if even(d) {
		fmt.Println(max(a, b) - d/2)
	} else {
		fmt.Println("IMPOSSIBLE")
	}
}


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

#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1e9)

int main(){
  int n,a[100010];
  cin >> n;
  rep(i,n){
    cin >> a[i+1];
  }
  a[0]=a[n+1]=0;
  int s=0;
  rep(i,n+1){
    s+=abs(a[i]-a[i+1]);
  }
  for(int i=1; i<=n; i++){
    cout << s+abs(a[i-1]-a[i+1])-abs(a[i-1]-a[i])-abs(a[i]-a[i+1]) << endl;
  }
}
  

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

using lli = long long;
using pii = pair<int, int>;
using pll = pair<lli, lli>;
using Double = long double;
template<typename T>
using Vector = vector<vector<T>>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

#define IOS() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define X first
#define Y second
#define Push push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

void solve() {
	string s;
	cin >> s;
	int sz = s.size();

	lli ans = 0;
	for (int i = 0; i < (1<<sz); i += 2) {
		lli now = 0;
		for (int j = 0; j < sz; ++j) {
			if ((i & (1 << j)) == 0) {
				now = 10 * now + s[j] - '0';
			}
			else {
				ans += now;
				now = s[j] - '0';
			}
		}
		ans += now;
	}

	cout << ans << "\n";
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n, q;
  cin >> n >> q;
  for(int i = 0; i < q; i++){
    long long v, w;
    cin >> v >> w;
    if(n == 1) cout << min(v, w) << endl;
    else{
      while(v != w){
        if(v > w) v = (v+n-2)/n;
        else w = (w+n-2)/n;
      }
      cout << v << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 1280
def bubble_sort(arr):
    n = len(arr)
    flag = True
    i = 0
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if int(arr[j][1]) < int(arr[j - 1][1]):
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
                flag = True
        i += 1
    return arr


def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        minj = i
        for j in range(i, n):
            if int(arr[j][1]) < int(arr[minj][1]):
                minj = j
        arr[i], arr[minj] = arr[minj], arr[i]
    return arr


def is_stable(arr, arr_sorted):
    print("Stable" if arr_sorted == sorted(arr, key=lambda x:int(x[1])) else "Not stable")


n = int(input())
arr = input().split()
arr_b = bubble_sort(arr[:])
arr_s = selection_sort(arr[:])

print(*arr_b)
is_stable(arr, arr_b)
print(*arr_s)
is_stable(arr, arr_s)



Measured memory_bytes: 5616
let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let read_ints () = read_line () |> split_on_char ' ' |>  List.map int_of_string

let dfs vs n =
  let d = Array.make n (-1) in
  let rec doit i j =
    d.(i) <- j;
    List.iter (fun v -> if d.(v) = (-1) then doit v j) vs.(i) in
  Array.iteri (fun i e -> if e = (-1) then doit i i) d;
  d

let solve n m =
  let g = Array.make n [] in
  for _ = 0 to m - 1 do
    match read_ints () with
    | [s; t] ->
      g.(s) <- t :: g.(s);
      g.(t) <- s :: g.(t);
    | _ -> assert false
  done;
  let v = dfs g n in
  let q = read_int () in
  for _ = 0 to q - 1 do
    match read_ints () with
    | [s; t] -> print_endline (if v.(s) = v.(t) then "yes" else "no")
    | _ -> assert false
  done

let () =
  match read_ints () with
  | [n;m] -> solve n m
  | _ -> assert false

Measured memory_bytes: 19088
#include<iostream>
#include<algorithm>
using namespace std;
int arr[1000000]={0};
bool isPrime(int n){ 
    if(n<2)
        return false;
    for(int i=2; i*i<=n; i++){
        if(n%i==0)
            return false;
    }   
    return true;
}
void arra(int n, int m){ 
    int c=0;
    if(n>m){
        int memo=m;
        m=n;
        n=memo;
    }   
    for(int i=n+1; i<=m; i++){
        if(isPrime(i)){
            c++;
            //arr[i]=arr[n]+c;
        }   
        arr[i]=arr[n]+c;
    }   
    //arr[m]=arr[n]+c;
}
int main(){
    int n, m=0;
    while(cin>>n){
        if(arr[n]==0){
            arra(n, m); 
        }   
        cout<<arr[n]<<endl;
        m=max(n, m); 
    }   
    return 0;
}



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

using namespace std;

int main() {
	int n, t, s; cin >> n >> t >> s;
	vector<int>fun(n); vector<int>time(n);
	for (int i = 0; i < n; i++) { cin >> fun[i] >> time[i]; }

	vector<int>frontmax(n + 1); vector<int>frontdp(s + 1);
	for (int i = 1; i <= s; i++) {
		frontdp[i] = -1145141919;
	}
	for (int i = 0; i < n; i++) {
		frontmax[i + 1] = frontmax[i];
		for (int j = s; j >= time[i]; j--) {
			frontdp[j] = max(frontdp[j], frontdp[j - time[i]] + fun[i]);
			frontmax[i + 1] = max(frontmax[i + 1], frontdp[j]);
		}
	}

	vector<int>backmax(n + 1); vector<int>backdp(t - s + 1);
	for (int i = 1; i <= t - s; i++) {
		backdp[i] = -1145141919;
	}
	for (int i = n - 1; i >= 0; i--) {
		backmax[i] = backmax[i + 1];
		for (int j = t - s; j >= time[i]; j--) {
			backdp[j] = max(backdp[j], backdp[j - time[i]] + fun[i]);
			backmax[i] = max(backmax[i], backdp[j]);
		}
	}

	int ret = 0;
	for (int i = 0; i <= n; i++) {
		ret = max(ret, frontmax[i] + backmax[i]);
	}
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 3184
import java.util.Scanner;

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

		int W = Integer.parseInt(sc.next());
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());

		if (a+W < b){
			System.out.println(b-(a+W));
		}else if (b+W < a){
			System.out.println(a-(b+W));
		}else {
			System.out.println(0);
		}
	}
}

Measured memory_bytes: 21844
//8 Queens Problem

#include<stdio.h>
#define N 8
#define FREE -1
#define NFREE 1
#define FALSE 0
#define TRUE 1

int l[N],b[N],dpos[2*N-1],dneg[2*N-1],arr[N][N];

void initialize()
{
  int i;
 
  for(i = 0; i < N; i++)
    {
      l[i] = FREE;
      b[i] = FREE;
    }
  for(i = 0; i < 2 * N - 1; i++)
    {
      dpos[i] = FREE;
      dneg[i] = FREE;
    }
}

void printBoard()
{
  int i,j;

  for(i = 0; i < N; i++)
    {
      for(j = 0; j < N; j++)
	{
	  if(arr[i][j] == TRUE)
	    {
	      if(l[i] != j) return;
	    }
	}
    }

  for(i = 0; i < N; i++)
    {
      for(j = 0; j < N; j++)
	{
	  if(l[i] == j) printf("Q");
	  else printf(".");
	}
      printf("\n");
    }
}

void putQ(int i)
{
  int j;
  
  if(i == N)
    {
      printBoard();
      return;
    }
  
  for(j = 0; j < N; j++)
    {
      if(b[j] == NFREE ||
	 dpos[i + j] == NFREE ||
	 dneg[i - j + N - 1] == NFREE) continue;

      l[i] = j;
      b[j] = dpos[i+j] = dneg[i-j+N-1] = NFREE;
      putQ(i+1);

      l[i] = b[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;

    }
  
}

int main()
{
  int n,i,j,l,b;
 

  initialize();
  
  //initialize array
  for(i = 0;i < N; i++)
    {
      for(j = 0; j < N; j++)
	{
	  arr[i][j] = FALSE;
	}
    }
  

  //input data
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    {
      scanf("%d %d",&l,&b);
      arr[l][b] = TRUE;  
    }
  
  putQ(0);
 
  return 0;
}



Measured memory_bytes: 2148
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var xn = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var (varX, varN) = (xn[0], xn[1]);
        var seqP = varN == 0 ? Array.Empty<int>() : Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

        var set = new HashSet<int>(seqP);
        int lesser = varX;
        int greater = varX;
        var z = int.MaxValue;
        while (z == int.MaxValue)
        {
            if (!set.Contains(lesser))
            {
                z = lesser;
                break;
            }

            if (!set.Contains(greater))
            {
                z = greater;
                break;
            }

            --lesser;
            ++greater;
        }

        Console.WriteLine(z);
    }
}


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

const int S=(1<<20)+5;
char buf[S],*H,*T;
inline char Get()
{
    if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
    if(H==T) return -1;return *H++;
}
inline int read()
{
    int x=0;char c=Get();
    while(!isdigit(c)) c=Get();
    while(isdigit(c)) x=x*10+c-'0',c=Get();
    return x;
}

const int N=100010;
struct Edge{int to,next;} e[N<<1];
int h[N],n,K,sum=0;
int fa[N],deg[N],dep[N];
int c[N],id[N];
bool done[N];

void add_edge(int u,int v)
{
    e[++sum].to=v;
    e[sum].next=h[u];
    h[u]=sum;
}

void dfs(int u)
{
    if(done[u]) return;
    for(int t=h[u];t;t=e[t].next)
    {
        dep[e[t].to]=dep[u]+1;
        dfs(e[t].to);
    }
}

int main()
{
    n=read();K=read();
    for(int i=1;i<=n;i++) fa[i]=read();
    for(int i=2;i<=n;i++)
    {
        add_edge(fa[i],i);//反向建图
        deg[fa[i]]++;
    }
    dfs(1);
    for(int i=1;i<=n;i++) c[dep[i]]++;
    for(int i=1;i<=n;i++) c[i]+=c[i-1];
    for(int i=1;i<=n;i++) id[c[dep[i]]--]=i;//三行桶排
    reverse(id+1,id+1+n);//上面排序是按深度从小到大的，现在要反转过来
    int ans=(fa[1]!=1);//如果fa[1]一开始不等于1，就要修改一次，让它等于1
    for(int i=1;i<=n;i++)
    {
        int x=id[i];
        if(deg[x]==0&&dep[x]>K)
        {
            int u=x;
            for(int j=1;j<K;j++) u=fa[u];
            ans++;dep[u]=1;dfs(u);
            deg[fa[u]]--;
            done[u]=1;//特别注意必须要有done标记
        }
    }
    printf("%d\n",ans);
    return 0;
}

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

int main() {
  int A, B, X;
  cin >> A >> B >> X;
  
  if((A+B)>=X && A<=X){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }

return 0;  
}

Measured memory_bytes: 256
n = int(input())

f=2
cf =1
flag =0
while flag == 0:
	if n % f ==0:
		if f*f <= n:
			cf = f
	if f*f > n:
		flag =1
	else:
		f = f+1
#print(cf)
ans = (cf-1)+(n//cf-1)
print(ans)

Measured memory_bytes: 3316
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=sc.nextInt();
        int d=sc.nextInt();
        
        if((a+b)<(c+d)) {
            System.out.println("Right");
        } else if((a+b) > (c+d)) {
            System.out.println("Left");
        } else {
            System.out.println("Balanced");
        }
    }
}

Measured memory_bytes: 22608
#include <iostream>
#include <vector>

using namespace std;

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int n, min_val, max_val;
    long long sum = 0;
    vector<int> arr;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        arr.emplace_back(a);
        sum += a;
    }

    for (int i = 0; i < n - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            swap(arr[i], arr[i + 1]);
        }
    }
    max_val = arr[arr.size() - 1];

    for (int i = n - 1; i != 0; --i) {
        if (arr[i] < arr[i - 1]) {
            swap(arr[i], arr[i - 1]);
        }
    }
    min_val = arr[0];

    cout << min_val << ' ' << max_val << ' ' << sum << endl;

    return 0;
}


Measured memory_bytes: 3252
def main():
    n, m = map(int, input().split())
    students = [tuple(map(int, input().split())) for i in range(n)]
    check_points = [tuple(map(int, input().split())) for i in range(m)]

    for st in students:
        min_pt = check_points[0]
        for pt in check_points:
            if abs(pt[0] - st[0]) + abs(pt[1] - st[1]) < \
               abs(min_pt[0] - st[0]) + abs(min_pt[1] - st[1]):
                min_pt = pt
        print(check_points.index(min_pt) + 1)


if __name__ == "__main__":

    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	vector<int>v;
	int now=1,cnt=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]==(char)('0'+now)) 
			cnt++;
		else
		{
			v.push_back(cnt);
			now=1-now;
			cnt=1;
		}
	}
	if(cnt!=0) 
		v.push_back(cnt);
	if(v.size()%2==0) 
		v.push_back(0);
	int t=2*k+1,ans=0,left=0,right=0,tmp=0;
	for(int i=0;i<v.size();i+=2)
	{
		int nleft=i;
		int nright=min(i+t,(int)v.size());  
		while(nleft>left)
		{
		    tmp-=v[left];
		    left++;
		}  
		while(nright>right)
		{
		    tmp+=v[right];
		    right++;
		}  
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1020