akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;
using System.Runtime.InteropServices.ComTypes;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var (N, M) = Slice2<long>();
            var AB = new (long a, long b)[N];
            for (var i = 0; i < N; ++i)
                AB[i] = Slice2<long>();
            Array.Sort(AB);
            var sum = 0L;
            var num = 0L;
            foreach (var ab in AB)
            {
                var n = Min(M - num, ab.b);
                sum += n * ab.a;
                num += n;
                if (num == M)
                    break;
            }
            WriteLine(sum);
        }

        static long Mod = 998244353;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
        static public (T a, T b, T c, T d) Slice4<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)),
            (T)Convert.ChangeType(t[3], typeof(T)));
        }
    }
}

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

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

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

    vector<vector<P>> A;
    rep(i, N) {
        int a;
        cin >> a;
        vector<P> v;
        rep(j, a) {
            int x, y;
            cin >> x >> y;
            x--;
            v.push_back(P(x, y));
        }
        A.push_back(v);
    }

    int ans = 0;
    for (int i = 0; i < (1 << N); ++i) {
        bool ok = true;
        rep(j, N) {
            if ((i >> j) & 1) {
                for (auto p : A[j]) {
                    if (p.second != (i >> p.first & 1)) ok = false;
                }
            }
        }
        if (ok) {
            int res = 0;
            int X = i;
            while (X > 0) {
                res += X % 2;
                X /= 2;
            }
            ans = max(ans, res);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
long long mod=(long long)1e09+7;
int inf=1<<30;

int in(void){
    int i;scanf("%d",&i);
    return i;
}
long long llin(void){
    long long i;scanf("%lld",&i);
    return i;
}
double din(void){
    double i;scanf("%lf",&i);
    return i;
}
void chin(char s[]){
    scanf("%s",s);
}
void print(int a){
    printf("%d\n",a);
}
void llprint(long long a){
    printf("%lld\n",a);
}
void dprint(double a){
    printf("%.10f\n",a);
}
void print2(int a,int b){
    printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a<b?a:b;
}
int cmp(const void *a,const void *b){
    return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
    return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
    return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
    return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
    int t=*a;
    *a=*b;
    *b=t;
}
long long gcd(long long x,long long y){
    return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
    return x/gcd(x,y)*y;
}

// write codes below this
// when you use 'sort',
// make sure TYPE macro is correct
int main(void){
    int n=in(),s=0,t=n;
    while(t){
        s+=t%10;
        t/=10;
    }
    puts(n%s?"No":"Yes");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}
const int INF = 1e18;

signed main() {
    vi x(5);
    int res = 0;
    rep(i, 5) {
        cin >> x[i];
        if(x[i]!=i+1) res = i+1;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 3548
#include<stdio.h>
#include<stdlib.h>
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
Node root;
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while( x!=NIL ){
	  y=x;
	  if( z->key < x->key ) x=x->left;
	  else x=x->right;
  }
  z->parent=y;
  if( y==NIL ) root=z;
  else if( z->key < y->key ) y->left=z;
  else y->right=z;
}
void inorder(Node u){
	if( u->left!=NIL ) inorder(u->left);
	printf(" %d", u->key);
	if( u->right!=NIL ) inorder(u->right);
}
void preorder(Node u){
	printf(" %d", u->key);
	if( u->left!=NIL ) preorder(u->left);
	if( u->right!=NIL ) preorder(u->right);
}
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }
    else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}

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

vector<int> eratosthenes(int n) {
  vector<int> res, p(n + 1, 1);
  p[0] = p[1] = 0;
  for (int i = 2; i * i <= n; ++i) {
    if (p[i]) {
      for (int j = 2 * i; j <= n; j += i) {
        p[j] = 0;
      }
    }
  }
  for (int i = 0; i <= n; ++i) {
    if (p[i]) res.push_back(i);
  }
  return res;
}

int main() {
  int n;
  while (cin >> n) cout << eratosthenes(n).size() << endl;
}

Measured memory_bytes: 7888
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("");
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	int f; cin >> f;
	Cout((f - 30) / 2);
}


Measured memory_bytes: 3072
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <locale>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
#include <map>


using namespace std;

