akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>

using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define rrep(i, x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i, x) for(int i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007
#define put2darr(arr, row, col) rep(i, row) { rep(j, col) { printf("%18d", arr[i][j]); } cout << endl; }

using namespace std;

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

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

/* 1..10
 * rep:   0 1 2 3 4 5 6 7 8 9
 * reps:  1 2 3 4 5 6 7 8 9 10
 * rrep:  9 8 7 6 5 4 3 2 1 0
 * rreps: 10 9 8 7 6 5 4 3 2 1
 */

int main() {
    double t,x;
    cin >> t >> x;
    cout << setprecision(20) << t / x;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;


int main(){
  ll i,j;
  ll m;
  cin>>m;
  ll d,c;
  ll sum=0,ke=0;
  for(i=0;i<m;i++){
	  cin>>d>>c;
	  sum+=d*c;
	  ke+=c;
  }
  sum--;
  sum/=9;
  cout<<ke-1+sum<<endl;
}

Measured memory_bytes: 256
n,m,y = map(int, input().split())
l = [input().split() for x in range(n)]
c = [0]*n
a=[[0 for x in range(m)] for y in range(n)]
for i in range(n):
    c[i] = l[i][0]
    for j in range(m):
        a[i][j] = l[i][j+1]

ans=float('inf')
for i in range(2 ** n):
    cost = 0
    d=[0]*m
    for j in range(n):
        if i >> j & 1:
            cost += int(c[j])
            for k in range(m):
                d[k] += int(a[j][k])
    ok = True
    for x in range(m):
        if d[x] < y: ok = False
    if ok: ans = min(ans, cost)
if ans == float('inf'): print(-1)
else:print(ans)


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

typedef long long int ll;

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll x;
    cin >> x;
    
    ll ans = (x / 500LL) * 1000LL + ((x % 500LL) / 5LL) * 5LL;
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 768
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;

#define dump(x) cerr << #x << " : " << x << '\n'
#define MOD(x, y) (((y) + (x) % (y)) % (y))

int N, Y;

int main(int argc, char* argv[])
{
	scanf("%d%d", &N, &Y);
	for (int i = 0; i <= 2000; i++) {
		for (int j = 0; j <= 2000; j++) {
			int k = N - i - j;
			if (i < 0 || j < 0 || k < 0) continue;
			if (10000 * i + 5000 * j + 1000 * k == Y) {
				printf("%d %d %d\n", i, j, k);
				return 0;
			}
		}
	}
	printf("-1 -1 -1\n");

	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]

count = [0] * (10**5 + 10)

for a in A:
  count[a] += 1

ans = sum(A)

for b,c in BC:
  x = count[b]
  y = c - b
  ans += x * y
  print(ans)
  count[b] = 0
  count[c] += x

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

int main(){
  int N,al[105],bl[105],a,b,c;
  char msg[105],t;

  while (1){
    cin >> N;
    if (N==0)break;
    cin >> msg;
    
    for (int i=0;i<N;i++){
      cin >> al[i] >> bl[i];
    }
    for (int i=N-1;i>=0;i--){
      a=al[i];
      b=bl[i];
      c=b-a;
      c = c%('z'-'a'+1);
      if ((int)msg[a-1]+c>'z')msg[a-1]+=-('z'-'a'+1)+c;
      else msg[a-1]+=c;
      if ((int)msg[b-1]+c>'z')msg[b-1]+=-('z'-'a'+1)+c;
      else msg[b-1]+=c;
      swap(msg[a-1],msg[b-1]);
    }
    cout << msg<<endl;
  }
  return 0;
}

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

const int N = 100000;
int t[N][2];

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	while(cin >> n && n){
		
		int x;
		cin >> x;
		t[0][0] = x;
		
		int size;
		t[0][1] = size = 1;
		
		for(int i = 0; i < n - 1; ++i){
			cin >> x;
			if(i % 2 == 0){
				if(t[size - 1][0] == x){
					t[size - 1][1] ++;
				}
				else {
					if(size >= 2){
						t[size - 2][1] += t[size - 1][1] + 1;
						size --;
					}
					else {
						t[size - 1][0] = x;
						t[size - 1][1]++;
					}
				}
			}
			else {
				if(t[size - 1][0] == x){
					t[size - 1][1] ++;
				}
				else {
					t[size][0] = x;
					t[size++][1] = 1;
				}
			}
		}
		
		int ans = 0;
		for(int i =0; i < size; ++i){
			ans += t[i][0] == 0 ? t[i][1] : 0;
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1192
N = int(input())
nums = list(map(int, input().split()))


def check():
    for i in range(1, N):
        if nums[i] == nums[i - 1]:
            continue
        elif nums[i] - 1 >= nums[i - 1]:
            nums[i] -= 1
            continue
        else:
            return "No"
    return "Yes"


print(check())

Measured memory_bytes: 14396
# include <stdio.h>

int main(void){
	int n,m,a[100][100],b[100],t,i,p[100],q,l;
	scanf("%d %d",&n,&m);
	for(t=0;t<m;t++){
		scanf("%d",&b[t]);
	}
	for(t=0;t<m;t++){
		for(i=0;i<n;i++){
			scanf("%d",&a[t][i]);
		}
	}
	
	for(t=0;t<n;t++){
		p[t]=0;
	}
	
	for(t=0;t<m;t++){
		l=0;
		for(i=0;i<n;i++){
			if(a[t][i]==b[t]){
				p[i]++;
				l++;
			}
		}
		p[b[t]-1] += n-l;
	}
	
	for(t=0;t<n;t++){
		printf("%d\n",p[t]);
	}
	
	return 0;
}
	

Measured memory_bytes: 636
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
	int N, X, Y, H;
	int x[110], y[110], h[110];
	cin >> N;
	int I;
	for (int i = 0; i < N; ++i) {
		cin >> x[i] >> y[i] >> h[i];
		if (h[i] > 0) {
			I = i;
		}
	}
	for (int i = 0; i <= 100; ++i) {
		for (int j = 0; j <= 100; ++j) {
			bool can = true;
			H = h[I] + abs(x[I] - i) + abs(y[I] - j);
			for (int k = 0; k < N; ++k) {
				if (h[k] > 0) {
					if (h[k] != H - abs(x[k] - i) - abs(y[k] - j)) {
						can = false;
					}
				}
				if (h[k] == 0) {
					if (H > abs(x[k] - i) + abs(y[k] - j)) {
						can = false;
					}
				}
			}
			if (can) {
				X = i;
				Y = j;
				cout << X << " " << Y << " " << H << endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Eric
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CNextPrime solver = new CNextPrime();
        solver.solve(1, in, out);
        out.close();
    }

    static class CNextPrime {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int max = 100004;
            int a = in.nextInt();
            boolean[] isPrime = new boolean[max];
            Arrays.fill(isPrime, true);
            for (int i = 2; i < Math.sqrt(max); i++) {
                if (isPrime[i]) {
                    for (int j = 2; j * i < max; j++) {
                        isPrime[i * j] = false;
                    }
                }
            }
            for (int i = a; i < max; i++) {
                if (isPrime[i]) {
                    out.println(i);
                    return;
                }
            }
            throw new RuntimeException("Not found");
        }

    }

    static class FastReader {
        public BufferedReader br;
        public StringTokenizer st;
        String context = null;

        public FastReader(InputStream in) {
            this(new InputStreamReader(in));
        }

        public FastReader(InputStreamReader input) {
            br = new BufferedReader(input);
        }

        public String next() {
            if (context != null) {
                System.err.print("[" + context + "] Wait for input ...");
            }
            while (st == null || !st.hasMoreElements()) {
                try {
                    String s = br.readLine();
                    if (s == null)
                        return null;
                    st = new StringTokenizer(s);
                } catch (IOException e) {
                    e.printStackTrace();
                    throw new RuntimeException("Could not read");
                }
            }
            String res = st.nextToken();
            if (context != null) {
                System.err.println("[" + context + "] ... received : " + res);
            }
            return res;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21460
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int A = N / 1000;
    N = N % 1000;
    int B = N / 100;
    N = N % 100;
    int C = N /10;
    N = N % 10;
    int D = N / 1;

    if (A + B + C + D == 7){
      System.out.println(A + "+" + B + "+" + C + "+" + D + "=7");
    } else if (A - B + C + D == 7) {
      System.out.println(A + "-" + B + "+" + C + "+" + D + "=7");
    } else if (A + B - C + D == 7) {
      System.out.println(A + "+" + B + "-" + C + "+" + D + "=7");
    } else if (A + B + C - D == 7) {
      System.out.println(A + "+" + B + "+" + C + "-" + D + "=7");
    } else if (A - B - C + D == 7) {
      System.out.println(A + "-" + B + "-" + C + "+" + D + "=7");
    } else if (A - B + C - D == 7) {
      System.out.println(A + "-" + B + "+" + C + "-" + D + "=7");
    } else if (A + B - C - D == 7) {
      System.out.println(A + "+" + B + "-" + C + "-" + D + "=7");
    } else if (A - B - C - D == 7) {
      System.out.println(A + "-" + B + "-" + C + "-" + D + "=7");
    }
  }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const int nmax = 8;
bool graph[nmax][nmax];
const ll INF = 1e11;
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

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

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

void solve(long long x, long long y)
{
    ll ans = INF;
    for (int i = 0; i < 4; i++)
    {
        ll tmpx = x,tmpy = y;
        int cnt = 0;
        if (i & 1)
        {
            tmpx = -1 * x;
            cnt++;
        }

        if (i & 2)
        {
            tmpy = -1 * y;
            cnt++;
        }
        if (tmpx <= tmpy)
            ans = min(ans, tmpy - tmpx + cnt);
    }

    cout << ans << endl;
}

int main()
{
    long long x;
    scanf("%lld", &x);
    long long y;
    scanf("%lld", &y);
    solve(x, y);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define rp(i,n) for(int i=0;i< n;i++)
#define rpd(i,n) for(int i=n-1;i >= 0;i--)

using namespace std;



int main() {

	ll n,k,x,y;
	cin >> n >> k >> x >> y;
	cout << x*min(k,n)+y*max(0ll,n-k);

	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int n;
long long arr[405],dp[405][405],cost[405][405],pre[405];
 
int main(){
	memset(cost,0,sizeof(cost));
	scanf("%d",&n);
	for (int i = 0;i<n;i++){
		scanf("%lld",&arr[i]);
		if(i==0){
			pre[i] = arr[i];
		} else{
			pre[i] = pre[i-1]+arr[i];
		}
		dp[i][i] = 0;
	}
	long long ans = 0;
	for (int iter  =n-1; iter>=1;iter--){
		for (int i= 0;i<iter;i++){
				int ii = i;
				int jj = n-iter+i;
				long long ret = 1000000000000000;
//				printf(">> %d %d\n", ii,jj);
				for(int k =ii;k<jj;k++){
					long long tmp1 = pre[k]-(ii==0?0:pre[ii-1]);
					long long tmp2 = pre[jj]-(k+1==0?0:pre[k+1-1]);
//					printf("%d %d ss %d %d\n",ii,k,k+1,jj);
//					printf("tmp %lld %lld\n", tmp1,tmp2);
//					printf("dp %lld %lld\n",dp[ii][k],dp[k+1][jj]);
					ret = min(ret,dp[ii][k]+dp[k+1][jj]+tmp1+tmp2);
				}
//				printf("\n");
				if(ret==1000000000000000) dp[ii][jj] = arr[ii]+arr[jj] ;
				else dp[ii][jj] = ret;
//				,printf("%lld dp[%d][%d] = %lld\n", ret,ii,jj,dp[ii][jj]);
		}
	}
//	for (int i = 0; i<n;i++){
//		for(int j =0; j<n;j++){
//			printf("%2lld ", dp[i][j]);
//		}
//		printf("\n");
//	}
	printf("%lld\n",dp[0][n-1]);
	return 0;
}

Measured memory_bytes: 2816
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const string nl="\n";
const ll MOD=1000000007;

int main(){
    ll n;
    cin>>n;
    ld p[n];
    for(int i=0;i<n;i++) cin>>p[i];
    ld dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j==0){
                dp[i][j]=dp[i-1][j]*(1-p[i-1]);
                continue;
            }
            dp[i][j]=dp[i-1][j]*(1-p[i-1]) + dp[i-1][j-1]*p[i-1];
        }
    }
    ld x=0;
    for(int i=n;2*i>n;i--){
        x+=dp[n][i];
    }
    cout<<fixed<<setprecision(12);
    cout<<x;
    return 0;
}

Measured memory_bytes: 140928
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>

typedef long long ll;
using namespace std;

typedef pair<int,int> P;

map<string,int> freq;

int main()
{
	char buf[64];
	while(~scanf("%s",buf)){
		string tmp = buf;
		freq[tmp]++;
	}

	int msize=0;
	string msize_str;
	int mfreq=0;
	string mfreq_str;
	for(map<string,int>::iterator it = freq.begin(); it != freq.end(); it++){
		if(msize < it->first.size()){
			msize_str = it->first;
			msize = it->first.size();
		}

		if(mfreq < it->second){
			mfreq_str = it->first;
			mfreq = it->second;
		}	
	}

	cout << mfreq_str << " " << msize_str << endl;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(void){
    ll n,k; cin>>n>>k;
    ll b = k;
    ll r = n-k;
    COMinit();
   
    for(int i=1;i<=k;i++){
        if(i==1) {cout<<n-k+1<<endl; continue;}
        ll bc = COM(b-1,i-1);
        ll rbc = COM(r+1,i);
        ll ans = bc*rbc;
        ans %= MOD;
        cout<<ans<<endl;
     }
}


Measured memory_bytes: 12160
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
inline LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1<<18;
int n,bin;
int a[N][2],maxi;
inline void merge(int *x,int *y)
{
	if(x[0]<y[0]){
		x[1]=max(x[0],y[1]);
		x[0]=y[0];
	}
	else{
		x[1]=max(x[1],y[0]);
	}
}
int main()
{
	n=read();
	bin=1<<n;
	for(int i=0;i<bin;++i){
		a[i][0]=read();
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<bin;++j){
			if((j&(1<<i))==0){
				merge(a[j|(1<<i)],a[j]);
			}
		}
	}
	for(int i=1;i<bin;++i){
		maxi=max(maxi,a[i][0]+a[i][1]);
		printf("%d\n",maxi);
	}
	return 0;
}

Measured memory_bytes: 5120
#include <stdio.h>

int main() {
  char s[16];
  char buf[16];
  int top = 0;
  int i;
  
  scanf("%s", s);
  for(i = 0; s[i] != '\0'; i++) {
    if(s[i] == 'B') {
      if(top > 0) top--;
    } else {
      buf[top] = s[i];
      top++;
    }
  }
  for(i = 0; i < top; i++) printf("%c", buf[i]);
  printf("\n");
  
  return 0;
}

Measured memory_bytes: 128
import java.util.*;

class P{
  String s;
  int digit;
  boolean re;

  public P(String s,int digit,boolean re){
    this.s = s;
    this.digit = digit;
    this.re = re;
  }

  public String toString(){
    return String.format("[%s, %d, %b]",s,digit,re);
  }
}

public class Main{
  static int n;
  static HashMap<String,Stack<Integer>> map;
  static P[] p;

  public static void Ichi(int idx){
    int now = 1;
    int popIdx = -1;
    Stack<Integer> st = new Stack<Integer>();

    while(!map.get(p[idx].s).isEmpty()){
      popIdx = map.get(p[idx].s).pop();
      if(now + 1 != p[popIdx].digit){
        map.get(p[idx].s).push(popIdx);
        popIdx = -1;
        break;
      }
      System.out.println(popIdx+1);
      st.push(popIdx);
      now++;
    }

    while(!st.isEmpty()){
      int p = st.pop();
      Re(p);
    }
  }

  public static void Re(int idx){
    for(int j=idx-1;j>=0 && p[j].re;j--){
      System.out.println(j+1);
      if(p[j].digit == 1){
        Ichi(j);
      }
    }
  }

  public static void solve(){
    for(int i=0;i<n;i++){
      if(p[i].s.equals("-")){
        System.out.println(i+1);
        Re(i);
        continue;
      }
      if(p[i].digit >= 2){
        map.get(p[i].s).push(i);
        continue;
      }
      if(p[i].re){
        continue;
      }

      System.out.println(i+1);

      if(p[i].digit == 1){
        Ichi(i);
      }

      Re(i);
    }
  }

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

    while(true){
      n = sc.nextInt();
      if(n == 0) break;

      map = new HashMap<String,Stack<Integer>>();
      p = new P[n+2];

      for(int i=0;i<n;i++){
        String s = sc.next();
        p[i] = new P("",-1,false);

        if(s.endsWith("v")){
          p[i].re = true;
          s = s.substring(0,s.length()-1);
        }

        int idx = s.length() - 1;
        for(;idx>=0 && '0' <= s.charAt(idx) && s.charAt(idx) <= '9';idx--);

        if(idx != s.length() - 1){
          p[i].digit = Integer.parseInt(s.substring(idx+1));
          s = s.substring(0,idx+1);
        }

        p[i].s = s;
        if(!p[i].s.equals("")){
          map.put(p[i].s,new Stack<Integer>());
        }
      }

      solve();
    }
  }
}

Measured memory_bytes: 17000
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
#define vi vector<int>
#define vl vector<long long>
#define vii vector<int,vector<int>>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{
    map<int,int> A;
    int N;
    cin >> N;
    rep(i,N){
        int a;
        cin >> a;
        A[a] ++ ;
        
    }
    int ans = 0;
    for(auto p : A){
        if(p.se % 2 == 1) ans ++ ;
        
    }
    out(ans);


    return 0;
}


Measured memory_bytes: 4992
def gcd(a,b):
    while b != 0:
        a, b = b, a%b
    return(a)

def main():    
    N,X = map(int,input().split())
    x = list(map(int,input().split()))
    for i in range(N):
        x[i] = abs(x[i]-X)
    y = x[0]
    for i in range(N):
        if x[i]%y == 0:
            continue
        y = gcd(y,x[i])
    print(y)

if __name__ == "__main__":
    main()

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

int main() {
  double n, m;
  cin >> n >> m;
  vector<double> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr.at(i);
  }
  double L = accumulate(arr.begin(), arr.end(), 0) / (4 * m);

  sort(arr.begin(), arr.end());

  if (arr.at(n - m) >= L) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }}


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

using lint = long long int;
using Graph = std::vector<std::vector<std::pair<int, lint>>>;

using namespace std;

template<typename T>
std::pair<T, int> dfs(const std::vector<std::vector<std::pair<int, T>>> &g, int cur, int par) {

  std::pair<T, int> ret(0, cur);
  for (auto e : g[cur]) {
    int nxt;
    T weight;
    tie(nxt, weight) = e;
    // auto [nxt, weight] = e; TODO こっちの戻す
    if (nxt == par) continue;
    auto cost = dfs(g, nxt, cur);
    cost.first += weight;
    ret = max(ret, cost);
  }

  return ret;
}

template<typename T>
std::tuple<int, int, T> tree_diameter(const std::vector<std::vector<std::pair<int, T>>> &g) {

  int u = dfs(g, 0, -1).second;
  // auto [_, u] = dfs(g, 0, -1); TODO こっちに戻す
  T dist;
  int v;
  tie(dist, v) = dfs(g, u, -1);
  // auto [dist, v] = dfs(g, u, -1); TODO こっちに戻す
  return make_tuple(u, v, dist);
}

int main() {

  int n;
  std::cin >> n;
  Graph g(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    lint c;
    std::cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }

  int u, v;
  lint dist;
  tie(u, v, dist) = tree_diameter<lint>(g);
  // auto [u, v, dist] = tree_diameter<lint>(g); TODO こっちに戻す
  // std::cout << dist << std::endl;
  // std::cout << u + 1 << " " << v + 1 << std::endl;
  cout << dist << endl;
  return 0;
}



Measured memory_bytes: 19060
H, W = (int(i) for i in input().split())  
A = [[int(i) for i in input().split()] for i in range(H)]
lst = []

for i in range(H-1):
  for j in range(W):
    if A[i][j] % 2 == 0:
      continue
    else:
      A[i][j] -= 1
      A[i+1][j] += 1
      lst.append([i+1, j+1, i+2, j+1])

for j in range(W-1):
  if A[H-1][j] % 2 == 1:
    A[H-1][j] -= 1
    A[H-1][j+1] += 1
    lst.append([H, j+1, H, j+2])
print(len(lst))
for l in lst:
  print(*l)

Measured memory_bytes: 30096
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

typedef long long int lli;

int main() {
  int n; cin >> n;
  lli w; cin >> w;
  vector<lli> ws(n, 0), vs(n, 0);

  for (int i = 0; i < n; i++) {
    cin >> ws[i] >> vs[i];
  }
  
  vector< vector<lli> > memo(n, vector<lli>(w+1, 0));
  memo[0][ws[0]] = vs[0];
  
  lli ans = 0;
  for (int i = 1; i < n; i++) {
    memo[i][ws[i]] = max(memo[i - 1][ws[i]], vs[i]);
    for (int j = 1; j <= w; j++) {
      memo[i][j] = max(memo[i][j], memo[i-1][j]);
      lli prev = j - ws[i];
      if (prev < 0) continue;
      if (memo[i-1][prev] <= 0) continue;
      memo[i][j] = max(memo[i][j], memo[i - 1][prev] + vs[i]);
    }
  }

  cout << *max_element(memo[n-1].begin(), memo[n-1].end()) << endl;
  return 0;
}

Measured memory_bytes: 79488
s=int(input())
a=s//100
b=s%100
if a>12 and b>12 or a==0 and b>12 or b==0 and a>12 or a==0 and b==0:print("NA")
elif a>12 or a==0:print("YYMM")
elif b>12 or b==0:print("MMYY")
else:print("AMBIGUOUS")

Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nk = sc.nextLine().split(" ");
        String[] lss = sc.nextLine().split(" ");
        ArrayList<Integer> ls = new ArrayList<>();
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);
        int ans = 0;
        for (int index = 0;index<n;index++) {
            ls.add(Integer.parseInt(lss[index]));
        }
        Collections.sort(ls);
        Collections.reverse(ls);
        for (int index = 0;index<k;index++) {
            ans += ls.get(index);
        }
        System.out.println(String.valueOf(ans));
    }
}

