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

#define int long long

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    double d, t, s;
    cin >> d >> t >> s;
    double cur = d / (s * 1.00);
    cout << (cur <= t ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3748
#include<stdio.h>
int main(void){
    int a, b, c;
    int i;
    int n=0;
    scanf("%d %d %d", &a, &b, &c);
    for(i=a;i<=b;i++){
        if(c%i==0){
            n++;
        }
    }
    printf("%d\n",n);
    return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m; i < n; i++) 
#define mod 1000000007
#define pi 3.1415926535
typedef long long ll;
int main(){
    int X,Y;
    cin>>X>>Y;
    rep(i,101){
        rep(j,101){
            if(i+j==X&&2*i+j*4==Y){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }

    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define ll  long long
#define endl '\n'
#define pi 3.14159265
ll p(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b%2!=0)

            res*=a;
        a*=a;
        b/=2;
    }
    return res;
}
int main()
{           
    IOS;
    ll n;
    cin>>n;
    long double ans=0;
    for(ll i=0;i<n;i++)
    {
    	double x;
    	string s;
    	cin>>x>>s;
    	if(s=="BTC")
    	{
    		x=380000*x;
    	}
    	ans+=x;
    }
    cout<<fixed<<setprecision(10);
    cout<<ans;
}       

Measured memory_bytes: 256
# --------------------------------------
# 関数定義
# --------------------------------------


def chmin(a, b):
    if a > b:
        a = b
    return a

# --------------------------------------
# メイン処理
# --------------------------------------


def main():
    INF = 10 ** 10
    N = int(input())
    h = list(map(int, input().split()))

    dp = [INF] * N
    dp[0] = 0

    for i in range(1, N):
        dp[i] = chmin(dp[i], dp[i-1] + abs(h[i]-h[i-1]))
        if i >= 2:
            dp[i] = chmin(dp[i], dp[i-2] + abs(h[i]-h[i-2]))

    print(dp[N - 1])


# --------------------------------------
# 実行
# --------------------------------------
if __name__ == "__main__":
    main()


Measured memory_bytes: 52208
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
   if ( A+B == C+D ){
    cout << "Balanced" <<endl;
  }
  else if ( A+B > C+D ){
    cout << "Left" <<endl;
  }
  if ( A+B < C+D){
    cout << "Right" <<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int prime(long val){
    if(val < 2) return 0;
    for(int i = 2; i * i <= val; i++){
        if((val % i) == 0){
            return 0;
        }
    }
    
    return 1;
}

int main(){
    int n, num;
    num = 0;
    
    cin >> n;
    for(int i = 0; i < n; i++){
        long val;
        cin >> val;
        num += prime(val);
    }
    cout << num << endl;
    
    return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include<iomanip>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60

int H, W;
bool block[2001][2001];

vector<int> C[2001]; // C[i] : i行目にある障害物を左から
vector<int> L[2001]; // L[j] : j列目にある障害物を上から

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

	cin >> H >> W;
	

	for (int i = 1; i <= H; i++) {
		string S; cin >> S;
		for (int j = 0; j < W; j++) {
			if (S[j] == '#') {
				block[i][j + 1] = true;
				C[i].push_back(j + 1);
				L[j + 1].push_back(i);
			}
		}
	}
	for (int i = 1; i <= H; i++) {
		C[i].push_back(0);
		C[i].push_back(W + 1);
	}
	for (int j = 1; j <= W; j++) {
		L[j].push_back(0);
		L[j].push_back(H + 1);
	}
	for (int i = 1; i <= H; i++) sort(C[i].begin(), C[i].end());
	for (int j = 1; j <= W; j++) sort(L[j].begin(), L[j].end());

	int ans = 0;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (!block[i][j]) {
				vector<int>::iterator up = upper_bound(L[j].begin(), L[j].end(), i);
				vector<int>::iterator bott = up; bott--;
				vector<int>::iterator right = upper_bound(C[i].begin(), C[i].end(), j);
				vector<int>::iterator left = right; left--;
				//cout << *up << " " << *bott << " " << *right << " " << *left << endl;

				//cout << (*up - *bott - 1) + (*right - *left - 1) - 1 << endl;
				int tmpans = (*up - *bott - 1) + (*right - *left - 1) - 1;
				ans = max(ans, tmpans);
			}
		}
	}
	cout << ans << endl;

	return 0;
}

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

int main(){
  int N;
  cin>>N;
  if(N<10){
    cout<<N<<endl;
  }else if(N<100){
    cout<<9<<endl;
  }else if(N<1000){
    cout<<N-90<<endl;
  }else if(N<10000){
    cout<<909<<endl;
  }else if(N<100000){
    cout<<N-9999+909<<endl;
  }else{
    cout<<90909<<endl;
  }
}

Measured memory_bytes: 3644
#include <iostream>


using namespace std;
int N;



int main()
{

	cin >> N;

	int ans = 0;

	int a = N / 500;
	int b = (N % 500) / 5;

	ans = 1000 * a + 5 * b;


	cout << ans <<endl;

	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define ll2(x, y) ll x, y; cin >> x >> y;
#define scn(n, a) rep(i, n)cin >> a[i]
#define sc2n(n, a, b) rep(i, n)cin >> a[i] >> b[i]
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

int cnt[26] = {0};

signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
    string s; cin >> s;
    rep(i, s.size())++cnt[s[i] - 'a'];
    bool fl = true;
    rep(i, 26)if(cnt[i] % 2 == 1)fl = false;
    puts(fl ? "Yes" : "No");

/*/

//*/ break;
  }
  return 0;
}


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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

