akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int n, m, a, b, c;
    cin >> n >> m;
    vector<vector<int>> edge(n, vector<int>(n, 1e6));
    for(int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        a--; b--;
        edge[a][b] = edge[b][a] = c;
    }
    for(int i = 0; i < n; i++)
        edge[i][i] = 0;
    vector<vector<int>> e2 = edge;
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // if (i == k || j == k) continue;
                // if (e2[i][k] + e2[k][j] < e2[i][j])
                //    e2[i][j] = e2[i][k] + e2[k][j];
                e2[i][j] = min(e2[i][j], e2[i][k] + e2[k][j]);
            }
        }
    }
    // floyd-warshall
    int ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if (edge[i][j] != 1e6 && edge[i][j] != e2[i][j])
                ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}




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


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,n) for(int i=1; i<=(n); i++)
#define pii pair<int,int>
#define gsort(x,n) sort((x),(x)+(n),greater<int>())
#define all(x) (x).begin(), (x).end()
#define int int64_t
#define ll long long
#define re(s) reverse((s).begin(),(s).end())
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const long long mod = 1000000007;
using namespace std;

vector<bool> y;
signed main(){
    int n,m,cnt=0,ans=0;
    cin>>n>>m;
    vector<int> x;
    vector<string> s;
    int a;
    string b;

    rep(i,n+1){
        y.push_back(false);
    }

    rep(i,m){
        cin>>a>>b;
        x.push_back(a);
        s.push_back(b);
        if(b == "AC"){
            y[a] = true;
        }
    }

    rep(i,m){
        if(s[i] == "AC" && y[x[i]]){
            ++ans;
            y[x[i]] = false;
        }
        if(s[i] == "WA" && y[x[i]]){
            ++cnt;
        }
    }

    cout<<ans<<' '<<cnt<<'\n';
}

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

ll xor_f(ll n){
	int t = n % 4;
	switch(n % 4){
		case 0:	return n^0;
		case 1: return 1;
		case 2: return n^1;
		case 3: return 0;
	}
}

int main(){
    ll A,B;
    cin>> A >> B;
	ll ans = xor_f(A-1) ^ xor_f(B);
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
use std::collections::HashMap;
use std::num;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        s: String,
    }
    println!("{}", s.chars().filter(|n| *n == '1').count());
}


Measured memory_bytes: 4352
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, W = LI()
wv = LIR(N)

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    w, v = wv[i]
    for j in range(W+1):
        if (j < w):
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)

print(dp[N][W])

Measured memory_bytes: 120428
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <vector>
#include <string>

using ll = long long;

using namespace std;

void solve() {
    map<ll, int> counts;
    int n;
    cin >> n;
    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        ll a;
        cin >> a;
        ans += counts[i - a];
        ++counts[i + a];
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    solve();
}


Measured memory_bytes: 26200
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  int n;
  cin >> n;
  
  vector<int> p(n);
  rep(i,n){
  cin >> p[i];
  }
  
  sort(all(p));
  
  int ans = 1;
  repo(i,n) {
    if(p[i]!=p[i-1])ans++;
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<string.h>

int main() {
   char s[10];

   scanf("%s",s);

   int min = 1000;
   int size = strlen(s);
   for(int i=0;i<=size-3;i++){
        int tmp = (s[i] - '0')*100 + (s[i+1] - '0')*10 + (s[i+2] - '0');
        tmp = abs(753 - tmp);
        if(tmp < min){
            min = tmp;
        }
   }
   printf("%d\n",min);
    return 0;
}

Measured memory_bytes: 128
using namespace std;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <cassert>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    int a[3];
    for (int i = 0; i < 3; i++){
        cin >> a[i];
    }
    int m = max({10 * a[0] + a[1] + a[2], a[0] + 10 * a[1] + a[2], a[0] + a[1] + 10 * a[2] });
    cout << m << endl;

    


}


Measured memory_bytes: 256
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start; i<n; i++)

int main(void){
  string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 string s;
  int N;
  cin >> N;
  cin >> s;
  int count[(int)s.size()];
  int amari;
  rep(i, s.size()){
   	rep(j, 26){
      if (s[i] == alphabet[j]) {
        amari = (j+N)%26;
        cout << alphabet[amari];
      }
    }
  }
}

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

