akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define mod 1000000007
#define INF 1e9
 
#define p(x) cout<<x<<" ";
#define p2(x,y) cout<<x<<" "<<y<<" "
#define p3(x,y,z) cout<<x<<" "<<y<<" "<<z<<" "
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
 
#define ff first
#define ss second
#define mp(x,y) make_pair(x,y)
#define pi pair<ll,ll>
#define ppi pair<ll,pi>
#define pb push_back
#define all(v) v.begin(), v.end() 

ll power(ll a,ll b){
  ll result=1;
  while(b){
    if(b&1)
      result=(result*a)%mod;
      a=(a*a)%mod;
      b=b/2;
  }
  return result;
}

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


vi v(105),wt(105);
ll dp[105][100005];




int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cout<<fixed<<setprecision(6);

// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
  
    ll t=1;
    //cin>>t;
    
    while(t--)
    {
      ll n,capacity;
      cin>>n>>capacity;
      F(i,0,n-1) cin>>wt[i]>>v[i];
      // here capacity is very huge 
      // so instead of dp of weight make dp of value
      // for specific val calculate min weight
      ll sum=0;
      F(i,0,n-1)
      sum+=v[i];
      vi dp(sum+5,INF); 
      dp[0]=0;
      F(i,0,n-1){
        RF(j,sum,v[i]){
          dp[j]=min(wt[i]+dp[j-v[i]],dp[j]);
        }
        // F(i,0,sum)
        // cout<<dp[i]<<" ";
        // cout<<"\n";
      }
      ll ans=0;
      F(i,0,sum){
        if(dp[i]<=capacity){
          ans=max(i,ans);
        }
      }
      cout<<ans<<"\n";

    }
        
}

Measured memory_bytes: 1024
//  Created by conan1024hao in 2020.
//  Copyright © 2020 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll n;cin>>n;
    vector<ll>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    map<ll,ll>m;
    for(int i=0;i<n;i++){
        if(m[a[i]]>0){
            cout<<"NO"<<endl;
            return 0;
        }
        m[a[i]]++;
    }
    cout<<"YES"<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------








Measured memory_bytes: 14336
import java.util.Scanner;

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

		int[]a = new int[M];
		int[]b = new int[M];
		for(int i = 0; i < M; i++) {
			a[i] = sc.nextInt() - 1;
			b[i] = sc.nextInt() - 1;
		}
		sc.close();
		int cnt = 0;

		for(int i = 0; i < M; i++) {
			DisjointSet ds = new DisjointSet(N);
			for(int j = 0; j < M; j++) {
				if(i == j) continue;
				ds.unite(a[j], b[j]);
			}
			for(int j = 1; j < N; j++) {
				if(ds.findSet(0) != ds.findSet(j)) {
					cnt++;
					break;
				}
			}
//			for(int j = 0; j < N; j++) {
//				System.out.print(ds.findSet(j) + " ");
//			}
//			System.out.println();
		}
		System.out.println(cnt);
	}
	static class DisjointSet {
		int[]p;
		int[]rank;
		DisjointSet(){}
		DisjointSet(int size){
			rank = new int[size];
			p = new int[size];
			for(int i = 0; i < size; i++) {
				makeSet(i);
			}
		}
		void makeSet(int x) {
			p[x] = x;
			rank[x] = 0;
		}
		boolean same(int x, int y) {
			return findSet(x) == findSet(y);
		}
		void unite(int x, int y) {
			link(findSet(x), findSet(y));
		}
		void link(int x, int y) {
			if(rank[x]  > rank[y]) {
				p[y] = x;
			}else {
				p[x] = y;
				if(rank[x] == rank[y]) {
					rank[y]++;
				}
			}
		}
		int findSet(int x) {
			if(x != p[x]) {
				p[x] = findSet(p[x]);
			}
			return p[x];
		}
	}
}

Measured memory_bytes: 23252
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N;
    cin >> N;
    ll ans = 0;
    FOR(i, 1, N+1) {
        if (i % 3 == 0 || i % 5 == 0) continue;
        ans += i;
    }

    cout << ans << endl;
    
}


Measured memory_bytes: 3652
import sys

def main():
    input = sys.stdin.readline
    S = str(input().strip())
    n = len(S)

    R = [1 if s == 'R' else 0 for s in S]
    L = [1 if s == 'L' else 0 for s in S]

    A = [0] * n
    r0, r1 = 0, 0
    for i, r in enumerate(R):
        if r == 0:
            if i % 2 == 0:
                A[i] += r0
                A[i-1] += r1
            else:
                A[i] += r1
                A[i-1] += r0

            r0 = 0
            r1 = 0
        else:
            if i % 2 == 0:
                r0 += 1
            else:
                r1 += 1

    B = [0] * n
    l0, l1 = 0, 0
    for i, l in enumerate(L[::-1]):
        if l == 0:
            if i % 2 == 0:
                B[i] += l0
                B[i-1] += l1
            else:
                B[i] += l1
                B[i-1] += l0

            l0 = 0
            l1 = 0
        else:
            if i % 2 == 0:
                l0 += 1
            else:
                l1 += 1

    for a, b in zip(A, B[::-1]):
        print(a + b, end=' ')

    print()