int main()
{
	for(;;)
	{
		int n,m;
		cin >> n >> m;
		if(!n && !m) break;

		multimap<int,int> road;
		for(int i = 0; i < n; i++)
		{
			int d,p;
			cin >> d >> p;
			road.insert(make_pair(p,d));
		}

		multimap<int,int>::iterator itr = road.end();
		itr--;
		for(;;itr--)
		{
			if(m >= itr->second)
			{
				m -= itr->second;
				itr->second = 0;
			}
			else
			{
				itr->second -= m;
				m = 0;
				break;
			}

			if(itr == road.begin()) break;
		}

		int sum = 0;
		for(itr = road.begin(); itr != road.end(); itr++)
		{
			sum += itr->first * itr->second;
		}

		cout << sum << endl;
	}

	return 0;
}


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

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	ll n{0};
	cin>>n;

	if(n%1000==0){
		cout<<0<<endl;
	}
	else{
		ll used=n/1000+1;
		used=used*1000;
		ll change=used-n;
		cout<<change<<endl;
	}
	return 0;
}



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

    int[] taro, hanako;
    boolean[] T, H; // そのカードが既に場に出されたか
    int t, h, n;

    void run(){
	while(sc.hasNext()){
	    n = sc.nextInt();
	    if(n!=0){
		taro = new int[n];
		hanako = new int[n];
		T = new boolean[n];
		H = new boolean[n];
		Arrays.fill(T, true);
		Arrays.fill(H, true);
		
		for(int i=0; i<n; i++)
		    taro[i] = sc.nextInt();
		Arrays.sort(taro);
		int a = 0;
		int b = 0;
		for(int i=1; i<=2*n; i++)
		    if(a<n && taro[a]==i) a++;
		    else hanako[b++] = i;
		//show();
		solve();
	    }
	}
    }

    void solve(){
	int place = 0;
	int turn = 0; // even=taro

	while(count(T)>0 && count(H)>0){
	    t = 0; h = 0;
	    if(turn%2==0){
		while(t<taro.length && (taro[t]<place || !T[t])) t++;
		if(t==taro.length)
		    place = 0;
		else {
		    place = taro[t];
		    T[t] = false;
		}
	    }
	    else{
		while(h<hanako.length && (hanako[h]<place || !H[h])) h++;
		if(h==hanako.length)
		    place = 0;
		else {
		    place = hanako[h];
		    H[h] = false;
		}
	    }
	    turn++;
	}
	
	System.out.println(count(H));
	System.out.println(count(T));
    }
    
    void show(){
	System.out.print("taro :");
	for(int i=0; i<n; i++)
	    System.out.print(" "+taro[i]);
	System.out.println();
	System.out.print("hana :");
	for(int i=0; i<n; i++)
	    System.out.print(" "+hanako[i]);
	System.out.println();
    }

    int count(boolean[] a){
	int sum = 0;
	for(int i=0; i<a.length; i++)
	    if(a[i]) sum++;
	return sum;
    }
}

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

int main(){
    int A[3], i, j, v;
    
    for(i = 0; i < 3; i ++) cin >> A[i];
    
    for(i = 1; i < 3; i ++){
        
        v = A[i];
        j = i - 1;
        
        while(j >= 0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        }
        
        A[j+1] = v;
        
    }
    
    cout << A[0] << " " << A[1] << " " << A[2] << endl;
    
    return 0;
}


Measured memory_bytes: 3088
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

int n, c[30], s[400][30];
int d[30];
int ans[400];

int score() {
	int res = 0;
	int dd[30];
	fill(dd, dd + 30, 0);
	for (int i = 1; i <= n; i++) {
		res += s[i][ans[i]];
		dd[ans[i]] = i;
		for (int j = 1; j <= 26; j++)res -= c[j] * (i - dd[j]);
	}
	return res;
}

signed main() {
	std::random_device rnd;
	cin >> n;
	for (int i = 1; i <= 26; i++)cin >> c[i];
	for (int i = 1; i <= n; i++)for (int j = 1; j <= 26; j++)cin >> s[i][j];
	for (int i = 1; i <= n; i++) {
		int ma = -1000000000, p = 0;
		for (int j = 1; j <= 26; j++) {
			int cnt = 0;
			for (int k = 1; k <= 26; k++)if (j != k)cnt -= c[k] * (i - d[k]);
			cnt += s[i][j];
			if (ma < cnt) {
				ma = cnt;
				p = j;
			}
		}
		ans[i] = p;
		d[p] = i;
	}
	int q = 140000;
	while (q) {
		int x = rnd() % 365 + 1, y = rnd() % 26 + 1;
		int g = ans[x];
		int f = score();
		ans[x] = y;
		if (score() < f) ans[x] = g;
		q--;
	}
	for (int i = 1; i <= n; i++)cout << ans[i] << endl;
	//cout << score() << endl;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M;
  cin>>N;
  vector<string> s(N); 
  for(int i=0;i<N;i++){
      cin>>s.at(i);
  }
//青要素
   cin>>M;
  vector<string> t(M);
  for(int i=0;i<M;i++){
      cin>>t.at(i);
  }
//赤要素
  int ans = 0;//最低0
  for(int i=0;i<N;i++){
   int count=0;//青カード総当たり
      for(int j=0;j<N;j++){
          if(s.at(i)==s.at(j)){//i番目の青とj番目の青が一致する場合
              count++;
          }
      }
        for(int k=0;k<M;k++){
          if(s.at(i)==t.at(k)){//i番目の青とk番目の赤が一致する場合
              count--;
          }
      }
   ans = max(ans,count);//ansを最大値に更新していく
  }
  
  cout<<ans<<endl;

}