int h, w, k;
int a[11][1005];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> h >> w >> k;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            char c; cin >> c;
            a[i][j] = c-'0';
        }
    }
    int ans = 2e9;
    for (int mask = 0; mask < (1<<h); mask++) {
        int cut = 0;
        vector<bool> v;
        for (int i = 0; i < h; i++) {
            v.push_back(mask&(1<<i));
        }
        vector<int> cnt;
        vector<int> comp(h);
        int pt = 0;
        for (int i = 0; i < v.size(); i++) {
            if (i > 0 && v[i] != v[i-1]) {
                cut++;
                pt++;
            }
            comp[i] = pt;
        }
        ++pt;
        cnt.resize(pt);
        for (int i = 0; i < w; i++) {
            vector<int> add(pt);
            for (int j = 0; j < h; j++) {
                if (a[j][i]) add[comp[j]]++;
            }
            for (int j = 0; j < pt; j++) {
                if (add[j] > k) {
                    goto cont;
                }
            }
            bool flag = false;
            for (int j = 0; j < pt; j++) {
                if (cnt[j] + add[j] > k) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                //cut here
                for (int j = 0; j < pt; j++) {
                    cnt[j] = add[j];
                }
                cut++;
            }
            else {
                for (int j = 0; j < pt; j++) {
                    cnt[j] += add[j];
                }
            }
        }
        ans = min(ans,cut);
        //cout << mask << "; " << cut << '\n';
        cont: ;
    }
    cout << ans << '\n';
}



Measured memory_bytes: 256
n=int(input())
taro=0
hana=0
for i in range(n):
    a,b=input().split()
    l=[a,b]
    l.sort()
    if a==b:
        taro+=1
        hana+=1
    elif l[0]==a:
        hana+=3
    else:
        taro+=3
print(taro,hana)