if __name__ == '__main__':
    main()


Measured memory_bytes: 8164
#9の倍数の判定
n = int(input())
a = list(map(int, input().split( )))
s = 0
hi = 0
for i in range(n-1):
  dis = a[i] +  hi - a[i+1]
  if dis >= 0:
    hi = dis
    s += dis
  else:
    hi = 0

print(s)

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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int a,b;

main() {
    cin >> a >> b;
    ct(b*2-a)
}

Measured memory_bytes: 256
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
string s;
cin>>s;
if (s[0]!=s[1] && s[1]!=s[2] && s[0]!=s[2]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
} 

Measured memory_bytes: 256
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    D = il()

    ret = 0
    for i in range(N):
        for j in range(i+1, N):
            ret += D[i]*D[j]
    print(ret)


if __name__ == '__main__':
    main()


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

using namespace std;
using ll = long long;

template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_V(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_M(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}

int main() {
    int m, d;
    cin>>m>>d;
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int di=1;di<=d;di++){
            if(di/10 >= 2 && di%10 >= 2 && i==(di/10)*(di%10)){
                ans++;
            }

        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <set>
#include <queue>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define pb(x) push_back(x)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=100+5;
int n,m;
ll ans;
struct P
{
    ll x,y;
}pnt1[N],pnt2[N];
bool cmp1(P a,P b)
{
    return a.x<b.x;
}
bool cmp2(P a,P b)
{
    return a.y<b.y;
}
int vis[N];
void judge(ll lx,ll rx)
{
    ll y[N];
    int u=0,d=0;
    for(int i=0;i<n;++i)
        if(pnt2[i].x>=lx&&pnt2[i].x<=rx){
            y[u++]=pnt2[i].y;
            if(u-d==m){
                ans=min(ans,(y[u-1]-y[d])*(rx-lx));
                ++d;
            }
        }
}
int main()
{
    while(~scanf("%d%d",&n,&m)){

        for(int i=0;i<n;++i){
            scanf("%lld%lld",&pnt1[i].x,&pnt1[i].y);
            pnt2[i]=pnt1[i];
        }
        sort(pnt1,pnt1+n,cmp1);
        sort(pnt2,pnt2+n,cmp2);
        ans=1;
        for (int i=0; i<62; i++)  ans *= 2;
        int l,r;
        for(int i=0;i<n;++i)
            for(int j=i;j<n;++j)
                judge(pnt1[i].x,pnt1[j].x);
        printf("%lld\n\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int a, b, c, x, y, r1, r2, r3;
int main() {
  cin >> a >> b >> c >> x >> y;
  r1 = a*x+b*y;
  r2 = c*2*max(x,y);
  r3 = min(x,y)*2*c+abs(x-y)*(x>y?a:b);
  cout << min(r1,min(r2,r3));
  return 0;
}

Measured memory_bytes: 256
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

bCeil(p,q)=p%q==0?div(p,q):div(p,q)+1

function main()
	n = readline() |> parseInt
	a = readline() |> split |> parseMap
	if a[n] != 2
		println(-1)
	else
		flg = 0
		b = Array{Int}(n)
		c = Array{Int}(n)
		b[n] = 2
		c[n] = 2
		for i in 1:n-1
			if div(b[n-i+1],a[n-i+1])==div(c[n-i+1],a[n-i+1])&&b[n-i+1]%a[n-i+1]>0&&c[n-i+1]%a[n-i+1]>0
				flg = 1
				break
			else
				b[n-i] = bCeil(b[n-i+1],a[n-i+1])*a[n-i+1]
				c[n-i] = div(c[n-i+1],a[n-i+1])*a[n-i+1]+a[n-i+1]-1
			end
		end
		if div(b[1],a[1])==div(c[1],a[1])&&b[1]%a[1]>0&&c[1]%a[1]>0
			flg = 1
		else
			b[1] = bCeil(b[1],a[1])*a[1]
			c[1] = div(c[1],a[1])*a[1]+a[1]-1
		end
		if flg == 1
			println(-1)
		else
			println(b[1], " ", c[1])
		end
	end
end
main()

Measured memory_bytes: 170988
#include<iostream>
#define _USE_MATH_DEFINES
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vec;
typedef vector<vector<ll>> mat;
typedef pair<ll,ll> P;
typedef map<ll,ll> MP;
typedef priority_queue<ll> PQ;
typedef stack<ll> ST;
typedef queue<ll> QUE;
#define pb push_back
#define st first
#define nd second
#define SZ(x) ((int)(x).size())
#define FOR(i,s,n) for(int i=(int)(s); i< (int)(n); i++)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define each(x,c) for(auto x: (c))
#define LB(x,a) lower_bound(all(x), a)
#define UB(x,a) upper_bound(all(x), a)
const ll mod=1e9+7;
const ll INF=1e18;
const double EPS=1.0e-10;
const double PI=M_PI;

int main(){
    int N; cin>>N;
    vec S; S.pb(0);
    ll sum=0;
    rep(i,N){
        ll A; cin>>A;
        sum+=A;
        S.pb(sum);
    }
    sort(all(S)); S.pb(INF);
    ll ans=0;
    int i=0;
    while(i<N){
        ll res=distance(S.begin(),UB(S,S[i]))-i;
        ans+=res*(res-1)/2;
        i+=res;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using ll=long long;

ll INF = 1e12;

ll dp[100005];
ll h[100005];
ll N;

int main()
{
    cin >> N;
    for(int i = 0;i < N;i++)
    {
        cin >> h[i];
    }
    memset(dp, INF, N);
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for(int i = 2;i < N;i++)
    {
        dp[i] = min(dp[i-2]+abs(h[i-2]-h[i]), dp[i-1]+abs(h[i-1]-h[i]));
    }
    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1792
# include <iostream>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int a=N;
  const int n=N;
  char S[n];
  for(int i=0;i<N;i++){
    cin>>S[i];
  }
  for(int i=0;i<N-1;i++){
    if(S[i]==S[i+1]){a--;}
  }
  cout<<a<<endl;
  return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[]d = new int[6];
		for(int i = 0; i < 6; i++) {
			d[i] = scan.nextInt();
		}
		String s = scan.next();
		scan.close();
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			int []t = new int[6];
			for(int j = 0; j < 6; j++) {
				t[j] = d[j];
			}
			if(c == 'E') {
				d[0] = t[3];
				d[5] = t[2];
				d[2] = t[0];
				d[3] = t[5];
			}else if(c == 'W') {
				d[0] = t[2];
				d[2] = t[5];
				d[5] = t[3];
				d[3] = t[0];
			}else if(c == 'N') {
				d[0] = t[1];
				d[4] = t[0];
				d[5] = t[4];
				d[1] = t[5];
			}else {
				d[0] = t[4];
				d[4] = t[5];
				d[5] = t[1];
				d[1] = t[0];
			}
		}
		System.out.println(d[0]);
	}
}


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

using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define int long long
#define all(c) (c).begin(),(c).end()
#define M 1000000007
#define INF LLONG_MAX
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ", "; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
// Use pr(a,b,c,d,e) or cerr<<anything or prc(v.begin(),v.end()) or prc(v,v+n)
//  


int32_t main()
{
    fastio;
    int n, k;
    cin >> n >> k;
    vector<int> a(n), f(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> f[i];
    sort(all(a));
    sort(all(f));
    reverse(all(f));
    int l = 0, r = INF;
    int temp = 0, ans = INF; 
    while(l <= r)
    {
        int mid = l + (r-l)/2;
        temp = 0;
        for(int i=0;i<n;i++)
        {
            int loc = max(0LL, a[i] - mid/f[i]);
            temp += loc;
            if(temp > k)
            {
                break;
            }

        }
        if(temp <= k)
        {
            ans = min(ans, mid);
            r = mid-1;
        }
        else l = mid+1;
    }
    cout << ans << "\n";

    return 0;
}




Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define FR first
#define SC second
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

bool Is_Prime(int n){
  if(n==1) return false;
  else if(n==2)return true;
  else if(n%2==0)return false;

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

signed main(){
  int a,d,n;
  while(cin>>a>>d>>n,a){
    int p=0;int tmp;
    for(int i=0;;i++){
      tmp=a+i*d;
      if(Is_Prime(tmp))p++;
      if(p==n){
        cout<<tmp<<endl;
        break;
      }
    }
  }
  return 0;
}



Measured memory_bytes: 3008
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(((a <= b)&&(c >= a && c <= b))||((a>=b)&&(c <= a && c >= b))) cout << "Yes";
    else cout << "No";
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
A, B, K = map(int, input().split())

first = [i for i in range(A, B+1)] if A + K >= B else [i for i in range(A, A+K)]
latter = [i for i in range(B-K+1, B+1)] if B - K >= A else [i for i in range(A, B+1)]

for i in sorted(list(set(first + latter))):
    print(i)


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

int main(){
	int N,W; cin >> N >> W;
	vector<int> v(N);
	vector<int> w(N);
	for(int i=0; i<N; i++)cin >> w[i] >> v[i];

	vector<ll> dp(N*1e3+1,1e18);
	dp[0] = 0;
	for(int i=1; i<=N; i++){
		for(int j=N*1e3; j>=v[i-1]; j--){
			dp[j] = min(dp[j-v[i-1]]+w[i-1], dp[j]);
		}
	}
	ll ans=0;
	for(int i=N*1e3; i>0; i--){
		if(dp[i] <= W) { ans=i; break; }
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4048
import sys
sys.setrecursionlimit(200002)

n, m = map(int, input().split())
a = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    a[l].append((r, d))
    a[r].append((l, -d))

bio = [None for i in range(n)]
def dfs(x):
    for y, d in a[x]:
        if bio[y] is None:
            bio[y] = bio[x] + d
            if not dfs(y):
                return False
        elif bio[y] != bio[x] + d:
            return False
    return True

for i in range(n):
    if bio[i] is None:
        bio[i] = 0
        if not dfs(i):
            print('No')
            exit(0)
print('Yes')


Measured memory_bytes: 129100
using System;

class Test
{
    static void Main()
    {
        string ss = Console.ReadLine();

        foreach ( var c in ss)
        {
            if (char.IsUpper(c)) Console.Write(char.ToLower(c));
            else if (char.IsLower(c)) Console.Write(char.ToUpper(c));
            else Console.Write(c);
        }
        Console.Write("\n");
    }
}


Measured memory_bytes: 15792
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
#include <time.h>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

int main() {
    ll N, P;
    cin >> N >> P;
    string s;
    cin >> s;

    ll ans = 0;
    if (P == 2 || P == 5){
        REP(i, N){
            if((s[i] - '0') % P == 0) ans += (i + 1);
        }
        cout << ans << endl;
        return 0;
    }
    vector<ll> M(P, 0);
    M[0]++;
    ll tmp = 0;
    ll k = 1;
    for(ll i = N - 1; i >= 0; i--){
        tmp = (tmp + (s[i] - '0') * k) % P;
        k = (k * 10) % P;
        M[tmp]++;
    }
    REP(i, P) ans += (M[i] * (M[i] - 1)) / 2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/math/common_factor.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/numeric/ublas/vector.hpp>
// ↓これいる？
#include <boost/graph/strong_components.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::math;
using namespace boost::numeric;

using ll = long long;
namespace bst = boost;
template<class T> void fill(T& v) { for (auto&& i : v) cin >> i; }

//#include "atcoder.hpp"

int main() {
    int N;
    
    cin >> N;
    
    
    for (int m = 1;m <= N; m++) {
      
      int tx = m * 8 / 100;
      if (m + tx == N) {
        cout << m << endl;
        return 0;
      }
    }
    cout << ":(" << endl;
    
    return 0;
}







Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
int cnt[2005];
int d[2005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, x, y;
  cin >> n >> x >> y;
  for (int i = 1; i <= n; i++) {
    fill(d, d + 2005, 0x3f3f3f3f);
    d[i] = 0;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u - 1 > 0 && d[u] + 1 < d[u - 1])
        d[u - 1] = d[u] + 1, q.push(u - 1);
      if (u + 1 <= n && d[u] + 1 < d[u + 1])
        d[u + 1] = d[u] + 1, q.push(u + 1);
      if (u == x && d[u] + 1 < d[y])
        d[y] = d[u] + 1, q.push(y);
      if (u == y && d[u] + 1 < d[x])
        d[x] = d[u] + 1, q.push(x);
    }
    for (int j = i + 1; j <= n; j++)
      cnt[d[j]]++;
  }
  for (int i = 1; i <= n - 1; i++) {
    cout << cnt[i] << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        if (b >= a) {
            System.out.println(a);
        } else {
            System.out.println(a - 1);
        }
    }
}


Measured memory_bytes: 25044
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  int n;
  cin>>n;
  vector<long long> a(n),sum;
  long long tmp=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    tmp+=a[i];
    sum.push_back(tmp);
  }
  vector<long long> ans;
  for(int i=0;i<n-1;i++){
    ans.push_back(abs(2*sum[i]-sum[n-1]));
  }
  cout<<*(min_element(ans.begin(),ans.end()));
  
}


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

int main() {
  int N, count = 1;
  cin >> N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  for (int i = 0; i < N; i++) {
    if (i + 1 < N) {
      if (vec.at(i) != vec.at(i + 1)) {
        count++;
    }
    else {
      continue;
    }
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 256
uses math;

type
  int32 = longint;
  double = extended;
  bool = boolean;

const inf = 1061109567;

var
  i, j, swap_tmp, x, y, z: int32;
  n, ans: int32;
  h, p: array [0 .. 5005] of int32;
  dp: array [0 .. 5005] of int64;

function qsort_less(i, j: int32): bool;
begin
  qsort_less := (h[i] + p[i]) < (h[j] + p[j]);
end;
procedure qsort_swap(i, j: int32);
  var _swap_tmp: int32;
begin
  _swap_tmp := h[i]; h[i] := h[j]; h[j] := _swap_tmp;
  _swap_tmp := p[i]; p[i] := p[j]; p[j] := _swap_tmp;
end;
procedure qsort(_l, _r: int32);
  var i, j, _p: int32;
begin
  if (_r = _l) then exit;
  i := _l; j := _r;
  _p := _l;
  repeat
    while qsort_less(i, _p) do inc(i);
    while qsort_less(_p, j) do dec(j);
    if (i <= j) then begin
      qsort_swap(i, j);
      inc(i); dec(j);
    end;
  until (i > j);
  if (i < _r) then qsort(i, _r);
  if (j > _l) then qsort(_l, j);
end;

begin
//  assign(input,'in'); reset(input);
//  assign(output,'1.out'); rewrite(output);
  randseed := 6714;
  
  readln(n);
  for i := 1 to n do begin
    readln(h[i], p[i]);
  end;
  qsort(1, n);
  
  fillchar(dp, sizeof(dp), 63);
  dp[0] := 0;
  for i := 1 to n do begin
    for j := i - 1 downto 0 do begin
      if (dp[j] <= h[i]) and (dp[j + 1] > dp[j] + p[i]) then begin
        dp[j + 1] := dp[j] + p[i];
      end;
    end;
  end;
  
  ans := 0;
  for i := 0 to n do begin
    if (dp[i] < 1000000000000000000) then begin
      ans := i;
    end;
  end;
  writeln(ans);
  
  close(input);
  close(output);
end.


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;

int main(){
  int n,m,ans=0;
  int x[100000],f[100000];
  cin>>n>>m;
  rep(i,m){
    cin>>x[i];
  }
  sort(x,x+m);
  for(int i=0;i<m-1;i++){
    f[i]=x[i+1]-x[i];
  }
  sort(f,f+m-1);
  for(int i=0;i<m-n;i++){
    ans+=f[i];
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node Node;

void insert(int);
void inorder(Node*);
void preorder(Node*);
void delete(Node*);
Node * search(Node*,int);
Node * s(Node*);
Node * check(Node*,int);  
Node *NIL,*root;

int main(){
  int N,i,v,n;
  char o[7];
  Node *r;
  scanf("%d",&N);

  for(i=0;i<N;i++){
 
    scanf("%s",o);
    if(o[0]=='i'){
      scanf("%d",&v);
      insert(v);
    }
    else if(o[0]=='f'){
      scanf("%d",&n);
      r=check(root,n);
      if(r!=NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(o[0]=='d'){
      scanf("%d",&n);
      delete(search(root,n));
    }


    else {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }

  }
  return 0;
}

void insert(int k){

  Node *z;
  Node *x;
  Node *y;
  z=(Node *)malloc(sizeof(Node));

  z->key=k;
  z->left=NIL;
  z->right=NIL;
  y=NIL;
  x=root;
 
  while(x!=NIL){
    y=x;
    if( z->key < x->key )x=x->left;
    else x=x->right;
     
  }
  z->parent=y;


  if(y==NIL)root=z;
  else if(z->key < y->key) y->left=z;
  else y->right=z;

}






void inorder(Node *u){

  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node *u){

  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

Node * check(Node *u,int n){
  while(1){
 if(u==NIL||n==u->key) break;
    if(n<u->key)u=u->left;
      else u=u->right;

	  	     
	     }
  return u;
}

void delete(Node *a){
  Node *b;
  Node *c;

  if(a->left==NIL||a->right==NIL) b=a;
  else b=s(a);

  if(b->left != NIL){
    c=b->left;
  }else{
    c=b->right;
  }
  if(c!=NIL){
    c->parent=b->parent;
  }

  
  if(b->parent==NIL){
    root=a;
  }else{
    if(b==b->parent->left){
      b->parent->left=c;
    }else{
      b->parent->right=c;
    }
  }
  if(b!=a){
    a->key=b->key;
  }

  free(b);
}

Node * s(Node *a){
  if(a->right!=NIL) {
    Node *z=a->right;
    while(z->left!=NIL) z=z->left;
    return z;
  }
  Node *b=a->parent;
  while(b!=NIL&&a==b->right){
    a=b;
    b=b->parent;
  }
  return b;
}
Node * search(Node *a,int k){
  while(a!=NIL&&k!=a->key){
    if(k<a->key)a=a->left;
    else a=a->right;
  }
  return a;
  
}

Measured memory_bytes: 19364
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> a(n), dp(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = n - 2; i >= 0; --i) {
    dp[i] = 2e9;
    for (int j = 1; j <= m && i + j < n; ++j) {
      dp[i] = min(dp[i], dp[i + j] + abs(a[i] - a[i + j]));
    }
  }
  printf("%d\n", dp[0]);
  return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
#define debug(x) cerr << #x << "=" << x << endl;
typedef long long ll;
ll n, m, ans;
int main() {
    cin >> n >> m;
    if(m - 2*n >= 0) {
        ans += n;
        ans += (m-2*n)/4;
    } else {
        ans = m/2;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

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

    int a, b, c;
    cin >> a >> b >> c;
    cout << c << " " << a << " " << b;
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
'use strict'

const Main = (input) => {
  const tmp = input.trim().split(' ')
  const A = parseInt(tmp[0])
  const B = parseInt(tmp[1])
  const C = parseInt(tmp[2])
  const X = parseInt(tmp[3])
  const Y = parseInt(tmp[4])

  const resultArr = []

  resultArr.push(A * X + B * Y)
  resultArr.push(Math.max(X, Y) * C * 2)

  const minC = Math.min(X, Y) * C * 2
  if (X > Y) {
    resultArr.push(minC + (X - Y) * A)
  } else {
    resultArr.push(minC + (Y - X) * B)
  }

  const result = Math.min.apply(null, resultArr)
  console.log(result)
  return result
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'))

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

int main() {
  int n,k;
  cin >> n >>k;
  int a[n+1];
  for(int i = 1;i<n+1;i++){
    cin >> a[i];
  }
  
  for(int j =k+1 ;j <n+1;j++){
    //cout << a[k+1] << " " << a[j-k] << endl;
    if(a[j] > a[j-k]){cout << "Yes" << endl;}
    else{cout << "No" << endl;}
  }

  
}

Measured memory_bytes: 4288
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define f first
#define s second
#define lint long long
#define mp make_pair
#define pii pair<int, int>
#define pll pair<lint, lint>
#define ld long double
#define inlld(x) scanf("%lld", &x)
#define ind(x) scanf("%d", &x)
#define vi vector<int>

const int N=1e5+5;
const int MOD=1e9+7;
const lint INF=1e18;

typedef long long ll;

lint _add(lint x, lint y)
{
    lint ret=x+y;
    while(ret<0LL)
        ret+=MOD;
    return ret;
}

lint _mult(lint x, lint y)
{
    x%=MOD;
    y%=MOD;
    lint ret=x*y;
    ret%=MOD;
    while(ret<0LL)
        ret+=MOD;
    return ret;
}

using namespace std;
using namespace __gnu_pbds;

template <typename T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n, X[N], Y[N], vis[N];
vector<pair<ll, ll> >vec_x[N], vec_y[N];
vector<ll>adj[N];
set<ll>numx, numy;

void dfs(ll u)
{
    numy.insert(Y[u]);
    numx.insert(X[u]);
    vis[u]=1;
    for(auto x:adj[u])
        if(!vis[x])
            dfs(x);
}

int main()
{
    inlld(n);
    for(ll a=1; a<=n; a++)
    {
        inlld(X[a]);inlld(Y[a]);
        vec_x[X[a]].pb({Y[a], a});
        vec_y[Y[a]].pb({X[a], a});
    }
    for(ll a=1; a<N; a++)
    {
        if(vec_x[a].size())
        {
            sort(vec_x[a].begin(), vec_x[a].end());
            for(ll b=0; b<vec_x[a].size()-1; b++)
            {
                adj[vec_x[a][b].s].pb(vec_x[a][b+1].s);
                adj[vec_x[a][b+1].s].pb(vec_x[a][b].s);   
            }
        }
        if(vec_y[a].size())
        {
            sort(vec_y[a].begin(), vec_y[a].end());
            for(ll b=0; b<vec_y[a].size()-1; b++)
            {
                adj[vec_y[a][b].s].pb(vec_y[a][b+1].s);
                adj[vec_y[a][b+1].s].pb(vec_y[a][b].s);   
            }
        }
    }
    ll ans=0;
    for(ll a=1; a<=n; a++)
        if(!vis[a])
        {
            numx.clear();
            numy.clear();
            dfs(a);
            ll p1=numx.size()*1LL, p2=numy.size()*1LL;
            ans+=p1*p2;
        }
    ans-=n;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 25472
/*
ID: zhaowei10
TASK:
LANG: C++
*/
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define pb push_back
#define MOD 1000000007
#define NDIG(x) floor(log10(x)) + 1
#define FOR(i, j, k, l) for (s32 i = j; i < k; i += l)
#define RFOR(i, j, k, l) for (s32 i = j; i >= k; i -= l)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(x) x.begin(), x.end()
#define MEAN(a, b) min(a, b) + (abs(b - a) >> 1)
#define FASTIO()    \
  cin.tie(nullptr); \
  ios::sync_with_stdio(false);

typedef long long ll;
typedef int64_t s64;
typedef uint64_t u64;
typedef int32_t s32;
typedef uint32_t u32;
typedef float f32;
typedef double f64;
typedef pair<s32, s32> II;
typedef pair<s64, s64> LL;
typedef vector<s32> VI;
typedef vector<II> VII;
typedef vector<char> VC;
typedef vector<VII> VVII;
typedef priority_queue<s32> PQI;
typedef priority_queue<s32, VI, greater<s32>> PQIA;
typedef priority_queue<s64> PQL;
typedef priority_queue<II> PQII;
typedef priority_queue<II, VII, greater<II>> PQIIA;
typedef priority_queue<LL> PQLL;
typedef unordered_set<s32> USI;
typedef unordered_set<s64> USL;
typedef set<II> SII;
typedef multiset<s32> MSI;

template <typename T, typename U>
inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void amax(T &x, U y) {
  if (x < y) x = y;
}

template <typename T>
inline s32 ndigits(T x, T b) {
  s32 r = 0;
  while (x) {
    x /= b;
    ++r;
  }
  return r;
}

int main() {
  FASTIO();

  int n;
  cin >> n;
  int cmin = INT_MAX;
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if (x < cmin) {
      cmin = x;
      ++cnt;
    }
  }
  cout << cnt;
}

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

class Solver {
  public:
    vector<vector<int>> E;
    int grundy(int now, int prev) {
        int g = 0;
        for(int nxt : E[now]) {
            if(nxt == prev) continue;
            g ^= grundy(nxt, now) + 1;
        }
        return g;
    }
    bool solve() {
        int N; cin >> N;
        E.resize(N);
        rep(i, N - 1) {
            int a, b; cin >> a >> b;
            a--; b--;
            E[a].push_back(b);
            E[b].push_back(a);
        }
        cout << (grundy(0, -1) == 0 ? "Bob" : "Alice") << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


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

int main(){
    string S;
    cin >> S;
    if ( S[2] == S[3] and S[4] == S[5] ){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    
    return 0;
}



Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var a, b int

func readVariables() {
	a, b = nextInt(), nextInt()
}

func main() {
	readVariables()
	answer := 6 - (a + b)
	fmt.Println(answer)
}

/* 以下、テンプレート*/

var scanner *bufio.Scanner

func init() {
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
}

//nextInt converts next token from stdin and returns integer value.
//nextInt panics when conversion into an integer fails.
func nextInt() int {
	if !scanner.Scan() {
		panic("No more token.")
	}
	num, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic("nextInt(): cannot convert to int: " + scanner.Text())
	}
	return num
}

func nextStr() string {
	if !scanner.Scan() {
		panic("No more token.")
	}
	return scanner.Text()
}


Measured memory_bytes: 640
package main

import (
  "fmt"
)

func main() {
  var c1, c2, c3 string
  fmt.Scanf("%s", &c1)
  fmt.Scanf("%s", &c2)
  fmt.Scanf("%s", &c3)
  
  fmt.Printf("%s\n", c1[0:1] + c2[1:2] + c3[2:3])
}

Measured memory_bytes: 1832
#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;
#define all(q) (q).begin(),(q).end()
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);
     int n,k;
     cin>>n>>k;
     vector<int>v;
     for(int i=0;i<n;i++)
     {
         int a;
         cin>>a;
         v.push_back(a);
     }
     sort(all(v));
     int mx=INT_MAX;
     for(int i=0;i<=n-k;i++){
        int cur=v[i+k-1]-v[i];
        mx=min(mx,cur);
     }
     cout<<mx<<endl;



    return 0;
}


Measured memory_bytes: 3872
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

int main()
{
	for(;;){
		int n, m, cont = 0, i;
		int list[10000][2];
		int c_list[10000][2];
		int my_fr[10000];
		int temp = 0;
		bool tomodachi_inai = 1;
		
		cin >> n >> m;
		if(n == 0 && m == 0){
			break;
		}
		
		for(i = 0; i < m; i++){
			cin >> list[i][0];
			cin >> list[i][1];
		}
		
		for(i = 0; i < m; i++){
			if(list[i][0] == 1){
				my_fr[cont] = list[i][1];
				cont++;
//				cout <<list[i][1] <<"ツつウツづアツづ債友ツ達ツづつキ" << endl;
				tomodachi_inai = 0;
			}
		}
		if(tomodachi_inai == 1){
			cout << "0" << endl;
			return 0;
		}
	//	temp = cont;
		for(i = 0; i < cont; i++){
			for(int j = 0; j < m; j++){
				if(my_fr[i] == list[j][0] || (my_fr[i] == list[j][1] && list[j][0] != 1)){
					c_list[temp][0] = list[j][0];
					c_list[temp][1] = list[j][1];
					temp++;
				}
			}
		}
		/*
		for(int i = 0; i < temp; i++){
			printf("%d %dツづ個δ環スツトツづーツチツェツッツク\n",c_list[i][0],c_list[i][1]);
		}
		*/
		
		deque<int> tomo;
		deque<int> inte;
		
		for(int i = 0; i < cont; i++){
			tomo.push_back(my_fr[i]);
		}
		for(int i = 0; i < temp; i++){
			tomo.push_back(c_list[i][0]);
			tomo.push_back(c_list[i][1]);
		}
		
		sort(tomo.begin(), tomo.end());
	/*	
		for(int i = 0;i < tomo.size();i++){
			cout << tomo[i] << endl;
		}
		*/
	
		cont = 1;
		temp = tomo[0];
		for(int i = 0; i < tomo.size();i++){
	//		printf("tempツづ個値:%d\ttomo[%d]:%d\n",temp,i,tomo[i]);
			 if(temp != tomo[i]){
	//		 	cout << "ツ暗。ツつ、ツつシ" << endl;
			 	temp = tomo[i];
				cont++;
			 }
		}
		cout << cont << endl;
	}
}

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

#define all(a) a.begin(),a.end()
#define pb(x) push_back(x)
#define vec vector<long long>
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define fi first
#define se second
#define print(a) for(auto i:a)cout<<i<< " ";cout<<endl
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define MP(a,b) make_pair(a,b)
#define hii cout<<"hi\n"
#define printpair(x) for(auto i: x)cout<<i.fi<<" "<<i.se<<endl
#define D(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using namespace std;

const ll N = 1e9 + 5;
bool col2(pair<ll,ll> p1, pair<ll, ll> p2){
  if(p1.fi == p2.fi)return p2.se<p1.se;
  else return p1.fi< p2.fi;
}
struct comp{
  bool operator() (ll const &x, ll const &y){
    return x>y;
  }
};


int main()
{
  fast;
  string a,b;cin>>a>>b;
  ll n = a.length();
  ll ans = 0;
  rep(i,0,n){
    if(a[i] != b[i])ans++;
  }
  cout<<ans<<endl;
}




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

if n % 2 == 0:
    # 1 <-> n, 2 <-> n-1... is Pair
    print(int(n*(n-1)/2-n/2))
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if i + j != n + 1:
                print(str(i) + " " + str(j))
else:
    # Each edge has (sum - N)
    print(int(n*(n-1)/2-(n-1)/2))
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if i + j != n:
                print(str(i) + " " + str(j))


Measured memory_bytes: 3336
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main() 
{
    fastio();

    int n,k,q;
    cin>>n>>k>>q;
    vector<int>ans(n,k-q);
    while( q-- )
    {
        int x;
        cin>>x;
        ans[x-1]++;
    }
    for(int i=0;i<n;i++)
    {
        if( ans[i] > 0 )
            cout<<"Yes";
        else
            cout<<"No";
        nl;
    }
    return 0;
}

Measured memory_bytes: 1024
import collections

S = input()
split_str = list(S)
coll = collections.Counter(split_str)
# print(coll.values())
# print(coll.most_common()[0][1])
# print(coll.most_common()[1][1])


if len(coll) == 2 & coll.most_common()[0][1] == 2 & coll.most_common()[1][1] == 2:
    print('Yes')
else:
    print('No')

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

int main() {
  int a, b;
  std::cin >> a >> b;
  if (a > b) std::swap(a, b);
  for (int i = a; i <= b; i++) {
    if (i - a == b - i) {
      std::cout << i << std::endl;
      return 0;
    }
  }
  std::cout << "IMPOSSIBLE" << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    int n,m;
    cin >> n;
    vector<string> s(n);
    for(auto& i:s) cin >> i;
    cin >> m;
    vector<string> t(m);
    for(auto& i:t) cin >> i;
    int ans=0;
    rp(i,n){
        int ctr=0;
        rp(j,n){
            if(s[i]==s[j]) ctr++;
        }
        rp(j,m){
            if(s[i]==t[j]) ctr--;
        }
        chmax(ans,ctr);
    }
    rp(i,n){
        int ctr=0;
        rp(j,n){
            if(t[i]==s[j]) ctr++;
        }
        rp(j,m){
            if(t[i]==t[j]) ctr--;
        }
        chmax(ans,ctr);
    }
    print(ans);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 3592
import math

k, a, b = map(int, input().split())

if b - a > 1 or k <= a:
    x = a + (b - a) * (k - a) // 2 + 1 if (k - a +
                                           1) % 2 == 1 else a + (b - a) * (k - a + 1) // 2
else:
    x = 1 + k

print(x)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
cin>>n;
for (int i = 0; i < n; ++i) {
int sum=0,out=0,finsum=0;
while(1){
cin>>s;
if(s=="HIT"){sum++;if(sum==4){finsum+=1;sum=3;}}
if(s=="OUT"){out++;if(out==3)break;}
if(s=="HOMERUN"){finsum+=sum;finsum++;sum=0;}
}
cout<<finsum<<endl;
}
}

Measured memory_bytes: 3028