akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef long double louble;

#define so(a) ((int)((a).size()))

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

const char lf = '\n';

namespace ae86
{
	const int bufl = 1 << 15;

	char buf[bufl],*s=buf,*t=buf;

	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}

	inline int ty()
	{
		int a=0;int b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 100007 , D = 3 , __ = _ * D , LIM = 512 , mo = 998244353;
const lint linf = 1000000000000000000;

template<typename T1,typename T2> inline T1 ad(T1 &a,T2 b){return a=a+b>=mo?a+b-mo:a+b;}
template<typename T1,typename T2> inline T1 dl(T1 &a,T2 b){return a=a>=b?a-b:a-b+mo;}
template<typename T1,typename T2> inline T1 add(T1 a,T2 b){return a+b>=mo?a+b-mo:a+b;}
template<typename T1,typename T2> inline T1 del(T1 a,T2 b){return a>=b?a-b:a-b+mo;}

lint powa(lint a,lint t)
{
	lint b=1;
	while(t){if(t&1)b=b*a%mo;a=a*a%mo,t>>=1;}
	return b;
}

inline lint inva(lint a){return powa(a,mo-2);}

vector<int> e[_];
lint bas[__];
int n,sg[_];

void makef(lint f[])
{
	int m=ty();
	for(int i=1;i<=n;i++)sg[i]=0,e[i].clear();
	for(int i=1,a,b;i<=m;i++)a=ty(),b=ty(),e[min(a,b)].emplace_back(max(a,b));
	for(int i=n;i>=1;i--)
	{
		unordered_set<int> hav;
		for(auto b:e[i])hav.emplace(sg[b]);
		sg[i]=0;
		while(hav.count(sg[i]))sg[i]++;
	}
	for(int i=0;i<LIM;i++)f[i]=0;
	for(int i=1;i<=n;i++)ad(f[sg[i]],bas[i]);	
}

lint f[D][LIM];

int main()
{
	ios::sync_with_stdio(0),cout.tie(nullptr);

	n=ty();
	bas[0]=1;
	for(int i=1;i<__;i++)bas[i]=bas[i-1]*(linf%mo)%mo;
	for(int i=0;i<D;i++)makef(f[i]);

	lint ans=0;
	for(int i=0;i<LIM;i++)
		for(int j=0;j<LIM;j++)
			ad(ans,f[0][i]*f[1][j]%mo*f[2][i^j]%mo);
	cout<<ans<<lf;
	
	return 0;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
#define lol long long;
#define dob double;
int a[100000];
// size_t a =s.length();
int main(){
  string s;
  int b=0;
  for(int i=0;i<50;i++) a[i]=0;
  cin>>s;
  size_t size = s.length();
  for(int i=0;i<size;i++) a[s[i]]++;
  for(int i=0;i<size;i++){
    if(a[s[i]]%2!=0) b=1;
  }
  if(b!=0) cout<<"No\n";
  else cout<<"Yes\n";
  return(0);
}


Measured memory_bytes: 256
#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<list>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII > VP;

#define AIN(A, B, C) assert(IN(A, B, C))

//typedef int LL;
typedef long long int LL;
//typedef __int64 LL;

int dp[500005];
char S[500005];
int nxt[500005];

int main()
{
	int N;
	scanf("%d %s", &N, S+ 1);

	nxt[N + 1] = N + 1;
	nxt[N + 2] = N + 2;
	for (int i = N; i >= 1; i--) {
		if (S[i] == '0') nxt[i] = i;
		else nxt[i] = nxt[i + 1];
	}

	S[N + 1] = S[N + 2] = '0';
	dp[N + 1] = dp[N + 2] = 0;
	for (int i = N; i >= 1; i--) {
		if (S[i] == '1' && S[i + 1] == '0') {
			int nx = nxt[i + 2];
			int len = nx - (i + 2);
			dp[i] = len + dp[nx];

			//
			if (len > 0) {
				int cand = len - 1 + dp[nx - 1];
				dp[i] = MAX(dp[i], cand);
			}
		}
		if (S[i] == '1') {
			int nx = nxt[i];
			if (S[nx + 1] == '1') {
				int cand = dp[nx + 2] + nx - i;
				dp[i] = MAX(dp[i], cand);
			}

		}
		dp[i] = MAX(dp[i], dp[i + 1]);
	}
	printf("%d\n", dp[1]);
	return 0;
}


Measured memory_bytes: 4608
#include <bits/stdc++.h>
#define ll long long
#define fop(i,m,n) for(int i=m; i<n; i++)
#define MOD 998244353
#define ios ios::sync_with_stdio(0), cin.tie(0)
 
using namespace std;

int main()
{
    ios;
    
    int n, W;
    cin >> n >> W;
    int w[n], v[n];
    int vsum = 0;
    fop(i,0,n){
        cin >> w[i] >> v[i];
      	vsum += v[i];
    }
  
    ll dp[vsum+1];
    fop(i,0,vsum+1) dp[i] = pow(10, 18);
    dp[0] = 0;
    
    fop(i,0,n){
        for(int j=vsum; j>=v[i]; j--){
            dp[j] = min(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    
    for(int i=vsum; i>=0; i--){
        if(dp[i]<=W){
            cout << i;
            break;
        }
    }
    
    return 0;
}

Measured memory_bytes: 4392
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
#define eps 1e-8
#define eq(x,y) (fabs((x)-(y)) < eps)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int>pii;
const ll mod = 1e9+7;
long double PI = acosl(-1);
const ll infl = 1e18;
const int inf = 2e9;
const int nmax = 1e5+5;
const int MAXLG = log2(nmax)+1;
//mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;


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

    int n;
    cin>>n;
    ll total = 0;
    for(int i=1; i<=n; i++) total += 1LL*i*(n+1-i);
    for(int i=1; i<n; i++){
        int u,v;
        cin>>u>>v;
        if(u>v) swap(u, v);
        total -= 1LL*u*(n-v+1);
    }
    cout<<total<<endl;

}
/*

*/


Measured memory_bytes: 3628
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
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; }
bool odd(const int &n) { return n & 1; }
bool even(const int &n) { return ~n & 1; }
template<typename T> int len(const T &v) { return v.size(); }
template<typename T = int> T in() { T x; cin >> x; return x; }
template<typename T = int> T in(T &&x) { T z(forward<T>(x)); cin >> z; return z; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { return is >> p.first >> p.second; }
template<typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : "\n"); return os; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : " "); return os; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << ' ' << p.second; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
// clang-format on

main() {
  int a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;
  int ans = 0, f = a < 0;
  while (a != b) {
    if (a < 0) {
      ans += c;
      a++;
    } else if (a == 0 && f) {
      ans += d;
      f = false;
    } else {
      ans += e;
      a++;
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 3080
use proconio::*;
use std::cmp::*;

fn main() {
    input! {
        n: usize,
        m: usize,
        k: i64,
        mut a: [i64; n],
        mut b: [i64; m],
    };
    a.insert(0, 0);
    let a = a
        .iter()
        .scan(0, |a, b| {
            *a += *b;

            Some(*a)
        })
        .collect::<Vec<_>>();

    let b = b
        .iter()
        .scan(0, |a, b| {
            *a += *b;

            Some(*a)
        })
        .collect::<Vec<_>>();

    let mut ans = 0;
    for i in 0..a.len() {
        if a[i] > k {
            break;
        }

        let n = i;
        ans = max(
            ans,
            n + b
                .binary_search_by(|e| e.cmp(&(k - a[i])).then(Ordering::Less))
                .unwrap_or_else(|e| e),
        );
    }

    println!("{}", ans);
}


Measured memory_bytes: 12504
#include<stdio.h>
int main(){
  int a,b,c,d,s,g;
  scanf("%d%d%d%d",&a, &b, &c, &d);
  if(d<a || b<c){
    printf("0\n");
  }
  else{
    if(a>c){
      s=a;
    }
    else{
      s=c;
    }
    if(b>d){
      g=d;
    }
    else{
      g=b;
    }
    printf("%d\n",g-s);
  }
  return 0;
}


Measured memory_bytes: 128
def blackjack(s):
    a, b, c = [int(_) for _ in s.split()]
    if a + b + c >= 22:
        print("bust")
    else:
        print("win")

if __name__ == "__main__":
    import sys
    in_str = ''
    for line in sys.stdin:
        in_str += line
    blackjack(in_str)


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

int main(void){
    int w = 0, h = 0, n = 0;
    int x[101], y[101], a[101]; 
    int lx = 0, rx = 100, uy = 0, ty = 100;
    int ans  = 0;

    scanf("%d%d%d", &w, &h, &n);
    rx = w;
    ty = h;
    for(int i = 0; i < n; i++){
        scanf("%d%d%d", &x[i], &y[i], &a[i]);
        if(a[i] == 1){
            if(x[i] > lx){
                lx = x[i];
            }
        }else if(a[i] == 2){
            if(x[i] < rx){
                rx = x[i];
            }            
        }else if(a[i] == 3){
            if(y[i] > uy){
                uy = y[i];
            }

        }else if(a[i] == 4){
            if(y[i] < ty){
                ty = y[i];
            }
        }
//        fprintf(stderr, "lx = %d rx = %d uy = %d ty = %d\n", lx, rx, uy, ty);
    }

    if(lx >= rx || uy >= ty){
        ans = 0;
    }else{
        ans = (rx - lx) * (ty - uy);
    }
    if(ans <= 0){
        ans = 0;
    }

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

    return 0;

} 


Measured memory_bytes: 384
# 方針
"""
- 標準入力はどこから???
  - コマンとライン引数かな?
    - https://qiita.com/orange_u/items/3f0fb6044fd5ee2c3a37
  - input関数のことらしい
    - https://qiita.com/yasu_teco/items/e8db933ac4f647166996

- python 関数作り方
  - https://bi.biopapyrus.jp/python/syntax/def.html
"""

rating = int(input()) 
# print(rating) #出力：s

def Rank(rating):
    #print(rating)
    if(400<= rating <=599):
        print(8)
    elif(600 <= rating <= 799):
        print(7)
    elif(800 <= rating <= 999):
        print(6)
    elif(1000 <= rating <= 1199):
        print(5)
    elif(1200 <= rating <= 1399):
        print(4)
    elif(1400 <= rating <= 1599):
        print(3)
    elif(1600 <= rating <= 1799):
        print(2)
    elif(1800 <= rating <= 1999):
        print(1)

    else:
        print("エラー(400<=ratin<=1999) の範囲外")

Rank(rating)


Measured memory_bytes: 9196
def main
  while (n = gets.to_i) != 0
    p1, p2 = 0, 0
    n.times do
      a, b = gets.split(" ").map(&:to_i)
      if a > b
        p1 += a + b
      elsif a < b
        p2 += a + b
      else
        p1 += a
        p2 += a
      end
    end
    puts "#{p1} #{p2}"
  end
end
main

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

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

int N, A[20];

bool solve(int i, int m) {
    if(m == 0) return true;
    if(i >= N) return false;
    return solve(i + 1, m) || solve(i + 1, m - A[i]);
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> N;
    rep(i, N) cin >> A[i];
    
    int q;
    cin >> q;
    rep(i, q) {
        int m;
        cin >> m;
        cout << (solve(0, m) ? "yes" : "no") << "\n";
    }

    return 0;
}


Measured memory_bytes: 3196
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

const int maxn = 102;
const int maxm = 100002;

int n, m, d[maxn];
bool f[maxm];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }

    f[0] = false;
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j < n && !f[i]; ++j)
            if (i >= d[j] && !f[i - d[j]])
                f[i] = true;
    }

    if (f[m])
        cout << "First" << endl;
    else
        cout << "Second" << endl;

	return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

template<typename T>
T& ckmin(T& a, T b){ return a = a > b ? b : a; }

template<typename T>
T& ckmax(T& a, T b){ return a = a < b ? b : a; }

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

namespace ioUtils {

    char vector_delimiter = ' ';

    template<typename T>
    istream& operator >>(istream&, vector<T>&);

    template<typename... Ts>
    istream& operator >>(istream& is, pair<Ts...>& p){
        is >> p.first >> p.second;
        return is;
    }

    template<typename T> 
    istream& operator >>(istream& is, vector<T>& v){
        for(auto& e : v) is >> e;
	       return is;
    }

    template<typename T>
    ostream& operator <<(ostream&, vector<T>&);

    template<typename... Ts>
    ostream& operator <<(ostream& os, pair<Ts...>& p){
        os << p.first << " " << p.second;
        return os;
    }

    template<typename T>
    ostream& operator <<(ostream& os, vector<T>& v){
        for(auto&& e : v) os << e << vector_delimiter;
        return os;   
    }   
}

using namespace ioUtils;


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    #ifdef DEBUG
        freopen("debug", "w", stderr);
    #endif

    const int INF = 2e9;
    
    int N, K;
    cin >> N >> K;

    vi h(N);
    cin >> h;

    vi dp(N, INF);
    for(int i = N - 1; i >= max(N - K, 0); i--) dp[i] = abs(h[i] - h[N - 1]);
    for(int i = N - K - 1; i >= 0; i--)
    	for(int j = 1; j <= K; j++)
    		ckmin(dp[i], abs(h[i] - h[i + j]) + dp[i + j]);
    cout << dp[0] << '\n';
    #ifdef DEBUG
        dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}


Measured memory_bytes: 3996
#include<bits/stdc++.h>
#define mo 1000000007
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,i,j,top,flag[200005],flag2;
long long book[200005],book2[200005],sum[200005],ans,m,min1;
struct nyh{
	long long x,id;
}o[200005];
bool cmp(nyh u,nyh v){
	return u.x<v.x;
}
int main(){
   	n=read();
   	for(i=1;i<=n;i++){
   		top++;
   		o[top].x=read();
   		o[top].id=i;
   		top++;
   		o[top].x=read();
   		o[top].id=i+n;
   	}
   	sort(o+1,o+top+1,cmp);
   	for(i=1;i<=n;i++){
   		if(o[i].id>n){
   			flag[o[i].id-n]|=2;
   			flag2|=2;
   		}
   		else{
   			flag[o[i].id]|=1;
   			flag2|=1;
   		}
   		ans+=o[i].x;
   	}
   	for(i=1;i<=n;i++)
   		if(flag[i]==3)
   			flag2=0;
   	if(flag2<=2){
   		pus(ans,2);
   		return 0;
   	}
   	ans=0;
   	for(i=1;i<=top;i++){
   		sum[i]=sum[i-1]+o[i].x;
   		if(o[i].id<=n)
   			book[o[i].id]=i;
   		else
   			book2[o[i].id-n]=i;
   	}
   	for(i=1;i<=n;i++)
   		if(book[i]>book2[i])
   			swap(book[i],book2[i]);
   	for(i=1;i<=n;i++){
   		m=n-2;
   		ans=0;
   		if(m>=book[i])
   			m++;
   		else
   			ans+=o[book[i]].x;
   		if(m>=book2[i])
   			m++;
   		else
   			ans+=o[book2[i]].x;
   		ans+=sum[m];
   		if(ans<min1||i==1)
   			min1=ans;
	}
   	pus(min1,2);
    return 0;
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

int main()
{
    ll n, sum = 0, ans = 0;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(ALL(a));
    rep(i, n - 1)
    {
        sum += a[i];
        if (2 * sum >= a[i + 1])
            ans++;
        else
            ans = 0;
    }
    cout << ++ans << endl;
    return 0;
}

Measured memory_bytes: 1152
# -*- coding: utf-8 -*-
A = int(input())
B = int(input())

"""
if A == 1 and B == 2 or A == 2 and B == 1:
    print(3)
elif A == 1 and B == 3 or A == 3 and B == 1:
    print(2)
elif A == 2 and B == 3 or A == 3 and B == 2:
    print(1)
"""
"""
if A > B:
    A, B = B, A

if A == 1 and B == 2:
    print(3)
if A == 2 and B == 3:
    print(1)
if A == 1 and B == 3:
    print(2)
"""
for i in range(1,4):
    if A != i and B != i:
        print(i)


Measured memory_bytes: 2940
#include <stdio.h>
#include <string.h>

int main(){
	char str[8];
	scanf("%s", str);
	
	if (strcmp("Sunny",str) == 0) printf("Cloudy");
	if (strcmp("Cloudy",str) == 0) printf("Rainy");
	if (strcmp("Rainy",str) == 0) printf("Sunny");
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
//#include <chrono>
using namespace std;

int main(void){
/*
	chrono::system_clock::time_point start, end;
	start = chrono::system_clock::now(); // 計測開始時間
*/
	int n, i;
	int r;
	cin >> n;

	int min, ans = -1000000002;
	int t;

	cin >> min;
	for (i = 1;i<n;i++) {
		cin >> r;
		t = r - min;
		if (ans<t)ans = t;
		if (min>r)min = r;
	}

	cout << ans << endl;
/*
	end = chrono::system_clock::now();  //計測終了時間
	double elapsed = chrono::duration_cast<chrono::milliseconds>(end - start).count();  //処理に要した時間をミリ秒に変換 
	cout << elapsed << endl;
*/  
	return 0;
}



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

using namespace std;
using ll = long long;

using Field = vector<vector<int>>;
using Graph = vector<vector<int>>;
using VI = vector<int>;
using VC = vector<char>;
using PI = pair<int, int>;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

const long long INF = 1LL<<60;
const int mod = 1000000007;

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; }

bool is_integer(long double x) {
    double xx = x;
    return floor(xx) == xx;
}

long double X;

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

    cin >> X;

    ll A = 0, B = 0;

    while (true) {
        ll b = pow(B, 5);
        long double a1 = X + b;
        long double a2 = X - b;
        long double a11 = pow(a1, (long double)1.0/5.0);
        long double a22 = pow(a2, (long double)1.0/5.0);
        if (is_integer(a11)) {
            A = a11;
            break;
        } else if (is_integer(a22)) {
            A = a22;
            B = -B;
            break;
        }
        B++;
    }

    cout << A << " " << B << endl;
    
    return 0;
}

Measured memory_bytes: 4212
N, K = map(int, input().split())
A_list = list(map(int, input().split()))

dic = {1: 1}
dis = [1]
position = 0
for i in range(len(A_list)):
    if A_list[position] not in dic:
        dic[A_list[position]] = 1
        dis.append(A_list[position])

    else:
        dis.append(A_list[position])
        break
    position = A_list[position] - 1

# print(dic)
temp = dis.index(dis[-1])
# print(temp)
if K <= temp:
    print(dis[K])
    exit()
loop = len(dis) - temp - 1

#print(dis, loop)
K -= len(dis) - (loop + 1)
# print(K)

loop_list = dis[temp:]
# print(loop_list)
loop_temp = K % loop
# print(loop_temp)
print(loop_list[loop_temp])

Measured memory_bytes: 35580
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxV 201
#define maxE 10001
#define oo 0x3f3f3f3f
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define f(i,k) for(int i=k;i!=-1;i=edge[i].next)
struct ji{
    int next,to;
}edge[2*maxE];
int E,head[maxV],match[maxV];
bool vis[maxV];
int n;
void init(){
    E=0;
    memset(match,0,sizeof(match));
    memset(head,-1,sizeof(head));
}
void add(int x,int y){
    edge[E].next=head[x];
    edge[E].to=y;
    head[x]=E++;
}
int dfs(int k){
	f(i,head[k])if (!vis[edge[i].to]){
		vis[edge[i].to]=1;
		if (dfs(match[edge[i].to])){
			match[edge[i].to]=k;
			return 1;
		}
	}
	return !k;
}
int calc(){
	int ans=0;
	fo(i,1,n){
		memset(vis,0,sizeof(vis));
		ans+=dfs(i);
	}
	return ans;
}
int main(){
	init();
	int x[101],y[101],a,b;
	scanf("%d",&n);
	fo(i,1,n)scanf("%d%d",&x[i],&y[i]);
	fo(i,1,n){
		scanf("%d%d",&a,&b);
		fo(j,1,n)if ((x[j]<a)&&(y[j]<b))add(i,j+n);
	}
	printf("%d",calc());
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x,t=1;
        while(true){
            x=sc.nextInt();
            if(x == 0) break;
            System.out.println("Case "+ t++ +": "+x);
        }
    }
}