Measured memory_bytes: 5600
//vector<pair<int,int>>vp;
/*
  int knapsack(int W,int Wr,int n,int val)
  {
      if(n==0)
    {
     // cout<<val<<" ";

    }
    else{
         int w=vp[n].first;
         int v=vp[n].second;

         if(Wr>=w){
         knapsack(W,Wr-w,n-1,val+v);}
         knapsack(W,Wr,n-1,val);
    }

  }
int main()
{
    int W;
    cin>>W;
    int n;
    cin>>n;
   vp.push_back({0,0});
     for(int i=0;i<n;i++)
    {
        int temp1,temp2;
        cin>>temp1>>temp2;
        vp.push_back({temp1,temp2});
    }
    knapsack(W,W,n,0);
}
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{   int n;
    cin>>n;
   int W;
    cin>>W;
    int val[n+1];
    int arr[n+1];
    int dp[n+1][n*1000+1];

    for(int i=1;i<=n;i++)
        cin>>arr[i]>>val[i];

    for(int i=0;i<=n;i++)
    {
        dp[i][0]=0;
    }
    for(int j=1;j<=n*1000;j++)
    {
        dp[0][j]=-1;
    }


    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n*1000;j++)
        {
            if(j-val[i]>=0&&dp[i-1][j-val[i]]!=-1&&arr[i]+dp[i-1][j-val[i]]<=W)
            {
                if(dp[i-1][j]!=-1)
                    dp[i][j]=min(arr[i]+dp[i-1][j-val[i]],dp[i-1][j]);
                else
                     dp[i][j]=arr[i]+dp[i-1][j-val[i]];
            }

            else
                dp[i][j]=dp[i-1][j];

              // cout<<j<<" "<<dp[i][j]<<" ";
        }
       // cout<<endl;

    }

    int ans=-1;
    for(int j=n*1000;j>=0;j--)
    {
        for(int i=1;i<=n;i++)
        {
            if(dp[i][j]!=-1)
            {
                ans=j;
                break;
            }
        }
        if(ans!=-1)
            break;
    }

     cout<<ans<<endl;



}


Measured memory_bytes: 79104
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<int, pii>
#define puu pair<ULL, ULL>
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head
 
int n, k;
vector<pii> vc;
int main() {
	scanf("%d %d", &n, &k);
	if(k > (n-2)*(n-1)/2) return 0*puts("-1");
	for (int i = 2; i <= n; ++i) vc.pb({1, i});
	int res = (n-2)*(n-1)/2-k;
	int x = 2, y = 3;
	for (int i = 1; i <= res; ++i) {
		vc.pb({x, y});
		y++;
		if(y >= n+1) {
			x++;
			y=x+1;
		}
	}
	printf("%d\n", (int)vc.size());
	for (pii p : vc) printf("%d %d\n", p.fi, p.se);
	return 0;
} 

Measured memory_bytes: 384
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;

public static class P
{
    public static void Main()
    {
        var nk = Console.ReadLine().Split().Select(long.Parse).ToArray();
        var n = (int)nk[0];
        var m = nk[1];
        var a = Console.ReadLine().Split().Select(long.Parse).OrderByDescending(x => x).ToArray();
        //一回の握手で得られる幸福度が単調減少するため、m回で得られる奴 
        var valid = 0;
        var invalid = 200001;
        while (invalid - valid > 1)
        {
            var mid = (invalid + valid) / 2;
            long ctr = 0;
            for (int i = 0; i < n; i++)
            {
                ctr += a.LargerCount(mid - a[i]);
            }
            if (m <= ctr) valid = mid;
            else invalid = mid;
        }
        long res = 0;
        var accum = new long[a.Length + 1];
        for (int i = 0; i < a.Length; i++)
            accum[i + 1] = a[i] + accum[i];
        long count = 0;
        long min = long.MaxValue;
        for (int i = 0; i < n; i++)
        {
            var largerCount = a.LargerCount(valid - a[i]);
            count += largerCount;
            if (largerCount != 0) min = Min(min, a[i] + a[largerCount - 1]);
            res += largerCount * a[i];
            res += accum[largerCount];
        }
        res -= Max(count - m, 0) * min;
        Console.WriteLine(res);
    }
    static int LargerCount(this long[] a, long threshold)
    {
        var valInd = -1;
        var invalInd = a.Length;
        while (invalInd - valInd > 1)
        {
            var midInd = (valInd + invalInd) / 2;
            if (threshold <= a[midInd]) valInd = midInd;
            else invalInd = midInd;
        }
        return valInd + 1;
    }
}


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

int main() {
	int a, b, c;
	std::cin >> a >> b >> c;

	int x = (a == b) + (b == c) + (c == a);

	std::cout << (x == 1 ? "Yes" : "No") << std::endl;
}

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

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int dif = min(b,d) - max(a,c);

	if(dif >= 0) cout << dif << endl;
	else cout << 0 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<boost/dynamic_bitset.hpp>
using namespace std;
using u64 = uint64_t;
using s64 = int64_t;

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

    if(N < 2) { // N is 1
        cout << 0 << endl;
        return 0;
    }

    map<u64, u64> prms;
    u64 p = 2;

    while(N >= p) {
        if(N % p == 0) {
            prms[p] = prms[p] + 1;
            N /= p;
        } else {
            p++;
            if(p*p > N) { // N is prime
                prms[N] = 1;
                break;
            }
        }
    }

    u64 ans = 0;

    for(auto itr=prms.begin(); itr!=prms.end(); itr++) {
        u64 k = 1;
        u64 val = itr->second;
        while(val >= k) {
            val -= k;
            k++;
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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

	int dp[101][4][4][4] = { 0 };

	int N;
	cin >> N;

	dp[0][3][3][3] = 1;

	REP(len, N) {
		REP(c1, 4) {
			REP(c2, 4) {
				REP(c3, 4) {

					if (dp[len][c1][c2][c3] == 0)continue;

					REP(a, 4) {

						if (a == 2 && c1 == 1 && c2 == 0)continue;
						if (a == 2 && c1 == 0 && c2 == 1)continue;
						if (a == 1 && c1 == 2 && c2 == 0)continue;
						if (a == 2 && c1 == 1 && c3 == 0)continue;
						if (a == 2 && c2 == 1 && c3 == 0)continue;

						dp[len + 1][a][c1][c2] += dp[len][c1][c2][c3];
						dp[len + 1][a][c1][c2] %= mod;

					}

				}
			}
		}
	}

	int ans = 0;
	REP(i, 4) {
		REP(j, 4) {
			REP(k, 4) {

				ans += dp[N][i][j][k];
				ans %= mod;
			}
		}
	}


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



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

struct Card { char suit, value; };

void bubble(struct Card A[], int N){
    for(int i=0; i<N; i++){
        for(int j = N-1; j >= i+1; j--){
            if (A[j].value < A[j-1].value){
                Card t = A[j]; A[j] = A[j - 1]; A[j - 1] = t;
            }
        }
    }
}

void selection(struct Card A[], int N){
    for(int i=0; i < N; i++){
        int minj = i;
        for(int j = i; j < N; j++){
            if (A[j].value < A[minj].value) minj = j;
        }
        Card t = A[i]; A[i] = A[minj]; A[minj] = t;
    }
}

void print(struct Card A[], int N){
    for(int i=0; i < N; i++){
        if (i>0) cout << " ";
        cout << A[i].suit << A[i].value;
    }
    cout << endl;
}

bool isStable(struct Card C1[], struct Card C2[], int N){
    for(int i=0; i < N; i++){
        if (C1[i].suit != C2[i].suit) return false;
    }
    return true;
}

int main(){
    Card C1[100], C2[100];
    int N;
    char ch;

    cin >> N;
    for(int i=0; i < N; i++){
        cin >> C1[i].suit >> C1[i].value;
    }

    for(int i=0; i < N; i++) C2[i] = C1[i];

    bubble(C1, N);
    selection(C2, N);

    print(C1, N);
    cout << "Stable" << endl;
    print(C2, N);
    if (isStable(C1, C2, N)){
        cout << "Stable" << endl;
    }
    else{
        cout << "Not stable" << endl;
    }

    return 0;
}


Measured memory_bytes: 3120
S = str(input())
mod = 10 ** 9 + 7

dp = [[0] * 13 for i in range(len(S))]
for i in range(len(S)):
  if i == 0:
    if S[i] == "?":
      for j in range(10):#"?"
        dp[i][j] = 1
    else:
      x = int(S[i])
      dp[i][x] = 1
  else:
    if S[i] == "?":
      for j in range(10):#"?"
        for k in range(13):
          now = (10 * k + j) % 13
          dp[i][now] += dp[i - 1][k]   
          dp[i][now] %= mod
    else:
      x = int(S[i])
      for k in range(13):
        now = (10 * k + x) % 13
        dp[i][now] += dp[i - 1][k]
        dp[i][now] %= mod
        
#print(dp)        
print(dp[-1][5] % mod)        
      
      


Measured memory_bytes: 88180
def combination(n,k):
    if n<0 or k<0 or n<k:
        return 0
    else:
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
N, K = map(int, input().split())    
MOD = int(1e9+7)
fac = [0 for _ in range(N+1)]
finv = [0 for _ in range(N+1)]
inv = [0 for _ in range(N+1)]
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
    
def H(n, r):
    return combination(n-1, r-1)


#N, K = map(int, input().split())
for k in range(K):
    i = k+1
    print(H(K,i)*combination(N-K+1, i)%(int(1e9+7)))

Measured memory_bytes: 3572
#include <stdio.h>

int main(void) {
    int a[3][3];
    int b[3][3] = {
        {0,0,0},
        {0,0,0},
        {0,0,0},
    };
    int i, j, k;
    for (i = 0; i < 3; i++) {
        scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
    }
    int n, x, flag;
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d", &x);
        flag = 0;
        for (j = 0; j < 3; j++) {
            for (k = 0; k < 3; k++) {
                if (a[j][k] == x) {
                    b[j][k] = 1;
                    flag = 1;
                    break;
                }
            }
            if (flag) break;
        }
    }

    if (b[0][0] && b[0][1] && b[0][2] || b[1][0] && b[1][1] && b[1][2] 
    || b[2][0] && b[2][1] && b[2][2]) {
        printf("Yes\n");
        return 0;
    }
    if (b[0][0] && b[1][0] && b[2][0] || b[0][1] && b[1][1] && b[2][1] 
    || b[0][2] && b[1][2] && b[2][2]) {
        printf("Yes\n");
        return 0;
    }
    if (b[0][0] && b[1][1] && b[2][2] || b[0][2] && b[1][1] && b[2][0]) {
        printf("Yes\n");
        return 0;
    }
    printf("No\n");
    return 0;
}

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

using namespace std;



void solve()
{


int a;
cin >> a;
cout << a + a*a + a*a*a;

}

int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin >> t;
while (t--) solve();

}


Measured memory_bytes: 3648
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 200000;
struct edge {
	int next=0, to=0;
}edges[MAX];
int h[MAX], flag[MAX], head[MAX] = {0},lower;
int cnt = 1;
void add(int a,int b){
	edges[cnt].to = b;
	edges[cnt].next = head[a];
	head[a] = cnt++;
}
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> h[i];
	}
	while (M--) {
		int a, b;
		cin >> a >> b;;
		add(a,b);
		add(b, a);
	}
	cnt = 0;
	queue<int> Q;
	for (int i = 1; i <= N; i++) {
		if (flag[i])continue;
		Q.push(i);
		while (!Q.empty()) {
			int c = Q.front();
			if (flag[c]) {
				Q.pop();
				continue;
			}
			flag[c] = 1;
			Q.pop();
			int t;
			lower = 0;
			for (t = head[c]; t; t = edges[t].next)
			{
				int d = edges[t].to;
				if (h[d] >= h[c])lower = 1;
				if (flag[d])continue;
				Q.push(d);
			}
			if (!lower) { cnt++; }
		}
	}
	cout << cnt;
	return 0;
}


Measured memory_bytes: 6700
Scanf.scanf "%d %d" (fun n m ->
    let hist = Array.make n 0 in
    for i = 1 to m do
        Scanf.scanf " %d %d" (fun a b ->
            hist.(a - 1) <- hist.(a - 1) lxor 1;
            hist.(b - 1) <- hist.(b - 1) lxor 1;
        )
    done;
    print_endline @@ if Array.fold_left (+) 0 hist = 0 then "YES" else "NO"
)

Measured memory_bytes: 6628
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = (int) 1e5 + 5;
const int mod = (int) 1e9 + 7;
int n;
int x[maxn];

int read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &x[i]);
  }
  return true;
}

int mina[maxn];

void solve() {
  int cura = 0;
  for (int i = 0; i < n; i++) {
    mina[i] = cura;
    int a = i + 1, b = x[i] - a;
    if (b >= a - 1) {
      continue;
    }
    int na = (a + b + 1) / 2;
    int need = a - na;
    cura = max(cura, need);
  }
  int res = 1;
  for (int i = n - 1; i >= 0; i--) {
    int cnt = n - mina[i];
    cnt -= (n - i - 1);
    res = (long long) res * cnt % mod;
  }
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;

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

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
int N,P;
struct mint {
    long long x; // typedef long long long long;
    mint(long long _x=0):x((_x%P+P)%P){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= P) x -= P;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += P-a.x) >= P) x -= P;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= P;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint modpow(long long t) const {
        if (!t) return 1;
        mint a = modpow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime P
    mint inv() const {
        return modpow(P-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin>>N>>P;
    string S;
    cin>>S;
    if(10 % P == 0){//2 or 5
        ll ans = 0;
        rep(r,N){
            if ((S[r] - '0') % P == 0){
                ans += r+1;
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    vector<mint> cumsum(N+1, 0);
    rep(i,N){
        cumsum[i+1] = cumsum[i] + mint(10).modpow(N-1-i) * (S[i] - '0');
    }
    map<ll, int> cnt;
    ll ans = 0;
    rep(i,N+1){
        ans += cnt[cumsum[i].x];
        cnt[cumsum[i].x]++;
    }
    cout<<ans<<endl;
}

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

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

template<class T>inline bool chmax(T &a, const T &b) { if (b > a) { a = b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

template<class T>
class BinaryIndexedTree {
    private:
        int N;
        std::vector<T> dat;
    public:
        BinaryIndexedTree(int n) : N(n), dat(n+1, static_cast<T>(0)) {}
        // a is 1-indexed
        void add(int a, const T v) {
            while (a <= N) {
                dat[a] += v;
                a += (a & -a);
            }
        }
        // return sum of [1, a]
        // a is 1-indexed
        T sum(int a) const {
            T res = static_cast<T>(0);
            while (a > 0) {
                res += dat[a];
                a -= (a & -a);
            }
            return res;
        }
        // return sum of [a. b)
        // a and b are 1-indexed
        T sum(int a, int b) const {
            return sum(b-1) - sum(a-1);
        }
};

void solve() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i=0; i<N; ++i) cin >> a[i];

    // compress
    vector<int> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int M = (int)b.size();

    BinaryIndexedTree<ll> bitNum(M), bitSum(M);
    for (int i=1; i<N; ++i) {
        int pla = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        bitNum.add(pla, 1);
        bitSum.add(pla, a[i]);
    }
    vector<ll> res(N);
    for (int i=0; i<N; ++i) res[0] += a[i];
    int l = 0;
    for (int r=1; r<N; ++r) {
        int plaR = lower_bound(b.begin(), b.end(), a[r]) - b.begin() + 1;
        if (a[l] < a[r]) {
            int plaL = lower_bound(b.begin(), b.end(), a[l]) - b.begin() + 1;
            ll num = bitNum.sum(plaL+1, M+1), sum = bitSum.sum(plaL+1, M+1);
            res[r] = sum - num * a[l];
            res[l] -= res[r];
            l = r;
        }
        bitNum.add(plaR, -1);
        bitSum.add(plaR, a[r]);
    }
    for (ll x : res) cout << x << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 4224
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 100000
#define INF 0x3f3f3f3f
#define SetIt set<int>::iterator
struct Edge{
    int v,w;
    Edge(){}
    Edge(int a,int b){
        v=a,w=b;
    }
};
int N,M;
set<int> I[MAXN+5];
vector<Edge> P[MAXN+5];
vector<Edge> G[20*MAXN+5];
map<pair<int,int>,int> Num;

inline void AddEdge(vector<Edge> *Gr,int u,int v,int w){
    Gr[u].push_back(Edge(v,w));
    Gr[v].push_back(Edge(u,w));
}

int dist[20*MAXN+5];
bool vis[20*MAXN+5];
int SPFA(int S,int T,int cnt){
    fill(dist+1,dist+cnt+N+1,INF);
    queue<int> Q;Q.push(S);
    dist[S]=0;vis[S]=1;
    while(!Q.empty()){
        int u=Q.front();
        vis[u]=0;Q.pop();
        for(int i=0;i<int(G[u].size());i++){
            int v=G[u][i].v,w=G[u][i].w;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
    if(dist[T]==INF)
        return -2;
    return dist[T];
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        P[u].push_back(Edge(v,c));
        I[u].insert(c),I[v].insert(c);
    }
    int cnt=N;
    for(int i=1;i<=N;i++){
        //printf("Points under %d:",i);
        for(SetIt j=I[i].begin();j!=I[i].end();j++){
            AddEdge(G,i,++cnt,1);
            Num[make_pair(i,*j)]=cnt;
            //printf(" %d(%d)",cnt,*j);
        }
        //puts("");
    }
    //printf("%d %d",Num[make_pair(1,1)],Num[make_pair(2,1)]);
    //for(int i=1;i<=Sum[N];i++)
    //    for(int j=0;j<int(G[i].size());j++)
    //        printf("%d -> %d : %d\n",i,G[i][j].v,G[i][j].w);
    for(int i=1;i<=N;i++){
        for(int j=0;j<int(P[i].size());j++){
            int v=P[i][j].v,c=P[i][j].w;
            AddEdge(G,Num[make_pair(i,c)],Num[make_pair(v,c)],0);
        }
    }
    //for(int i=1;i<=cnt;i++)
    //    for(int j=0;j<int(G[i].size());j++)
    //        printf("%d -> %d : %d\n",i,G[i][j].v,G[i][j].w);
    printf("%d",SPFA(1,N,cnt)/2);
    return 0;
}


Measured memory_bytes: 126208
N = int(input())
BA = []
for _ in range(N):
    a, b = map(int, input().split())
    BA.append((b, a))

BA.sort()

can = True
cum = 0
for ba in BA:
    cum += ba[1]
    if cum > ba[0]:
        can = False
        break

print('Yes' if can else 'No')


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

int main(){
  int a,b;
  cin>>a>>b;
  if(a>=13)cout<<b<<endl;
  else if(a>=6)cout<<b/2<<endl;
  else cout<<0<<endl;
  return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef pair<int, int> P;
int main() {
    int n, m, ans = 0;
    vector<P> p;
    set<int> res;
    cin >> n >> m;
    for(int i=0;i<n;i++){
        int a, b;
        cin >> a >> b;
        p.push_back(P(b, -a));
    }
    sort(p.begin(), p.end(), greater<P>());
    for(int i=1;i<=m;i++){
        res.insert(i);
    }
    for(int i=0;i<n;i++){
        int a = -p[i].second;
        int b = p[i].first;
        auto itr = res.lower_bound(a);
        if(itr != res.end()){
            res.erase(itr);
            ans += b;
        }
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5748
use proconio::input;

fn main() {
    input! {
        s: String,
        t: String,
    }
    let s: Vec<char> = s.chars().into_iter().collect();
    let t: Vec<char> = t.chars().into_iter().collect();
    let n = s.len();
    let mut ret = 0;
    for i in 0..n {
        if s[i] != t[i] {
            ret += 1;
        }
    }
    println!("{}", ret);
}


Measured memory_bytes: 4364
def resolve():
    import itertools
    n = int(input())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    a = 0
    b = 0
    for i, l in enumerate(list(itertools.permutations(range(1, n+1), n))):
        l = list(l)
        if l == p:
            a = i+1
        if l == q:
            b = i+1
    print(abs(a-b))
resolve()

Measured memory_bytes: 13792
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<ll> v;
  ll sum = 0;
  for(int i = 0; i < n; i++){
    ll a;
    cin >> a;
    v.push_back(a);
  }
  sort(v.begin(), v.end());
  ll cnt = 0, idx = 0;
  while(idx < n){
    ll tmp = v[idx];
    while(v[idx] == tmp) cnt++, idx++;
    sum += cnt % 2;
    cnt = 0;
    if(idx > n) break;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1400
/* vo00_09.cpp */

