akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define int ll
ll solve(vector<P> vec){
  vector<ll> comp;
  ll n=vec.size(),res=0;
  for(int i=0;i<n;i++){
    comp.push_back(vec[i].first);
    comp.push_back(vec[i].first+vec[i].second);
  }
  sort(comp.begin(),comp.end());
  comp.erase(unique(comp.begin(),comp.end()),comp.end());
  vector<ll> imos(comp.size()+100,0);
  for(int i=0;i<n;i++){
    ll Llb=lower_bound(comp.begin(),comp.end(),vec[i].first)-comp.begin();
    ll Rlb=lower_bound(comp.begin(),comp.end(),vec[i].first+vec[i].second)-comp.begin();
    imos[Llb]++;
    imos[Rlb]--;
  }
  for(int i=1;i<imos.size();i++) imos[i]+=imos[i-1];
  for(int i=0;i<imos.size()-1;i++) res+=(imos[i]>0?(ll)1:(ll)0)*(comp[i+1]-comp[i]);
  return res;
}
signed main(){
  ll n,x,d;
  cin>>n>>x>>d;
  if(d<0){
    d=abs(d);
    x-=(n-1)*d;
  }
  else if(d==0){
    if(x==0) cout<<1<<endl;
    else cout<<n+1<<endl;
    return 0;
  }
  vector<P> vec;
  vector<ll> comp;
  for(ll k=0;k<=n;k++){
    ll kx=k*x;
    ll l=k*(k-1)/2;
    ll r=(2*n-k-1)*k/2;
    r++;
    ll r2=r-l;
    ll md=kx%d;
    if(md<0){
      md+=d;
      md%=d;
    }
    comp.push_back(md);
    vec.push_back(P(kx+l*d,r2));
  }
  sort(comp.begin(),comp.end());
  comp.erase(unique(comp.begin(),comp.end()),comp.end());
  vector<P> vc[comp.size()+5];
  for(int i=0;i<vec.size();i++){
    ll md=vec[i].first%d;
    if(md<0) {
      md+=d;
      md%=d;
    }
    ll pos=lower_bound(comp.begin(),comp.end(),md)-comp.begin();

    ll nk=(vec[i].first-md)/d;
    vc[pos].push_back(P(nk,vec[i].second));
  }
  ll ans=0;
  for(int i=0;i<comp.size();i++){
    ans+=solve(vc[i]);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 18912
#include "bits/stdc++.h"

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=(n); i--)
#define LREP(lst,itr) for(auto itr = lst.begin(); itr != lst.end(); ++itr)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define P(s) cout<<(s)<<endl
#define P2(a, b) cout<<(a)<<" "<<(b)<<endl
#define V2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

vector<int> z_algorithm(const string &s) {
    vector<int> prefix(s.size());
    for(int i = 1, j = 0; i < s.size(); i++) {
        if(i + prefix[i - j] < j + prefix[j]) {
            prefix[i] = prefix[i - j];
        }else{
            int k = max(0, j + prefix[j] - i);
            while(i + k < s.size() && s[k] == s[i + k]) ++k;
            prefix[i] = k;
            j = i;
        }
    }
    prefix[0] = (int)s.size();
    return prefix;
}

int main(){
    int N;
    string S;
    cin >> N >> S;
    int maxi=0;
    REP(i,0,N){
        vector<int> vec;
        vec=z_algorithm(S.substr(i,N));
        REP(j,0,vec.size()){
            if(vec[j]<=j){
                maxi=max(maxi,vec[j]);
            }
        }
    }
    P(maxi);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(vector<ll> arr, ll n){
    vector<ll> temp(n);
    temp[0] = 0;
    temp[1] = abs(arr[1] - arr[0]);
    for(ll i = 2; i < n; i++){
        temp[i] = min(temp[i - 1] + abs(arr[i] - arr[i - 1]), temp[i - 2] + abs(arr[i] - arr[i - 2]));
    }
    return temp[n - 1];
}
int main(){
    ll n;
    cin>>n;
    vector<ll> arr(n);
    for(auto &i: arr) cin>>i;
    cout<<solve(arr, n);
    return 0;
}

Measured memory_bytes: 2560
def solve(K):
 # if K % 2 == 0:
  #  return -1
 # if K % 5 == 0:
 #   return -1
  current = 7 % K
  for i in range(K + 10):
    if current == 0:
      return i+1
    current = (current * 10 + 7 )% K
  return -1

K = int(input())
print(solve(K))



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

int main(void){
    string s,t;
    cin >> s >> t;
    s += t;
    int a = stoi(s),b = 0;
    for(int i = 1;i*i <= a;i++){
        if(i*i == a)b = 1;
    }
    if(b == 1)cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

typedef unsigned long long UL;
typedef long long LL;
typedef long double LD;
#define LP(i, a, b) for (int i = int(a); i < int(b); i++)
#define LPE(i, a, b) for (int i = int(a); i <= int(b); i++)
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<vector<PII> > WAL;
typedef vector<vector<int> > SAL;
#define Ep 1e-8
#define INF 1e9
#define LINF 1e18

/*
 shifting symmetric/complementary gives same result => because they are same anyway?!

 claim: if (A, B) is good, then (A+1, B+1) is good too
 proof:
 S[(i+A) % N, (j+B) % N] = Sjj

 r^n = first period

 */

int const MaxSize = 300 + 5;
int N;
string S[MaxSize];
char m[MaxSize][MaxSize];

bool good(int shift) {

	LP(r, 0, N)
	{
		int mr = (r + shift) % N;

		LP(c, 0, N)
		{
			m[mr][c] = S[r][c];
		}
	}

	LP(i, 0, N)
	{
		LP(j, 0, i)
		{
			if (m[i][j] != m[j][i])
				return false;
		}
	}

	return true;
}

int main() {

	ios_base::sync_with_stdio(false);
	//freopen("/Users/georgeli/A_1.in", "r", stdin);
	cin >> N;
	LP(i, 0, N)
	{
		cin >> S[i];
	}

	int ans = 0;
	LP(shift, 0, N)
	{
		if (good(shift)) {
			ans += N;
		}
	}

	cout << ans;

	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

const string YES = "Yes";
const string NO = "No";

void solve(long long K, long long X){
  if(500*K>=X){
    cout<<YES<<endl;
  }else{
    cout<<NO<<endl;
  }
}

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


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}

int main(){
    ll a,b,c;cin>>a>>b>>c;
    ll res = 0;
    if(a==b && b==c && a%2==0){
        cout<<-1<<endl;
        return 0;
    }
    while(1){
        if(a%2!=0 || b%2!=0 || c%2!=0)break;
        ll aa = a,bb = b,cc = c;
        a = (bb+cc)/2;
        b = (aa+cc)/2;
        c = (aa+bb)/2;
        res++;
    }
    cout<<res<<endl;
}



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

int K;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>K;
	for(int i = 1;i <= K;i++){
		cout<<"ACL";
	}
	cout<<endl;
}


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

using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
//#define int ll

const int md = 1000000007;
const int INF = 1<<30;

int main(){
    string s;  cin >> s;
    int ans = 0;
    bool f = false;
    rep(i,3){
        if(s[i] == 'R'){
            if(!f){
                ans = 1;
                f = true;
            }else{
                ans += 1;
            }
        }else{
            f = false;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3588
/*||>>>> Praveen Ojha <<<<>>>> 16 June 2019 <<<<>>>> 15:04:02 <<<<||*/
// #pragma GCC optimize("Ofast") //(Very Fast but Inaccurate)
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //(Small operations in many loops)
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf 1e18+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> > 
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
//Read Problems Carefully & Check for corner cases N=0,1 ?
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

int32_t main(){__
	int x,a;
	cin>>x>>a;
	if(x<a)
		cout<<0<<"\n";
	else
		cout<<10<<"\n";
return 0;
}

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

const int MAX = 210000;
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() {
    int N, M, K;
    cin >> N >> M >> K;

    COMinit();
    long long res = 0;
    long long com = COM(N * M - 2, K - 2);
    for(int d=1; d<N; ++d) {
        res += com * d * (N - d) * M * M % MOD;
        res %= MOD;
    }
    for(int d=1; d<M; ++d) {
        res += com * d * (M - d) * N * N % MOD;
        res %= MOD;
    }
    cout << res << endl;
}

Measured memory_bytes: 5120
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rel register ll
#define rec register char
#define gc getchar
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++)
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) pc('-'),x=-x;
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int yuzu=2e5;
typedef int fuko[yuzu|10];
fuko a,b;
int main() {
  int n,k,i,t;
  read(n),read(k);
  for (i=1;i<=n;++i) a[i]=read();
  for (t=1;t<=min(k,50);++t) {
    memset(b,0,sizeof b);
    for (i=1;i<=n;++i) 
      b[max(1,i-a[i])]++,b[min(n,i+a[i])+1]--;
    for (i=1;i<=n;++i) b[i]+=b[i-1];
    memcpy(a,b,sizeof b);
  }
  for (i=1;i<=n;++i) printf("%d ",b[i]);
}

Measured memory_bytes: 5284
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int matrix[][] = new int[3][3];

		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				matrix[i][j] = sc.nextInt();
			}
		}

		for(int j = 0; j < 2; j++){
			for(int i = 1; i < 3; i++){
				if(matrix[i - 1][j] - matrix[i - 1][j + 1] != matrix[i][j] - matrix[i][j + 1]){
					System.out.println("No");
					return;
				}
			}
		}
		for(int i = 0; i < 2; i++){
			for(int j = 1; j < 3; j++){
				if(matrix[i + 1][j - 1] - matrix[i][j - 1] != matrix[i + 1][j] - matrix[i][j]){
					System.out.println("No");
					return;
				}
			}
		}

		System.out.println("Yes");
	}


}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define Ans(f, y, n) if(f) cout << y << endl; else cout << n << endl;
#define int long long
#define INF 1000000000000000000
using namespace std;

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
template<typename T>
void debug(vector<vector<T>> m){ REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl;} }