Measured memory_bytes: 42784
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

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

//解説AC
//https://atcoder.jp/contests/agc016/submissions/4386806
//実装力がほしい
//1. count(string.begin(), string.end(), word)で文字数を数えられる
//2. char word = char('a'+i);でアルファベット
//3. アルファベットで全探索

map<char, int> mp;
int n;

int
main(void){  
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  string s;
  int ans = 1e9/2;
  string max_s = "";
  cin >> s;
  n = s.size();

  REP(i, 26){
    char word = char('a'+i);
    int num=0;
    string tmp1=s, tmp2;
    while(count(tmp1.begin(), tmp1.end(), word) != tmp1.size()){
      tmp2 = tmp1;
      tmp1 = "";
      REP(i, tmp2.size()-1){
	if(tmp2[i] == word || tmp2[i+1] == word){
	  tmp1 += word;
	}
	else{
	  tmp1 += tmp2[i];
	}
      }
      num++;
    }
    ans = min(ans, num);
  }
  
  cout << ans << endl;

  
  return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

//const MAX:usize = 100006;
//const INF:u64 = u64::max_value();

fn main() {
    let n:u32 = read();
    let p:Vec<u32> = (0..n).map(|_| read()).collect();
    let mut q = p.clone();

    q.sort();

    let mut cnt:u32 = 0;
    for i in 0..n {
        let i = i as usize;
        if p[i] != q[i] { cnt += 1; }
    }

    println!("{}", if cnt<=2 {"YES"} else {"NO"});

    
}

Measured memory_bytes: 4352
fun main(arr:Array<String>) {
    val (totalStep, brokenCount) = readLine()!!.split(" ").map { it.toInt() }
    val broken = (1..brokenCount).map { readLine()!!.toInt() }.toMutableList()
    broken.add(totalStep  + 1)
    setDic(totalStep+1)
    var current = 0
    var ans = 1L
    for (step in broken) {
        if(current >= step) {
            println(0)
            return
        }
        if(step - current == 1) {
            current = step + 1
            continue
        }
        ans *= dic[step - current - 1]
        ans %= md
        current = step + 1
    }
    println(ans)
}

val md = 1000000000 + 7

val dic = mutableListOf(0L, 1L, 2L)
fun setDic(num:Int) {
    for(i in 3..num) {
        val tmp = (dic[i-2] + dic[i-1]) % md
        dic.add(tmp)
    }
}


Measured memory_bytes: 45552
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int main(){
  int n;
  int a,b;
  while(cin >> n, n){
    int asum = 0;
    int bsum = 0;
    for(int i=0; i<n; i++){
      cin >> a >> b;
      if(a > b) asum += a+b;
      else if(a < b) bsum += a+b;
      else{
        asum += a;
        bsum += b;
      }
    }
    cout << asum << " " << bsum << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
	int n; cin >> n;
	int ac = 0, wa = 0, tle = 0, re = 0;
	while (n--) {
		string s; cin >> s;
		char c = s[0];
		if (c == 'A')
			ac++;
		else if (c == 'W')
			wa++;
		else if (c == 'T')
			tle++;
		else
			re++;
	}
	cout << "AC x " << ac << '\n';
	cout << "WA x " << wa << '\n';
	cout << "TLE x " << tle << '\n';
	cout << "RE x " << re << '\n';
	return 0;
}


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

int main() {
    int n, d;
    cin >> n >> d;
    vector<vector<int> > x(n, vector<int>(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> x.at(i).at(j);
        }
    }
    int count = 0;
    double dis;
    int diss;
    for (int i  = 0; i < n; i++) {
        for (int j  = i + 1; j < n; j++) {
            dis = 0;
            for (int k = 0; k < d; k++) {
                dis += (x.at(i).at(k) - x.at(j).at(k)) * (x.at(i).at(k) - x.at(j).at(k));
            }
            dis = sqrt(dis);
            diss = (int)(dis / 1);
            if (dis == diss) count++;
        }
    }
    cout << count << endl;
}


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

const int INF = 1 << 30;

int N;
int h[100009];
int dp[100009];

int main() {
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> h[i];

    dp[0] = INF;
    dp[1] = 0;
    for(int i = 2; i <= N; i++)
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
                    dp[i - 2] + abs(h[i] - h[i - 2]));

    cout << dp[N] << endl;

    return 0;
}

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

int main() {
  int n, k, sum = 1;
  cin >> n >> k;
  
  for(int i = 0; i < n; i++){
  	if(sum * 2 >= sum + k){
    	sum += k;
    }else{
    	sum *= 2;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<vector<ll> >vec;
ll k,ans;
const ll M=1e9+7;
vector<vector<ll> >dp,tmp1,tmp2;
void go()
{
    tmp1=dp;
    for(int i=0;i<n;i++)
	{
        for(int j=0;j<n;j++)
		{
            dp[i][j]=0;
            for(int k=0;k<n;k++)
                dp[i][j]=(dp[i][j]+(tmp1[i][k]*tmp1[k][j]))%M;
        }
    }
}
void odd()
{
    tmp1=dp;
    tmp2=vec;
    for(int i=0;i<n;i++)
	{
        for(int j=0;j<n;j++)
		{
            dp[i][j]=0;
            for(int k=0; k<n; k++)
                dp[i][j]=(dp[i][j]+(tmp1[i][k]*tmp2[k][j]))%M;
        }
    }
}
void solve(ll k)
{
    if(k==1)return;
    solve(k/2);
    go();
    if(k%2)odd();
    return;
}
int main()
{
    cin>>n>>k;
    vec.resize(n);
    dp.resize(n);
    for(int i=0;i<n;i++)
	{
        for(int j=0;j<n;j++)
		{
            int x;
            cin>>x;
            vec[i].push_back(x);
            dp[i].push_back(x);
        }
    }
    solve(k);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)
        ans+=(dp[i][j]%M);
    cout<<ans%M<<endl;
    return 0;
}

Measured memory_bytes: 3708
fun main(args:Array<String>) {
	val (n,m) = readLine()!!.split(" ").map{ it.toLong() }
	when{
	    n==1L && m==1L -> 1L
	    n==1L && m!=1L -> m-2
	    n!=1L && m==1L -> n-2
	    else -> (n-2)*(m-2)
	}.let {println(it)}
	
}

Measured memory_bytes: 37872
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

using System.Collections;

class Program
{
    static void Main()
    {
        int[] nm = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        int N = nm[0];
        int M = nm[1];

        var lrList =
            Enumerable.Range(0, M)
            .Select(n => Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray())
            .Select(arr => new { L = arr[0], R = arr[1] })
            .ToList();


        var lMax = lrList.Max(itm => itm.L);
        var rMin = lrList.Min(itm => itm.R);

        var ans = rMin - lMax + 1;

        ans = Math.Max(0, ans);

        Console.WriteLine(ans);
    }    
}


Measured memory_bytes: 23484
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;


int main()
{
//回答が整数の場合
ll ans=-1;
//整数値の入力
ll n,k;
cin >> n>>k;
//行列の入力
ll table[n]={};
for (int i = 0; i < n; ++i) {
    cin >> table[i];
}

int ichi[40]={};
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 40; ++j) {   
     if((table[i]>>j)&1LL){ichi[j]++;}
}
}

//反転すべき時1でそのままの時0
for (int j = 0; j < 40; ++j) { 
    if(ichi[j]<=n/2){ichi[j]=1;}
    else{ichi[j]=0;}
}
ll dp[40]={};
//dpまわす
int syu=1;
for (int j = 0; j < 40; ++j) {
    for(int i = 1 ; i < syu; ++i){
        if(ichi[39-j]){
        dp[i]=dp[i]+(1LL<<(39-j));
        }
    }
    if(ichi[39-j]&&(dp[0]+(1LL<<(39-j))<=k)){
        dp[syu]=dp[0];
        dp[0]=dp[0]+(1LL<<(39-j));
        syu=syu+1;
    }
}
ll f;
for (int i = 0; i < 40; ++i) {
    ll sum=0;
    for (int j = 0; j < n; ++j) {
    sum=sum+(dp[i]^table[j]);
    }
    if(ans<sum){ans=sum;f=dp[i];}

}

/* for (int i = 0; i < 40; ++i) {
    cout << dp[i] << " ";
} cout <<  endl; */

//cout << f << " "<< ans<< endl;
cout << ans<< endl;
return 0;
}





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

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;
}