const int MAX = 1000000 + 1;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  vector<int> cnt(MAX, 0);
  rep(i, n) {
    int b = a[i];
    for (int j = 2; j * j <= b; j++) {
      if (b % j == 0) cnt[j]++;
      while (b % j == 0) b /= j;
    }
    if (b != 1) cnt[b]++;
  }

  bool f = true;
  rep(i, MAX) if (cnt[i] > 1) f = false;

  if (f) {
    cout << "pairwise coprime" << endl;
    return 0;
  }

  int _g = a[0];
  rep(i, n) _g = __gcd(_g, a[i]);

  cout << (_g == 1 ? "setwise coprime" : "not coprime") << endl;
}


Measured memory_bytes: 11068
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<iomanip>
#include<map>

#define rep(i, n) for (int i = 0; i < n; i++) 
#define rrep(i, n) for(int i = n-1; i>=0; i--)
#define range(i, n, m) for (int i = n; i < m; i++) 
#define rrange(i, n, m) for (int i = n - 1; i => m; i--) 
#define MOD 1000000007
#define MAX 20000000000

typedef long long int ll;
typedef unsigned long long int ull;


using namespace std;

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


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

	ll A, B;
	cin >> A >> B;

	ll ret = 0;

	if (A == B) {
		ret = A * 2;
	}
	else {
		ll m = max(A, B);
		ret = m + (m - 1);
	}

	cout << ret << endl;

	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef pair<ll, ll> P;

int main(){
    int n;
        cin >> n;
    vec a(n);
        for(int i=0; i<n; i++)
            cin >> a.at(i);
    int cnt=0;
    string ans = "YES";
        for(int i=0; i<n-1; i++){
            if(a[i]==i+1) continue;
            cnt += 1;
        }
        if(2<cnt) ans ="NO"; 
        cout << ans << endl;

}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    Scanner(System.`in`).use {
        val n = it.nextInt()
        val L = it.nextInt()
        val list = mutableListOf<String>()
        for (i in 0 until n) {
            list.add(it.next())
        }
        list.sort()
        val r: String = list.joinToString("")
        println(r)
    }
}


Measured memory_bytes: 31396
#include <bits/stdc++.h>
 
using namespace std;
 
long long dp[100010][110];
long long v[101];
long long t[101];
long long maxi = 1000000000000;
 
void namesti(int n)
{
    for(int i = 0; i <= 100000; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            if(dp[i][j] == 0 && i > 0) dp[i][j] = maxi;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, w;
    cin >> n >> w;
    
    for(int i = 1; i <= n; i++)
    {
        cin >> t[i] >> v[i];
        dp[t[i]][i] = v[i];
    }
    
    
    for(int i = 1; i <= 100000; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i >= t[j]) dp[i][j] = max(dp[i][j-1], v[j] + dp[i - t[j]][j-1]);
            else dp[i][j] = dp[i][j-1];
        }
    }
    int pok = w;
    long long res = -1;
    while(pok > 0)
    {
        if(dp[pok][n] > res && dp[pok][n] != maxi) res = dp[pok][n];
        pok--;
    }
    cout << res;
    
    return 0;
}

Measured memory_bytes: 86144
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#include<iostream>

using namespace std;

int a, b, c, d, result;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
		string s;
		cin >> s;
		if(s.size() == 2) cout << s << "\n";
		else cout << s[2] << s[1] << s[0] << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int x,y;
	while(1)
	{
		scanf("%d %d",&x,&y);
		if(x == 0 && y == 0)
		{
			break;
		}
		if(x > y)
		{
			printf("%d %d\n",y,x);
		}
		else
		{
			printf("%d %d\n",x,y);
		}
	}
	return 0;
}

Measured memory_bytes: 600
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <stack>

typedef long long ll;