signed main(){

    int L; cin >> L;
    vec A(L); readv(A);

    mat dp(L + 1, vec(5, INF));
    REP(i, 5) dp[0][i] = 0;
    REP(i, L){
        REP(j, 5){
            if(j == 0 || j == 4) dp[i + 1][j] = dp[i][j] + A[i];
            else if(j == 1 || j == 3){
                if(A[i] >= 2) dp[i + 1][j] = dp[i][j] + A[i] % 2;
                else dp[i + 1][j] = dp[i][j] + 2 - A[i];
            }else dp[i + 1][j] = dp[i][j] + (A[i] + 1) % 2;
        }
        FOR(j, 1, 5) Min(dp[i + 1][j], dp[i + 1][j - 1]);
    }
    //debug(dp);
    cout << dp[L][4] << endl;

    return 0;
}


Measured memory_bytes: 15872
/***********************************************
#
#      Filename: a.cpp
#
#        Author: Comsyl - ylsong15@fudan.edu.cn
#   Description: ---
#        Create: 2017-05-19 20:12:30
***********************************************/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000 + 5;
string sa[maxn];
string sz[maxn];

int main()
{
    int N;
    cin >> N;
    string x;
    for (int i = 0; i < N; ++ i) {
        cin >> x;
        for (int j = 0; j < x.length(); ++ j) {
            sa[i] += x[j] == '?' ? 'a' : x[j];
            sz[i] += x[j] == '?' ? 'z' : x[j];
        }
    }
    cin >> x;
    int l = 0, g = 0;
    for (int i = 0; i < N; ++ i) {
        if (sz[i] < x) ++ l;
        else if (sa[i] > x) ++ g;
    }

    for (int i = l+1; i <= N+1-g; ++ i) {
        if (i == l+1) cout << i;
        else cout << " " << i;
    }
    cout << endl;
    return 0;
}


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