Measured memory_bytes: 3536
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
ll W[5000];
ll S[4004];
int K[4004][4004];
ll dp[4004][4004];
int main(){
  cin >> N;
  for(int i=0;i<N;i++) cin >> W[i];
  for(int i=0;i<N;i++){
    S[i+1] = S[i] + W[i];
    K[i][i] = i;
  }
  
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++) dp[i][j] = 100000000000000000LL;
    dp[i][i] = 0LL;
  }

  for(int w=1;w<N;w++){
    for(int i=0,j;(j=i+w)<N;i++){
      for(int k=K[i][j-1];k<=K[i+1][j];k++){
	ll at = dp[i][k] + dp[k+1][j] + S[j+1] - S[i];
	if( dp[i][j] > at ){
	  dp[i][j] = at; K[i][j] = k;
	}
      }
    }  
  }
  cout << dp[0][N-1] << endl;
}

Measured memory_bytes: 187976
n,k = gets.chomp.split(" ").map(&:to_i)
a = gets.chomp.split(" ").map(&:to_i)
hash = Hash.new(0)
n.times do |i|
  hash[a[i]] += 1
end
kind = hash.length
sortedarr = hash.each_value.sort
ans = 0
(kind-k).times do |i|
  ans += sortedarr[i]
end
puts ans


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

