akhauriyash/Code-Regression huggingface dataset:
from collections import deque

k = int(input())
q = deque(range(1, 10))
 
for i in range(k):
    x = q.popleft()
    if x % 10 != 0:
        q.append(10 * x + x % 10 - 1) #左端

    q.append(10 * x + x % 10) #真ん中

    if x % 10 != 9:
        q.append(10 * x + x % 10 + 1) #右端
 
print(x)

Measured memory_bytes: 11908
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    int n, x;
    cin >> n>> x;

    while (!(n == 0 && x == 0))
    {
        int ans = 0;
        for (int i = 1; i <= n - 2; i++)
        {
            for (int j = i + 1; j <= n - 1; j++)
            {
                for (int k = j + 1; k <= n; k++)
                {
                    if (i+j+k == x){
                        ans++;
                        //break;
                    }
                }
            }
        }
        cout << ans << endl;
        cin >> n >> x;
    }
}


Measured memory_bytes: 3112
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
const int N=200010;
map <int,int> w;
int a[N],b[N],fa[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
int main() {
    int n,ans=0,tt=0;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),a[0]^=a[i],fa[i]=i;
    for(int i=1;i<=n;i++) b[i]=gi(),b[0]^=b[i];
    for(int i=0;i<=n;i++)
	if(!i||a[i]!=b[i]) {
	    if(i) ++ans;
	    if(!w[a[i]]) w[a[i]]=++tt,fa[tt]=tt;
	    if(!w[b[i]]) w[b[i]]=++tt,fa[tt]=tt;
	    fa[find(w[a[i]])]=find(w[b[i]]);
	}
    for(int i=1;i<=tt;i++)
	if(fa[i]==i) ++ans;
    sort(a,a+n+1),sort(b,b+n+1);
    for(int i=0;i<=n;i++)
	if(a[i]!=b[i]) return puts("-1"),0;
    cout<<ans-1;
    return 0;
}

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

int main(){
	int n,k,q; cin>>n>>k>>q;
	if(k>q){
		rep(i,n) cout<<"Yes"<<endl;
	}else{
		vector<int> v(n);
		rep(i,q){
			int a; cin>>a;
			v[a-1]++;
		}
		rep(i,n){
			if(v[i]>q-k) cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
}

Measured memory_bytes: 3736
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

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

	int N;
	cin >> N;

	int prev_t, prev_x, prev_y;
	prev_t = 0;
	prev_x = 0;
	prev_y = 0;

	for (int i = 0; i < N; i++)
	{
		int t, x, y;
		cin >> t >> x >> y;

		int check_t = (t - prev_t);
		int check_pos = (abs(x - prev_x) + abs(y - prev_y));
		if (check_t < check_pos || check_t % 2 != check_pos % 2)
		{
			cout << "No";
			return 0;
		}

		prev_t = t;
		prev_x = x;
		prev_y = y;
	}

	cout << "Yes";

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>

using namespace std;

#define max_n 1000

int main(){
  int n;
  int l[max_n], r[max_n];
  cin >> n;
  int i;
  for(i=0; i<n; i++){
    cin >> l[i];
    cin >> r[i];
  }
  int sum = 0;
  for(i=0; i<n; i++){
    sum += r[i] - l[i] + 1;
  }
  cout << sum << endl;
  return 0;
}


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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string s,t;
	cin >> s >> t;
	int m = s.size();
	int n = t.size();
	int dp[m+1][n+1];
	string subseq="";
	for(int i=0; i<=m; ++i) {
		for(int j=0; j<=n; ++j) {
			if(i==0||j==0) 
				dp[i][j] = 0;
			else if(s[i-1]==t[j-1]){
				dp[i][j] = 1+dp[i-1][j-1];
				subseq+=s[i-1];
			}
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}
	}
	// cout << dp[m][n] << "\n";
	int index= dp[m][n];
	char lcs[index+1];
	lcs[index]='\0';
	int i=m,j=n;
	while(i>0 && j>0) {
		if(s[i-1]==t[j-1]) {
			lcs[index-1] = s[i-1];
			i--;j--;index--;
		}
		else if(dp[i-1][j]>dp[i][j-1])
			i--;
		else
			j--;
	}

	cout << lcs;
	return 0;
}


Measured memory_bytes: 51588
#include<vector>
#include<iostream>
#include<numeric>

using namespace std;
template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}

int main(){
   long n; 
    long l;
    cin>>n;
    cin>>l;
  
    cout<< n*l/ gcd(n, l);
    return 0;
}

Measured memory_bytes: 256
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
hl = inpl()
pre = 0
ans = 'Yes'
for i in range(0, n):
    if(hl[i] < pre):
        ans = 'No'
        break
    if(hl[i] > pre):
        pre = hl[i]-1
    else:
        pre = hl[i]
print(ans)

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


string S;