#include <iostream>
using namespace std;

const int N = 1000000;
int prime[N];

void init();

int main()
{
	init();

	int n;
	while (cin >> n) {
		
		cout << prime[n] << '\n';

	}

	return 0;
}

void init()
{
	for (int i = 0; i < N; ++i) { prime[i] = 1; }

	prime[0] = prime[1] = 0;

	for (int i = 2; i < N; ++i) {
		if (prime[i])
			for (int j = i * 2; j < N; j += i) { prime[j] = 0; }
	}

	int count = 0;
	for (int i = 0; i < N; ++i) { if (prime[i]) { count++; } prime[i] = count; }
}

Measured memory_bytes: 5064
#include <iostream>

using namespace std;

int main() {
	int n;
	while (cin >> n&& n!=0) {
		int f[21][21] = {};

		for (int i = 0; i<n; i++) {
			int x, y;
			cin >> x >> y;
			f[y][x] = 1;
		}

		int x = 10, y = 10;
		int cnt = 0;

		int m;
		cin >> m;
		for (int i = 0; i<m; i++) {
			char dir;
			int step;
			cin >> dir >> step;
			while (step--) {
				if (dir == 'N') { y++; }
				else if (dir == 'S') { y--; }
				else if (dir == 'E') { x++; }
				else { x--; }

				if (f[y][x]) {
					f[y][x] = 0;
					cnt++;
				}
			}
		}

		if (cnt == n) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3052
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::string;

int main()
{
    string S;
    cin >> S;

    int result = 0;
    if (S == "SUN")
        result = 7;
    else if (S == "MON")
        result = 6;
    else if (S == "TUE")
        result = 5;
    else if (S == "WED")
        result = 4;
    else if (S == "THU")
        result = 3;
    else if (S == "FRI")
        result = 2;
    else if (S == "SAT")
        result = 1;    

    cout << result << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <bits/stdc++.h>

//https://atcoder.jp/contests/abc088/tasks/abc088_b

int main()
{
    std::ios::sync_with_stdio(false); // toggler av synkronisjon mellom c og c++ data streams. kan ikke blade de etter skrudd av
    std::cin.tie(NULL);               //gj;r at man ikke venter på cout og de can printe samtidig tror jeg

    //linjen er opp til 100. det er en linje p[ lengde hundre med hus p[ bare de nevte stedene]]

    int numberOfCards;
    std::cin >> numberOfCards;

    std::vector<int> vec(numberOfCards);
    for (int i = 0; i < numberOfCards; i++)
    {
        std::cin >> vec[i];
    }

    std::sort(vec.begin(), vec.end(), std::greater<int>());

    int total = 0;
    int mul = 1;
    for (int i = 0; i < numberOfCards; i++)
    {
        total = total + (mul * vec[i]);
        mul = mul * -1;
    }

    std::cout << total << "\n";
}

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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

template<class T>
inline void out(T a) {
	cout<<a<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


int X;

void input() {
	cin>>X;
}

void solve() {
	if(X>=30) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


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

using namespace std;

#define MAX_N 21
#define MAX_M 150001
#define INF (1<<29)
typedef long long ll;

double dp[MAX_N][MAX_M];

int main()
{
    int N;
    cin >> N;
    vector<double> v(N);
    for (int i = 0; i < N; i++) {
        cin >> v[i];
    }

    fill(dp[0], dp[MAX_N], INF);
    dp[0][1] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = MAX_M-1; j >= 0; j--) {
            if (dp[i][j] == INF) continue;
            for (int k = 1; k <= MAX_M; k++) {
                ll nv = (ll)j * k; 
                if (nv >= MAX_M) break;
                dp[i+1][nv] = min(dp[i+1][nv],
                                  max(dp[i][j], abs(v[i]-nv) / v[i]));
            }

        }
    }
    double res = INF;
    for (int i = 0; i < MAX_M; i++) {
        res = min(res, dp[N][i]);
    }
    printf("%.15f\n", res);
    return 0;
}

Measured memory_bytes: 27872
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, k = map(int, input().split())
data = getSomeInputInt(n)

data.sort()


ans = sys.maxsize

for i in range(n-k+1):
    tmp = data[i+k-1] - data[i]
    ans = min(ans, tmp)

print(ans)

Measured memory_bytes: 17700
#include<bits/stdc++.h>
using namespace std;
 
#define MOD 998244353
template<typename ty1,typename ty2>
inline int add(ty1 x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x += y; return x < MOD ? x : x - MOD;
}
template<typename ty1,typename ty2>
inline void addto(ty1 &x, ty2 y) {
		  if(y>=MOD)y%=MOD;
		  if(x>=MOD)x%=MOD;
	      x += y; if (x >= MOD) x -= MOD;
}
template<typename ty1,typename ty2>
inline int sub(ty1 x, ty2 y) {
		if(y>=MOD)y%=MOD;
		 if(x>=MOD)x%=MOD;
        x -= y; return x < 0 ? x + MOD : x;
}
template<typename ty1,typename ty2>
inline void subto(ty1 &x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x -= y; if (x < 0) x += MOD;
}
template<typename ty1,typename ty2>
inline int mul(ty1 x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        return 1ll * x * y % MOD;
}
template<typename ty1,typename ty2>
void multo(ty1 &x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        x=1ll * x * y % MOD;
}
 
 
long long int ppow(long long int i, long long int j){
		long long int res = 1LL;
		while (j){
			if ((j & 1LL)){
				res *= i;
				if (res >= MOD){
					res %= MOD;
				}
			}
			j >>= 1;
			i *= i;
			if (i >= MOD){
				i %= MOD;
			}
		}
		return res;
	}
class Combination{
	
public:
	vector<long long int> k;
	vector<long long int> r;
	void resize(int N){
		k.resize(N + 2);
		r.resize(N + 2);
		k[0] = 1;
		for (int i = 1; i < N+2; i++){
			k[i] = k[i - 1];
			k[i] *= i;
			if (k[i] >= MOD)k[i] %= MOD;
		}
		long long int al = k[k.size() - 1];
		long long int iv = ppow(k[k.size() - 1],MOD-2);
		r[k.size() - 1] = iv;
		for (int i = (int)(r.size()) - 2; i >= 0; i--){
			r[i] = r[i + 1] * (i + 1);
			if (r[i] >= MOD){
				r[i] %= MOD;
			}
		}
	}
	long long int C(int a, int b){
		if (a < b)return 0;
		long long int up = k[a];
		long long int dw = r[b] * r[a - b];
		dw %= MOD;
		up *= dw;
		up %= MOD;
		return up;
	}
	long long int H(int a, int b){
		return C(a + b - 1, b);
	}
	long long int catalan_number(int n){
		return (C(2 * n, n) + MOD - C(2 * n, n - 1)) % MOD;
	}
};
Combination C;

#define MAX 302

int n;
int m;

bitset<MAX> ar[MAX];
vector<bitset<MAX> > basis;


int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int a;
			scanf("%d",&a);
			ar[i].set(j,a);
		}
	}
	auto cmp=[&](bitset<MAX> a,bitset<MAX> b){
		auto sz=(MAX+63)/64;
		auto a_=(const uint64_t *)&a;
		auto b_=(const uint64_t *)&b;
		for(int i=sz-1;i>=0;i--){
			if(a_[i]==b_[i])continue;
			return a_[i]<b_[i];
		}
		return false;
	};
	for(int i=0;i<n;i++){
		sort(basis.begin(),basis.end(),cmp);
		for(int j=basis.size()-1;j>=0;j--){
			auto tmp=(basis[j]^ar[i]);
			if(cmp(tmp,ar[i])){
				swap(ar[i],tmp);
			}
		}
		if(ar[i].any()){
			basis.push_back(ar[i]);
		}
	}
	long long int ans=sub(ppow(2,n),ppow(2,n-basis.size()));
	multo(ans,ppow(2,m-1));
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
#define dbg          cout<<"Freak"<<endl;
#define dbgg(i)      cout<<i<<endl;
#define N            1e9+7;
using namespace std;
ll t;
ll arr[200005];
int main()
{
    ll a,b,c,d,e,f,i,j;
    cin>>a>>b;
    c=0;
    for(i=0;i<a;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+a);
    if(a<=b)cout<<'0'<<endl;
    else
    {
        for(i=0;i<a-b;i++)c+=arr[i];
        cout<<c<<endl;
    }
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template < typename T > string tost( const T& n ) { ostringstream stm; stm << n; return stm.str();}
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 const INF = 1001001001;


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

int N,M,X;
cin >> N >> M >> X;
vi cost(N+1,0);
rep(i,M) {
    int A;
    cin >> A;
    cost[A] = 1;
}
int cnt = 0;
rep(i,N+1) {
    cnt += cost[i];
    if(i == X) break;
}
int ans = min(cnt, M-cnt);
cout << ans << endl;
return 0;
}

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

using namespace std;

signed main() {
    int N;
    cin >> N;
    vector<int> yen;
    vector<float> btc;
    for (int i=0;i<N;i++){
        float value;
        string which_coin;
        cin >> value >> which_coin;
        if(which_coin == "JPY"){
            yen.push_back((int)value);
        }else{
            btc.push_back(value);
        }
    }
    float rate = 380000.0;
    float sum_yen = 0.0;
    for(int yen_e: yen){
        sum_yen += yen_e;
    }
    for(float btc_e: btc){
        sum_yen += btc_e * rate;
    }

    cout << sum_yen << endl;
}


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

typedef complex<double> P;
typedef vector<P> G;

int main()
{
  int n,k,m;
  for(;cin>>n>>k>>m,n;)
    {
      vector<int> s;
      for(int i=0;i<n;i++)
        s.push_back(i+1);
      int now=(m-1)%n;
      //   cerr<<now<<endl;
      s.erase(s.begin()+now);
      while(s.size()>1)
        {
          now=((now+k)-1)%s.size();
          //     cerr<<now<<endl;
          s.erase(s.begin()+now);
        }

      cout<<s[0]<<endl;
    }

}

Measured memory_bytes: 1324
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999

int main() {
	int a,b;
	cin >> a >> b;
	cout << max(a,b) - min(a,b) << endl;
}


Measured memory_bytes: 3104