Measured memory_bytes: 256
from sys import exit

s=input()
t=input()
alp=[0]*26
for i in range(len(s)):
	if alp[ord(s[i])-97]==0:
		alp[ord(s[i])-97]=t[i]
	else:
		if alp[ord(s[i])-97]!=t[i]:
			print("No")
			exit()
			
alp=[0]*26
for i in range(len(t)):
	if alp[ord(t[i])-97]==0:
		alp[ord(t[i])-97]=s[i]
	else:
		if alp[ord(t[i])-97]!=s[i]:
			print("No")
			exit()

print("Yes")

Measured memory_bytes: 3632
n,m,c=map(int,input().split())
co=0
b=list(map(int,input().split()))
for i in range(n):
  a=list(map(int,input().split()))
  s=0
  #co=0
  for i in range(len(a)):
    s+=(a[i]*b[i])
  res=(s+c)
  if res>0:
    co+=1
print(co)

Measured memory_bytes: 9136
import sys


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


N, Y = il()
N = N + 1
for x in range(N):
    for y in range(N - x):
        z = N - x - y - 1
        if (Y - (10000 * x + 5000 * y + 1000 * z)) == 0:
            print(x, y, z)
            exit()
print("-1 -1 -1")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

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

vector<bool> sieve(int n) {
  vector<bool> vec(n+1, true);
  vec[0] = false;
  vec[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if (is_prime(i)) {
      int x = i * 2;
      while(x <= n) {
        vec[x] = false;
        x += i;
      }
    }
  }
  return vec;
}