typedef long long ll;

int main() {
    ll N, M, K;
    cin >> N >> M >> K;
    vector<ll>A(N);
    vector<ll>B(M);
    vector<ll>a(N+1, 0);
    vector<ll>b(M+1, 0);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
        a[i+1] = a[i] + A[i];
    }
    for (ll i = 0; i < M; i++) {
        cin >> B[i];
        b[i+1] = b[i] + B[i];
    }


    int j = M;
    ll ans = 0;
    for (int i = 0; i <= N; i++) {
        if (a[i] > K) {
            break;
        }
        while (true) {
            if (b[j] <= K-a[i]) {
                break;
            } else {
                j--;
            }
        }
        ans = max(ans, (ll)(i+j));
    }
    cout << ans << endl;
}


Measured memory_bytes: 9584
#include <bits/stdc++.h>
using namespace std;
int point[100];
int main(){
	int n,m;	cin>>n>>m;
	int a[m];	for(int i=0;i<m;i++){	cin>>a[i];	a[i]--;	}
	int b[n];
	for(int t=0;t<m;t++){
		for(int i=0;i<n;i++){
			cin>>b[i];	b[i]--;
			if(b[i]==a[t])	point[i]++;
			else 			point[a[t]]++;
		}
	}
	for(int i=0;i<n;i++)	cout<<point[i]<<endl;
	return 0;
}

Measured memory_bytes: 1160
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

#n,m = ips()
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!