int n, A[20];

bool solve(int i, int m)
{
    if (m == 0)
    {
        return true;
    }
    if (i == n)
    {
        return false;
    }

    bool result = solve(i+1, m) || solve(i+1, m-A[i]);

    return result;
}

int main()
{
    int q, x;

    cin >> n;

    for (int i = 0; i != n; ++i)
    {
        scanf("%d", &A[i]);
    }

    cin >> q;

    for (int i = 0; i != q; ++i)
    {
        scanf("%d", &x);

        if (solve(0, x))
        {
            printf("yes\n");
        }
        else
        {
            printf("no\n");
        }
        
    }

    return 0;
}


Measured memory_bytes: 3140
<?php

fscanf(STDIN, "%d %d %d %d", $x1, $y1, $x2, $y2);

$dx = $x2 - $x1;
$dy = $y2 - $y1;

$x3 = $x2 - $dy;
$y3 = $y2 + $dx;

$dx = $x3 - $x2;
$dy = $y3 - $y2;

$x4 = $x3 - $dy;
$y4 = $y3 + $dx;

echo "$x3 $y3 $x4 $y4";


Measured memory_bytes: 4728
ai = lambda: list(map(int, input().split()))

h,w = ai()
d = [ai() for _ in range(10)]

from scipy.sparse import csgraph
d = csgraph.floyd_warshall(d)