int main()
{
  int n;
  cin >> n;
  map<int, int> mp;
  vector<bool> ps = sieve(n);
  ll r = 1e9+7;
  for (int i = 2; i <= n; i++) {
    int x = i;
    rep(j, (int)ps.size()) {
      if (ps[j]) {
        while(x % j == 0) {
          x /= j;
          mp[j]++;
        }
      }
    }
  }
  ll ans = 1;
  for (auto m = mp.begin(); m != mp.end(); m++) {
    ans *= (m->second + 1);
    ans %= r;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	FastScanner sc;

	void run() {
		sc = new FastScanner();
		int N = sc.nextInt();
		int K = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();

		int sum = 0;
		for (int i = 0; i < N; i++) {
			if (i + 1 > K) {
				sum += Y;
			} else {
				sum += X;
			}
		}
		
		System.out.println(sum);
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 7892
n = int(input())
dp = [[0]*3 for _ in range(n)]
a, b, c = map(int, input().split())
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c
for i in range(n-1):
    a, b, c = map(int, input().split())
    dp[i+1][0] = max(dp[i][1]+a, dp[i][2]+a)
    dp[i+1][1] = max(dp[i][0]+b, dp[i][2]+b)
    dp[i+1][2] = max(dp[i][0]+c, dp[i][1]+c)


print(max(dp[n-1]))


Measured memory_bytes: 82404
from collections import deque
n = int(input())
a = [list(map(int, input().split())) + [0] for i in range(n)]
for i in range(n):
    for j in range(n):
        a[i][j] -= 1
l = [0] * n
d = [0] * n
Q = deque(range(n))
while Q:
    p = Q.popleft()
    q = a[p][l[p]]
    if a[q][l[q]] == p:
        m = max(d[p], d[q]) + 1
        d[p] = m
        d[q] = m
        l[p] += 1
        l[q] += 1
        Q.append(p)
        Q.append(q)
for i in l:
    if i != n - 1:
        exit(print(-1))
print(max(d))

Measured memory_bytes: 41024
#include <bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],c[100005],dp[100005][3];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i]>>b[i]>>c[i];
	for(int i=1;i<=n;i++){
		dp[i][1]=max(dp[i-1][2],dp[i-1][3])+a[i];
		dp[i][2]=max(dp[i-1][1],dp[i-1][3])+b[i];
		dp[i][3]=max(dp[i-1][2],dp[i-1][1])+c[i];
	}
	cout<<max(dp[n][1],max(dp[n][2],dp[n][3]))<<endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;

int main(){
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll ans=0;
    if(k<=a+b){
        ans=min(a,k);
    }
    if(k>a+b){
        ans=a-k+(a+b);
    }
    cout<<ans<<endl;
}

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

int main(void){
    int n;
    cin >> n;
    vector<tuple<string, int, int>> a;
    for(int i = 1; i <= n; i++){
    string s;
    int p;
    cin >> s >> p;
    p = -p;
      
    tuple<string, int, int> tup = make_tuple(s, p, i);
    a.emplace_back(tup);
    }
  
    sort(a.begin(), a.end());
    for(int i = 0; i < n; i++){
        cout << get<2>(a.at(i)) << endl;
    }
    return 0;
   
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#define LL long long
#define MOD 1000000007
using namespace std;

int n;
char arr[105];

int main(){
	scanf("%d%s",&n,arr);
	int num = 0, mn = 0;
	for(int i = 0; i < n; i++ ){
		if(arr[i]=='(') num++;
		else num--;
		mn = min(mn,num);
	}
	for(int i = 0; i < -mn; i++ ) printf("(");
	printf("%s",arr);
	num -= mn;
	for(int i = 0; i < num; i++ ) printf(")");
	printf("\n");
	return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=200005;
int t[N*4],tg[N*4],n,m;
struct info{int l,r;}a[N];
bool cmp(info a,info b){
	return a.l<b.l;
}
void build(int k,int l,int r){
	if (l==r){
		t[k]=r-m-1;return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	t[k]=max(t[k<<1],t[k<<1|1]);
}
void add(int k,int x){t[k]+=x;tg[k]+=x;}
void pushdown(int k){
	if (tg[k])
		add(k<<1,tg[k]),add(k<<1|1,tg[k]),tg[k]=0;
}
void modify(int k,int l,int r,int x){
	if (r<=x){add(k,1);return;}
	int mid=(l+r)>>1;pushdown(k);
	modify(k<<1,l,mid,x);
	if (x>mid) modify(k<<1|1,mid+1,r,x);
	t[k]=max(t[k<<1],t[k<<1|1]);
}
int query(int k,int l,int r,int x){
	if (x<=l) return t[k];
	pushdown(k);
	int mid=(l+r)>>1,y=query(k<<1|1,mid+1,r,x);
	if (x<=mid) y=max(y,query(k<<1,l,mid,x));
	t[k]=max(t[k<<1],t[k<<1|1]);
	return y;
}
int main(){
	scanf("%d%d\n",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d%d\n",&a[i].l,&a[i].r);
	std::sort(a+1,a+n+1,cmp);
	build(1,1,m+1);
	int ans=max(0,n-m);
	for (int i=0,j=1;i<=m && j<=n;i++){
		for (;j<=n && a[j].l==i;j++) modify(1,1,m+1,a[j].r);
		ans=max(ans,query(1,1,m+1,i+1)-i);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 6912
//                             In The Name Of Allah
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
#define ld long double
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 
 
const int N = 1e4 + 100, OO = 1e16 + 1000, T = 150, M = 1e9 + 7, P = 6151, SQ = 1000, lg = 44;
typedef pair <int, int> pii;
int a[N], n;

void go(int x, int y) {
	if(x > n) {
		for(int i = 1; i <= n; i++)
			cout << (char)(a[i] + 'a');
		cout << endl;
		return;
	}
	for(int i = 0; i < y; i++) {
		a[x] = i;
		go(x + 1, y);
	}
	a[x] = y;
	go(x + 1, y + 1);
}

int32_t main() {
	use_fast;	
	cin >> n;
	a[1] = 0;
	go(2, 1);
	return 0;
} 
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- ... 
*/

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

const int MOD = (int)1e9+7;

int main(){
	long long N;
	cin >> N;
	
	if(N%2==1){
		cout << 0 << endl;
		return 0;
	}
	
	long long ans=0;
	long long xx=10;
	long long yy=50;
	for(;xx<=N;){
		ans+=N/xx;
		xx*=10;
	}
	for(;N>0;N/=10){
		yy=50;
		for(;yy<=N;){
			ans+=N/yy;
			ans-=N/(yy*2);
			yy*=5;
		}
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926525
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  ll a,b;cin>>a>>b;
  P(max(a+b, max(a-b, a*b)));
  return 0;
}

Measured memory_bytes: 256
n = int(input())
ABs = [list(map(int, input().split())) for i in range(n)]
cnt = 0
for i in range(n):
    plus = 0 if (ABs[n-i-1][0] + cnt) % ABs[n-i-1][1] == 0 else ABs[n-i-1][1] - (ABs[n-i-1][0] + cnt) % ABs[n-i-1][1]
    cnt += plus
print(cnt)

Measured memory_bytes: 27380
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    ab=[0]*n
    for i in range(n):
        ab[i]=list(map(int,readline().split()))
    cd=[0]*n
    for i in range(n):
        cd[i]=list(map(int,readline().split()))

    ab.sort(key=lambda x:x[1])
    ab.sort(key=lambda x:x[0])
    cd.sort(key=lambda x:x[1],reverse=True)
    cd.sort(key=lambda x:x[0],reverse=True)

    res=0
    m=-1
    for i in range(n):
        c=cd[m][0]
        d=cd[m][1]
        now=-1
        key=-1
        for j in range(len(ab)):
            a=ab[j][0]
            b=ab[j][1]
            if a<c:
                if b<d and now<b:
                    now=b
                    key=j
            else:
                break
        if key>=0:
            res+=1
            ab.pop(key)
            cd.pop(m)
        else:
            m-=1
    print(res)

if __name__=="__main__":
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,sum=0,cnt=0,cnt2=0,a[2000],i,j;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
        cnt=0;
        for(j=0;j<i;j++){
            if(a[i]>=a[j])
                cnt++;
        }
        if(cnt==i)
            cnt2++;
    }
    cout<<cnt2;
    
}


Measured memory_bytes: 256
n, m = gets.split(' ').map(&:to_i)
h = gets.split(' ').map(&:to_i)

result = Array.new(n, true)

m.times do
        a, b = gets.split(' ').map(&:to_i)
        if h[a-1] == h[b-1]
                result[a-1] = false
                result[b-1] = false
        elsif h[a-1] > h[b-1]
                result[b-1] = false
        else
                result[a-1] = false
        end
end

puts result.count(true)

Measured memory_bytes: 22608
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
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);
    int k;
    string s;
    cin >> k;
    cin >> s;
    if(s.size()<=k) cout << s << endl;
    else {
        string s2 = s.substr(0,k) + "...";
        cout << s2 << endl;
    }
}


Measured memory_bytes: 3628
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

inline char get(void) {
	static char buf[100000], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, 100000, stdin);
		if(S == T) return EOF;
	}
	return *S++;
}
template<typename T>
inline void read(T &x) {
	static char c; x = 0; int sgn = 0;
	for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
	for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
	if (sgn) x = -x;
}

const int N = 101010;

int a[N << 2];
int n;
long long sum;

int main(void) {
	read(n);
	for (int i = 0; i < n * 3; i++) {
		read(a[i]); a[i] = -a[i];
	}
	sort(a, a + n * 3);
	for (int i = 0; i < n; i++) sum -= a[i << 1 | 1];
	cout << sum << endl;
}


Measured memory_bytes: 1536
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<math.h>
#include<bitset>
#include<random>
using namespace std;
using ll = long long;
using lll = __int128_t;
typedef pair<ll,ll> P;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
const ll longinf=1ll<<60;
const int inf=(1<<30)-1;
const ll mod=1e9+7;


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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
const ll INF = 1e18L + 1;

int main() {
  string x;
  cin >> x;
  rep(i, x.length()) cout << 'x';
  cout << "\n";
  return 0;
}

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

using namespace std;

int main()
{
	const int M = 3;
	vector<vector<int>> A(M, vector<int>(M));

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> A[i][j];
		}
	}

	int N;
	cin >> N;

	for (int k = 0; k < N; ++k) {
		int b;
		cin >> b;
		for (int i = 0; i < M; ++i) {
			for (int j = 0; j < M; ++j) {
				if (A[i][j] == b) {
					A[i][j] = 0;
				}
			}
		}
	}

	bool bingo = false;
	for (int i = 0; i < M; ++i) {
		bool ok = true;
		for (int j = 0; j < M; ++j) {
			if (A[i][j] != 0) {
				ok = false;
			}
		}
		if (ok) {
			bingo = true;
		}
	}

	for (int j = 0; j < M; ++j) {
		bool ok = true;
		for (int i = 0; i < M; ++i) {
			if (A[i][j] != 0) {
				ok = false;
			}
		}
		if (ok) {
			bingo = true;
		}
	}

	{
		bool ok = true;
		for (int i = 0; i < M; ++i) {
			if (A[i][i] != 0) {
				ok = false;
			}
		}
		if (ok) {
			bingo = true;
		}
	}
	{
		bool ok = true;
		for (int i = 0; i < M; ++i) {
			if (A[i][2 - i] != 0) {
				ok = false;
			}
		}
		if (ok) {
			bingo = true;
		}
	}

	if (bingo) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <math.h>
#include <vector>
#include <cstdio>
using namespace std;

int main ()
{
    string n;
    cin >> n;
    int counter = 0;
    for (int i = 0; i < 4; ++i) {
        if (n[i] == '2') {
            counter++;
        }
    }
    cout << counter;
}

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

typedef long long ll;
#define ar array
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define all(x) (x).begin(), (x).end()
#define en '\n'
#define FILL(x, v) memset(x, v, sizeof(x))
#define pb push_back
#define fast                     \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(NULL);
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...)       \
	F_ORC(__VA_ARGS__) \
	(__VA_ARGS__)

#define E_ACH2(x, a) for (auto &x : a)
#define E_ACH3(x, y, a) for (auto &[x, y] : a)
#define E_ACH4(x, y, z, a) for (auto &[x, y, z] : a)
#define E_ACHC(...) GET5(__VA_ARGS__, E_ACH4, E_ACH3, E_ACH2)
#define EACH(...)       \
	E_ACHC(__VA_ARGS__) \
	(__VA_ARGS__)

template <typename A, typename B>
inline void chmin(A &a, B b)
{
	if (a > b)
		a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b)
{
	if (a < b)
		a = b;
}

int main()
{
	fast;
	int n;
	cin >> n;
	set<int> st;
	FOR(n)
	{
		int t;
		cin >> t;
		if (st.find(t) != st.end())
		{
			cout << "NO";
			return 0;
		}
		st.insert(t);
	}
	cout << "YES";
}

Measured memory_bytes: 12992
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

from collections import defaultdict

d = defaultdict(lambda: 0)

for elem in a:
    d[elem] += 1
    
lst = list(d.items())
lst.sort(key=lambda x: -x[1])

i = k
res = 0

while True:
    try:
        now = lst[i]
    except IndexError:
        break
    res += now[1]
    i += 1

print(res)

Measured memory_bytes: 39348
//
//  main.cpp
//  Test
//
//  Created by Nag on 2017/08/18.
//  Copyright ?? 2017??´ Nag. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>

using namespace std;

int main(void) {
    string text, word;
    int cnt = 0;
    
    cin >> word;
    
    //word????°??????????
    for(int i=0; i<word.size(); i++) {
        word[i] = tolower(word[i]);
    }
    
    
    cin >> text;
    while ( text!="END_OF_TEXT" ) {
        //text????°??????????
        for(int i=0; i<text.size(); i++) {
            text[i] = tolower(text[i]);
        }
        
        if( text == word ) cnt++;
        
        //cout << text << " " << cnt << endl;
        
        cin >> text;
    }
    

    cout << cnt << endl;
    
    return 0;
    
}

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

int main()
{
	bool solution = false;
	int A,B,K;
	cin >> K >> A >> B ;
	int i;
	for(i=A;i<=B;i++)
	{
		if(i % K == 0) solution = true;
	}
	if(solution == true) cout << "OK";
	else cout << "NG";
	return 0;
}


Measured memory_bytes: 3636
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define ALL(a) (a).begin(), (a).end()
string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";

/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/

int main(void){
  string s;
  cin >> s;
  rep(i, s.length()){
    if (i%2 == 0) cout << s[i];
  }
  
  
}


Measured memory_bytes: 512
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int D;
	scanf("%d", &D);
	int c[26], s[D][26], t[D], last[26], bst = -10000000, ans[D];
	for (int i = 0; i < 26; ++i) scanf("%d", &c[i]);
	for (int i = 0; i < D; ++i) {
		for (int j = 0; j < 26; ++j) scanf("%d", &s[i][j]);
	}
	for (int h = 0; h < 13; ++h) {
		fill_n(last, 26, -1);
		for (int i = 0; i < D; ++i) {
			int x = -10000000, opt = 0;
			for (int j = 0; j < 26; ++j) {
				if (c[j] * (i - last[j] + h) + s[i][j] > x) x = c[j] * (i - last[j] + h) + s[i][j], opt = j;
			}
			last[opt] = i;
			t[i] = opt;
		}
		fill_n(last, 26, -1);
		int sc = 0;
		for (int i = 0; i < D; ++i) {
			last[t[i]] = i;
			sc += s[i][t[i]];
			for (int j = 0; j < 26; ++j) sc -= c[j] * (i - last[j]);
		}
		if (sc > bst) {
			bst = sc;
			for (int i = 0; i < D; ++i) ans[i] = t[i];
		}
	}
	for (int i = 0; i < D; ++i) printf("%d\n", ans[i] + 1);
	return 0;
}

Measured memory_bytes: 1772
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+5;

#define endl '\n'

char str[N];

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n,cnt=0;
	cin>>n>>str;
	for(int i=0;i<n;i++){
		if(str[i]=='A'){
			if(str[i+1]=='B'){
				if(str[i+2]=='C'){
					cnt++;
					i+=2;
				}
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
X, L = [], []
for _ in range(N):
    tmp_x, tmp_l = map(int, input().split())
    X.append(tmp_x)
    L.append(tmp_l)

end = [[X[i], L[i], X[i] + L[i]] for i in range(N)]
end = sorted(end, key = lambda x: x[2])

ans = N
target = 0
for i in range(1,N):
    if end[target][0] + end[target][1] <= end[i][0] - end[i][1]:
        target = i
    else:
        ans -= 1

print(ans)

Measured memory_bytes: 26812
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 110000

struct travel{
  int t,x,y;
};

int main(){
  int rt,x,y;
  travel t[MAX];
  t[0]={0,0,0};
  bool ans=true;
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>t[i].t>>t[i].x>>t[i].y;
    rt=t[i].t-t[i-1].t;
    x=t[i].x-t[i-1].x;
    y=t[i].y-t[i-1].y;

    if(x<0) x=-1*x;
    if(y<0) y=-1*y;

    if(x+y>rt || (rt-x-y)%2!=0){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;

}


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

int main()
{
    int h, w;
    bool lflat, rflat;
    while (true)
    {
        cin >> h >> w;
        lflat = false;
        if (h == 0 && w == 0)
        {
            break;
        }
        for (int i = 0; i != h; ++i)
        {
            lflat = !lflat;
            rflat = lflat;
            for (int j = 0; j != w; ++j)
            {
                if (rflat)
                {
                    cout << "#";
                }
                else
                {
                    cout << ".";
                }
                rflat = !rflat;
                
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



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

int main()
{
    int a, b, x;
    scanf("%d%d%d", &x, &a, &b);
    if(b - a <= 0)
    {
        cout << "delicious" << endl;
    }
    else if(b - a > x)
    {
        cout << "dangerous" << endl;
    }
    else cout << "safe" << endl;
    return 0;
}


Measured memory_bytes: 256
// Created by sz
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;

int main(){
//    freopen("./input.txt", "r", stdin);
    char s[maxn];
    scanf("%s",s);
    int length= strlen(s);
    int min_diff = 1e9;
    int pos = 0;
    for (int i = 2; i < length; i++){
        int num = 0;
        for(int j= i-2; j <=i; j++){
            num = num*10 + s[j] - '0';
        }
        if(abs(num -753) < min_diff)
        {
            min_diff = abs( num - 753);
        }
    }
    printf("%d\n", min_diff);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int r, D;
    int x[20];
    cin >> r >> D >> x[0];
    for(int i=1; i<=10; i++){
        x[i] = r * x[i-1] -D;
        cout<< x[i] <<endl;
    }
}

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

#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long int
#define N 7

int n,w;
int dp[100009][101];
int val[101];
int wgh[101];

signed main()
{
	boost;
	cin>>n>>w;
	for(int i=0;i<n;i++)
	{
		cin>>wgh[i]>>val[i];
	}
	for(int i=0;i<=n;i++)
		{
			for(int j=0;j<100009;j++)
			{
				dp[j][i]=-1;
			}
		}
		dp[val[0]][1]=wgh[0];
		for(int i=2;i<=n;i++)
		{
			for(int j=0;j<100009;j++)
			{
				if(j>=val[i-1]&&dp[j-val[i-1]][i-1]!=-1&&dp[j][i-1]!=-1)
				{
					dp[j][i]=min(dp[j-val[i-1]][i-1]+wgh[i-1],dp[j][i-1]);
				}
				else if(j>=val[i-1]&&dp[j-val[i-1]][i-1]!=-1)
				{
					dp[j][i]=dp[j-val[i-1]][i-1]+wgh[i-1];
				}
				else if(dp[j][i-1]!=-1&&j==val[i-1])
				{
					dp[j][i]=min(wgh[i-1],dp[j][i-1]);
				}
				else if(dp[j][i-1]!=-1)
				{
					dp[j][i]=dp[j][i-1];
				}
				else if(j==val[i-1])
				{
					dp[j][i]=wgh[i-1];
				}
			}
		}
		int ans=-1;
		for(int i=100008;i>=0;i--)
		{
			if(dp[i][n]!=-1&&dp[i][n]<=w)
			{
				ans=i;
				break;
			}
		}
		cout<<ans<<endl;
}	

Measured memory_bytes: 79232
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

outs = -1
c = 0
for i in range(n-1):
    c += arr[i]
    if 2*c < arr[i+1]:
        outs = i

if outs >= 0:
    print(n - 1 - outs)
else:
    print(n)




Measured memory_bytes: 14320
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <set>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
typedef long long ll;

const int MOD = 1000000007;  // 1 000 000 007


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

    // input
    int x, y, z;
    cin >> x >> y >> z;
    
    if (x+y == z || y+z == x || z+x == y) {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }
    
    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)

def main():
    n=int(input())
    aa=list(map(int, input().split()))
    stu=[]
    for i,a in enumerate(aa):
        stu.append([a,i])
    stu.sort()
    for a,i in stu:
        print(i+1)

main()

Measured memory_bytes: 21440
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int D = sc.nextInt();
    int[][] A = new int[H*W][2];
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        int a = sc.nextInt();
        A[a-1][0] = i;
        A[a-1][1] = j;
      }
    }
    
    int[] cost = new int[H*W];
    for (int i = D; i < H*W; i++) {
      cost[i] += cost[i-D]+Math.abs(A[i][0]-A[i-D][0])+Math.abs(A[i][1]-A[i-D][1]);
    }
    
    StringBuilder ans = new StringBuilder();
    int Q = sc.nextInt();
    while (Q-- > 0) {
      int L = sc.nextInt();
      int R = sc.nextInt();
      ans.append(cost[R-1]-cost[L-1]).append('\n');
    }
    
    System.out.print(ans.toString());
  }
}

Measured memory_bytes: 94724
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author KY2001
 */


#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

int bpm(int x, int y) {
  if (x == 0)
    return 0;
  else if (y == 0) {
    return 1;
  }
  int ans = 1;
  x %= MOD;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  for (int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) {
      ans *= x;
      ans %= MOD;
    }
    x = x * x;
    x %= MOD;
  }
  return ans;
}

class CTravelingPlan {
public:
  int solve(std::istream &cin, std::ostream &cout) {
    int N;
    cin >> N;
    vector<int> A(N + 2);
    A[0]     = 0;
    A[N + 1] = 0;
    vector<vector<int>> distance(N + 1, vector<int>(2, 0));
    rep(i, N) {
      cin >> A[i + 1];
    }
    int sum = 0;
    rep(i, N + 1) {
      distance[i][0] = abs(A[i + 1] - A[i]);
      sum += distance[i][0];
    }
    rep(i, N) {
      distance[i][1] = abs(A[i + 2] - A[i]);
    }
    rep(i, N) {
      cout << sum - distance[i][0] - distance[i + 1][0] + distance[i][1] << endl;
    }
  }
};


signed main() {
	CTravelingPlan solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 7424
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <cstring>
#include <iomanip>
using namespace std;

#define double long double
//#define int long long
#define mp make_pair
#define debug(x) cerr << #x << ": " << x << '\n';
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
template <typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; };
template <typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; };

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}

const int N = 1e5 + 10;
const int NN = 1e7 + 10;
int prime[NN];
int p[N];
int d[N];
pii qq[N];
int rs[N];

signed main() {
	fast();
	int x;
	cin >> x;
	cout << (x / 500) * 1000 + x % 500 - x % 5; 
 	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using P = pair<int,int>;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 100000000000000000
#define EPS 1e-9
#define PI  acos(-1)
const vector<vector<int>> DXY={{-1,0},{1,0},{0,-1},{0,1}};

//----***パーツ***----
#define fi first
#define se second
#define pb push_back
#define re return
#define br break

//----***入出力***---
void print() { std::cout << "\n"; }
template <class T>void print(const T &x) {std::cout << x<<"\n";}
template <class T, class... Args>void print(const T &x, const Args &... args) {std::cout << x << " ";print(args...);}
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;

int N,M;
string S;

signed main(){
  cin>>N>>M;
  print(N*M);

}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n%1000==0)///3000
    {
        cout<<"0"<<endl;
    }
    else if(n<=1000) ///800
    {
        cout<<1000-n<<endl;///200
    }
    else ///3300
    {
        cout<<1000-(n%1000)<<endl; ///700
    }
}


Measured memory_bytes: 3572