n = ip()
a = iprow()
a.sort()
if a[n//2-1] == a[n//2]:
    print(0)
else:
    print(a[n//2]-a[n//2-1])

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

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

V<int> a;

bool check(int md) {
    using P = pair<int, int>;
    V<P> st;
    int _b = 0;
    for (int d: a) {
        int b = _b; _b = d;
        if (b < d) {
            st.push_back(P(b, 0));
            continue;
        }
        while (d <= st.back().first) st.pop_back();
        int p = d;
        while (st.size() && st.back().second == md - 1) {
            p = st.back().first;
            st.pop_back();
        }
        if (!st.size()) return false;
        int la = st.back().second;
        if (st.back().first == p - 1) st.pop_back();
        st.push_back(P(p - 1, la + 1));
        if (p != d) st.push_back(P(p, 0));
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;
    int n;
    cin >> n;
    a = V<int>(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int lw = 0, up = n + 10;
    while (up - lw > 1) {
        int md = (lw + up) / 2;
        if (!check(md)) {
            lw = md;
        } else {
            up = md;
        }
    }
    cout << up << endl;
    return 0;
}


Measured memory_bytes: 4692
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <numeric>
#include <utility>
#include <ctime>
#define INF 100000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;
/*---------------------------------------------------*/

int main(){
  string s,ss;
  cin>>s;
  if(s.size()==1){
    cout<<0<<endl;
    return 0;
  }
  
  int cnt=0;
  rep(i,s.size()){
    if(s[i]!='x'){
      ss+=s[i];
    }else{
      cnt++;
    }
  }

  rep(i,ss.size()){
    if(ss[i]!=ss[ss.size()-1-i]){   
      cout<<-1<<endl;
      return 0;
    }
  }

  vi diff;
  cnt=0;
  rep(i,s.size()){
    if(s[i]!='x'){
      diff.pb(cnt);
      cnt=0;
    }else{
      cnt++;
    }
  }
  diff.pb(cnt);
  int ans=0;
  for(int i=0;i<diff.size()/2;i++){
    ans+=abs(diff[i]-diff[diff.size()-1-i]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1216
// 自力AC まあ初期のころだったから多少はね？ write-6min
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int>a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort (a.begin(), a.end(), greater<int>());
  int sum = 0;
  for (int i = 1; i < n; i++) {
    sum += a[i];
  }
  if (a[0] < sum) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int,int> pii;

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	ll m;
	cin >> n >> k >> m;

	vector<vl> bin(n+1, vl(n+1));
	rep(a,0,n+1){
		bin[a][0] = 1;
		rep(b,1,a+1)
			bin[a][b] = (bin[a-1][b-1] + bin[a-1][b]) % m;
	}

	vector<vl> f(n+1, vl(k+1)), F(n+1, vl(k+1));

	rep(b,0,k+1){
		f[0][b] = 1;
		if(b > 0) rep(a,0,n+1)
			F[a][b] = (F[a][b-1] + f[a][b-1])%m;
		rep(A,0,n+1){
			rep(a,0,A)
				f[A][b] += F[a][b]*f[A-1-a][b]%m * bin[A-1][a] % m;
			f[A][b] %= m;
		}
	}
	cout << f[n][k] << endl;
}

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

int main(){
    string s;
    int m,h,count=0;
    while(true){
        cin>>s;
        if(s=="-")break;
        else{
            cin>>m;
            for(int i=0;i<m;i++){
                cin>>h;
                int tmp=count;
                for(int j=tmp;j<tmp+h;j++){
                    s+=s[j];
                    count++;
                }
            }
            for(int k=count;s[k]!='\0';k++)cout<<s[k];
            cout<<"\n";
        }
        count=0;
    }

    return 0;
}


Measured memory_bytes: 3204
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Code author: Saurabh Singhal
Code copy karne vaale tera muh kaala
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ppb pop_back

using namespace std;
typedef long long int ll;
typedef vector<int> vi_t;
typedef vector<ll> vll_t;
int t=1;
vll_t a,b;
int  main(){
	// #ifndef ONLINE_JUDGE
 //    // for getting input from input.txt
 //    freopen("input.txt", "r", stdin);
 //    // for writing output to output.txt
 //    freopen("output.txt", "w", stdout);
	// #endif
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	cout<<x2-y2+y1<<" "<<y2+x2-x1<<" "<<x1-y2+y1<<" "<<y1+x2-x1<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    string x,y;
    int a=0;
    cin>>x>>y;
    for(int i=0; i<x.length(); i++)
    {
        a*=10;
        a+=(x[i]-48);
    }
    for(int i=0; i<y.length(); i++)
    {
        a*=10;
        a+=(y[i]-48);
    }
    int sq=sqrt(a);
    sq*=sq;
    if(sq==a)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;


    return 0;
}


Measured memory_bytes: 3680
a,b=map(int,input().split())
if a==2:
 A=2
elif a==4 or a==6 or a==9 or a==11:
 A=1
else:
 A=3
if b==2:
 B=2
elif b==4 or b==6 or b==9 or b==11:
 B=1
else:
 B=3
if A==B:
 print("Yes")
else:
 print("No")

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


int main(){
    string s;
    cin >> s;
    ll k;
    cin >> k;
    string ans;
    REP(i, s.size() - 1){
        ll j = s.at(i) - 'a';
        ll num_until_a = 0;
        if(j != 0){
            num_until_a = 26 - j;
        }
        if(k >= num_until_a){
            ans.push_back('a');
            k -= num_until_a;
        }else{
            ans.push_back(s.at(i));
        }
    }

    ll j = s.back() - 'a';
    j = (j + k) % 26;
    ans.push_back('a' + (char)j);
    assert(s.size() == ans.size());
    cout << ans << endl;
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n + 1; i++) {
        cin >> a[i];
    }
    for (int j = 0; j < n; j++) {
        cin >> b[j];
    }

    long long ct = 0;
    for (int k = 0; k < n; k++) {
        int dif = 0;
        if (a[k] >= b[k]) ct += b[k];
        else {
            ct += a[k];
            dif = b[k] - a[k];
            if (dif < a[k+1]) {
                ct += dif;
                a[k+1] -= dif;
            } else {
                ct += a[k+1];
                a[k+1] = 0;
            }
        }
    }
    cout << ct << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

int main(){
    int n;
    while(cin >> n, n){
        cin.ignore();
        map<string, int> m;
        string inp, word;
        char k;
        int j = 0;
        rep(i,n){
            getline(cin, inp);
            inp+= ' ';
            rep(j,inp.size()){
                if(inp[j] != ' ') word += inp[j];
                if(inp[j] == ' '){
                    m[word]++;
                    word = "";
                }
            }
        }
        cin >> k;

        vector<pair<int, string>> p;
        for(auto it = m.begin(); it != m.end(); it++){
            if(it->first[0] == k){
                p.emplace_back(make_pair(it->second * -1, it->first));
            }
        }
        sort(all(p));

        int cnt = 5;
        for(auto it = p.begin(); it != p.end(); it++){
            if(not cnt) break;
            if(it != p.begin()) cout << ' ';
            cout << it->second;
            cnt--;
        }
        if(p.size() == 0) cout << "NA";
        cout << endl;
    }
}

Measured memory_bytes: 3084
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> P1;
typedef pair<int, pair<int, int> > P2;
static const int INF = 1ll<<60;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };
static const int mod = 1000000007;

int A,B,C,D;

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

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

signed main(){
    cin>>A>>B>>C>>D;
    int a=A-(A/C+A/D-A/lcm(C,D));
    int b=B-(B/C+B/D-B/lcm(C,D));
    int c=b-a;
    if(A%C!=0&&A%D!=0)c++;
    cout<<c<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int a = sc.nextInt();
		if (h % a == 0) {
			System.out.println(h / a);
		} else {
			System.out.println((h / a) + 1);
		}
	}
}


Measured memory_bytes: 23764
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){

    string S, T;
    cin >> S;
    cin >> T;
    vector<int>SA(S.size()+1, 0);
    vector<int>SB(S.size()+1, 0);
    vector<int>TA(T.size()+1, 0);
    vector<int>TB(T.size()+1, 0);
    rep(i, S.size()){
        SA[i+1] = SA[i] + (S[i]=='A');
        SB[i+1] = SB[i] + (S[i]=='B');
    }
    rep(i, T.size()){
        TA[i+1] = TA[i] + (T[i]=='A');
        TB[i+1] = TB[i] + (T[i]=='B');
    }
    int q;
    cin >> q;
    rep(i, q){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int s = ((SA[b] - SA[a-1]) + 2 * (SB[b] - SB[a-1])) % 3;
        int t = ((TA[d] - TA[c-1]) + 2 * (TB[d] - TB[c-1])) % 3;
        if(s==t)cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 2432
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;
//========================================================================


int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================

	
	string S, T;
	cin >> S >> T;

	cout << T << S;




}


Measured memory_bytes: 256
//42
#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

map<string,int> pm;
map<string,vector<string> >rm;

int cost(string s){
  if(rm.find(s)!=rm.end()){
    int c=0;
    for(int i=0;i<rm[s].size();i++){
      c+=cost(rm[s][i]);
    }
    return min(c,pm[s]);
  }else{
    return pm[s];
  }
}

int main(){
  for(int n;cin>>n,n;){
    pm.clear();
    rm.clear();
    for(int i=0;i<n;i++){
      string i;
      int p;
      cin>>i>>p;
      pm[i]=p;
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
      string p;
      int k;
      cin>>p>>k;
      while(k--){
	string q;
	cin>>q;
	rm[p].push_back(q);
      }
    }
    string a;
    cin>>a;
    cout<<cost(a)<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <stdint.h>
#include <queue>
#include <bitset>
#include <iomanip>

using namespace std;

#define PI 3.14159265358979323846
#define INF 1e+9
#define DIV_NUM (1000000007)



int main() {

	string S, T;
	cin >> S >> T;
	int A, B;
	cin >> A >> B;
	string U;
	cin >> U;
	if (U == S) A--;
	if (U == T) B--;


	long long int N = 100000000000;
	long long ans = 0;
	for (long long i = 0; i < N; i++) {
		ans += 1;
	}

	cout << A << " " << B << endl;

	return 0;
}


Measured memory_bytes: 256
n,*t=map(int,open(0).read().split());A=t[:n];B=t[n:];r=c=1
while c:
 c=0
 for i in range(n):b=B[~-i%n]+B[-~i%n];t=(A[i]<B[i]>b)*(B[i]-A[i])//b;c+=t;B[i]-=t*b
 r+=c
print(r*(A==B)-1)

Measured memory_bytes: 122116
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

#define sp ' '
using namespace std;

int D;

int main(){
	cin >> D;
	cout << "Christmas" << sp;
	for (int i = 25; i != D; --i) {
		cout << "Eve" << sp;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
using namespace std;
typedef long long int ll;

int dp[305][305][305];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string s; cin >> s;
	int m; cin >> m;
	int n=s.size();
	string t=s;
	reverse(t.begin(),t.end());
	int ans=0;
	for(int i=0;i<n+1;i++){
		for(int j=0;j<n+1;j++){
			for(int k=0;k<m+1;k++){
				ans=max(ans,dp[i][j][k]);
				if(i+j>n-1)continue;
				dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
				dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]);
				int x=(i+j==n-1)?1:2;
				if(s[i]==t[j]){
					dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+x);
				}else{
					dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k+1],dp[i][j][k]+x);
				}
			}
		}
	}
	cout << ans << endl;
}
 

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

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

  int a[10000];
  a[1] = s;
  for(int i = 2; ; i++){
      if(a[i - 1] % 2 == 0){
        a[i] = a[i - 1] / 2;
      }else{
        a[i] = 3 * a[i-1] + 1;
      }
      for(int j = 1; j < i; j++){
        if(i != j && a[i] == a[j]){
          cout << i;
          return 0;
        }
      }
  }

  return 0;
}


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

int main()
{
    int n = 0;
    std::cin >> n;

    int x = 0;
    std::cin >> x;
    --x;

    int y = 0;
    std::cin >> y;
    --y;

    // BFS
    std::vector<int> ans(n);
    for (auto vertex = 0; vertex < n; ++vertex)
    {
        constexpr auto INF = 0x7fffff;
        std::vector<int> dists(n, INF);
        std::queue<int> queue;
        auto push = [&dists, &queue, &INF](int v, int d)
        {
            if (dists[v] != INF) return;
            dists[v] = d;
            queue.push(v);
        };
        push(vertex, 0);
        while (!queue.empty())
        {
            auto pop_front = [&queue]()
            {
                auto ret = queue.front();
                queue.pop();
                return ret;
            };
            auto v = pop_front();
            auto d = dists[v];
            if (v - 1 >= 0) push(v - 1, d + 1);
            if (v + 1 < n) push(v + 1, d + 1);
            if (v == x) push(y, d + 1);
            if (v == y) push(x, d + 1);
        }

        for (auto index = 0; index < n; ++index)
        {
            ans[dists[index]]++;
        }
    }
    for (auto& val : ans)
    {
        val /= 2;
    }

    for (auto dist = 1; dist < n; ++dist)
    {
        std::cout << ans[dist] << std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll ans;
int main(){
	cin>>n;
	if(n==1){
		cout<<"0"<<endl;
		return 0;
	}
	for(register ll i=1;i<=sqrt(n);i++) if(n%i==0&&n%((n-i)/i)!=0&&i<(n-i)/i) ans+=(n-i)/i;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using Graph = vector<vector<int>>;
using ll = long long;
using p = pair<int, int>;

int main()
{
    double d, t, s;
    cin >> d >> t >> s;

    double m = d / s;
    if (m <= t)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3716
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		List<int[]> hws = new ArrayList<>();
		while(true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			
			if(H == 0) break;	// 1 <=H.W<= 300
			
			int[] hw = new int[]{H, W};
			hws.add(hw);
			
		}
		sc.close();
		
		for(int[] hw : hws) {
			
			for(int hh = 0; hh < hw[0]; hh++) {
				for(int ww = 0; ww < hw[1]; ww++) {
					System.out.print("#");
				}
				System.out.println();
			}
			System.out.println();
		}
		
	}
}

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

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

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int n;
    cin >> n;
    if (n % 1000 == 0)
        cout << 0 << endl;
    else
        cout << 1000 - n % 1000 << endl;
}

Measured memory_bytes: 3628
n, w = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for _ in range(n)]
v = sum(list(zip(*wv))[1])

# i番目までの品物から、価値がjとなるように選んだときの重さの最小値
dp = [[float("inf")] * (v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    w_i, v_i = wv[i]
    for j in range(v+1):
        # i番目を選ぶとき
        if j - v_i >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v_i] + w_i)
        # i番目を選ばないとき
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])