ans = 0

for _ in range(h):
    for aa in ai():
        if aa != -1:
            ans += int(d[aa][1])
print(ans)


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

int main(void){
    long long n, r, g, b, cnt=0;
    cin >> r >> g >> b >> n;
    for(int i=0;i*r<=n;++i){
        for(int j=0;j*g<=n-i*r;++j){
            if((n-i*r-j*g)%b==0){
                ++cnt;
            }
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n;
	int h, m;
	int i, j;
	int exist[24][60] = {};
	int printed;

	for (i = 0; i < 2; i++){	
		scanf("%d", &n);
		for (j = 0; j < n; j++){
			scanf("%d %d", &h, &m);
			exist[h][m] = 1;
		}
	}

	printed = 0;
	for (h = 0; h < 24; h++){
		for (m = 0; m < 60; m++){
			if (exist[h][m]){
				if (printed){
					printf(" ");
				}
				printed = 1;
				printf("%d:%02d", h, m);
			}
		}
	}
	printf("\n");

	return (0);
}

Measured memory_bytes: 620
#include <bits/stdc++.h>
#define ll long long int
#define r(a, b) for(ll i = a; i < b; i++)
#define pb push_back
using namespace std;
#define mod 998244353
const long long int INF = 1e10;
vector<ll>v,h,s,h1,s1;
vector<ll>::iterator i,j;
ll gcd(ll a,ll b){
    if(a==0){
        return b;
    }
    else{
        return gcd(b%a,a);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    ll arr[9][9];
    for(ll i=0;i<9;i++){
        for(ll j=0;j<9;j++){
            arr[i][j]=0;
        }
    }
            for(ll x=1;x<=n;x++){
                ostringstream str1;
                str1 << x;
                string s = str1.str();
                ll m=s.length();
                for(ll i=1;i<=9;i++){
        for(ll j=1;j<=9;j++){
                if(s.at(0)-'0'==i && s.at(m-1)-'0'==j){
                    arr[i-1][j-1]++;
                }
            }
        }
    }
    ll sum=0;
    for(ll i=0;i<9;i++){
        for(ll j=0;j<9;j++){
            sum+=arr[i][j]*arr[j][i];
        }
    }
    cout<<sum<<"\n";
    return 0;
}




Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque, defaultdict
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

def divisor(n):
    ret = list()
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            # ret.append(n // i) if i * i != n else None
    return sorted(ret)


def main():
    S = ii()
    X1, Y1 = 0, 0
    if (S <= 10 ** 9):
        print(0, 0, S, 0, 0, 1)
        sys.exit()
    for i in range(floor(sqrt(S)) - 3, floor(sqrt(S)) + 1000):
        if i * i >= S:
            if i * i == S:
                print(0, 0, i, 0, 0, i)
                sys.exit()
            if (i ** 2 - S) // divisor(i ** 2 - S)[-1] > 10**9:
                continue
            else:
                n = i
                break
    print(0, 0, n, divisor(n ** 2 - S)[-1], (n ** 2 - S) // divisor(n ** 2 - S)[-1], n)

if __name__ == '__main__':
    main()


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

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

    int t;
    int ans = 0;
    int mx = 0;
    for (int i=0; i<5; ++i) {
        cin >> t;
        ans += (t / 10)*10 + (t % 10 == 0 ? 0 : 10);
        mx = max(mx, (10 - t % 10) % 10);
    }

    cout << ans - mx << endl;

    return 0;
}

Measured memory_bytes: 256
## ABC154E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


M = 10**9+7 # 出力の制限
N = 100 # 必要なテーブルサイズ

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 



n = input()
k = int(input())
l = len(n)

dp0 = [[0]*(k+1) for _ in range(l+1)] # i桁目まででNより小さく、非零がjの個数
dp1 = [[0]*(k+1) for _ in range(l+1)] # i桁目でNと同じで、非零がjの個数
dp1[0][0] = 1

if k>l:
    ans = 0
else:
    for i in range(1,l+1):
        for j in range(k+1):
            c = int(n[i-1])
            if j>=1:
                dp0[i][j] += 9 * dp0[i-1][j-1]
            dp0[i][j] += dp0[i-1][j]            
            if c>=1:
                dp0[i][j] += dp1[i-1][j]
                if j>=1:
                    dp0[i][j] += (c-1) * dp1[i-1][j-1]
                
            if c==0:
                dp1[i][j] += dp1[i-1][j]
            elif j>=1:
                dp1[i][j] += dp1[i-1][j-1]
                
ans = dp0[l][k] + dp1[l][k]
print(ans)

Measured memory_bytes: 38384
fn getline() -> String {
    let mut __ret = String::new();
    std::io::stdin().read_line(&mut __ret).ok();
    return __ret;
}

fn solve(a: i32, b: i32) -> String {
    if a == 1 && b == 1 {
        return "Draw".to_string();
    }
    if a == 1 && b != 1 {
        return "Alice".to_string();
    }
    if a != 1 && b == 1 {
        return "Bob".to_string();
    }
    if a > b {
        return "Alice".to_string();
    }
    if a < b {
        return "Bob".to_string();
    }

    return "Draw".to_string();
}

fn main() {
    let s = getline();
    let vec: Vec<i32> = s.trim().split(' ').map(|s| s.parse().unwrap()).collect();
    let a = vec[0];
    let b = vec[1];

    let ans = solve(a, b);
    println!("{}", ans);
}


Measured memory_bytes: 4476
import java.util.*;
import java.io.*;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
	int M = in.nextInt();
    int NA = (N * (N - 1))/2, MA = (M * (M - 1))/2;
    System.out.println(NA + MA);
  }
}

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

using namespace std;

int main () {
        int n;
        cin >> n;
        int arr[n];
        int sum = 0;
        int curr = 1;

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

        for (int j = 0; j < n - 1; ++j) {
                curr = arr[j];
                for (int i = j + 1; i < n; ++i) {
                        if (i != j) {
                                curr *= arr[i];
                                sum += curr;
                                curr = arr[j];
                        }
                }
        }

        cout << sum << "\n";
}


Measured memory_bytes: 256
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

X=[a,b,c,d,e]
M=[]
for i in X:
   M.append((10-i%10)%10)

ans=0

for i in X:
    ans+=(i+((10-i%10)%10))

print(ans-max(M))

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

const char color[5] = "RYGB";

int main(void) {
    int h,w,d;
    int x,y;
    cin >> h >> w >> d;
    for (int i=1; i<=h; i++) {
        for (int j=1; j<=w; j++) {
            x = (i+j)/d;
            y = (i-j+500)/d;
            cout << color[(x%2)*2+y%2];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())



#define MOD 1000000007



vector<pair<int, int>> v;


long long dp[101][80000];
long long s[80000];


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


	int n, k;
	cin >> n >> k;

	int x = 1;
	while (x <= n) {
		int div = n / x;

		int p = x;
		for (int b = 30; b >= 0; b--) {
			if (p + (1<<b) <= n && n / (p + (1 << b)) == div) {
				p += 1 << b;
			}
		}
		v.emplace_back(x, p - x + 1);
		x = p + 1;
	}



	dp[0][0] = 1;

	for (int i = 1; i <= k; i++) {
		s[0] = dp[i - 1][0];
		for (int j = 1; j < v.size(); j++) {
			(s[j] = s[j - 1] + dp[i - 1][j]) %= MOD;
		}

		rep(j, v.size()) {
			int d = n / v[j].first;

			int idx = upper_bound(all(v), make_pair(d, INF)) - v.begin() - 1;
			dp[i][j] += s[idx] * v[j].second;
		}

	}

	long long ans = 0;
	rep(j,v.size()){
		ans += dp[k][j];
	}


	cout << ans % MOD << endl;



	return 0;
}

Measured memory_bytes: 63608
#include <bits/stdc++.h>
#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 K,X; cin >> K >> X;
    for(int i = X-K+1; i < X+K; i++) {
        if(i != X+K-1)
            cout << i << " ";
        else 
            cout << i << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 998244353;

int main(){
    char S;
    cin >> S;
    if(isupper(S)){
        printf("A\n");
    }
    else{
        printf("a\n");

    }

}


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

int main() {
    int w,h,l;
    int a[101][101],b[101][101];
    long long c[101][101] = {0};
    
    cin >> w >> h >> l;
    for ( int i = 0; i < w; i++ ) 
    	for ( int j = 0; j < h; j++ ) cin >> a[i][j];
    for ( int i = 0; i < h; i++ ) 
        for ( int j = 0; j < l; j++ ) cin >> b[i][j];
    for ( int i = 0; i < w; i++ ) 
        for ( int j = 0; j < l; j++ ) 
            for ( int k = 0; k < h; k++ ) c[i][j] += a[i][k] * b[k][j];
    for ( int i = 0; i < w; i++ ) {
        for ( int j = 0; j < l; j++ ) {
        	cout << c[i][j];
        	if ( j != l - 1 ) cout << " ";
        }
        cout << endl;
    }
    return 0;
}


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

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


int main() {
	int n;
	vector<long long> gcdd = { 1,9,30,76,141,267,400,624,885,1249,1590,2208,2689,3411,4248,5248,6081,7485,8530,10248,11889,13687,15228,17988,20053,22569,25242,28588,31053,35463,38284,42540,46581,50893,55362,61824,65857,71247,76884,84388,89349,97881,103342,111528,120141,128047,134580,146316,154177,164817,174438,185836,194157,207927,218812,233268,245277,257857,268182,288216,299257,313635,330204,347836,362973,383709,397042,416448,434025,456967,471948,499740,515581,536073,559758,583960,604833,633651,652216,683712,709065,734233,754734,793188,818917,846603,874512,909496,933081,977145,1006126,1041504,1073385,1106467,1138536,1187112,1215145,1255101,1295142,1342852,1373253,1422195,1453816,1502376,1553361,1595437,1629570,1691292,1726717,1782111,1827492,1887772,1925853,1986837,2033674,2089776,2145333,2197483,2246640,2332104,2379085,2434833,2490534,2554600,2609625,2693919,2742052,2813988,2875245,2952085,3003306,3096024,3157249,3224511,3306240,3388576,3444609,3533637,3591322,3693924,3767085,3842623,3912324,4027884,4102093,4181949,4270422,4361548,4427853,4548003,4616104,4718640,4812789,4918561,5003286,5131848,5205481,5299011,5392008,5521384,5610705,5739009,5818390,5930196,6052893,6156139,6239472,6402720,6493681,6623853,6741078,6864016,6953457,7094451,7215016,7359936,7475145,7593865,7689630,7886244,7984165,8130747,8253888,8403448,8523897,8684853,8802826,8949612,9105537,9267595,9376656,9574704,9686065,9827097,9997134,10174780,10290813,10493367,10611772,10813692 };
	cin >> n;
	cout << gcdd[n - 1] << endl;
}


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

const int inf = 987654321;
int n, m;
vector< vector<int> > G;
vector< vector<int> > dp;

int rec(int visited, int now) {
  if (dp[visited][now] != -1) return dp[visited][now];
  if (visited == (1<<n)-1 && now == 0) return dp[visited][now] = 0;
  int res = inf;
  for (int i = 0; i < n; i++) {
    if (visited >> i & 1) continue; /* ??¢????¨??????? */
    res = min(res, rec(visited | (1 << i), i) + G[now][i]);
  }
  return dp[visited][now] = res;
}

int main(void) {
  cin >> n >> m;
  G.assign(n, vector<int>(n, inf));
  for (int i = 0; i < m; i++) {
    int p, q, c;
    cin >> p >> q >> c;
    G[p][q] = c;
  }
  dp.assign(1 << n, vector<int>(n, -1));
  int res = rec(0, 0);
  if(res != inf) cout << res << endl;
  else cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 4440