int main() {
    cin >> S;

    for (int i = 0; i < S.size() - 1; i++) {
        if (S[i] == 'B' && S[i+1] == 'C') {
            S[i] = 'X';
            S.erase(i+1, 1);
        }
    }

    ll ans = 0;
    ll A_cnt = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == 'A') A_cnt++;
        else if (S[i] == 'X') ans += A_cnt;
        else A_cnt = 0;
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    
    for(int i=1;i<=a*b;i++){
        
        if((a*i)%b==c){
            cout << "YES" << endl;
            return 0;
        }
    }
    
    cout<< "NO"<<endl;
}


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

using namespace std;

int main() {
	string S;
	string pat[4] = { "maerd", "remaerd", "esare", "resare" };
	cin >> S;
	reverse(S.begin(), S.end());

	for(int i = 0; i < S.size(); i++) {
		if(S.substr(i, 5) == "maerd") i += 4;
		else if(S.substr(i, 7) == "remaerd") i += 6;
		else if(S.substr(i, 5) == "esare") i += 4;
		else if(S.substr(i, 6) == "resare") i+= 5;
		else { cout << "NO" << endl; return 0; }
	}

	cout << "YES" << endl;

	return 0;
}


Measured memory_bytes: 512
def main():
  n,k=map(int,input().split())
  ab=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:x[0])
  count=0
  for i in range(n):
    count+=ab[i][1]
    if count>=k:
      print(ab[i][0])
      exit()  
if __name__=='__main__':
  main()

Measured memory_bytes: 29716
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static BufferedReader reader;
	final static boolean MODE_DEBUG = true;
	//static field here
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		reader = new BufferedReader(new InputStreamReader(System.in));
		//code here
		
		
		long N=1;
		long M = readLineInt()[0];
		for(int i=0;i<M;i++) {
			while(true) {
				int c = check(N);
				if(c==-1) {break;}
				long t = 1;
				for(int j=0;j<c;j++) {
					t*=10;
				}
				N = N/t;
				N++;
				N = N*t;
			}
			N++;
		}
		print(N-1);
	}
	
	//functions here
	//note that all methods should be STATIC

	private static int check(long num) {
		char[] cs = (num+"").toCharArray();
		for(int ci=0;ci<cs.length-1;ci++) {
			if(Math.abs(cs[ci]-cs[ci+1])>1) {return cs.length-ci-2;}
		}
		return -1;
	}

	private static <T> int arraySearch(T needle, T[] heystack) {
		for(int i=0;i<heystack.length;i++) {
			if(needle.equals(heystack[i])) {
				return i;
			}
		}
		return -1;
	}
	private static String[] readLine(){
		try{
			return reader.readLine().split(" ");
		}catch(Exception e){
			e.printStackTrace();
			return new String[]{e.getMessage()};
		}
	}
	private static int[] readLineInt(){
		try{
			String[] s = readLine();
			int[] ints = new int[s.length];
			for(int i=0;i<ints.length;i++) {
				ints[i] = Integer.parseInt(s[i]);
			}
			return ints;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static byte[] readLineByte(){
		try{
			String[] s = readLine();
			byte[] bytes = new byte[s.length];
			for(int i=0;i<bytes.length;i++) {
				bytes[i] = Byte.parseByte(s[i]);
			}
			return bytes;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static char[] readLineChar(){
		try{
			String[] s = readLine();
			char[] chars = new char[s.length];
			for(int i=0;i<chars.length;i++) {
				chars[i] = (char)Integer.parseInt(s[i]);
			}
			return chars;
		}catch(Exception e){
			e.printStackTrace();
			return null;
		}
	}
	private static void print(Object o){
		System.out.println(o);
	}
	private static void print(){
		System.out.println();
	}
	private static void printd(Object o){
		if(MODE_DEBUG)System.err.println(o);
	}
	private static void printd(){
		if(MODE_DEBUG)System.err.println();
	}
}


Measured memory_bytes: 58324
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use proconio::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [usize;n],
    }

    let sum = a.iter().sum::<usize>();
    println!(
        "{}",
        if m <= a.iter().filter(|&t| t * 4 * m >= sum).count() {
            "Yes"
        } else {
            "No"
        }
    );
}


Measured memory_bytes: 2132
using System;

class Class001
{
    public static void Main(string[] args)
    {
        int w = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        string[][] a = new string[n][];
        int[] c = new int[w];

        for (int i = 0; i < n; i++)
        {
            string s = Console.ReadLine();
            a[i] = s.Split(',');
        }

        for (int i = 0; i < w; i++)
        {
            c[i] = i + 1;
            for (int j = 0; j < n; j++)
            {
                if (c[i] == int.Parse(a[j][0]))
                {
                    c[i] = int.Parse(a[j][1]);
                }
                else if (c[i] == int.Parse(a[j][1]))
                {
                    c[i] = int.Parse(a[j][0]);
                }
            }
        }

        for (int i = 0; i < w; i++)
        {
            Console.WriteLine(Array.IndexOf(c, i + 1) +1);
        }
    }
}

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

class Program
{
    static void Main(string[] args)
    {
        var array1 = Console.ReadLine().ToCharArray();
        var array2 = Console.ReadLine().ToCharArray();

        var ans = 0;
        for(var i = 0; i < array1.Length; i++)
        {
            if(array1[i] != array2[i])
            {
                ans += 1;
            }
        }

        Console.WriteLine(ans);


        Console.ReadLine();

    }
}

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



Measured memory_bytes: 3512
//Author - Rahil Malhotra
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int32_t main() 
{
    IOS;
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    while(a>=b)
    {
        b*=2;
        k--;
    }
    while(b>=c)
    {
        c*=2;
        k--;
    }
    if(k<0)
        print("No");
    else
        print("Yes");
}   

Measured memory_bytes: 3636
import Control.Monad
import Data.Array
import Data.Bits
import Data.List

main = do
    [n, k] <- fmap read <$> words <$> getLine
    a      <- fmap read <$> words <$> getLine
    putStrLn $ show $ solve n k a

solve :: Integer -> Integer -> [Integer] -> Integer
solve n k a = doit 50 + sum a
  where
    doit (-1)                           = 0
    doit bit | k .&. 1 `shift` bit /= 0 = max (doit (bit - 1) + diff !! bit) $ sum $ take bit diff
             | otherwise                =      doit (bit - 1)
    diff = [max 0 $ sum $ [if ai .&. msb /= 0 then -msb else msb | ai <- a] | msb <- map (shift 1) [0..50]]


Measured memory_bytes: 67964
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}
fn func(a: i64, b: i64, x: i64) -> i64 {
    (a * x) / b - a * (x / b)
}