ans = 0
for j in range(v+1):
    if dp[n][j] <= w:
        ans = j

print(ans)


Measured memory_bytes: 314128
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <cmath>
#include <bits/stdc++.h>
#include <limits>
using namespace std;

int main(void){
    // Your code here!
    long long h, w;
    long long min_diff = LLONG_MAX;
    
    cin >> h >> w;
    for(int i = 1; i < h; i++){
        long long s1 = i * w;
        long long s2 = (h - i) / 2 * w;
        long long s3 = ((h - i) - ((h - i) / 2)) * w;
        min_diff = min(min_diff, max(s1, max(s2, s3)) - min(s1, min(s2, s3)));
    }
    for(int i = 1; i < w; i++){
        long long s1 = i * h;
        long long s2 = (w - i) / 2 * h;
        long long s3 = ((w - i) - ((w - i) / 2)) * h;
        min_diff = min(min_diff, max(s1, max(s2, s3)) - min(s1, min(s2, s3)));
    }
    for(int i = 1; i < h; i++){
        long long s1 = i * w;
        long long s2 = (h - i) * (w / 2);
        long long s3 = (h - i) * (w - w / 2);
        min_diff = min(min_diff, max(s1, max(s2, s3)) - min(s1, min(s2, s3)));
    }
    for(int i = 1; i < w; i++){
        long long s1 = i * h;
        long long s2 = (w - i) * (h / 2);
        long long s3 = (w - i) * (h - h / 2);
        min_diff = min(min_diff, max(s1, max(s2, s3)) - min(s1, min(s2, s3)));
    }
    cout << min_diff << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
char m[255];
int main(){
  int n;
  char c,d;
  for(;;){
    scanf("%d\n",&n);
    if(n == 0) break;
    memset(m,0,sizeof(m));
    while(n>0){
      scanf("%c %c\n",&c,&d);
      m[c] = d;
      n--;
    }
    scanf("%d\n",&n);
    while(n>0){
      scanf("%c\n",&c);
      if(m[c] != 0) printf("%c",m[c]);
      else printf("%c",c);
      n--;
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(), v.end()
#define mod 1000000007
#define mod2 1000000006
#define inf 1000000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<lli>
#define vii vector<int>
#define is indexed_set
#define eps 0.000001
#define endl '\n'
#define mo 998244353
#define pi 3.141592653589793
#define FF first
#define SS second
using namespace std ;
 
const lli dx4[] = {-1, 0, 1, 0};
const lli dy4[] = {0, 1, 0, -1};
const lli dx8[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const lli dy8[] = {0, 1, 0, -1, -1, 1, -1, 1};
 
typedef tree<pll,null_type,less<pll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); // can give negative values too

#define N 1000001

lli pr[N];

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

	loopl(i,0,n)
	{
		lli x;
		cin>>x;

		pr[x]++;
	}

	set<pll> s;

	loopl(i,1,N)
	{
		if(pr[i] == 1) s.insert({i,1});
		else if(pr[i] > 1) s.insert({i,0});
	}

	lli ans=0;

	while(s.size() > 0)
	{
		pll xx = *(s.begin());
		lli sum = xx.ff;

		lli x = xx.ff;
		ans += xx.ss;

		while(x <= 1000000)
		{
			s.erase({x,0});
			s.erase({x,1});
			x+=sum;
		}


	}

	cout<<ans<<endl;

}

int main()
{
/////////////////////////////////////
    fastio;
/////////////////////////////////////  

    lli t;
    t=1;
    while(t--)
    	solve();
}

Measured memory_bytes: 22708
//============================================================================
// Name        : AOJCpp.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <algorithm>
using namespace std;

void trace(int A[], int n) {
	for (int j = 0; j < n-1; j++) {
		cout << A[j] << " ";
	}

	cout << A[n-1] << endl;
}

int main() {

	int n;


	cin >> n;
	int A[n];

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

	int count = 0;
	bool flag = 1;
	int j = 0;
	while(flag) {
		flag = 0;
		for(int i = n-1; i > j; i--) {
			if (A[i] < A[i-1]) {
				int tmp = A[i-1];
				A[i-1] = A[i];
				A[i] = tmp;
				flag = 1;
				count++;
			}
		}
		j++;
	}
	trace(A,n);
	cout << count << endl;
}



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

int main(){
    ll D;
    cin >> D;
    vector<ll> c(26), t(D), last(26, -1);
    vector< vector<ll> > s(365, vector<ll> (26));
    rep(i, 0, 26) cin >> c[i];
    rep(i, 0, D){
        rep(j, 0, 26) cin >> s[i][j];
    }
    srand((unsigned int)time(NULL));
    rep(i, 0, D){
        t[i] = (ll) (rand() % 26);
    }
    ll M = 1e6;
    vector<ll> rec(26, 0);
    /*
    vector<ll> d(M), q(M), rec(26, 0);
    rep(i, 0, M){
        d[i] = (ll) (rand() % D);
        q[i] = (ll) (rand() % 26);
    }
    */
    ll res = 0;
    rep(d, 0, D){
        res += s[d][t[d]];
        last[t[d]] = d;
        rep(j, 0, 26) {
            res -= c[j] * (d - last[j]);
            rec[j] += c[j] * (d - last[j]);
        }
    }
    // t[d[m]] := 0 - 25
    rep(m, 0, M){
        ll prev_res = res;
        // ll d = (ll) (rand() % D);
        ll d = m % D;
        ll q = (ll) (rand() % 26);
        res -= s[d][t[d]];
        res += s[d][q];
        res += rec[t[d]];
        res += rec[q];
        ll tdrec = 0, qrec = 0;
        ll lst = -1;
        rep(i, 0, D){
            if(i != d && t[i] == t[d]){
                lst = i;
            }
            res -= c[t[d]] * (i - lst);
            // rec[t[d[m]]] +=  c[t[d[m]]] * (i - lst);
            tdrec +=  c[t[d]] * (i - lst);
        }
        lst = -1;
        rep(i, 0, D){
            if(i == d || t[i] == q){
                lst = i;
            }
            res -= c[q] * (i - lst);
            // rec[q[m]] += c[q[m]] * (i - lst);
            qrec += c[q] * (i - lst);
        }
        if(res > prev_res){
            rec[t[d]] = tdrec;
            rec[q] = qrec;
            t[d] = q;
        }else{
            res = prev_res;
        }
        // cout << res << endl;
    }
    rep(i, 0, D) cout << t[i]+1 << endl;
    return 0;
}

Measured memory_bytes: 3720
#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; }

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

	for (int i = 1; i <= x; i++)
	{
		if (100 * i <= x && x <= 105 * i)
		{
			cout << 1 << endl;
			return 0;
		}
	}
	cout << 0 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 999999999
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define MOD(x) (x%(mod))
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

bool debug=false;
/*---------------------------------------------------*/

int n,r,p,c;
int card[55];

void init(int n){
  rep(i,n)card[i]=n-i;
}

void shuffle(){
  int tmp[55];
  rep(i,r){
    cin>>p>>c;
    rep(i,c)tmp[i]=card[p+i-1];
    if(debug){cout<<"tmp ";rep(i,c)cout<<tmp[i]<<" ";cout<<endl;}
    for(int i=p-2;i>=0;i--)card[i+c]=card[i];
    rep(i,c)card[i]=tmp[i];
    if(debug){rep(i,n)cout<<card[i]<<" ";cout<<endl;}
  }
}

int main(){

  while(cin>>n>>r){
    if(n==0&&r==0)break;
    init(n);
    shuffle();
    cout<<card[0]<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 2964