int main(int argc, char* argv[])
{
  ll N, x;
  std::cin >> N >> x;
  std::vector< ll > va(N+1, 0);
  std::vector< ll > vsum(N+1, 0);
  for (ll i = 0; i < N; i++) {
    std::cin >> va[i];
  }

  for (ll i = 1; i <= N; i++) {
    vsum[i-1] = va[i] + va[i-1];
  }

  ll ans = 0;
  for (ll i = 1; i < N; i++) {
    if (vsum[i] > x && vsum[i-1] > x) {
      ll minus = std::min(va[i], std::min(vsum[i], vsum[i-1]) - x);
      va[i]     -= minus;
      vsum[i-1] -= minus;
      vsum[i+0] -= minus;
      ans += minus;
      //std::cout << "minus1: " << minus << std::endl;
    }
    if (vsum[i-1] > x) {
      ll minus = std::min(va[i-1], vsum[i-1] - x);
      va[i-1]   -= minus;
      if (i-2 >= 0) {
	vsum[i-2] -= minus;
      }
      vsum[i-1] -= minus;
      ans += minus;
      //std::cout << "minus2: " << minus << std::endl;
    }
  }

  //std::vector< ll >::iterator it;
  //for (it = va.begin(); it != va.end(); it++) {
  //  std::cout << *it << std::endl;
  //}

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



Measured memory_bytes: 1792
/**
    AUTHOR:JUNSH
    TIME:19/5/25
**/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rev(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
inline int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
ll quick_pow(ll a,ll k){
    ll res=1;
    while(k){
        if(k&1)res=(res*a)%mod;
        a=(a*a)%mod;
        k/=2;
    }
    return res;
}
ll inv(ll x){
    return quick_pow(x,mod-2);
}
//ll inv(ll a){
//  ll t=1;
//  while (a>1){
//    t=t*(mod-mod/a)%mod;
//    a=mod%a;
//  }
//  return t;
//}
ll cal(ll n,ll k){
    k=min(k,n-k);
    ll num=1,Div=1;
    for(int i=1;i<=k;++i){
        Div=(Div*i)%mod;
        num=num*(n-i+1)%mod;
    }
    return num*inv(Div)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    for(ll i=1;i<=n;++i)
        ans=(ans+(i*(n-i)*m*m))%mod;
    for(ll i=1;i<=m;++i)
        ans=(ans+(i*(m-i)*n*n))%mod;
    ans=(ans*cal(n*m-2,k-2))%mod;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
line = gets.split(' ').map(&:to_i)

a = line[0]
b = line[1]
c = line[2]
d = line[3]

arr = []

arr.push(a*c)
arr.push(a*d)
arr.push(b*c)
arr.push(b*d)

arr.sort!.reverse!

puts arr[0]

Measured memory_bytes: 14368
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,l;
  cin >> n >> l;
  vector<string>vec(n);
  for(int i = 0;i<n;i++) cin >> vec[i];
  sort(vec.begin(),vec.end());
  for(int i = 0;i<n;i++){ 
    cout << vec[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
alp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
N = int(input())
S = input()

ans = ''
for c in S:
    c_ind = alp.index(c)
    ind = c_ind + N
    if ind > len(alp)-1:
        ind -= len(alp)
    ans += alp[ind]
print(ans)

Measured memory_bytes: 3064
n=int(input())
t=list(map(int,input().split()))
time=0
for i in range(n):
    time+=t[i]
m=int(input())
ans=[]
for i in range(m):
    p,x=map(int,input().split())
    ans.append(time-t[p-1]+x)
for i in range(m):
    print(ans[i])

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <set>

using namespace std;

const int N = 200;
bool ok[N][N];
set<int> dp[N][N];

string s;
set<int> calc(int l, int r){
	if (ok[l][r]) return dp[l][r];
	ok[l][r] = 1;
	auto &res = dp[l][r];

	int nest = 0;
	bool ope = false;
	for (int i = l; i < r; ++i){
		if (s[i] == '(') ++nest;
		else if (s[i] == ')') --nest;
		else if (!nest && s[i] < '0' || s[i] > '9'){
			ope = true;
			auto L = calc(l, i), R = calc(i+1, r);
			for (auto e1 : L){
				for (auto e2 : R){
					if (s[i] == '+') res.insert(e1 + e2);
					if (s[i] == '-') res.insert(e1 - e2);
					if (s[i] == '*') res.insert(e1 * e2);
					if (s[i] == '/' && e2) res.insert(e1 / e2);
				}
			}
		}
	}

	if (!ope){
		if (s[l] == '(' && s[r - 1] == ')') res = calc(l + 1, r - 1);
		else res.insert(stoi(s.substr(l, r - l)));
	}
	return res;
}

int main(){
	while (cin >> s, s != "#"){
		int n = s.size();
		for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j){
			ok[i][j] = 0;
			dp[i][j].clear();
		}
		cout << calc(0, n).size() << endl;
	}

	return 0;
}

Measured memory_bytes: 3236
// { Driver Code Starts
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  ll n, d;
  cin >> n >> d;
  ll count = 0;
  for (ll i = 0 ; i < n ; i++)
  {
      double x, y;
      cin >> x >> y;
      ll distance = abs(x*x) + abs(y*y);
      if (distance <= d*d)
      {
          count++;
      }
  }
  cout << count;
	return 0;
}


Measured memory_bytes: 3784
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
int n,x,y;
int a,b,c,d;
int main(){
     scanf("%d%d%d",&n,&x,&y);
    if((y-x)%2==0)printf("Alice");
    else printf("Borys");
     
    return 0;
}


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

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
long long getDigit(long long n);      // 数字の桁数を取得する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      ((a)/GCD((a),(b))*(b))
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

typedef long long ll;
typedef unsigned long long ull;

// code
// ------------------------------------------------
int main() {

  ll n,t;
  cin >> n >> t;

  ll bef = 0;
  ll ans = 0;

  rep(i,n)
  {
    ll buf;
    cin >> buf;

    if(i == 0)
    {
      bef = buf;
    }
    else
    {
      if(buf - bef > t)
        ans += t;
      else
      {
        ans += buf - bef;
      }
      bef = buf;
    }
  }

  ans += t;

  cout << ans << endl;
  
  return 0;
}
// funcの実体
// ------------------------------------------------
ll getDigit(ll n)
{
  int i = 1;
  while(1)
  {
    n = n / 10;
    if(n == 0)
      break;
    i++;
  }
  return i;
}
ll CalcSumOfDigit(ll n)
{
  ll s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 256
from math import sqrt, factorial
import itertools


N = int(input())

XY = [tuple(map(int, input().split())) for _ in range(N)]

def calc(a, b):
    tmp = (XY[a][0] - XY[b][0]) ** 2 + (XY[a][1] - XY[b][1]) ** 2
    return sqrt(tmp)

lst = [i for i in range(N)]

ans = 0
for tmp in itertools.permutations(lst):
    for i in range(N - 1):
        ans += calc(tmp[i], tmp[i + 1])

ans /= factorial(N)

print (ans)

Measured memory_bytes: 3064
def task(n, m, a, b):
    graph = []
    for i in range(0, n + 1):
        graph.append(set())

    for i in range(0, m):
        graph[a[i]].add(b[i])
        graph[b[i]].add(a[i])
    # print(graph)

    stack = [1]
    ans = 0
    traversed = {}
    traversed[1] = True

    while len(stack):
        nxtstack = set()
        ans += 1
        while len(stack):
            nxt = stack.pop()
            for value in graph[nxt]:
                if not value in traversed:
                    nxtstack.add(value)
                    traversed[value] = nxt
        stack = nxtstack

    for i in range(1, n + 1):
        if not i in traversed:
            print("No")
            return

    print("Yes")
    for i in range(2, n + 1):
        print(traversed[i])


n, m = map(int, input().split())
a = []
b = []
for i in range(0, m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
task(n, m, a, b)


Measured memory_bytes: 156544
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define out(str) cout << str << endl

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 (b<a) { a=b; return 1; } return 0; }



int main(){
    int N;
    cin >> N;
    out((N>999 ? "ABD" : "ABC"));
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) begin(x), end(x)
#define x first
#define y second
typedef long long ll;
typedef long double ld;

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

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;

const int MAX_N = 2e5 + 10;

pair<int, bool> a[MAX_N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i].x, a[i].y = 1;
	sort(a, a + n);
	int ans = 0;
	for (int i = n; i--; ) {
		if (!a[i].y)
			continue;
		for (int j = 31; j--; ) {
			int h = (1 << j) - a[i].x;
			int k = lower_bound(a, a + i, pair<int, bool>{h, 1}) - a;
			if (k == i || a[k] != pair<int, bool>{h, 1})
				continue;
			a[k].y = 0;
			++ans;
			// cout << i << " " << k << endl;
			break;
		}
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 5204
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

int32_t main() {
  int32_t N, M, T;
  cin >> N >> M >> T;

  vector<int32_t> times;
  for (uint32_t i = 0; i < N; i++) {
    int32_t time;
    cin >> time;
    times.push_back(time - M);
    times.push_back(time + M);
  }

  int32_t count = times[0] - 0;
  for (uint32_t i = 1; i < times.size() - 1; i += 2) {
    if (times[i + 1] - times[i] >= 0) {
      count += times[i + 1] - times[i];
    }
  }

  if (T - times[times.size() - 1] >= 0) {
    count += T - times[times.size() - 1];
  }

  cout << count << endl;

  return 0;
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define INF (1e9)
using namespace std;

string s;
int p,flg;
int bnf();
bool check(int i){return i<s.size()&&s[i]!='+'&&s[i]!='-'&&s[i]!='*'&&s[i]!=')';}

bool check2(){
  if(s[p]!='(')return 1;
  int i=p+1;
  while(isdigit(s[i]))i++;
  if(s[i]==')')return 0;
  
  i=p+2;
  int c=s[p+1]=='(';
  while(i<s.size()&&c) c+=(s[i]=='(')-(s[i++]==')');
  return c==0&&s[i]!=')';
}


int Num(){
  int res=0;
  flg&=check2();
  if(s[p]=='('){
    p++;
    res=bnf(),flg&=s[p++]==')';
    return res;
  }

  while(isdigit(s[p]))res=res*2+s[p++]-'0';
  if(res>1024)flg=0;
  return res;
}

int calc(){
  int res;
  p++;
  flg&=check2()&check(p);
  if(s[p]=='(')res=bnf();
  else {
    res=Num();
    if(s[p]=='*') res*=calc();
  }
  if(res<0||res>=1024) flg=0;
  return res;
}

int bnf(){
  flg&=check(p);
  int res=Num();
  while(p<s.size()&&flg){
    if(s[p]=='(') flg=0;
    if(s[p]==')')break;
    flg&=check(p+1);
    if(s[p]=='+')res+=calc();
    else if(s[p]=='-')res-=calc();
    else if(s[p]=='*')res*=calc();
    else break;
    if(res<0||res>=1024) flg=0;
  }
  if(res<0||res>=1024) flg=0;
  if(!flg)res=-INF;
  return res;
}

int dfs(int idx){
  char ch[]={'0','1','+','-','*','(',')'};
  while(idx<s.size()&&s[idx]!='.')idx++;
  if(idx==s.size()){p=0,flg=1;return max(-1.0,bnf()-(p!=s.size())*INF);}

  int res=-1;
  for(int i=0;i<7;i++)s[idx]=ch[i],res=max(res,dfs(idx+1));
  s[idx]='.';
  return res;
}

int main(){
  cin>>s;
  cout<<dfs(0)<<endl;
  return 0;
}

Measured memory_bytes: 3168
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin>>s;
  
  if(s[s.size()-1]=='s') cout<<s+"es"<<endl;
  else cout<<s+"s"<<endl;

  return 0; 
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <unistd.h>

#define L 6
#define putchar_buf(X) do{ buf[point] = X; point++; }while(0)
#define putlong_buf(X) \
    do{ \
        long n=X; \
        char c[L]; \
        long i=L-1; \
        do{ c[i]=n%10+'0'; n/=10; i--; }while(n>0); \
        for(i++;i<L;i++){ putchar_buf(c[i]); } \
    }while(0)
#define puts_buf(X) \
    do { \
        for(size_t i=0; X[i]!='\0'; i++){ \
            putchar_buf(X[i]); \
        } \
        putchar_buf('\n'); \
    }while(0)

int data[1<<17];
char buf[819200];

static void solve(const long a, const long b, const size_t sp, const size_t ep, long mask, const long common){
    if(ep-sp<=2){
        data[sp+0] = common|a;
        data[sp+1] = common|b;
        printf("%ld ",  common|a);
        printf("%ld ",  common|b);
    }else{
        const long t = a^b;
        const long d = t&(-t);
        mask ^= d;
        const long aa = a & mask;
        const long ab = aa ^ (mask&(-mask));
        const size_t mp = (sp+ep)/2;
        solve(aa,     ab, sp, mp, mask, common|(a&d));
        solve(ab, b&mask, mp, ep, mask, common|(b&d));
    }
}

int main(void){
    long n, a, b;
    scanf("%ld %ld %ld", &n, &a, &b);
    if(__builtin_parity(a) == __builtin_parity(b)){
        puts("NO");
    }else{
        const size_t m = 1<<n;
        size_t point=0;
        puts("YES");
        solve(a, b, 0, m, 0xFFFFFFFFFFFFFFFF, 0);
        /*
        for(size_t i=0; i<m-1; i++){
            putlong_buf(data[i]);
            putchar_buf(' ');
        }
        putlong_buf(data[m-1]);
        putchar_buf('\n');
        write(1, buf, point);
        */
    }
    return 0;
}


Measured memory_bytes: 1408
inf = 10**9
while True:
    n = int(input())
    if n == 0:
        break
    b = [(0,0)]
    b.extend([tuple(map(int,input().split())) for i in range(n)])
    dp = [[inf]*4 for i in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        update = False
        for j in range(4):
            if dp[i][j] is inf:
                continue
            now = b[i][0]
            nxt = b[i+1][0]
            if j<=2 and b[i][1]+abs(nxt-now)*(j+1) <= b[i+1][1] and dp[i+1][j+1] > dp[i][j]+abs(nxt-now):
                dp[i+1][j+1] = dp[i][j]+abs(nxt-now)
                update = True
            if b[i][1]+now*(j+1)+nxt <= b[i+1][1] and dp[i+1][1] > dp[i][j]+nxt+now:
                dp[i+1][1] = dp[i][j]+nxt+now
                update = True
        if not update:
            print('NG',i+1)
            break
    if update:
        print('OK',min(dp[n])+b[n][0])



Measured memory_bytes: 5624
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

void f(vector<vector<int> >& v, int y, int x, int nl, int l)
{
  if (v[y][x] > l){
    v[y][x] = l;
    if (nl == l)
      return;
    if (y != 0 && v[y-1][x] > l){
      f(v, y-1, x, nl, l+1);
    }
    if (y != v.size()-1 && v[y+1][x] > l){
      f(v, y+1, x, nl, l+1);
    }
    if (x != 0 && v[y][x-1] > l){
      f(v, y, x-1, nl, l+1);
    }
    if (x != v[0].size()-1 && v[y][x+1] > l){
      f(v, y, x+1, nl, l+1);
    }
  }
}

int main()
{
  int h, w, k;
  cin >> h >> w >> k;
  vector<vector<int> > v;
  int sx, sy;
  for(int i = 0; i < h; ++i){
    string str;
    cin >> str;
    vector<int> vv;
    for(int j = 0; j < str.size(); ++j){
      if (str[j] == 'S'){
        sx = j;
        sy = i;
      }
      if (str[j] == '#'){
        vv.push_back(-1);
      }else{
        vv.push_back(1000000);
      }
    }
    v.push_back(vv);
  }
  queue<int> q;
  q.push((sy << 12) + sx);
  for(int i = 0; i <= k; ++i){
    queue<int> qq;
    while(!q.empty()){
      int y = q.front() >> 12, x = q.front() & 4095;
      if (v[y][x] > i){
        v[y][x] = i;
        if (y != 0 && v[y-1][x] > i){
          qq.push(((y-1) << 12) + x);
        }
        if (y != v.size()-1 && v[y+1][x] > i){
          qq.push(((y+1) << 12) + x);
        }
        if (x != 0 && v[y][x-1] > i){
          qq.push((y << 12) + x-1);
        }
        if (x != v[0].size()-1 && v[y][x+1] > i){
          qq.push((y << 12) + x+1);
        }
      }
      q.pop();
    }
    while(!qq.empty()){
      q.push(qq.front());
      qq.pop();
    }
  }
  f(v, sy, sx, k, 0);
  int minl = h;
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      if (v[i][j] <= k && v[i][j] >= 0){
        if (minl > i){
          minl = i;
        }
        if (minl > h-1-i){
          minl = h-1-i;
        }
        if (minl > j){
          minl = j;
        }
        if (minl > w-1-j){
          minl = w-1-j;
        }
      }
    }
  }
  if (minl == 0){
    cout << 1 << endl;
  }else{
    cout << (minl-1)/k + 2 << endl;
  }
  return 0;
}


Measured memory_bytes: 2816
package main

import (
	"fmt"
)

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	var ans string
	if a+b+c >= 22 {
		ans = "bust"
	} else {
		ans = "win"
	}

	fmt.Println(ans)

}


Measured memory_bytes: 512
from collections import defaultdict
n, k = map(int, input().split())
rec = defaultdict(int)
num = 0
for i in range(1, n + 1):
    if (2 * i) % k == 0:
        num += 1
    rec[i % k] += 1

for i, v in rec.items():
    if (2 * i) % k == 0:
        if v >= 1:
            num += v * (v - 1) * 3
        if v >= 2:
            num += v * (v - 1) * (v - 2)

print(num)

Measured memory_bytes: 15428
#include <iostream>
#include <limits>

int main()
{
	unsigned int n = 0;
	int min = std::numeric_limits<int>::max();
	int max_gap = std::numeric_limits<int>::min();

	std::cin >> n;

	int R = 0;
	for (unsigned int i = 0; i < n; i++)
	{
		std::cin >> R;
		if (R - min > max_gap){ max_gap = R - min; }
		if (R < min){ min = R; }
	}

	std::cout << max_gap << std::endl;

	return 0;
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define N               200005
#define ff              first
#define ss              second
#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define mii             map<ll,ll>
#define pq_max          priority_queue<ll>
#define pq_min          priority_queue<ll,vi,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define inp(arr,n)      for(ll x=0;x<n;x++) cin>>arr[x];
#define w(x)            ll x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void fio(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

string k;
ll D, dp[10005][105][2];

ll f(ll pos, ll d, bool bound){

    if(dp[pos][d][bound] != -1) return dp[pos][d][bound];

    ll ub = bound ? k[pos] - '0' : 9;
    if(pos == k.length() - 1){
        ll ans = 0;
        for(ll x=0;x<=ub;x++){
            if(x%D == d) ans++;
        }

        return dp[pos][d][bound] = ans;
    }

    ll ans = 0;
    for(ll x=0;x<=ub;x++){
        ans = (ans + f(pos+1, (d + D - x % D) % D, bound and (ub == x))) % mod;
    }

    return dp[pos][d][bound] = ans;
}

int main(){
    fio();

    memset(dp, -1, sizeof dp);

    cin>>k;
    cin>>D;

    cout<<(f(0, 0, true) - 1 + mod) % mod;

    return 0;
}

Measured memory_bytes: 21012
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

using namespace std;

#include <atcoder/modint>

using mint = atcoder::modint998244353;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::print(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

const mint TEN = 10;

const long long NEUTRAL_VAL = 0;
struct SegmentTreeNode {
   mint val;
   int len;
   bool delay_flag;
   char delay_val;
   SegmentTreeNode(int _val = NEUTRAL_VAL, int _len = 0)
      : val(_val), len(_len), delay_flag(false), delay_val(0) { }
   SegmentTreeNode operator+(const SegmentTreeNode& R) const {
      SegmentTreeNode res;
      res.val = this->val * TEN.pow(R.len) + R.val;
      res.len = this->len + R.len;
      return res;
   }
   void update(int L, int R, char d) {
      delay_flag = true;
      delay_val = d;
      val = ((TEN.pow(R-L+1) - 1) / 9) * (d-'0');
   }
   void propagate(SegmentTreeNode& pL, SegmentTreeNode& pR, int L, int R) {
      if (delay_flag) {
         pL.update(L, (L+R)/2, delay_val);
         pR.update((L+R)/2+1, R, delay_val);
         delay_flag = false;
         delay_val  = 0;
      }
   }
};

class SegmentTree {
   int N;
   vector<SegmentTreeNode> tree;

   void _build(const string& S, int node, int L, int R) {
      if (L == R) {
         tree[node] = SegmentTreeNode(S[L]-'0', 1);
         return;
      }
      _build(S, 2*node, L, (L+R)/2);
      _build(S, 2*node+1, (L+R)/2+1, R);
      tree[node] = tree[2*node] + tree[2*node+1];
   }
   void _update(int p, int q, char val, int node, int L, int R) {
      if (q < L || p > R) return;
      if (p <= L && R <= q) {
         tree[node].update(L, R, val);
         return;
      }
      tree[node].propagate(tree[2*node], tree[2*node+1], L, R);
      _update(p, q, val, 2*node, L, (L+R)/2);
      _update(p, q, val, 2*node+1, (L+R)/2+1, R);
      tree[node] = tree[2*node] + tree[2*node+1];
   }
public:
   SegmentTree(const string& S) {
      N = S.size();
      int NUM_NODES = 4*N+1;
      tree = vector<SegmentTreeNode>(NUM_NODES);
      _build(S, 1, 0, N-1);
   }
   void update(int p, int q, char val) {
      _update(p, q, val, 1, 0, N-1);
   }
   mint query() {
      return tree[1].val;
   }
};


int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   int N, Q;
   cin >> N >> Q;
   string S(N, '1');

   SegmentTree ST(S);
   FOR(q, 1, Q) {
      int L, R, D;
      cin >> L >> R >> D;
      --L, --R;
      ST.update(L, R, '0'+D);
      mint res = ST.query();
      cout << res.val() << '\n';
   }

   return 0;
}


Measured memory_bytes: 12728
from functools import reduce
from fractions import gcd


def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(lst):
    return reduce(lcm_base, lst, 1)


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


ans = sum((l-1) % a for a in lst_a)
print(ans)

Measured memory_bytes: 5340
A,V=map(int,input().split())
B,W=map(int,input().split())
T=int(input())
if(A<B):
  A1=A+V*T
  B1=B+W*T

  if(A1>=B1):
    print('YES')
  else:
    print('NO')
    
else:
  A1=A-V*T
  B1=B-W*T

  if(A1<=B1):
    print('YES')
  else:
    print('NO')

Measured memory_bytes: 9128
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	vector<double> v(n);
	rep(i, n) cin >> v[i];
	rep(i, n - 1) {
		sort(all(v));
		v[0] = (v[0] + v[1]) / (double)(2.0);
		v[1] = INF;
	}
	cout << fixed << setprecision(8) << v[0] << endl;
}

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

bool dp[100001];
bool dp2[100001];
//state represents if it possible for player K to win if we consider a prefix of length i of the input with a pile of size J
int a[101];
int main(){
	int N, K;
	cin >> N >> K;
	for(int i = 0; i < N; i++){
		cin >> a[i];
	}
	
	for(int i = 0; i < N; i++){
		dp[a[i]]=true;
	}
	for(int i = 0; i <= K; i++){
		for(int j = 0; j < N; j++){
			if(i-a[j]<0){continue;}
			if(!dp[i-a[j]]){
				dp[i]=true;
			}
		}
	}

	if(!dp[K]){
		cout << "Second" << endl;
	} else {
		cout << "First" << endl;
	}

}


Measured memory_bytes: 3692
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;

fn main() {
    input! {
        n: usize,
        m: usize,
        mut a: [usize; m],
    }
    a.sort();
    let mut valid = vec![false; 10];
    for &ai in &a {
        valid[ai - 1] = true;
    }

    let cost = vec![2, 5, 5, 4, 5, 6, 3, 7, 6];

    let mut dp: Vec<Option<usize>> = vec![None; n + 1];
    dp[0] = Some(0);
    for i in 0..n + 1 {
        for j in 0..cost.len() {
            if !valid[j] || cost[j] > i {
                continue;
            }
            if dp[i - cost[j]].is_none() {
                continue;
            }
            dp[i] = Some(max(dp[i].unwrap_or(0), dp[i - cost[j]].unwrap() + 1));
        }
    }
    let mut left = n;
    let mut cur = a.len() - 1;

    while left > 0 {
        let digit = a[cur] - 1;
        // println!("{}, {}, {}", left, digit, cost[digit]);
        if left >= cost[digit]
            && dp[left - cost[digit]].is_some()
            && dp[left - cost[digit]].unwrap() == dp[left].unwrap() - 1
        {
            print!("{}", ('1' as u8 + digit as u8) as char);
            left -= cost[digit];
        } else {
            cur -= 1;
        }
    }
    println!("");
}


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

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

    while(k--)
    {
        int d;cin>>d;
        for(int i=0;i<d;i++)
        {
            int x;cin>>x;
            a[x]=1;
        }
    }

    int cnt=0;
    for(int i=1;i<=n;i++)if(a[i]==0)cnt++;
    cout<<cnt<<endl;
}


Measured memory_bytes: 3628
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<cmath>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include<cassert>
    #include<cmath>
    #include<cstdint>
     
    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
    #define ALL(a)  (a).begin(),(a).end()
    #define chmin(a, b) a = min(a, b)
    #define chmax(a, b) a = max(a, b)
    #define pb push_back
    #define sz size()
     
    using namespace std;
    using ll = long long int;
    using Graph = vector<vector<int>>;
    using P = pair<ll, ll>;
    using Vl = vector<ll>;
     
const int MOD = 1e9 + 7;
const ll ZER = 0;

int dp[10000000];
int main(){
    int x;
    cin >> x;
    dp[0] = 1;
    rep(i, 100000){
      	if(dp[i] == 0)continue;
        rep(j, 6){
            dp[i + 100 + j] = dp[i];
        }
    }
    cout << dp[x] << endl;
}



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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}



void _main() {
        int n; cin >> n;
        vector<int> b(4);
        for (int i = 0; i < n; i++) {
                int x; cin >> x;
                x %= 4;
                if (x == 3) x = 1;
                b[x]++;
        }

        vector<int> ans;
        if (b[2]) {
                while (b[2]--) ans.emplace_back(2);
                for (int i = 0; b[0] || b[1]; i++) {
                        if (i % 2 == 0 && b[0]) ans.emplace_back(0), b[0]--;
                        else if (b[1]) ans.emplace_back(1), b[1]--;
                }
        } else {
                for (int i = 0; b[0] || b[1]; i++) {
                        if (i % 2 == 0 && b[1]) ans.emplace_back(1), b[1]--;
                        else if (b[0]) ans.emplace_back(0), b[0]--;
                }
        }
        //2, 2, 2, 2, 0, 1, 0, 1, 0, 1,

        for (int i = 1; i < n; i++) {
                if (ans[i] * ans[i - 1] % 4) {
                        cout << "No";
                        return;
                }
        }

        cout << "Yes";
}




signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


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

int main(){
  int N,K; cin>>N>>K;
  string S; cin>>S;
  vector<pair<int,int>> T(1,{1,1});
  bool z=true;
  int s;
  for(int i=0;i<N;i++){
    if(z&&S[i]=='1'){
      s=i; z=false;
    }
    if(!z&&S[i]=='0'){
      T.push_back({s+1,i});
      z=true;
    }
  }
  if(!z)
    T.push_back({s+1,N});
  T.push_back({N,N});
  int ts=T.size();
  int ans=0,ansc;
  for(int i=0;i<ts;i++){
    //cout<<T[i].first<<" "<<T[i].second<<endl;
    if(i+K<ts){
      ansc=T[i+K].second-T[i].first+1;
      ans=max(ans,ansc);
    }
  }
  if(ans)
    cout<<ans<<endl;
  else
    cout<<N<<endl;
}

Measured memory_bytes: 1020
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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





int main() {
    ll a,b,c;
    cin>>a>>b>>c;
    if(4*a*b<(c-a-b)*(c-a-b) && c-a-b>0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define forn(i, n) for (llong i = 0ll; i < (llong) n; ++i)
#define fornn(i, l, r) for (llong i = (llong) l; i < (llong) r; ++i)
#define size(x) ((int) (x.size()))
 
using namespace std;
 
typedef long long llong;
const llong inf = (llong) 1e+9 + 7ll;
const llong linf = (llong) 1e+18 + 7ll;
const long double eps = (long double) 1e-9;
const long double pi = acosl((long double) -1.0);
const int alph = 26;

mt19937 mrand(random_device{} ()); 

template<typename T, typename U> inline llong umin(const T& a, const U& b) { return a < b ? a : b; }
template<typename T, typename U> inline llong umax(const T& a, const U& b) { return a > b ? a : b; }
 
static char buff[(int) 2e6 + 17]; // reads std::string
const int maxn = (int) 1e5 + 17;

int n, ctr, e;
llong ans;
vector< pair<int, int> > g[maxn];

bool read()
{
	if (scanf("%d", &n) != 1)
		return false;

	forn (i, n - 1)
	{
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		g[u - 1].push_back(make_pair(v - 1, c));
		g[v - 1].push_back(make_pair(u - 1, c));
	}

	return true;
}

int dfs1(int v, int pr)
{
	int sz = 1;

	for (auto to : g[v])
		if (to.first != pr)
			sz += dfs1(to.first, v);

	if (ctr == -1 && 2 * sz >= n)
		ctr = v;

	return sz;
}

int dfs2(int v, int pr)
{
	int sz = 1;

	for (auto to : g[v])
		if (to.first != pr)
		{
			int cur = dfs2(to.first, v);
			ans += 2ll * cur * to.second;
			sz += cur;

			if (2 * cur == n)
				e = to.second;
		}

	return sz;
}

void solve()
{
	ctr = -1;
	e = inf;
	dfs1(0, -1);
	dfs2(ctr, -1);

	if (e == inf)
		for (auto to : g[ctr])
			e = min(e, to.second);

	printf("%lld\n", ans - e);
}

int main()
{
#if SEREZHKA
	freopen("file.in", "r", stdin);
#endif

	while (read())
		solve();

	return 0;
}


Measured memory_bytes: 9728
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define mod 1000000007
#define MOD 998244353
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
signed main() {
    char X, Y;
    cin >> X >> Y;
    if(X > Y)
        cout << '>' << endl;
    else if(X == Y)
        cout << '=' << endl;
    else
        cout << '<' << endl;
}


Measured memory_bytes: 256