fn main() {
    let v = read_vec::<i64>();
    let (a, b, n) = (v[0], v[1], v[2]);
    if b > n {
        println!("{}", func(a, b, n));
    } else {
        println!("{}", func(a, b, b - 1));
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

void solve(){
    int n;
    cin >> n;

    list<ll> b;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        if (i & 1) {
            b.push_back(a);
        }else{
            b.push_front(a);
        }
    }

    if (n % 2 == 0) {
        b.reverse();
    }

    for (list<ll>::iterator it=b.begin(); it!=b.end(); it++) {
      if (it == b.begin()) {
        cout << *it;
      }else{
        cout << " " << *it;
      }
    }
    cout << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll r;cin >> r;
  cout << r * r << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main()
{
  char str[100];
  gets(str);
  int l=strlen(str);
  int count =0;
  int yes=0;
  for(int i=0;i<l/2;i++) // 0 1 2 3 4 5 6
  {
      if(str[i]!=str[l-1-i])
      {
          count++;
      }
  }
  if(count==0)
  {
      yes++;
  }
  count =0;
  for(int i=0;i<l/2;i++)
  {
      if(str[i]!=str[(l-3)/2-i])
      {
          count++;
      }
  }
  if(count==0)
  {
      yes++;
  }
  count =0;
   for(int i=(l+1/2);i<l;i++)
  {
      if(str[i]!=str[l-1-i])
      {
          count++;
      }
  }
  if(count==0)
  {
      yes++;
  }
  if(yes==3)
  {
      printf("Yes");

  }
  else printf("No");
}


Measured memory_bytes: 1592
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <limits>
#include <bits/stdc++.h>
#include <queue>
#include <type_traits>
#include<cstdint>
using namespace std;
using ld=long double;
ld T;
ld cal(ld x){
    return T-x*0.006;
}
int main(){
    ld N,A;
    cin >> N >> T >> A;
    ld m=1e9;
    ld reg;
    for(ld i=0;i<N;i++){
        ld h;
        cin >> h;
       // cout<<abs(cal(h))<<endl;
        if(abs(cal(h)-A)<m){
            reg=i;
            m=abs(cal(h)-A);
        }
    }
    cout << reg+1<< endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main()
{
    // 整数の入力
	string s;
  	bool check = false;

    cin >> s;
    for(int i=0;i<4;i++){
        if(s[i]==s[i+1]){
            check = true;
        }
    }
  	if(check){
      cout << "Bad" << endl;
      return 0;
    }
  
  cout << "Good" << endl;
  return 0;
    
}


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

int main(){
long long a,b,x;
cin >> a >> b >> x;
long long left = a/x;
if(left*x < a){
if((left+1)*x > b){
cout << 0 << '\n';
}else{
if( b % x == 0 ){
cout << (1 + (b-a)/x) << '\n';
}else{
long long temp = (left+1)*x;
cout << (1 + (b-temp)/x) << '\n';
}
}
}else{
cout << (1 + (b-a)/x) << '\n';
}
}

Measured memory_bytes: 3184
#include <iostream>
using namespace std;
#define ll long long
 
ll x,y,a,b;
 
int main(){
    cin>>x>>y;
    b=(y-2*x)/2;
    a=x-b;
    //cout<<a<<" "<<b<<endl;
    if(a*2+4*b==y && b+a==x && a>=0 && b>=0) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3644
#include <stdio.h>

int gcd(int s, int t)
{
    if (t == 0) return s;
    return gcd(t, s % t);
}

int main(void)
{
    int n, k;
    scanf("%d%d", &n, &k);
    int m = 0, g;
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        m = a > m? a: m;
        g = i? gcd(g, a): a;
    }
    if (k <= m && k % g == 0) printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");
    return 0;
}


Measured memory_bytes: 128
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		String s = sc.next();
		sc.close();
		String s1 = s.substring(0, s.length()/2);
		String s2 = new StringBuffer(s.substring((s.length()+1)/2)).reverse().toString();
		String s1a = s1.substring(0, s1.length()/2);
		String s1b = new StringBuffer(s1.substring((s1.length()+1)/2)).reverse().toString();
		out.println(s1.equals(s2)&&s1a.equals(s1b)?"Yes":"No");
	}
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
    */
int main(){
    ll A,V,B,W;
    cin >> A >> V>>B>>W;
    ll T;
    cin >> T;
    ll sa1 = abs(A - B);
    ll sa2 = V - W;
    if(sa2 <= 0)cout << "NO" << endl;
    else{
        if(sa1 <= sa2 * T)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
vector<int> a,b;
class BIT{
public:
	int n;
	vector<int> bit;
	BIT(){
		for(int i = 0; i < 200010; i++){
			bit.push_back(0);
		}
	}
	void insert(int i, int x){
		while(i <= 2*n){
			bit[i] += x;
			i += i & -i; 
		}
	}
	int count(int i){
		int sum = 0;
		while(i > 0){
			sum += bit[i];
			i -= i & -i;
		}
		return sum;
	}
};

int main(){
	LL N;
	cin >> N;
	LL all = (N * (N + 1)) / 4;
	for(int i = 0; i < N; i++){
		LL tmp;
		cin >> tmp;
		a.push_back(tmp);
		b.push_back(tmp);
	}
	sort(b.begin() ,b.end());
	int lo = 0, hi = b.size();
	while(hi -  lo > 1){
		int mid = (hi + lo) / 2;
		vector<int> c;
		c.push_back(0);
		for(auto &u:a){
			if(u >= b[mid]) c.push_back(1);
			else c.push_back(-1);
		}
		for(int i = 1; i <= N; i++){
			c[i] += c[i - 1];
		}
		for(int i = 0; i <= N; i++){
			c[i] += N + 1;
		}
		BIT bit1;
		bit1.n = N;
		LL sum = 0;
		for(int i = 0; i <= N; i++){
			
			sum += bit1.count(c[i]);
			bit1.insert(c[i], 1);
		}
		if(sum < all)hi = mid;
		else lo = mid;
	}
	cout << b[lo] << endl;
	return 0;
}

Measured memory_bytes: 3288
module Main where

import Control.Applicative
import Control.Monad
import Data.List (sort)

knss :: [Int] -> Int -> Int
knss as b = sum $ zipWith f as [1 .. length as]
  where
    f a i = abs $ a - (b + i)

main :: IO ()
main = do
    n <- readLn
    as <- fmap read . words <$> getLine
    let bs = sort $ zipWith (\a b -> a - b) as [1 .. n]
    if odd n
        then print $ knss as (bs !! (n `div` 2))
        else do
            let m = n `div` 2
            print $ minimum
                [ knss as (bs !! (m - 1))
                , knss as (bs !! m)
                ]

Measured memory_bytes: 148860
#include <bits/stdc++.h>
#define fort(i,n) for (int i = 1; i <= n; ++i)
#define ll long long
#define pi pair<int,int>
#define sz size()
#define er erase
#define fr first
#define sc second
using namespace std;

int n,m,r[100005],cnt[100005],a[100005],b[100005];
pair <pair<int,int>,int> p[100005];

int cif(int x)
{
    int t=0;
    while (x>0) x/=10, ++t;
    return t;
}

int main()
{
    cin >> n >> m;
    fort(i,m)
    {
        cin >> a[i] >> b[i];
        p[i].fr.sc=a[i], p[i].fr.fr=b[i], p[i].sc=i;
    }
    sort (p+1,p+m+1);
    fort(i,m)
        ++r[p[i].fr.sc], cnt[p[i].sc]=r[p[i].fr.sc];
    fort(i,m)
        swap(p[i].sc, p[i].fr.fr);
    sort (p+1,p+m+1);
    fort(i,m)
    {
        fort(j,6-cif(a[i]))
            cout << 0;
        cout << a[i];
        fort(j,6-cif(cnt[i]))
            cout << 0;
        cout << cnt[i] << '\n';
    }
}


Measured memory_bytes: 4224
import java.util.Map;
import java.util.Scanner;
public class Main {


    public static void main(String[] args) {
int P=-1;

        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int X = scan.nextInt();
        int C[] = new int[N];


        int A[][] = new int[N][M];
        for (int i = 0; i < N; i++) {
            C[i] = scan.nextInt();
            for (int ii = 0; ii < M; ii++) {
                A[i][ii] = scan.nextInt();
            }
        }
//入力完了


            for (int iii = 0; iii < (1 << N); iii++) {
                int PP=0;
                int S[] = new int[M];
                for (int j = 0; j < N; j++) {

                    if ((1 & iii >> j) == 1) {
                        for(int y=0;y<M;y++){S[y]=S[y]+A[j][y];}
                        PP=PP+C[j];
                    }

                }
                int K=0;
             for(int p=0;p<M;p++) {if(S[p]>=X){K=K+1;}  }
             if (K==M&&(P==-1||P>=PP)){P=PP;}
            }

        System.out.println(P);
    }

}



Measured memory_bytes: 37560
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
using itn = int;
using namespace std;
using Graph = vector<vector<int>>;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main() {
	ll N,M;
	cin >> N >> M;
	vector<ll> a[200000];
	rep(i,M){
		ll from,to;
		cin>>from>>to;
		a[from].push_back(to);
	}
	for(int i=0; i<a[1].size(); i++){
		ll tmp=a[1][i];
		for(int j=0; j<a[tmp].size(); j++){
			if(a[tmp][j]==N){
				cout<<"POSSIBLE"<<endl;
				return 0;
			}
		}
	}
	cout<<"IMPOSSIBLE"<<endl;
}

Measured memory_bytes: 8832
import scala.math

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  def divisors(n: Int): List[Int] =
    for (i <- (1 to n).toList if n % i == 0) yield i

  var n = sc.nextInt()
  var d = Array.fill(n)(sc.nextInt()).sorted
  println((d(0) - d(n-1)).abs)
}


Measured memory_bytes: 55632
import java.util.Scanner;

public class Main {
	public static void main(String [] args){
		//????????£????????????????????????
		Scanner sc = new Scanner(System.in);
		//W?????????
		int W = sc.nextInt();
		//H?????????
		int H = sc.nextInt();
		//x?????????
		int x = sc.nextInt();
		//y?????????
		int y = sc.nextInt();
		//r?????????
		int r = sc.nextInt();
		
		//?????¶??? 
		if(x-r >= 0 && y-r >= 0 && x+r <= W && y+r <= H ){
			//??¨????????????????????°Yes?????¨???
			System.out.println("Yes");
		}else{
			//No?????¨???
			System.out.println("No");
		 }
	}
}

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

#define PI 3.14159265359

int main() {
	int n, x[100], y[100], i, s[100], max = 0;
	double result = 0;
	scanf("%d", &n);
	for(i = 0; i < n; ++i) {
		scanf("%d", &x[i]);
	}
	for(i = 0; i < n; ++i) {
		scanf("%d", &y[i]);
		s[i] = x[i] - y[i];
	}
	for(i = 0; i < n; i++) {
		if(s[i] < 0) {
			result -= (double)s[i];
			if(max < -s[i]) max = -s[i];
		}
		else {
			result += (double)s[i];
			if(max < s[i]) max = s[i];
		}
	}
	printf("%f\n", result);
	result = 0;
	for(i = 0; i < n; i++) {
		result += pow((double)s[i], 2.0);
	}
	result = sqrt(result);
	printf("%f\n", result);
	result = 0;
	for(i = 0; i < n; i++) {
		if(s[i] < 0) result -= pow((double)s[i], 3.0);
		else result += pow((double)s[i], 3.0);
	}
	result = cbrt(result);
	printf("%f\n", result);
	result = 0;
	printf("%f\n", (double)max);
	
	return 0;
}


Measured memory_bytes: 2132
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll mod = 1e9 + 7;
ll powmod(ll a, ll b) { ll res=1; a%=mod; assert(b>=0); for(;b;b>>=1) { if(b&1) res=res*a%mod; a=a*a%mod; } return res; }
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a; }

int main() {
    ll x;
    cin >> x;
    
    ll p = 100, cnt = 0;
    while(p < x) {
        p += (p / 100);
        ++cnt;
    }

    cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;
const double INF = (1e15), EPS = (1e-10);

struct P{
  double X, Y, Z;
};

P operator+(P a, P b){ return (P){a.X+b.X, a.Y+b.Y, a.Z+b.Z};}
P operator*(P a, double c){ return (P){a.X*c, a.Y*c, a.Z*c};}
P operator*(double c, P a){ return a*c;}
P operator/(P a, double c){ return a*(1/c);}
P operator/(double c, P a){ return a*(1/c);}
P operator-(P a){ return -1*a;}
P operator-(P a, P b){ return a+(-b);}

double dot(P a, P b){ return a.X*b.X + a.Y*b.Y + a.Z*b.Z;}
double len(P a){ return sqrt(dot(a,a));}
P projection(P a, P b){ return b/len(b)*dot(a, b/len(b));}
P line_symmetry(P x, P a, P b){ return 2*a + 2*projection(x-a,b-a) - x;}

int main(){
  int N;
  while(cin >> N, N){
    double u, v, w;
    cin >> u >> v >> w;
    P d = {u, v, w};
    vector<P> V;
    vector<double> R(N);
    for(int i = 0; i < N; ++i){
      double x, y, z, r;
      cin >> x >> y >> z >> r;
      V.push_back((P){x,y,z});
      R[i] = r;
    }
    P p = {0,0,0};
    while(1){
      int id = -1;
      double l = INF;
      for(int i = 0; i < N; ++i){
        if(dot(d,V[i] - p) < EPS) continue;
        P proj = projection(V[i]-p,d);
        double r = R[i];
        if(dot(V[i]-p,V[i]-p) - dot(proj,proj) > r*r + EPS) continue;
        double l_ = len(proj) - sqrt(r*r-dot(V[i]-p,V[i]-p)+dot(proj,proj));
        //cerr << i << "; " << l_ << endl;
        if(l_ > EPS && l_ < l){
          l = l_;
          id = i;
        }
      }
      if(id < 0) break;
      P q = p + l/len(d)*d;
      //assert(dot(q-V[id],q-V[id]) - R[id]*R[id] < EPS);
      //printf("Error = %.12f\n",dot(q-V[id],q-V[id]) - R[id]*R[id]);
      d = line_symmetry(p,V[id],q) - q;
      p = q;
      //cerr << id << " ; ";
      //cerr << "(" << p.X << ", " << p.Y << ", " << p.Z << "), ";
      //cerr << "(" << q.X << ", " << q.Y << ", " << q.Z << ")" << endl;
    }
    printf("%.12f %.12f %.12f\n",p.X,p.Y,p.Z);
  }
  return 0;
}



Measured memory_bytes: 3356
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+5;
int fa[maxn],sz[maxn];
int getfa(int n) {
	return fa[n]==n?n:fa[n]=getfa(fa[n]);
}
int main() {
 	int n,m;cin>>n>>m;
 	for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
 	for(int i=1;i<=m;i++) {
 		int u,v;cin>>u>>v;
 		u=getfa(u);v=getfa(v);
 		if(u==v) continue;
 		sz[u]+=sz[v];
 		fa[v]=u;
 	}   
 	int ans=0;
 	for(int i=1;i<=n;i++) {
 		ans=max(ans,sz[getfa(i)]);
 	}
 	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5356
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   1000000007
#define PI 2*acos(0.0)
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
#define N 200005
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};


ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}



//=============================================ASIFAZAD==============================================//

int32_t main()
{
    io;
    int n;
    cin>>n;
    vi inp(n);
    for(auto& x: inp) cin>>x;
    int ans = INT_MAX;
    for(int i = 1; i<= 100; i++)
    {
        int ac = 0;
        for(auto x: inp)
            ac += (x-i)*(x-i);
        ans = min(ans, ac);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
using namespace	std;
int main(){

  int n,s1=1145141919,s2,result=-1145141919;

  cin>>n>>s2;
  for(int i=1;i<n;i++){
    s1=min(s1,s2);
    cin>>s2;
    result=max(result,s2-s1);
  }

  cout<<result<<endl;

  return 0;

}

Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int dp[201010];

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

    int ans=0;
    rep(i,n){
        int x=p[i];
        dp[x]=dp[x-1]+1;
        ans=max(ans,dp[x]);
    }

    cout<<n-ans<<endl;
}

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

int main() {
	int a, p;
	cin >> a >> p;
	int n;
	n = 3 * a + p;
	int ans;
	ans = (n - n % 2) / 2;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define foro(i, n) for(i=0; i<n; i++)
#define forl(i, n) for(i=1; i<=n; i++)
#define x first
#define y second
constexpr int INF = 1e9 + 1;
constexpr ll LLINF = 1e18 + 1;


int main()
{
	int i, j, k, l, tmp;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	ll arr[n];
	vector<ll> count(n+1);
	ll ans=0;
	foro(i, n){
		cin >> arr[i];
		count[arr[i]]++;
	}
	forl(i, n){
		ans += (count[i] * (count[i]-1)) >> 1;
	}
	ll sub;
	foro(i, n){
		sub = (count[arr[i]]-1);
		printf("%lld\n", ans-sub);
	}
}



Measured memory_bytes: 5760
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;


public class Main {

	public static void main(String[] args) {
		try {
			BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
			int n = Integer.parseInt(bf.readLine());

			// 各頂点につながっている頂点・距離をまとめる
			Map<Integer, Map<Integer, Integer>> connectMap = new HashMap<Integer, Map<Integer, Integer>>();
			for (int i = 1; i < n; i++) {
				String[] input = bf.readLine().split(" ");
				int from = Integer.parseInt(input[0]);
				int to = Integer.parseInt(input[1]);
				int range = Integer.parseInt(input[2]);

				if (!connectMap.containsKey(from)) {
					connectMap.put(from, new HashMap<Integer, Integer>());
				}
				connectMap.get(from).put(to, range);
				if (!connectMap.containsKey(to)) {
					connectMap.put(to, new HashMap<Integer, Integer>());
				}
				connectMap.get(to).put(from, range);
			}
			bf.close();

			// 頂点番号1を基準に、そこからの距離が偶数なら同色、違ったら異色に塗り替えていく
			int start = 1;
			int[] colors = new int[n + 1];
			colors[start] = 1;
			for (Integer next : connectMap.get(start).keySet()) {
				changeColor(start, next, connectMap, colors);
			}

			// 出力
			for (int i = 1; i < colors.length; i++) {
				System.out.println(colors[i]);
			}
		} catch (Exception e) {
		}
	}

	private static void changeColor(int from, int curr, Map<Integer, Map<Integer, Integer>> connectMap, int[] colors) {

		// 距離が偶数なら前の頂点と同じ色、奇数なら違う色（0→1 or 1→0）
		int range = connectMap.get(from).get(curr);
		colors[curr] = (range % 2 == 0 ? colors[from] : Math.abs(colors[from] - 1));

		// 現在の頂点につながっているほかの頂点にも同じことを繰り返す
		for (Integer next : connectMap.get(curr).keySet()) {
			if (next == from) {
				continue;
			}
			changeColor(curr, next, connectMap, colors);
		}
	}
}


Measured memory_bytes: 109440
//People only find me interesting because they can't tell whether I'm serious or not
//#include <boost/multiprecision/cpp_int.hpp> 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
typedef double db;
typedef __int128 s128;
typedef __uint128_t u128;
typedef unsigned long long u64;
#define int long long int
#define P 1000000007
#define Q 1000000006
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define umll unordered_map<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 100005
#define PI 3.14159265359
#define inf LLONG_MAX
//using namespace boost::multiprecision; 
using namespace __gnu_pbds;
using namespace std;
ll dp[N];
void solve(){
    ll n;
    cin>>n;
    vl h(n);
    f(i,0,n) cin>>h[i];
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    f(i,2,n) dp[i] = min(abs(h[i]-h[i-1]) + dp[i-1], abs(h[i]-h[i-2]) + dp[i-2]);
    cout<<dp[n-1];
}
signed main() {
    teevra_gati
    
       
    solve();

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
using ll = long long;
int main(){ 
    ll a,b,c;
    cin>>a>>b>>c;
    if(c-a+b>=0){
    cout<<c-a+b;}
    else{
        cout<<0;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef long double td;
typedef vector<td> vd;
typedef pair<ll,ll> ii;
typedef vector<ii> vii; typedef vector<bool> vb;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(ll i = ll(a); i < (ll)(b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define show(v,n) cerr << #v << " = "; forn(i,n) cerr << v[i] << " "; cerr << endl;
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
int MAXN = 500005;


ll solve(vector <int> &v, int n, int k)
{
	ll MAXN = (ll)(1e18);
	vector <ll> dp(n,MAXN);
	dp[0]=0;
	forr(i,1,n)
	{
		forr(j,1,k+1)
		{
			if(i-j < 0) break;
			dp[i]=min(dp[i],dp[i-j]+abs(v[i]-v[i-j]));
		}
	}
	return dp[n-1];
}
 
int main()
{ 	
	FIN;
	#ifdef input
		freopen("test1.txt", "r", stdin);
	#endif

	int n, k;
	cin >> n >> k;
	vector <int> v(n);
	forn(i,n) cin >> v[i];
	cout << solve(v,n,k) << endl;
    return 0;
}


Measured memory_bytes: 4508
#include <stdio.h>
#include <iostream>
using namespace std;

class Adjl{
private:
	int u;
	int k;
	int *v;
public:
	Adjl(int u, int k);
	~Adjl(){ delete[] v; }
	void setV(int vk);
	void printAdjm(int n);
};

Adjl::Adjl(int u, int k)
{
	this->u = u;
	this->k = 0;
	v = new int[k];
}

void Adjl::setV(int vk)
{
	v[k] = vk;
	k++;
}

void Adjl::printAdjm(int n)
{
	int j = 0;
	for (int i = 1; i <= n; i++) {
		if (j < k && v[j] == i) {
			cout << "1";
			j++;
		}
		else {
			cout << "0";
		}
		if (i < n) cout << " ";
		else cout << endl;
	}
}

int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int u, k;
		cin >> u >> k;
		Adjl *adjl = new Adjl(u, k);
		for (int j = 0; j < k; j++) {
			int vk;
			cin >> vk;
			adjl->setV(vk);
		}
		adjl->printAdjm(n);
		delete adjl;
	}

	return 0;
}

Measured memory_bytes: 3064
C1 = list(map(int,input().split()))
C2 = list(map(int,input().split()))
C3 = list(map(int,input().split()))
a = 0
if C2[0] - C1[0] == C2[1] - C1[1] == C2[2] - C1[2]:
  a2 = C2[0] - C1[0]
  a+= 1
if C3[0] - C2[0] == C3[1] - C2[1] == C3[2] - C2[2]:
  a3 = C3[0] - C2[0]
  a+= 1
if a == 2:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 38384
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

bool check(string s){
	bool res = true;
	if(s.size() <= 1) return res;
	for(int i = 1; i < s.size(); i++){
		if(s[i - 1] != s[i]) res = false;
	}
	return res;
}

int main(){
	string s1, s2;
	cin >> s1;
	s2 = s1;
	sort(begin(s2), end(s2));
	s2.erase(unique(begin(s2), end(s2)), end(s2));
	int ans = 100;
	for(int i = 0; i < s2.size(); i++){
		int cnt = 0;
		string t = s1;
		while(!check(t)){
			string u = "";
			for(int j = 0; j < t.size() - 1; j++){
				if(t[j] == s2[i] || t[j + 1] == s2[i]){
					u.push_back(s2[i]);
				} else{
					u.push_back(s1[j]);
				}
			}
			cnt++;
			t = u;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}


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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 2e5 + 5;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);


void solve(int testCase){

    int n;
    ll  W;
    scanf("%d %lld" , &n , &W);

    vi v(n) , w(n);

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

    vl dp(sum + 1 , INF);
    dp[0] = 0;
    for(int i = 0 ; i < n ; i ++){
            for(int curr_value = sum ; curr_value >= 0 ; curr_value --){
                    if(curr_value - v[i] >= 0)
                    dp[curr_value] = min(dp[curr_value] , dp[curr_value - v[i]] + 1ll * w[i]);
            }
    }

    int ans = 0;
    for(int i = 0 ; i <= sum ; i ++){
            if(dp[i] <= W)ans = i;
    }

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

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


Measured memory_bytes: 1024
// Problem: B - Distance
// Contest: AtCoder - AtCoder Beginner Contest 174
// URL: https://atcoder.jp/contests/abc174/tasks/abc174_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// Muallif: Azimjon Mehmonali o'g'li

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define F first
#define S second
#define pb push_back
#define endl "\n"

#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(ALL(a))
#define rSORT(a) sort(rALL(a))
#define REV(a) reverse(ALL(a))
#define sqr(x) ((x) * (x))

//===========================================================

int recur_depth = 0;
#ifdef DEBUG
#define xtp(x)                                                           \
	{                                                                    \
		++recur_depth;                                                   \
		auto x_ = x;                                                     \
		--recur_depth;                                                   \
		cerr << string(recur_depth, '\t') << __func__ << ":" << __LINE__ \
			 << "\t" << #x << " = " << x_ << endl;                       \
	}
#else
#define xtp(x)
#endif
template <typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(
	Ostream& os, const Cont& v) {
	os << "[";
	for (auto& x : v) {
		os << x << ", ";
	}
	return os << "]";
}
template <typename Ostream, typename... Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
	return os << "{" << p.first << ", " << p.second << "}";
}

//===========================================================

#define TEZ                  \
	ios::sync_with_stdio(0); \
	cin.tie(0);

const long double PI = 3.1415926535897932384626433832795;
const ll mod = 1000000007LL;
const int INF = 1000000000;
const ll LINF = 1000000000000000000LL;

int main() {
	TEZ;

	ll n, d;
	cin >> n >> d;

	ll x, y;
	int jv = 0;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;

		if (sqrt(x * x + y * y) <= d) jv++;
	}

	cout << jv << endl;

	return 0;
}


Measured memory_bytes: 3696
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    Q = int(input())
    ans = sum(A)
    for _ in range(Q):
        b,c = map(int, input().split())
        x = C[b]
        ans += (c-b) * x
        C[b] = 0
        C[c] += x
        print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 88888
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    int n, k;
    cin >> n >> k;
    int ans = 0;
    while(n){
        n /= k;
        ans++;
    }
    cout << ans << endl;
    return;
}

int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
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;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] <= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) left = mid;
		else right = mid;
	}
	/* left は条件を満たす最大の値、right は条件を満たさない最小の値になっている */
	return left;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int main() {
	int n, k;
	cin >> n >> k;
	vector<int>v;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		v.push_back(p);
	}
	sort(v.begin(), v.end());
	int ans = 0;
	for (int i = 0; i < k; i++) {
		ans = ans + v[i];
	}
	cout << ans;
}

Measured memory_bytes: 3644
#include <iostream>
#include <math.h>
using namespace std;
int main() {
	while (1) {
		/*for (int i = 0; i < n; i++) {
			e[i] = 0;
		}
		for (int i = 0; i < 4000; i++) {
			m[i] = 0;
			pr[i] = 0;
		}
		na = 1;*/
		int n = 0, p, q, na = 1, e[4000] = {}, pr[4000] = {};
		unsigned long long int m[4000] = {};

		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++) {
			cin >> e[i] >> p >> q;
			m[e[i] - 1] += p * q;
			if (m[e[i] - 1] >= 1000000 && pr[e[i] - 1] == 0) {
				cout << e[i] << endl;
				pr[e[i] - 1] = 1;
				na = 0;
			}
		}
		
		if (na)
			cout << "NA\n";

	}
	return 0;
}


Measured memory_bytes: 3044