Measured memory_bytes: 21844
use strict;
use warnings;

my ($h, $w, $k) = split(/\s/, <>);
my @t;
while(my $l = <>) {
  push(@t, [split(//, $l)]);
}
my $n = 0;
for (my $i = 0; $i < 2 ** $w; $i++) {
  for (my $j = 0; $j < 2 ** $h; $j++) {
    my $c = 0;
    for (my $ci = 0; $ci < $w; $ci++) {
      for (my $li = 0; $li < $h; $li++) {
        $c++ if $t[$li][$ci] eq '#' && ($i >> $ci & 1) && ($j >> $li & 1);
      }
    }
    $n++ if $c == $k;
  }
}
print $n;


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

int main() {
    string s,t;
    cin >> s >> t;

    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());

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



Measured memory_bytes: 3560
// Created by ahmed_drawy on 10/09/19.
///dp educational contest atcoder - vjudge
#include <bits/stdc++.h>
#include <string.h>
#pragma clang diagnostic push
#pragma ide diagnostic ignored "OCUnusedMacroInspection"
using namespace std;
#define lp(i,start , end)       for(int i = start ; i<end ; ++i)
#define lllp(i,start , end)       for(ll i = start ; i<end ; ++i)
#define inN(arr ,  n) for(int i = 0 ; i< n ; ++i)  cin>>arr[i];
#define Rlp(i,start , end)      for(int i = start ; i>end ; --i)
#define all(v)                   ((v).begin(),(v).end())
#define sz(v)                  (int)((v).size())
#define clr(v,d)                memset(v , d , sizeof(v))
#define inf 0x3f3f3f3f
//#define dbg (v)    for(auto it : v)cout<<it<<' ';
typedef long long               ll;
typedef vector<int>             vi;
typedef vector  <ll>            vll;
typedef vector<vector<int> >    adj;
typedef pair<int ,int>          pii;
const double EPS =1e-7;
const int OO = 1e6;
#define endl '\n'
#define cint(c) (int)c -'0';
#define itc(c) (char)c +'A';
bool sortpair( const pair<int , int> & x, const pair<int , int> & y){
    return  x.first != y.first ? x.first < y.first : x.second > y.second ;
}
int dcomp(double x , double y){
    return fabs(x-y) <= EPS? 0: x>y?1:-1;
}

void smile() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
//    freopen("/home/tw3/Desktop/Desktop/training/in.txt", "r", stdin);
//    freopen("/home/tw3/Desktop/Desktop/training/out.txt" , "w" , stdout);
#endif
}
#define fastin smile()

int n ;
const int N = 1e5 +3;
ll dp[N];
int h[N];
//ll solve(int indx , int state){
//    if(indx == n-1 )return 0 ;
//    ll &ret = dp[indx  ] [ state];
//    if(~ret )
//        return ret;
//    ret=  INT_MAX;
//    for (int i = 1; i <=2 && i+indx < n ; ++i) {
//        ret = min(ret , abs(h[indx]  - h[indx+ i])+solve(indx + i , i ));
//    }
//    return ret ;
//}
int main() {
    fastin;
    cin >> n;
    inN(h,  n );
    clr(dp , 0);
    for (int j = 1; j <n ; ++j) {
        if(j>=2){
            dp[j] = min(dp[j-1] + abs(h[j-1] - h[j]) , abs(h[j-2] - h[j])+dp[j-2]);
        }
        else if(j ==1){
            dp[j] = abs(h[j] - h[j-1])+dp[j-1];
        }
    }
    cout << dp[n-1];
//
//    clr(dp , -1);
//    cout << solve(0, 1)<<endl;
}

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

int main(){
  long long a,b,c;
  cin >> a >> b >> c;
  long long x = 4*a*b;
  long long y = (c-a-b)*(c-a-b);
  if (c-a-b > 0 && x < y){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}
  



Measured memory_bytes: 3596
require 'set'

n = gets.chomp.to_i
s = gets.chomp.chars

result = 0
r_idx = []
g_idx = []
b_idx = []

idx = 0
s.each do |c|
  r_idx << idx if c === 'R'
  g_idx << idx if c === 'G'
  b_idx << idx if c === 'B'
  idx += 1
end

r_set = Set.new(r_idx)
b_set = Set.new(b_idx)
g_set = Set.new(g_idx)

distance_error = 0
result = r_idx.length * g_idx.length * b_idx.length

r_set.each do |r|
  g_set.each do |g|
    r_g_unit = [r, g].sort
    d = r_g_unit[1] - r_g_unit[0]

    b_max_pattern_b = r_g_unit[1] + d
    if b_set.include?(b_max_pattern_b)
      distance_error += 1
    end

    b_min_pattern_b = r_g_unit[0] - d
    if b_set.include?(b_min_pattern_b)
      distance_error += 1
    end

    next if (r + g) % 2 == 1
    b_cen_pattern_b = (r + g) /2
    if b_set.include?(b_cen_pattern_b)
      distance_error += 1
    end
  end
end

puts result - distance_error

Measured memory_bytes: 14796
import sys
import math
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(20000000)


def main():
    S = list(input())
    ans = [0] * len(S)
    count = 0

    for _ in range(2):
        for x in range(len(S)):
            if S[x] == 'R':
                count += 1
            else:
                ans[x] += math.floor(count/2)
                ans[x - 1] += math.ceil(count / 2)
                count = 0

        if _ == 0:
            S.reverse()
            for s in range(len(S)):
                if S[s] == 'L':
                    S[s] = 'R'
                else:
                    S[s] = 'L'
            ans.reverse()

    ans.reverse()
    print(*ans, sep=' ')


if __name__ == '__main__':
    main()



Measured memory_bytes: 7588
import java.util.*;

class Main{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> maps = new HashMap<>();
        for(int i=0;i<n;i++){
            maps.put(sc.nextInt(), i+1);
        }
        for(int i=0;i<n;i++){
            System.out.print(maps.get(i+1) +" ");
        }
    }
}


Measured memory_bytes: 72736
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int S, T;
int U[200010], V[200010], DD[200010];
int vis[100010];
vector<vector<int> > G(100010);
vector<vector<int> > G2(100010);
struct data{
	long long leng;
	int to;
	long long num;
};
struct cmp {
	bool operator() (const struct data a, const struct data b) const {
		if(a.leng > b.leng)
			return true;
		else if(a.leng < b.leng)
			return false;
		else{
			if(a.to > b.to)
				return true;
			else
				return false;
		}
	}
};
priority_queue<struct data, vector<struct data>, cmp > pq;
int s, t;
long long D = 1000000007;
long long len;
long long L1[100010];
long long L2[100010];
long long Num1[100010];
long long Num2[100010];
long long Val[200010];
int VL;

void solve()
{
	int i, j;
	s = S;
	t = T;
	struct data d, d2;
	d.leng = 0;	
	d.to = s;
	d.num = 1;
	Num1[s] = 1;
	pq.push(d) ;
	int u, v;
	long long tl;
	long long tmp;
	while(!pq.empty() ){
		d = pq.top();
		u = d.to;
		if(vis[u]==1){
			pq.pop();
			continue;
		}
		vis[u] = 1;
		if(u == t){
			len = d.leng ;
			break;
		}
		tl = d.leng ;
		tmp = 0;
		while(d.to == u && d.leng==tl){
			tmp += d.num;
			tmp %= D;
			pq.pop() ;
			if(pq.empty() )
				break;
			d = pq.top();
		}
		//L1[u] = d.leng ;
		L1[u] = tl;
		Num1[u] = tmp;
		for(i=0; i<G[u].size(); i++){
			v = G[u][i];
			if(vis[v]==0){
				d2.leng = tl + G2[u][i];
				d2.to = v;
				d2.num = tmp;
				pq.push(d2) ;
			}
		}
	}
	while(!pq.empty() )
		pq.pop() ;
	
	for(i=0; i<N; i++)
		vis[i] = 0;
	s = T;
	t = S;
	d.leng = 0;	
	d.to = s;
	d.num = 1;
	Num2[s] = 1;
	pq.push(d) ;
	while(!pq.empty() ){
		d = pq.top();
		u = d.to;
		if(vis[u]==1){
			pq.pop();
			continue;
		}
		vis[u] = 1;
		tl = d.leng ;
		tmp = 0;
		while(d.to == u && d.leng==tl){
			tmp += d.num;
			tmp %= D;
			pq.pop() ;
			if(pq.empty() )
				break;
			d = pq.top();
		}
		Num2[u] = tmp;
		L2[u] = tl;
		if(u == t){
			break;
		}
		for(i=0; i<G[u].size(); i++){
			v = G[u][i];
			if(vis[v]==0){
				d2.leng = tl + G2[u][i];
				d2.to = v;
				d2.num = tmp;
				pq.push(d2) ;
			}
		}
	}
	while(!pq.empty() )
		pq.pop() ;
	
	VL = 0;
	for(i=0; i<N; i++){
		if(L1[i]<len/2 || (L1[i]==len/2&&len%2==1) ){
			for(j=0; j<G[i].size(); j++){
				v = G[i][j];
				if(L2[v]<len/2 || (L2[i]==len/2&&len%2==1) ){
					if(L1[i]+L2[v]+G2[i][j]==len){
						Val[VL] = Num1[i] * Num2[v];
						Val[VL] %= D;
						VL ++;
					}
				}
			}
		}
		else if(L1[i]==len/2 && len%2==0){
			if(L1[i]+L2[i]==len){
				Val[VL] = Num1[i] * Num2[i];
				Val[VL] %= D;
				VL ++;
			}
		}
	}
	long long sum = 0;
	for(i=0; i<VL; i++){
		sum += Val[i];
		sum %= D;
	}
	long long res=0;
	for(i=0; i<VL; i++){
		tmp = sum+D-Val[i];
		tmp %= D;
		tmp *= Val[i];
		tmp %= D;
		res += tmp;
		res %= D;
	}
	printf("%lld\n", res);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	int i;
	scanf("%d%d", &N, &M);
	scanf("%d%d", &S, &T);
	S--, T--;
	for(i=0; i<M; i++){
		scanf("%d%d%d", &U[i], &V[i], &DD[i]);
		U[i]--, V[i]--;
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
		G2[U[i]].push_back(DD[i]);
		G2[V[i]].push_back(DD[i]);
	}
	solve();
	return 0;
}

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
	int N, K;
	string S;
	cin >> N >> K >> S;
	int sw = 0;
	char bef = 'x';
	REP(i , N){
		if(i > 0 && S[i] != bef) sw++;
		bef = S[i]; 
	}
	//cout << sw << endl;
	int ex = 0;
	if (K >= sw){
		ans = N-1;
	} 
	else {
		int unhappy = sw + 1;
		ans = N - max(unhappy - (2 * K), 1);
	}
    cout << ans << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<cmath>
using namespace std;
int main(){
  int n;
  cin>>n;
  int arr[200006];
  int dp[200006];
  for(int i=0;i<n;i++){
    cin>>arr[i];
    dp[i] = 1000000000;
  }
  dp[0] = 0;
  for(int i = 1;i<n;i++){
      if(i>0){
        dp[i] = min(dp[i], dp[i-1] + abs(arr[i]-arr[i-1]));
        }
          if(i>1){
            dp[i] = min(dp[i] , dp[i-2] + abs( arr[i] - arr[i-2]));
          }       
  }
  cout<<dp[n-1];
  
 return 0; 
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#define INF 2147483647
using namespace std;
int tree[(1<<18)];
int n,q;

void update(int i,int x) {
  i+=(n-1);
  tree[i] = x;
  while(i!=0){
    i=(i-1)/2;
    tree[i] = min(tree[i*2+1],tree[i*2+2]);
  }
}

int find(int a ,int b,int ima,int L,int R){
  if(R<=a || b<=L) return INF;
  if(a<=L && R<=b) return tree[ima];
  int M = (R+L)/2;
  return min(find(a,b,ima*2+1,L,M),find(a,b,ima*2+2,M,R));
}

int main(){
  cin >> n >>q;
  int N=1;
  while(N<n)N*=2;
  n=N;

  for(int i=0;i<n;i++)update(i,INF);
  while(q--){
    int com,x,y;
    cin >>com >> x >> y;
    if(com == 0) update(x,y);
    if(com == 1) cout << find(x,y+1,0,0,n) <<endl;
  }
  return 0;
}

Measured memory_bytes: 2184
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll MOD=1e9+7;
const int INF=1<<30;

const int mod=1000000007;
struct mint{
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const{return mint(-x);}
  mint& operator+=(const mint a){
    if((x+=a.x)>=mod) x-=mod;
    return *this;
  }
  mint& operator-=(const mint a){
    if((x+=mod-a.x)>=mod) x-=mod;
    return *this;
  }
  mint& operator*=(const mint a){
    (x*=a.x)%=mod;
    return *this;
  }
  mint operator+(const mint a) const{
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const{
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const{
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const{
    if(!t) return 1;
    mint a=pow(t>>1);
    a*=a;
    if(t&1) a*=*this;
    return a;
  }

  // for prime mod
  mint inv() const{
    return pow(mod-2);
  }
  mint& operator/=(const mint a){
    return (*this)*=a.inv();
  }
  mint operator/(const mint a) const{
    mint res(*this);
    return res/=a;
  }
};

struct Eratosthenes{
  int n;
  vector<int> f,primes;
  Eratosthenes(int n=1):n(n),f(n+1){
    f[0]=f[1]=-1;
    for(ll i=2;i<=n;++i){
      if(f[i]) continue;
      primes.push_back(i);
      f[i]=i;
      for(ll j=i*i;j<=n;j+=i){
        if(!f[j]) f[j]=i;
      }
    }
  }
  bool isPrime(int x){return f[x]==x;}
  vector<int> factorList(int x){
    vector<int> res;
    while (x!=1){
      res.push_back(f[x]);
      x/=f[x];
    }
    return res;
  }
  vector<i_i> factor(int x){
    if(x<=0) return {};
    vector<int> fl=factorList(x);
    if(fl.size()==0) return {};
    vector<i_i> res(1,i_i(fl[0],0));
    for(int p:fl){
      if(res.back().first==p){
        res.back().second++;
      } else{
        res.emplace_back(p,1);
      }
    }
    return res;
  }
};

int main(){
  int N; cin >> N;
  vector<int> a(N);
  rep(i,N) cin >> a[i];
  Eratosthenes sieve(1e6);
  map<int,int> mp;
  rep(i,N){
    vector<i_i> f=sieve.factor(a[i]);
    for(auto c:f){
      mp[c.first]=max(c.second,mp[c.first]);
    }
  }
  mint lcm=1;
  for(auto c:mp){
    rep(i,c.second){
      lcm*=c.first;
    }
  }
  mint ans=0;
  rep(i,N){
    ans+=lcm/a[i];
  }
  cout << ans.x << endl;
}


Measured memory_bytes: 4988
using System;
 
class program
{
  static void Main(string[] args)
  {
	int N = int.Parse(Console.ReadLine());
	bool A = false;
    for(int c=1; c<=10000; ++c){ 
      Random r = new Random(1000+c);
      int Cakes = r.Next(25);
      int Donuts = r.Next(15);
      int Result = 4*Cakes + 7*Donuts;
      if(N == Result){
      Console.WriteLine("Yes");
        A = true;
        break;
      }
    }
    if(A == false){
      Console.WriteLine("No");
    }
  }
}

Measured memory_bytes: 15188
fun main() = Thread(null, ::abc170d, "(^o^)", 128 * 1024 * 1024).apply { start() }.join()

@OptIn(ExperimentalStdlibApi::class)
fun abc170d() {
    readLine()!!.toInt()
    val aList = readLine()!!.split(' ').map { it.toLong() }

    val max = aList.max()!!.toInt()
    val isValid = BooleanArray(max + 1)
    aList.forEach { isValid[it.toInt()] = true }
    aList.groupBy { it }.filter { it.value.size >= 2 }
        .forEach { (t, _) -> isValid[t.toInt()] = false }

    for (a in aList) {
        var num = 2
        while (num <= max / a) {
            isValid[(num * a).toInt()] = false
            num++
        }
    }

    val answer = isValid.count { it }

    println(answer)
}


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

#define N 100005
#define INF (ll)1000000005

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

    ll dp[n+1][N];
    memset(dp,INF,sizeof dp);

    ll arr[n+1][2];
    for(ll i=1;i<=n;i++)
        cin>>arr[i][0]>>arr[i][1];

    for(ll i=0;i<=n;i++)
        dp[i][0] = 0;

    for(ll i=1;i<=n;i++)
    {
        for(ll j=0;j<N;j++)
        {
            if(i>1)
                dp[i][j] = dp[i-1][j];
            if(arr[i][1]<=(j))
                dp[i][j] = min(dp[i][j],dp[i-1][j-arr[i][1]] + arr[i][0]);
        }
    }

    ll ans = INF;
    for(ll i=0;i<N;i++)
    {
        if(dp[n][i] <= w)
            ans = i;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 79104
import java.util.Scanner;
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int tmp=1;
		for(int i=1;i<X;i++) {
			for(int j=2;j<=100;j++) {
				if(Math.pow(i, j)>tmp&&Math.pow(i, j)<=X) {
 
					tmp = (int) Math.pow(i, j);
								}
				if(Math.pow(i, j)>X) {
						break;
				}
 
			}
 
		}
		System.out.println(tmp);
	}
 
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 10000
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x%mod;
}

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

int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int h, w, a, b;

signed main() {
	cin >> h >> w >> a >> b;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if ((i < b&&j < a) || i >= b && j >= a) {
				if (j < w - 1)cout << 1;
				else cout << 1 << endl;
			}
			else {
				if (j < w - 1)cout << 0;
				else cout << 0 << endl;
			}
		}
	}
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define pb push_back
#define nmax 200005
using namespace std;
vector<int>g[nmax];
int n, x, y, h[nmax], u, v, wh;
int lastNode[nmax], big[nmax], ans;
bool onPath[nmax];
void dfs1(int nod, int hei, int lst = -1){
    lastNode[nod] = lst;
    h[nod] = hei;
    if (nod == u){
        int curr = nod;
        while (curr != -1){
            onPath[curr] = true;
            curr = lastNode[curr];
        }
    }
    for (auto x:g[nod]){
        if (x == lst){
            continue;
        }
        dfs1(x, hei+1, nod);
    }
}
void dfs2(int nod, int lst = -1){
    for (auto x:g[nod]){
        if (x == lst || !onPath[x]){
            continue;
        }
        if (h[x] > h[u]-h[x]){
            ans = max(ans, big[x]-1);
        }
        if (nod != u){
            dfs2(x, nod);
        }
    }
}
void dfs3(int nod, int lst = -1){
    int leaf = true;
    for (auto x:g[nod]){
        if (x == lst){
            continue;
        }
        leaf = false;
        dfs3(x, nod);
    }
    if (leaf){
        big[nod] = h[nod];
    } else {
        int maxx = -1;
        for (auto x:g[nod]){
            if (x == lst){
                continue;
            }
            maxx = max(maxx, big[x]);
        }
        big[nod] = maxx;
    }
}
int main()
{
    cin>>n>>u>>v;
    for (int i=1;i<n;++i){
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs1(v, 0);
    ans = h[u] - 1;
    dfs3(v);
    dfs2(v);
    cout<<ans<<'\n';
    return 0;
}


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

using namespace std;

const int INF=1e9+7;
int main()
{
    int n;
    cin>>n;

    vector<int >dp(3);

    for(int i=0;i<n;i++)
    {
        vector<int>cost(3,0);
        vector<int>c(3);
        for(int l=0;l<3;l++)
            cin>>c[l];

        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            {
                if(j!=k)
                {
                    cost[k]=max(cost[k], dp[j]+c[k]);
                }
            }
        }
        dp=cost;
    }
    cout<<max({dp[0],dp[1],dp[2]});


    return 0;
}


Measured memory_bytes: 3592
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
b.sort(reverse=True)
el=-1
same=list()
for i in range (n):
    if a[i]==b[i]:
        el=a[i]
        same.append(i)
l=len(same)
c=0
for i in range (n):
    if c<l and b[i]!=el and a[i]!=el:
        b[i],b[same[c]]=b[same[c]],b[i]
        c+=1
#print(c)
#print(*b)
if c!=l:
    print("No")
else:
    print("Yes")
    print(*b)

Measured memory_bytes: 115044
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1<<27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2> void sortTwoVecter(vector<T1> &f, vector<T2> &s, bool isReverse = false){
    vector<pair<T1, T2>> p;
    rep(i, f.size()) p.emplace_back(make_pair(f[i], s[i]));
    if (!isReverse) sort(p.begin(), p.end());
    else sort(p.rbegin(), p.rend());
    rep(i, f.size()) tie(f[i], s[i]) = p[i];
    return;
}

int main(){
    ll N; cin >> N;
    vector<ll> s(N);
    rep(i, N) cin >> s[i];
    reverse(all(s));
    vector<ll> dp(N + 1, INF);
    rep(i, N){
        dp[upper_index(dp, s[i])] = s[i];
    }
    // debug(dp);
    rep(i, N + 1) if(dp[i] == INF){
        pt(i);
        return 0;
    }
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<long long int> A;
    for(int i=0; i<N; i++)
    {
    	long long int a;
    	cin >> a;
    	A.push_back(a);
    }

    map<long long int,int> m;
    for(int i=0; i<N; i++)
    {
    	m[A[i]] = 0;
    }    
    for(int i=0; i<N; i++)
    {
    	m[A[i]]++;
    }
    vector<long long int> S;
    sort(A.begin(),A.end());
    S.push_back(A[0]);
    for(int i=1; i<N; i++)
    {
    	if(A[i]!=A[i-1]) S.push_back(A[i]);
    }
    int cnt = 0;
    for(int i=0; i<S.size(); i++)
    {
    	if(m[S[i]]%2!=0) cnt++;
    }
    
    cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 8820
#include <iostream>

using namespace std;

int main(){
  int n;
  cin >> n;
  int A[n];
  for(int i = 0; i < n; i++) cin >> A[i];
  for(int i = 0; i < n; i++) {
    int key = A[i];
    int j = i - 1;
    while(j >= 0 && A[j] > key) {
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = key;
    for(int k = 0; k < n; k++) {
      if(k == n - 1) cout << A[k] << endl;
      else cout << A[k] << " ";
    }
  }
}



Measured memory_bytes: 3100