akhauriyash/Code-Regression huggingface dataset:
from math import factorial

MOD = 10**9+7
def comb_mod(n, r):
  combination = factorial(n) // (factorial(n-r)*factorial(r))
  return combination % MOD

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

if n == k:
  for i in range(1, k+1):
    if i == 1:
      print(1)
    else:
      print(0)
else:
  for i in range(1, k+1):
    if (n-k+1 >= i):
      print((comb_mod(n-k+1, i) * comb_mod(k-1, i-1))%MOD)
    else:
      print(0)

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

const int INF = 1001001001;

int main(){
    ll n, x; cin >> n >> x;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    ll ans = 0;
    for(int i = 0; i < n-1; i++){
        if(a[i] > x){
            ll tmp = a[i] - x;
            ans += tmp + a[i+1];
            a[i+1] = 0;
        }
        else{
            if(a[i+1] + a[i] <= x) continue;
            else{
                ll tmp = a[i+1] + a[i] - x;
                ans += tmp;
                a[i+1] -= tmp;
                if(i + 1 == n - 1 && a[i+1] > x) ans += a[i+1] - x;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4000
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long 
#define INF 1e9
#define LINF 1e18
 
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef pair<P, P> PP;
 
const int MOD = 1e9 + 7;
const int dy[] = { 0, 0, 1, -1 };
const int dx[] = { 1, -1, 0, 0 };
 
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

signed main() {
    int a[5];
    int latte = 10, malta;
    for(int i = 0; i < 5; ++i) {
        cin >> a[i];
        if(latte > a[i] % 10 && a[i] % 10 != 0) {
            latte = a[i] % 10;
            malta = i;
        }
    }
    int res = 0;
    for(int i = 0; i < 5; ++i) {
        if(i == malta) continue;
        res += a[i];
        if(a[i] % 10 != 0) res += 10 - (a[i] % 10);
    }
    cout << res + a[malta] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
int main()
{
	int t=1;
	//cin>>t;
	while(t--)
	{
		int x,n;
		cin>>x>>n;
		int arr[n];
		for(int i=0;i<n;i++)
		{
			cin>>arr[i];
		}
		if(n==0)
		{
			cout<<x<<endl;
		}
		else
		{
			int ans1=102,ans2=102;
			for(int i=x;i>=0;i--)
			{
				int flag=0;
				for(int j=0;j<n;j++)
				{
					if(arr[j]==i)
					{
						flag=1;
						break;
					}
				}
				if(flag)
				{
					continue;
				}
				else
				{
					ans1=i;
					break;
				}
			}
			//cout<<ans1<<endl;
			for(int i=x;i<=101;i++)
			{
				int flag=0;
				for(int j=0;j<n;j++)
				{
					if(arr[j]==i)
					{
						flag=1;
						break;
					}
				}
				if(flag)
				{
					continue;
				}
				else
				{
					ans2=i;
					break;
				}
			}
			int ans;
			if(abs(x-ans1)<abs(x-ans2))
			{
				ans=ans1;
			}
			else if(abs(x-ans1)>abs(x-ans2))
			{
				ans=ans2;
			}
			else
			{
				ans=min(ans1,ans2);
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3620
// abc173_b
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
  int N;
  cin>>N;
  multiset<string> S;
  rep(i, N) {
    string tmp;
    cin>>tmp;
    S.insert(tmp);
  }
  cout<<"AC x "<<S.count("AC")<<endl;
  cout<<"WA x "<<S.count("WA")<<endl;
  cout<<"TLE x "<<S.count("TLE")<<endl;
  cout<<"RE x "<<S.count("RE")<<endl;
  return 0;
}


Measured memory_bytes: 11448
#include <bits/stdc++.h>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define rep(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+5;
int prime[N],sum[N];
bool is_pr[N];
int cnt;
inline int Scan()
{
    int r = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        r = (r << 3) + (r << 1) + ch - '0';
        ch = getchar();
    }
    return r * f;
}
inline void Print(int x)
{
    if(x < 0)
    {
        x = -x;
        putchar('-');
    }
    if(x > 9)Print(x/10);
    putchar(x % 10 + '0');
}
void sieve()
{
    cnt=0;
    mem(is_pr,0);
    for(int i=2; i*i<=N; i++)
    {
        if(!is_pr[i])
        {
            for(int j=i*i; j<=N; j+=i)
                is_pr[j]=1;
        }
    }
    for(int i=2; i<N; i++) if(!is_pr[i]) prime[cnt++]=i;
    mem(sum,0);
    for(int i=1; i<cnt; i++)
    {
        int tmp=(prime[i]+1)/2;
        int pos=lower_bound(prime,prime+i,tmp)-prime;
        if(prime[pos]==tmp) sum[prime[i]]++;
    }
    for(int i=1; i<cnt; i++) sum[prime[i]]+=sum[prime[i-1]];
}
int main()
{
    sieve();
    int q;
    while(~scanf("%d",&q))
    {
        rep(i,0,q)
        {
            int l,r;
            l = Scan();
            r = Scan();
            int pos1=lower_bound(prime,prime+cnt,l)-prime;
            int pos2=lower_bound(prime,prime+cnt,r)-prime;
            r = (prime[pos2] == r) ? prime[pos2] : prime[pos2-1];
            int ans=sum[r]-sum[prime[pos1-1]];
            Print(ans);
            puts("");
        }
    }
    return 0;
}


Measured memory_bytes: 1152
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output


def chkprint(*args):
    names = {id(v): k for k, v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))

# Binary converter


def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]

# --------------------------------------------


dp = None


def main():
    lower = "abcdefghijklmnopqrstuvwxyzAC"
    S = input()

    if S[0] != "A":
        print("WA")
        return

    if S[2:-1].count("C") != 1:
        print("WA")
        return

    for s in S:
        if s not in lower:
            print("WA")
            return

    print("AC")


main()


Measured memory_bytes: 5140
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  int x, y;
  for (int i = 0; i < n; ++i) {
    cin >> x >> y;
    a[i] = x + y;
    b[i] = x - y;
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  cout << max(a[n-1] - a[0], b[n-1] - b[0]) << '\n';

  return 0;
}


Measured memory_bytes: 4828
#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;

int main(){
  int N, score;
  cin >> N >> score;
  vector<int> mon(N);
  vector<int> bornus(N);
  for(int i = 0; i < N; i++){
    cin >> mon[i] >> bornus[i];
  }
  int result = 1e9;
  for(int bit = 0; bit < (1 << N); bit++){
    bitset<10> bs(bit);
    int sum = 0, cnt = 0, j = -1;
    for(int i = 0; i < N; i++){
      if(bit & 1 << i){
        // 完全に解く配点
        sum += mon[i] * 100*(i + 1) + bornus[i];
        cnt += mon[i]; 
      }else{
        // 中途半端に解く配点(完全に解く配点以外の配点の中で最も高い配点)
        j = i;
      }
    }

    if(sum >= score){
      result = min(result, cnt);
      continue;
    }

    // 中途半端に解く配点の問題を1問除きすべて解いても目標点に達しない場合は、
    // 完全に解く配点の選択が不適切であったとて無視します
    int tmp = mon[j];   
    while(tmp > 0){
      sum += 100 * (j + 1);
      cnt++;
      tmp--;
      if(sum >= score){
        result = min(result, cnt);
        break;
      }
    }
  }

  cout << result << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;


int main(){
  ll n; cin >> n; ll sum = 0;
  rep(i,n){
    ll x; cin >> x;
    sum += x;
  }
  
  cout << sum - n << endl;
}

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

int main(){
    ll x;
    cin >> x;
    ll a = 100;
    ll ans = 0;
    for(int i=1; i>=0; i++){
        a += a/100;
        if(x <= a){
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
/* AtCoder Beginner Contest diverta2019_2
 * Problem B
 * Au: SJoshua
 */
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <set>
 
using namespace std;
 
struct point {
	int x, y;
	bool operator < (const point &p) const {
		return x == p.x ? y < p.y : x < p.x;
	}
};
 
int main(void) {
	int n;
	cin >> n;
	vector <point> points(n);
	for (int i = 0; i < n; i++) {
		cin >> points[i].x >> points[i].y;
	}
	sort(points.begin(), points.end());
	int ans = n == 1 ? 1 : 0xffffff;
	for (int i = 0; i < n; i++) { // the first ball
		for (int j = i + 1; j < n; j++) { // the second ball
			int p = points[i].x - points[j].x;
			int q = points[i].y - points[j].y;
			set <point> st;
			int cur = 1;
			for (int k = 0; k < n; k++) {
				if (k != i && k != j) {
					st.insert(points[k]);
				}
			}
			auto last = points[j];
			while (!st.empty()) {
				point nxt = {last.x - p, last.y - q};
				if (st.count(nxt)) {
					last = nxt;
					st.erase(nxt);
				} else {
					last = *st.begin();
					st.erase(st.begin());
					cur++;
				}
			}
			if (cur < ans) {
				ans = cur;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

const string str[10] = {
    "pon", "pon", "hon", "bon","hon", "hon", "pon", "hon", "pon", "hon"
};

int main(){
    int n; scanf("%d", &n);
    printf("%s\n", str[n%10].c_str());
    return 0;
}


Measured memory_bytes: 3692
#include <stdio.h>
#define N 10000
typedef struct {
  char name;
  int value;
 
}Card;

void Bubble(Card c[],int n){
  Card swap;
  int i,j;
  for(i=0; i<=n-1; i++) {
    for(j=n-1; j>=i+1; j--) {
      if(c[j].value<c[j-1].value) {
	swap=c[j];
	c[j]=c[j-1];
	c[j-1] =swap;
      }
    }
  }
  for(i=0; i<n-1; i++) {
    printf("%c%d ",c[i].name,c[i].value);
  }
  printf("%c%d",c[i].name,c[i].value);
  printf("\n");
}

void Selection(Card c[],int n){
  Card swap;
  int i,j;
  int minj;
  for(i=0; i<n; i++) {
    minj=i;
    for(j=i+1; j<n; j++) {
      if(c[j].value<c[minj].value) {
	minj=j;
 
      }
 
    }
    swap=c[i];
    c[i]=c[minj];
    c[minj] =swap;
  }
  for(i=0; i<n-1; i++) {
    printf("%c%d ",c[i].name,c[i].value);
  }
  printf("%c%d",c[i].name,c[i].value);
  printf("\n");
}

int isStable(Card A[],Card B[],int n){
  int flug=0,i;
  for(i=0; i<n; i++) {
    if(A[i].name!=B[i].name) {
      flug++;
    }
 
  }
  if(flug==0) return 1;
  else return 0;
}

int main(){
  int i,n;
  Card A[N],B[N];
  scanf("%d",&n);
  for(i=0; i<n; i++) {
    scanf("%c%c%d",&A[i].name,&A[i].name,&A[i].value);
    B[i]=A[i];
  }
 
  Bubble(A, n);
  printf("Stable\n");
  Selection(B, n);
  if(isStable(A,B,n)) {
    printf("Stable\n");
  }
  else  {
 
    printf("Not stable\n");
  }
  return 0;
}

Measured memory_bytes: 624
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

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

int n, k;
int d[110][70000];
vector<int> vec;

signed main() {
	cin >> n >> k;
	for (int i = 1; i*i <= n; i++) {
		vec.push_back(i);
		vec.push_back(n / i);
	}
	vec.push_back(0);
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	for (int i = 1; i < (int)vec.size(); i++)d[1][i] = vec[i] % mod;
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j < (int)vec.size(); j++) {
			d[i][j] = (d[i][j - 1] + (d[i - 1][(int)vec.size() - j])*(vec[j] - vec[j - 1])) % mod;
		}
	}
	cout << d[k][(int)vec.size() - 1] << endl;
}

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

const ll com_max = 510000;

ll fac[com_max], inv[com_max], finv[com_max];

void com_init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;

    for (ll i = 2; i < com_max; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

ll com(ll n, ll k) {
    if (n < k) {
        return 0;
    }
    if (n < 0 || k < 0) {
        return 0;
    }

    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main() {
source:
    ll n, k;
    cin >> n >> k;
    ll sum = 0;
    ll num = min(k, n - 1);
    com_init();
    rep(m, num + 1) {
        ll temp = com(n - 1, n - m - 1);
        sum += com(n, m) * temp;
        sum %= mod;
    }
    cout << sum << endl;
    return 0;
}



Measured memory_bytes: 12160
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int n,a;
	cin>>n;
	a=n;
	int sum=0;
	while (n)
	{
		sum+=n%10;
		n/=10;
	}
	if (a%sum==0)
	cout<<"Yes";
	else
	cout<<"No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector<long long> da(n);
	vector<bool> ju(n,false);
	int co = 0;
	for (int i = 0;i < n - 1;i++) {
		if (s[i] == 'A'&&s[i + 1] == 'C') {
			co++;
			ju[i] = true;
		}
		da[i] = co;
	}
	da[n - 1] = co;
	vector<long long> id(q);
	vector<long long> hu(q);
	for (int i = 0;i < q;i++)
		cin >> id[i] >> hu[i];
	for (int i = 0;i < q;i++) {
		int x = 0;
		if (ju[id[i]-1])
			x++;
		cout << (long long)da[hu[i]-2] - da[id[i]-1] + x << endl;
	}
	/*for (int i = 0;i < n;i++) {
		cout << da[i] << endl;
	}*/
}

Measured memory_bytes: 3456
#include <stdio.h>


int main(void){
  int a,b;
  int ans;

  scanf("%d %d",&a,&b );

  if (a>=b*2) {
    ans=a-b*2;
  }else{
    ans = 0;
  }


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

  return 0;
}


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

int main(){
    char X, Y;

    cin >> X >> Y;

    if(X > Y){
        cout << ">" << endl;
    }
    else if(X < Y){
        cout << "<" << endl;
    }
    else if(X = Y){
        cout << "=" << endl;
    }
    

} 

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 998244353
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	int n;cin>>n;
	vi v(n),a,b;
	rep(i,n){
		cin>>v[i];
		if(i%2==0){
			a.PB(v[i]);
		}
		else{
			b.PB(v[i]);
		}
	}
	vii ca(100001,MP(0,0));
	vii cb(100001,MP(0,0));
	int x=a.size();
	rep(i,x){
		ca[a[i]].F++;
		cb[b[i]].F++;
		if(ca[a[i]].S==0){ca[a[i]].S=a[i];}
		if(cb[b[i]].S==0){cb[b[i]].S=b[i];}	
	}
	sort(all(ca));reverse(all(ca));
	sort(all(cb));reverse(all(cb));
	if(ca[0].S!=cb[0].S){
		cout<<n-ca[0].F-cb[0].F<<endl;
	}
	else{
		cout<<min(n-ca[0].F-cb[1].F,n-ca[1].F-cb[0].F)<<endl;
	}
}


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

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;
	cin>>n;
	int** arr = new int*[n];
	for(int i=0;i<n;i++){
	    arr[i] = new int[n];
	    for(int j=0;j<n;j++){
	        cin>>arr[i][j];
	    }
	}
	ll score[(1<<n)] = {};
	for(int k=1;k<(1<<n);k++){
	    for(int i=0;i<n;i++){
	        if((k&(1<<i)) != 0){
	            for(int j=i+1;j<n;j++){
	                if((k&(1<<j)) != 0){
	                    score[k] += arr[i][j];
	                }
	            }
	        }
	    }
	}
	ll dp[(1<<n)] = {};
	for(int k=1;k<(1<<n);k++){
	    for(int m=k;m>=1;m=((m-1)&k)){
	        dp[k] = max(dp[k], score[m] + dp[k-m]);
	    }
	}
	cout<<dp[(1<<n)-1];
}

Measured memory_bytes: 1280
use std::cmp;

const INF: u64 = 1e15 as u64;

fn main() {
    let sc = std::io::stdin();
    let mut sc = Scanner { reader: sc.lock() };

    let n = sc.read();
    let limit = sc.read();
    let mut w: Vec<u64> = vec![0; n];
    let mut v: Vec<usize> = vec![0; n];
    for i in 0..n {
        w[i] = sc.read();
        v[i] = sc.read();
    }
    let v_sum = v.iter().sum::<usize>();
    let mut dp = vec![INF; v_sum + 1];
    dp[0] = 0;
    for i in 0..n {
        for cur in (0..v_sum).rev() {
            if cur + v[i] <= v_sum {
                dp[cur + v[i]] = cmp::min(dp[cur + v[i]], dp[cur] + w[i]);
            }
        }
    }

    let ans = dp
        .iter()
        .enumerate()
        .filter(|&(_, w)| *w <= limit)
        .map(|(v, _)| v)
        .max()
        .unwrap();
    println!("{}", ans);
}

pub struct Scanner<R> {
    reader: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

int main() {
  vector<char>s(3);
  for(int i=0; i<3; i++){
    cin >> s.at(i);
  }
  if((s.at(0) == s.at(1)) && (s.at(1) == s.at(2)))
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
}

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

int main(void){
  long long int x,y,g,l,t;
  while(cin >> x >> y){
    if(x<y)
      swap(x,y);
    g=__gcd(x,y);
    l=x*y/g;
    cout << g << " " << l <<endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
#include <algorithm>
#define INF 100000000000000
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());

//グラフ理論用変数
//vector<vector<llong> > graph(N);


int main(){
    llong X[5];
    for(int i=0; i<5; i++){
        cin >> X[i];
    }
    for(int i=0; i<5; i++){
        if(X[i]==0){
            cout << i+1 << endl;
        }
    }
}

Measured memory_bytes: 3132
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

#define MAX_N 310

double x[MAX_N], y[MAX_N];
int n, maxn;

int main() {
	while (true) {
		cin >> n;
		if (n == 0) { break; }
		for (int i = 0; i < n; i++) {
			cin >> x[i] >> y[i];
		}
		maxn = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				int sum = 0;

				double X = (x[i] + x[j]) / 2.0;
				double Y = (y[i] + y[j]) / 2.0;

				for (int k = 0; k < n; k++)
				{
					if (((x[k] - X)*(x[k] - X) + (y[k] - Y)*(y[k] - Y)) <= 1) {
						sum++;
					}
				}
				maxn = max(maxn, sum);

				double X1, Y1, X2, Y2, X3, Y3, VX2, VY2, Dist, Dist2;

				Dist = sqrt((x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]));
				Dist2 = sqrt(4 - Dist*Dist);

				X2 = x[j] - x[i]; Y2 = y[j] - y[i];
				VX2 = (X2 / Dist)*Dist2 / 2; VY2 = (Y2 / Dist)*Dist2 / 2;

				X1 = X + VY2; Y1 = Y - VX2;
				X3 = X - VY2; Y3 = Y + VX2;

				sum = 0;
				for (int k = 0; k < n; k++) {
					if (((x[k] - X1)*(x[k] - X1) + (y[k] - Y1)*(y[k] - Y1)) <= 1.0001) {
						sum++;
					}
				}
				maxn = max(maxn, sum);
				sum = 0;
				for (int k = 0; k < n; k++) {
					if (((x[k] - X3)*(x[k] - X3) + (y[k] - Y3)*(y[k] - Y3)) <= 1.0001) {
						sum++;
					}
				}
				maxn = max(maxn, sum);
			}
		}
		for (int i = 0; i < n; i++) {
			int sum = 0;
			long double X = x[i];
			long double Y = y[i];
			for (int k = 0; k < n; k++) {
				if (((x[k] - X)*(x[k] - X) + (y[k] - Y)*(y[k] - Y)) <= 1) {
					sum++;
				}
			}
			maxn = max(maxn, sum);
		}
		cout << maxn << endl;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
        int N;
        cin>>N;
        int a[101];
        for(int i=0;i<N;i++){
                cin>>a[i];
        }
        sort(a, a+N);
        ll ans=1000000000000;
        for(int i=-100;i<=100;i++){
                ll vans=0;
                for(int j=0;j<N;j++){
                        vans+=pow(a[j]-i, 2);
                }
                ans=min(ans, vans);
        }
        cout<<ans<<endl;
        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long int n; cin >> n;
	long long int x[200005], a[200005];
	for(long long int i=0;i<n;i++){
		cin >> x[i];
		a[i] = x[i];
	}
	sort(a,a+n);
	long long int s = a[n/2-1];
	long long int t = a[n/2];
	for(long long int i=0;i<n;i++){
		if(s<x[i]){
			cout << s << endl;
		}else{
			cout << t << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
map <string,int> mp;

int main()
{
	int n;
	cin>>n;
	string str;
	while(n--)
	{
		cin>>str;
		mp[str]++;
		
	}
	cout<<"AC x "<<mp["AC"]<<endl;
	cout<<"WA x "<<mp["WA"]<<endl;
	cout<<"TLE x "<<mp["TLE"]<<endl;
	cout<<"RE x "<<mp["RE"];
	 return 0;
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    ll a;
    set<ll> table;
    REP(i,n){
        cin >> a;
        auto itr=table.find(a);
        if(itr != table.end()){
            table.erase(a);
        }else{
            table.insert(a);
        }
    }
    cout << table.size() << endl;

}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
typedef long long int ll;
using namespace std;
using Graph = vector<vector<int> >;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
string s;
cin>>s;
replace(s.begin(),s.end(),',',' ');
cout<<s<<endl;
//system("pause");
return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#pragma GCC optimize("unroll-loops")
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define DB double
#define ST string
#define BS bitset
#define VE vector
#define VL vector<LL>
#define VP vector<pair<LL,LL>>
#define VVL vector<vector<LL>>
#define PQ priority_queue
#define PQS priority_queue<LL,vector<LL>,greater<LL>>
#define PB push_back
#define POB pop_back
#define PF push_front
#define POF pop_front
#define EB emplace_back
#define MP make_pair
#define TS to_string
#define TU to_ullong
#define FOR(i,a,n) for(i=a;i<n;i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define UB(a,n) *upper_bound(ALL(a),n)
#define LB(a,n) *lower_bound(ALL(a),n)
#define INF 1145141919810364364
#define PI 3.14159265358979
#define MOD 1000000007
//#define MOD 998244353
#define ERR 0.00000001
//#define ERR 0.00000000000001
#define NUM 200010
#define FAST cin.tie(0);ios::sync_with_stdio(false)

void Yn(LL a){if(a)printf("Yes\n");else printf("No\n");}
void YN(LL a){if(a)printf("YES\n");else printf("NO\n");}
LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;}
LL GCD(LL a,LL b){LL c=1,tmp=max(a,b);b=min(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int lcmpr(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return -1;if(*(LL*)a<*(LL*)b)return 1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int ccmpr(const void* a,const void* b){return *(char*)b-*(char*)a;}
int scmp(const void* a,const void* b){return strcmp((char*)a,(char*)b);}
int scmpr(const void* a,const void* b){return strcmp((char*)b,(char*)a);}
LL mod(LL a,LL m){if(a<0)return a%m+m;else return a%m;}
LL DIV(LL a,LL d){LL m=MOD,x=1,y=0,k;while(m){k=d/m;d-=k*m;swap(m,d);x-=k*y;swap(x,y);}return mod(a*mod(x,MOD),MOD);}
LL POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return ans;}
LL fact[NUM],finv[NUM],inv[NUM];
void comi(){LL i;fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}
bool cmps(pair<LL,LL> a,pair<LL,LL> b){if(a.second!=b.second)return a.second<b.second;return a.first<b.first;}

LL ans[100005],q;
void DFS(LL n){
  LL a,b;
  a=n*10+n%10;
  if(a<3234566668){
    ans[q++]=a;
    DFS(a);
    //cout<<a<<endl;
    if(n%10!=0){
      b=a-1;
      ans[q++]=b;
      DFS(b);
      //cout<<b<<endl;
    }
    if(n%10!=9){
      b=a+1;
      ans[q++]=b;
      DFS(b);
      //cout<<b<<endl;
    }
  }
}

int main(){
  FAST;
  LL i,K;
  q=9;
  cin>>K;
  rep(i,9)ans[i]=i+1;
  rep(i,9)DFS(i+1);
  qsort(ans,100000,sizeof(LL),lcmp);
  //rep(i,K)cout<<ans[i]<<endl;
  cout<<ans[K-1]<<endl;
}


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

int main() {
	//入力
	string k;
	cin >> k;

	//処理
	int ans = 0;
	if (k.at(0) == 'o') ans++;
	if (k.at(1) == 'o') ans++;
	if (k.at(2) == 'o') ans++;

	cout << 700 + (ans * 100) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    if (N == M) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
def main():
    N,M = map(int,input().split())
    A = [int(i) for i in input().split()]
    for i in A:
        N -= i
    if N < 0:
        print('-1')
    else:
        print(N)
if __name__ == '__main__':
    main()

Measured memory_bytes: 10056
def acinput():
    return list(map(int, input().split(" ")))

N=int(input())
bars=[]
for i in range(N):
    tmp = acinput()
    tmp.extend([tmp[0]-tmp[1],tmp[0]+tmp[1]])
    bars.append(tmp)

bars=sorted(bars,key=lambda x:x[3])

#print(bars)

count=0
R=-10000000000
for i in range(0,N):

    if R<=bars[i][2]:
        R=bars[i][3]
        count+=1


print(count)


Measured memory_bytes: 36264
import Control.Monad

main :: IO ()
main = do
  n <- readLn :: IO Int
  s <- replicateM n (readLn :: IO Int)
  print $ solve s

solve :: [Int] -> Int
solve ls = if sls `mod` 10 == 0 then subsolve ls else sls where
  sls = sum ls

subsolve :: [Int] -> Int
subsolve ls = if null ls' then 0 else sum ls - minimum ls' where
  ls' = filter (\n -> n `mod` 10 /= 0) ls


Measured memory_bytes: 1020
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, p = map(int, input().split())
l = list(map(int, input().split()))

o = 0
e = 0
for i in range(n):
    if l[i] % 2 == 0:
        e += 1
    else:
        o += 1

if p == 0:
    a = 0
    for i in range(e+1):
        a += comb(e, i)
    b = 0
    for i in range(0, o+1, 2):
        b += comb(o, i)
    print(a*b)

else:
    a = 0
    for i in range(e+1):
        a += comb(e, i)
    b = 0
    for i in range(1, o+1, 2):
        b += comb(o, i)
    print(a*b)
   

Measured memory_bytes: 3064
import java.util.*;
public class Main {
    public static void main(String[] args){
      // 入力
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      long[] A = new long[N];
      long result = 1L;
      
      for(int i = 0; i < N; i++){
        A[i] = sc.nextLong();
        if(A[i] == 0){
          result = 0L;
          break;
        }
      }
      
      // 計算
      if(result != 0){
        for(int i = 0; i < N; i++){
          long old = result;
          result *= A[i];
          if(result > 1000000000000000000L || result < old){
            result = -1;
            break;
          }
        }
      }
      
      
      // 出力
      System.out.println(result);
    }
    
}

Measured memory_bytes: 61040
extern crate core;

use std::io::{self, Read};
use std::collections::HashSet;

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let output = run(input.trim().to_string());
    println!("{}", output);
}

fn run(input: String) -> String {
    let list = input
        .split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect::<Vec<_>>();

    let a = list[0] * 100;
    let b = list[1] * 100;
    let c = list[2];
    let d = list[3];
    let e = list[4];
    let f = list[5];

    //砂糖の組み合わせ
    let ss = {
        let mut set = HashSet::new();
        for i in 0..1500 + 1 {
            for j in 0..1500 + 1 {
                set.insert(i * c + j * d);
            }
        }
        let mut vec = set.into_iter().collect::<Vec<_>>();
        vec.sort();
        vec
    };

    //パーセント/砂糖水/砂糖
    let mut max = (0.0, 0, 0);

    for i_1 in 0..30 + 1 {
        for i_2 in 0..30 + 1 {
            for &s in &ss {
                let w = i_1 * a + i_2 * b;
                //溶け残ってる||質量オーバー
                if s > w * e / 100 || s + w > f {
                    break;
                }

                //濃度
                let p = if w + s == 0 {
                    0.0
                } else {
                    100.0 * s as f64 / (s + w) as f64
                };

                //濃度がより高ければ
                if p > max.0 {
                    max = (p, w + s, s);
                }
            }
        }
    }

    if max.1 == 0 && max.2 == 0 {
        max.1 = a;
    }

    format!("{} {}", max.1, max.2).to_string()
}

macro_rules! tests {
    ($($name:ident: $input:expr=>$output:expr,)*) => {
        mod tests {
            $(
                #[test]
                fn $name() {
                    assert_eq!(super::run($input.to_string()), $output.to_string());
                }
            )*
        }
    }
}

tests! {
    test1: "1 2 10 20 15 200" => "110 10",
    test2: "1 2 1 2 100 1000" => "400 200",
    test3:"17 19 22 26 55 2802"=>"2634 934",
}


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

int main() {
	int n,k;cin>>n>>k;
	int arr[n],dp[n];
	for(int i=0;i<n;i++){cin>>arr[i];dp[i]=INT_MAX;}
	
	dp[0]=0;
	for(int i=1;i<min(n,k);i++){
	    for(int j=0;j<i;j++){
	        //cout<<dp[j]+abs(arr[i]-arr[j])<<" ";
	        dp[i]=min(dp[i],dp[j]+abs(arr[i]-arr[j]));
	    }
	}
	for(int i=k;i<n;i++){
	    for(int j=i-k;j<i;j++){
	        dp[i]=min(dp[i],dp[j]+abs(arr[i]-arr[j]));
	    }
	}
	//for(int i=0;i<n;i++){cout<<dp[i]<<" ";}cout<<endl;
	cout<<dp[n-1];
	return 0;
}


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

map<int,bool>mp;

int main()
{

    int n,k;
    cin>>n>>k;
    int a[n+5];
    for(int i=0; i<n; i++)
        cin>>a[i];

    for(int rem=0 ; rem<=k; rem++)
    {
        for(int i=0; i<n; i++)
        {
            if(a[i]>rem)
                continue;
            if(mp[rem-a[i]]==false)
                mp[rem]=true;
        }
    }

    if(mp[k]==true)
        cout<<"First"<<endl;
    else
        cout<<"Second"<<endl;
    return 0;
}


Measured memory_bytes: 8300
def contains3(n):
    x = n
    while x > 0:
        if x % 10 == 3:
            return True
        else:
            x //= 10
    return False

x = int(input())
out = ""
for i in range(x):
    n = i + 1
    if n % 3 == 0 or contains3(n):
        out += (" %d" % n)
print(out)

Measured memory_bytes: 7716
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using u128 = __uint128_t;

#define int long long
#define idxSet tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define atIdx find_by_order
#define idxOf order_of_key
#define MOD 1000000007
#define MAX 200005
//#define endl '\n'

#define v(type) vector<type>
#define p(type1, type2) pair<type1 , type2>
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int dp[MAX];


void solve() {
    int n;
    cin >> n;
    int l = 0, h = n - 1, m, ask;
    string replyL, replyH, replyM;
    ask = l;
    cout << ask << endl;
    cin >> replyL;
    if (replyL == "Vacant")
        return;

    ask = h;
    cout << ask << endl;
    cin >> replyH;
    if (replyH == "Vacant")
        return;
    while(l <= h){
        m = (l + h) / 2;
        ask = m;
        cout<<ask<<endl;
        cin>>replyM;
        if(replyM == "Vacant")
            return;
        if((m - l) % 2 == 1){
            if(replyL == replyM){
                h = m;
                replyH = replyM;
            }   else {
                l = m;
                replyL = replyM;
            }
        }else {
            if(replyL != replyM){
                h = m;
                replyH = replyM;
            }else {
                l = m;
                replyL = replyM;
            }
        }
    }

}

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

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

using namespace std;

template <long long Mod> struct ModInt {
  long long v;
  constexpr ModInt(const long long x = 0) {
    v = x % Mod;
    if (v < 0) {
      v += Mod;
    }
  }
  constexpr ModInt operator+(const ModInt rhs) const {
    return ModInt(*this) += rhs;
  }
  constexpr ModInt operator-(const ModInt rhs) const {
    return ModInt(*this) -= rhs;
  }
  constexpr ModInt operator*(const ModInt rhs) const {
    return ModInt(*this) *= rhs;
  }
  constexpr ModInt operator/(const ModInt rhs) const {
    return ModInt(*this) /= rhs;
  }
  const ModInt &operator+=(const ModInt rhs) {
    v += rhs.v;
    if (v >= Mod) {
      v -= Mod;
    }
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt rhs) {
    if (v < rhs.v) {
      v += Mod;
    }
    v -= rhs.v;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt rhs) {
    v = v * rhs.v % Mod;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt rhs) {
    long long exp = Mod - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  friend ostream &operator<<(ostream &s, ModInt<Mod> m) {
    s << m.v;
    return s;
  }
  friend istream &operator>>(istream &s, ModInt<Mod> m) {
    s >> m.v;
    return s;
  }
};

const int mod = 1e9 + 7;
using modint = ModInt<mod>;
modint fac[100005], finv[100005], inv[100005];

modint nCr(int n, int r) {
  if (n < 0 or r < 0 or n < r) {
    return 0;
  }
  return fac[n] * finv[r] * finv[n - r];
}

int main() {
  fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
  for (int i = 2; i < 100005; i++) {
    fac[i] = fac[i - 1] * i;
    inv[i] = modint(mod) - inv[mod % i] * (mod / i);
    finv[i] = finv[i - 1] * inv[i];
  }

  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (auto &a : A) {
    cin >> a;
  }
  sort(A.begin(), A.end());
  modint f_max = 0;
  modint f_min = 0;
  for (int i = 1; i <= N; i++) {
    f_max += modint(A[i - 1]) * nCr(i - 1, K - 1);
    f_min += modint(A[i - 1]) * nCr(N - i, K - 1);
  }
  cout << f_max - f_min << endl;

  return 0;
}


Measured memory_bytes: 2944
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


mod = 998244353
comb = combination(mod)
n, m, k = inpl()
ans = 0
for i in range(min(n, k + 1)):
    ans += m * pow(m - 1, n - 1 - i, mod) * comb.calc(n - 1, i) % mod
    ans %= mod
print(ans)


Measured memory_bytes: 115188
import sys
from collections import defaultdict
K = int(input())

cnt = 0
now = 0
if K % 2==0:
    print(-1)
    sys.exit(0)

for i in range(10**6):
    cnt += 1
    now = (now*10 + 7)%K
    if now == 0:
        print(cnt)
        sys.exit(0)

print(-1)

Measured memory_bytes: 67800
# https://atcoder.jp/contests/abc065/tasks/arc076_b

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):                                          # 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):  # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)  # xをxの根に置き換える
        y = self.find(y)  # yをyの根に置き換える

        if x == y:  # 根が同じなら置き換える必要なし
            return False

        if self.parents[x] > self.parents[y]:  # 子がたくさんある方を x とする
            x, y = y, x

        self.parents[x] += self.parents[y]  # xの子の数を更新
        self.parents[y] = x  # yの親を更新
        return True         # 同じ木にいるかの判定も同時に行うために、返り値を設定

#####( main )#########################################################################################################################

N = int(input())


data = [(i,) + tuple(map(int, input().split())) for i in range(N)]

datax = sorted(data, key=lambda x:x[1])
datay = sorted(data, key=lambda x:x[2])

cost = []
for i in range(N-1):
    p, q = datax[i:i+2]
    pi, px, py = p
    qi, qx, qy = q
    cost.append((pi, qi, min(abs(px-qx), abs(py-qy))))
    cost.append((qi, pi, min(abs(px-qx), abs(py-qy))))
    p, q = datay[i:i+2]
    pi, px, py = p
    qi, qx, qy = q
    cost.append((pi, qi, min(abs(px-qx), abs(py-qy))))
    cost.append((qi, pi, min(abs(px-qx), abs(py-qy))))

cost.sort(key=lambda x:x[2])

tree = UnionFind(N)
res = 0
for p, q, dist in cost:
    # p -= 1
    # q -= 1                                                        # デクリメントが必要ならば、コメントアウトを消す
    if tree.union(p, q):
        res += dist                                                 # 小さい順に足されていく（プリム法と異なる）

print(res)


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

using ll = long long;
using pii = pair<int, int>;

template <typename T> constexpr T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;
template <> constexpr double inf<double> = 1e18;

int main() {
    int N; cin >> N;
    vector<int> a(N), b(N);
    set<int> bs;
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    for(int i = 0; i < N; ++i) {
        cin >> b[i];
        bs.insert(b[i]);
    }
    if(bs.size() == N) {
        cout << "Yes" << endl;
    } else {
        int not_exist = -1;
        for(int i = 1; i <= N; ++i) {
            if(bs.count(i) == 0) {
                not_exist = i;
                break;
            }
        }
        vector<int> mapping(N); // map of d
        iota(begin(mapping), end(mapping), 1);
        if(not_exist == N) {
            mapping[N - 1] = 1;
        } else {
            mapping[not_exist - 1] = N;
        }
        
        cout << "No" << endl;
        for(int i = 0; i < N; ++i) { // c is id
            cout << a[i] << " \n"[i + 1 == N];
        }
        for(int i = 0; i < N; ++i) { // d
            cout << mapping[a[i] - 1] << " \n"[i + 1 == N];
        }
    }
}


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

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

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

  ll x, y; cin >> x >> y;
  ll ans = 1;
  ll tmp = x;
  while(true) {
    tmp *= 2;
    if(tmp > y) break;
    ans++;
  }

  cout << ans << '\n';
  return 0;
}


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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007
#define PI 3.1415926535897932384626433

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int sum = k;
    for(int i = 1; i < n; i++){
        sum *= k-1;
    }
    cout << sum << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;
const int INF = 1000000000;

int main(){
	bool first = true;
	while(true){
		int x;
		cin >> x;
		if(x == 0){ break; }
		if(!first){ cout << endl; }
		first = false;
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int answer = INF;
		int aa = 0, ab = 0, ac = 0, ad = 0;
		for(int i = 0; i <= a; ++i){
			for(int j = 0; j <= b; ++j){
				for(int k = 0; k <= c; ++k){
					for(int l = 0; l <= d; ++l){
						int s = (i * 10 + j * 50 + k * 100 + l * 500);
						if(s < x){ continue; }
						int r = s - x;
						if(l > 0 && r >= 500){ continue; }
						int rd = r / 500;
						r %= 500;
						if(k > 0 && r >= 100){ continue; }
						int rc = r / 100;
						r %= 100;
						if(j > 0 && r >= 50){ continue; }
						int rb = r / 50;
						r %= 50;
						if(i > 0 && r >= 10){ continue; }
						int ra = r / 10;
						r %= 10;
						int result =
							(a - i) + (b - j) + (c - k) + (d - l) +
							ra + rb + rc + rd;
						if(result < answer){
							answer = result;
							aa = i;
							ab = j;
							ac = k;
							ad = l;
						}
					}
				}
			}
		}
		if(aa > 0){ cout << "10 " << aa << endl; }
		if(ab > 0){ cout << "50 " << ab << endl; }
		if(ac > 0){ cout << "100 " << ac << endl; }
		if(ad > 0){ cout << "500 " << ad << endl; }
	}
	return 0;
}

Measured memory_bytes: 1164