akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

// 文字列 split / デリミタに含まれるいずれかの文字で分割
vector<string> split( const string &str, const string &delim = " " )
{
	int start = 0, pos;
	vector<string> result;

	while ( ( pos = str.find_first_of( delim, start ) ) != string::npos )
	{
		result.push_back( str.substr( start, pos - start ) );
		start = pos + 1;
	}

	return result;
}

const VS BUTTONS = {
	"",
	".,!? ",
	"abc",
	"def",
	"ghi",
	"jkl",
	"mno",
	"pqrs",
	"tuv",
	"wxyz"
};

string solve( string line )
{
	VS chars( split( line, "0" ) );
	string res;

	REP( i, 0, chars.size() )
	{
		if ( !chars[i].size() )
		{
			continue;
		}

		const int pushed_button = chars[i][0] - '0';
		const int pushed_number = chars[i].size() - 1;
		res += BUTTONS[ pushed_button ][ pushed_number % BUTTONS[ pushed_button ].size() ];
	}

	return res;
}

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

	int n;
	cin >> n;
	REP( i, 0, n )
	{
		string line;
		cin >> line;
		cout << solve( line ) << endl;
	}

	return 0;
}

Measured memory_bytes: 1232
# -*- coding: utf-8 -*-

class Node_Class():
    def __init__(self, key, parent, left, right):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def pre_order(node, list):
    if node is not None:
        list.append(node.key)
        pre_order(node.left, list)
        pre_order(node.right, list)

def in_order(node, list):
    if node is not None:
        in_order(node.left, list)
        list.append(node.key)
        in_order(node.right, list)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    else:
        A = []
        B = []
        in_order(root, A)
        pre_order(root, B)
        print " "+" ".join(map(str, A))
        print " "+" ".join(map(str, B))

Measured memory_bytes: 251836
from bisect import bisect_right
from itertools import accumulate


def can_survive(prev):
    while True:
        idx = bisect_right(A, 2 * acc_A[prev]) - 1
        if idx == N - 1:
            return True
        if idx == prev:
            return False
        prev = idx


def binary_search(left, right):
    while right - left > 1:
        mid = (left + right) // 2
        if can_survive(mid):
            right = mid
        else:
            left = mid
    return left if can_survive(left) else right


N = int(input())
A = sorted(map(int, input().split()))
acc_A = list(accumulate(A))
print(N - binary_search(0, N))


Measured memory_bytes: 14432
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

const ll MOD=1'000'000'007;

ll n,a,b;

ll mpow(ll x,ll n){
	if(n==0) return 1;
	if(n%2==1) return x*mpow(x,n-1)%MOD;
	else return mpow(x*x%MOD,n/2)%MOD;
}

ll mfrac(ll n){
	ll res=1;
	for(int i=1;i<=n;i++) res=res*i%MOD;
	return res;
}

ll mcomb(ll n,ll r){
	if(n-r<r) r=n-r;
	ll x=1;
	for(int i=0;i<r;i++) x=x*(n-i)%MOD;
	ll y=mpow(mfrac(r),MOD-2);
	return x*y%MOD;
}

int main(){
	cin>>n>>a>>b;
	
	ll x=mpow(2,n);
	ll y=mcomb(n,a);
	ll z=mcomb(n,b);
	//cout<<x<<" "<<y<<" "<<z<<endl;;

	ll ans=(x-y-z-1)%MOD;
	if(ans<0) ans+=MOD;

	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int mex=100001;
#define ll long long 
#define test int t;cin>>t;while(t--)
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,a,b) for(int i=a;i>=b;i--)
#define bg begin()
#define en end()
#define fi first
#define se second
#define ub upper_bound
#define lb lower_bound
#define pb push_back
#define veci vector<int>
#define veclli vector<long long int> 
#define all(x) x.begin(),x.end()
#define sci(x) scanf("%d",&x);
#define scc(x) scanf("%c",&x);
#define scs(x) scanf("%s",x);
#define debug(arr,n) for(int i=0;i<n;i++) printf("%d ",arr[i]);
#define sz(x) x.size()
#define loop(x) for(auto it=x.begin();it!= x.end();it++)

int main()
{
   ll int n,a,b;
   cin>>n>>a>>b;
   ll int k=n/(a+b);
   ll int j=n%(a+b);
   ll int an=k*a+min(j,a);
   cout<<an;
   
}


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

int main(){

  int N;
  bool ans=true;
  cin >> N;
  long H[N];
  for(int i=0; i<N; i++) cin >> H[i];

  for(int i=0; i<N-1; i++){
    if(H[i+1]>H[i]) H[i+1]--;
  }

  for(int i=1; i<N; i++){
    if(H[i]<H[i-1]) ans = false;
  }

  cout << (ans ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
int main() {
  char s;
  cin >> s;
  if(isupper(s)) cout << "A" << endl;
  else cout << "a" << endl;
}


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


using namespace std;

typedef long long ll;



int main() {
   int n, W;
   cin >> n >> W;
   vector<ll> v(n + 1), w(n + 1);
   for(int i = 1; i <= n; i++)cin >> w[i] >> v[i];
   vector<vector<ll> > dp(W + 1, vector<ll>(n + 1));
   for(int i = 1; i <= W; i++){
       for(int j = 1; j <= n; j++){
           if(w[j] <= i){
               dp[i][j] = max(dp[i][j - 1], dp[i - w[j]][j - 1] + v[j]);
           }else{
               dp[i][j] = dp[i][j - 1];
           }
       }
   }
   cout << dp[W][n] << endl;
}


Measured memory_bytes: 85256
#include<stdio.h>
int main(void)
{
    int H1 = 0;
    int M1 = 0;
    int H2 = 0;
    int M2 = 0;
    int K = 0;
    scanf("%d %d %d %d %d\n", &H1, &M1, &H2, &M2, &K);
    printf("%d", (((H2 * 60 + M2) - (H1 * 60 + M1)) - K));
    return 0;
}

Measured memory_bytes: 1732
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;
ll gcd(ll a, ll b) { return (b ? gcd(b, a % b) : a); }
ll lcm(ll a, ll b) { return a / (gcd(a, b)) * b; }

int main(){
  int n,k;
  cin>>n>>k;

  if(k==1) cout<<0<<endl;
  else cout<<n-k<<endl;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

const int MAX = 1000000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, M;
    cin >> N >> M;

    // for(auto p : prime_factor(N)) {
    //     while(p.second--) cout << " " << p.first;
    // }
    // cout << endl;

    map<ll, ll> PR;
    PR = prime_factor(M);

    // 前処理
    COMinit();

    ll ans = 1;
    for(auto p:PR){
        // cout << p.second << endl;
        ans = (ans * COM(p.second + N - 1, p.second)) % MOD;
        ans = ans % MOD;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    int c=a*b;
    if(c%2==0){
        cout << "Even" << endl;
    }else if(c%2!=0){
        cout << "Odd" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    string a, b, c;
    cin >> a >> b >> c;
    int k = 0;
    while (true)
    {
        char o;
        if (k == 0)
        {
            if (a.size() == 0)
                break;
            else
            {
                o = a[0];
                a.erase(0, 1);
            }
        }
        if (k == 1)
        {
            if (b.size() == 0)
                break;
            else
            {
                o = b[0];
                b.erase(0, 1);
            }
        }
        if (k == 2)
        {
            if (c.size() == 0)
                break;
            else
            {
                o = c[0];
                c.erase(0, 1);
            }
        }
        if (o == 'a')
            k = 0;
        if (o == 'b')
            k = 1;
        if (o == 'c')
            k = 2;
    }
    if (k == 0)
        cout << "A";
    if (k == 1)
        cout << "B";
    if (k == 2)
        cout << "C";
    return 0;
}


Measured memory_bytes: 256
s = input()
ls = ['MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT', 'SUN']
for i in ls:
    if s == i:
        p = ls.index(s)

if s == 'SUN':
    print(7)
else:
    print(ls.index('SUN') - p)


Measured memory_bytes: 2940
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for(i=0;i<n;i++)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define fact(n) nPr((int)(n),(int)(n))
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(const void *a, const void *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(const void *a, const void *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(const void* left, const void* right) {return strcmp((char *)left,(char *)right);}
int downchar(const void* left, const void* right) {return strcmp((char *)right,(char *)left);}
ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}
void initialize(){
    
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0;
  int x[LIMIT2]={0},l[LIMIT2]={0};
  char s[LIMIT1];
  
  scanf("%lld %lld",&n,&m);
  rep(i,m) scanf("%d",&x[i]);
  if(n>=m){
    printf("0");
    return 0;
  }
  qsort(x,m,sizeof(int),upint);
  rep(i,m-1){
    l[i]=x[i+1]-x[i];
    result += (ll)l[i];
  }
  qsort(l,m-1,sizeof(int),downint);
  
  rep(i,n-1){
    result -= (ll)l[i];
  }
  printf("%lld",result);
  
  return 0;
}



Measured memory_bytes: 4476
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
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;}
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    ll N,M;cin>>N>>M;
    vvl info(N,vl());
    vl dist(N),cnt(N),used(N);
    rep(i,M){
        ll a,b;cin>>a>>b;
        a--,b--;
        info[a].push_back(b);
        cnt[b]++;
    }
    queue<ll> que;
    rep(i,N){
        if(used[i] or cnt[i])continue;
        que.push(i);
        used[i]++;
        while(que.size()){
            ll q=que.front();que.pop();
            for(auto p:info[q]){
                dist[p]=max(dist[p],dist[q]+1);
                cnt[p]--;
                if(!cnt[p] and !used[p])que.push(p),used[p]++;
            }
        }
    }
    ll ans=0;
    rep(i,N)ans=max(ans,dist[i]);
    cout<<ans<<endl;
    return 0;
}

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

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	ll N;
	cin >> N;
    typedef pair<ll,ll> P;
    vector<P> X(N);
    rep(i,N){
        ll tmp_x,tmp_l;
        cin>>tmp_x>>tmp_l;
        X[i] = P{tmp_x-tmp_l,tmp_x+tmp_l};
    }
    sort(X.begin(),X.end(),[](P p1, P p2){return p1.first < p2.first;});

    ll ans = N;
    ll tmpx = X[0].second;
    for(int i=1;i<N;i++){
        if(X[i].first < tmpx){
            tmpx = min(X[i].second,tmpx);
            ans--;
        }else{        
            tmpx = X[i].second;
        }
    }
    cout<<ans<<"\n";
    
	return 0;
}

Measured memory_bytes: 1792
n, m = gets.split.map &:to_i
lights = m.times.map {gets.split.map &:to_i}
ps = gets.split.map &:to_i

cnt = (1 << n).times.count do |state|
  lights.each_with_index.all? do |(k, *switches), l|
    switches.count { |j| state[j-1] == 1 } % 2 == ps[l]
  end
end
p cnt

Measured memory_bytes: 14276
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

template<class T> void chmin(T &a, const T &b){ a = (a < b ? a : b); }
template<class T> void chmax(T &a, const T &b){ a = (a > b ? a : b); }

int main() {
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();
    auto dp = make_v(n+1, 2, k+1, 0UL);
    dp[0][0][0]= 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int l = 0; l <= k; ++l) {
                int d = j ? 9 : s[i]-'0';
                for (int x = 0; x <= d; ++x) {
                    if(l + (x!=0) <= k){
                        dp[i+1][j|(x < d)][l+(x!=0)] += dp[i][j][l];
                    }
                }
            }
        }
    }
    cout << dp[n][0][k]+dp[n][1][k] << "\n";
    return 0;
}

Measured memory_bytes: 256
solve :: String -> String
solve [] = "Yes"
solve [x] = if x `elem` ['R', 'U', 'D'] then "Yes" else "No"
solve (x:y:xs) = if x `elem` ['R', 'U', 'D'] && y `elem` ['L', 'U', 'D'] then solve xs else "No"

main = getLine >>= putStrLn . solve


Measured memory_bytes: 380
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,ans=0;
	cin>>n;
	long long a[n+1],b[n+1],c[n+1];
	b[0]=0;
	c[0]=0;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=b[i-1]+a[i];
		c[i]=c[i-1]^a[i];
	}
	long long l,r=1;
	for(l=1;l<=n;l++)
	{
//		cout<<l<<"&&&&&"<<endl;
		if(r<l) r=l;
		for(;r<=n;r++)
		{
//			cout<<l<<" "<<r<<"***"<<endl;
			if(b[r]-b[l-1]!=(c[r]^c[l-1]))
			{
//				cout<<b[r]-b[l-1]<<":::"<<(c[r]^c[l-1])<<endl;
//				cout<<ans<<" [[[[]]]] "<<ans+r-l<<endl; 
				ans+=r-l;
				r--;
				break;
			}
			if(r==n)
			{
				ans+=r-l+1;
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			char[] r = sc.next().toCharArray();
			char[] a = sc.next().toCharArray();
			if(r.length==1)break;
			int h = 0;
			int b = 0;
			int[] c1 = new int[10];
			int[] c2 = new int[10];
			for(int i=0;i<4;i++){
				if(r[i]==a[i]){
					h++;
					continue;
				}
				c1[r[i]-'0']++;
				c2[a[i]-'0']++;
			}
			for(int i=0;i<10;i++)b+=Math.min(c1[i], c2[i]);
			System.out.println(h+" "+b);
		}
	}
}

Measured memory_bytes: 44072
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <list>
#include <algorithm>
#include <iterator>
#include <utility>
#include <string>
#include <climits>
using namespace std;

int main(){

    int n;
    cin>>n;
    long A[n];
    long mx = 0;
    long sum = 0;
    for(int i = 0;i<n;i++){
        cin>>A[i];
        if(mx>A[i]){
            sum+=(mx - A[i]);
        }else{
            mx = max(A[i], mx);
        }
    }
    cout<<sum;
	return 0;
}


Measured memory_bytes: 5136
#include <stdio.h>
#include <string>
#include <queue>
#include <set>
using namespace std;

const int mod = 998244353;
int prv[3][3][2], nxt[3][3][2];
char S[200200];

int main()
{
	scanf ("%s",S);

	int l = 0;
	while (S[l]) l++;

	if (l <= 10){
		set<string> chk;
		queue<string> Q;
		Q.push(S); chk.insert(S);
		while (!Q.empty()){
			string s = Q.front(); Q.pop();
			for (int i=1;i<s.length();i++) if (s[i-1] != s[i]){
				string t = s;
				int c = 3 - (s[i-1] - 'a') - (s[i] - 'a') + 'a';
				t[i-1] = t[i] = c;
				if (!chk.count(t)){
					Q.push(t); chk.insert(t);
				}
			}
		}
		printf ("%d\n",chk.size());
		return 0;
	}

	int c = 0;
	for (int i=0;i<l;i++) c += S[i] - 'a';

	bool p = false, q = false;
	for (int i=1;i<l;i++){
		if (S[i-1] == S[i]) p = true;
		if (S[i-1] != S[i]) q = true;
	}

	prv[0][0][0] = prv[0][1][0] = prv[0][2][0] = 1;
	for (int i=1;i<l;i++){
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++) nxt[x][y][k] = 0;
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++){
			for (int z=0;z<3;z++){
				int nk = k || ((x + y + z) % 3 == 0);
				nxt[y][z][nk] = (nxt[y][z][nk] + prv[x][y][k]) % mod;
			}
		}
		for (int x=0;x<3;x++) for (int y=0;y<3;y++) for (int k=0;k<2;k++) prv[x][y][k] = nxt[x][y][k];
	}

	if (!q) puts("1");
	else{
		int ans = !p;
		for (int x=0;x<3;x++) ans = (ans + prv[x][c%3][1]) % mod;
		printf ("%d\n",ans);
	}

	return 0;
}

Measured memory_bytes: 896
#include<cstdio>
#include<algorithm>

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

using namespace std;

typedef long long ll;

const ll INF=1LL<<61;

int main(){
	for(int n;scanf("%d",&n),n;){
		int I[100];
		ll sat[100];
		rep(i,n){
			I[i]=0;
			int m; scanf("%d%lld",&m,sat+i);
			rep(j,m){
				int s,e; scanf("%d%d",&s,&e);
				for(int k=s;k<e;k++) I[i]|=1<<(k-6);
			}
		}

		static ll dp[101][1<<16];
		rep(i,n+1) rep(S,1<<16) dp[i][S]=(i==0&&S==0?0:-INF);
		rep(i,n) rep(S,1<<16) {
			dp[i+1][S]=max(dp[i+1][S],dp[i][S]);
			if((S&I[i])==0) dp[i+1][S|I[i]]=max(dp[i+1][S|I[i]],dp[i][S]+sat[i]);
		}
		printf("%lld\n",*max_element(dp[n],dp[n]+(1<<16)));
	}

	return 0;
}

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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni();
        long ans = n/500*1000;
        n = n-n/500*500;
        ans += n/5*5;
        out.println(ans);
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 22996
process.stdin.resume();
process.stdin.setEncoding('utf8');

class Score {
    constructor(id, score1, score2, score3) {
        this.id = id;
        this.score1 = score1;
        this.score2 = score2;
        this.score3 = score3;
    }
    comparison(scores) {

        let score1 = this.score1;
        let score2 = this.score2;
        let score3 = this.score3;

        scores.forEach(s => {
            if (this.id !== s.id) {

                if (this.score1 === s.score1) {
                    score1 = 0;
                }
                if (this.score2 === s.score2) {
                    score2 = 0;
                }
                if (this.score3 === s.score3) {
                    score3 = 0;
                }
            }
        });

        return new Score(this.id, score1, score2, score3);
    }

    sum() {
        return this.score1 + this.score2 + this.score3;
    }
}



process.stdin.on('data', function (chunk) {
    const n = chunk.toString() // 文字列化する
        .split("\n") // \nで分割
        .filter(x => x !== "");
    const [count, ...inputScore] = n;
    let scoreAll = [];
    const all = inputScore.map(x => x.split(" "));

    for (let i = 0; i < inputScore.length; i++) {
        var [score1, score2, score3] = all[i];
        scoreAll.push(new Score(i, Number(score1), Number(score2), Number(score3)));
    }

    const changed = scoreAll.map(x => x.comparison(scoreAll));

    changed.forEach(x => {
        console.log(x.sum());
    });
});


Measured memory_bytes: 18124
N = int(input())
A = list(map(int, input().split()))
M = int(input())
ans = []
for i in range(M):
  p, x = map(int, input().split())
  copy_A = A.copy()
  copy_A[p-1] = x
  ans.append(sum(copy_A))
for a in ans:
  print(a)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  string c1, c2;
  cin >> c1 >> c2;
  bool ans = true;

  rep(i, 3) {
    if (c1[i] != c2[2-i]) ans = false;
  }

  if (ans) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


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

int main() {
    int n, m, k, a, i, ans = 0;
    cin >> n >> m;
    int *f = new int[m+1];
    for (i = 1; i <= m; i++)
        f[i] = 0;
    
    for (i = 1; i <= n; i++) {
        cin >> k;
        int j;
        for (j = 0; j < k; j++) {
            cin >> a;
            f[a]++;
        }
    }

    for (i = 1; i <= m; i++) {
        if (f[i] == n)
            ans++;
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;

int main()
{
    int n;
    cin >> n;
    vector<int> even,odd;
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        if(i%2) odd.emplace_back(a);
        else even.emplace_back(a);
    }

    if(n%2){
        for(int i = even.size()-1; i >= 0; i--) cout << even[i] << ' ';
        for(int i = 0; i < odd.size(); i++) cout << odd[i] << ' ';
    }else{
        for(int i = odd.size()-1; i >= 0; i--) cout << odd[i] << ' ';
        for(int i = 0; i < even.size(); i++) cout << even[i] << ' ';
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 3188
using System;
using System.Collections.Generic;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());
            List<long> n = new List<long>();

            while (N / 26 != 0)
            {
                if (N % 26 == 0)
                {
                    n.Add(26);
                    N = N / 26 - 1;
                }
                else
                {
                    n.Add(N % 26);
                    N = N / 26;
                }
            }
            if (N != 0)
            {
                n.Add(N);
            }

            char[] map = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
            List<char> ans_char = new List<char>();
            for (int i = n.Count - 1; i >= 0; i--)
            {
                ans_char.Add(map[n[i] - 1]);
            }

            string ans = "";
            foreach (char element in ans_char)
            {
                ans = ans + element;
            }

            Console.WriteLine(ans);
        }
    }
}


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

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define PI 3.14159265359
#define sz(c) (int)c.size()
#define len(c) (int)c.length()
#define hcf(a, b) __gcd(a, b)
#define all(c) c.begin(), c.end()
#define vint vector<int>
#define vll vector<ll>
#define vpint vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define fr(it, a, b) \
    for (int it = (a); it < (b); it++)
#define tr(con, it) \
    for (auto it = con.begin(); it != con.end(); it++)
#define present(con, ele) (con.find(ele) != con.end())
#define cpresent(con, ele) (find(all(con), ele) != con.end())
#define maximum(a, b, c) (a > b ? (a > c ? a : c) : (b > c ? b : c))
#define minimum(a, b, c) (a < b ? (a < c ? a : c) : (b < c ? b : c))
typedef long long ll;
typedef long double lf;
typedef pair<int, int> pi;
typedef unsigned long long lu;
const ll mod = 1e9 + 7;
int32_t main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h, w, k, x1, x2, y1, y2;
    cin >> h >> w >> k >> x1 >> y1 >> x2 >> y2;
    vector<pair<int, int>> p = {{-1, 0},
                                {1, 0},
                                {0, -1},
                                {0, 1}};
    vector<string> a(h);
    fr(i, 0, h)
    {
        cin >> a[i];
    }
    vector<vll> vis(h, vll(w, 0)), dis(h, vll(w, 1e18));
    queue<pair<int, int>> q;
    q.push({x1 - 1, y1 - 1});
    dis[x1 - 1][y1 - 1] = 0;
    while (!q.empty())
    {
        pi nd = q.front();
        q.pop();
        if (vis[nd.F][nd.S])
        {
            continue;
        }
        vis[nd.F][nd.S] = 1;
        int i = nd.F, j = nd.S;
        for (auto u : p)
        {
            for (int l = 1; l <= k; l++)
            {
                if (i + u.F * l < h && i + u.F * l >= 0 && j + u.S * l >= 0 && j + u.S * l < w)
                {
                    if (a[i + u.F * l][j + u.S * l] == '@')
                    {
                        break;
                    }
                    if (dis[i + u.F * l][j + u.S * l] >= dis[i][j] + 1)
                    {
                        dis[i + u.F * l][j + u.S * l] = dis[i][j] + 1;
                        q.push({i + u.F * l, j + u.S * l});
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    break;
                }
            }
        }
    }
    if (!vis[x2 - 1][y2 - 1])
    {
        cout << -1 << "\n";
        return 0;
    }
    cout << dis[x2 - 1][y2 - 1] << "\n";
    return 0;
}

Measured memory_bytes: 27524
//*-- ILSH --*//
#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
#define pb push_back 
#define pop pop_back
#define mp make_pair
#define ve vector
#define vii vector < int >
#define vll vector < ll > 
#define pii pair < int , int >
#define pll pair < ll , ll >
#define vpi vector < pii >
#define vpl vector < pll >
#define viii vector < vii >
#define vlll vector < vll >
#define fi first
#define sz size 
#define len length 
#define se second 
//const ll mod=998244353;
const ll mod = 1000000000+7;
const ll N=200000+6;
const ll inf=1e17;
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return (res%mod);}
ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
bool arr[101][100001];
ll crr[101][100001];
void solve() {
	int n;
	cin>>n;
	int w;
	cin>>w;
	ll brr[n+1][2];
	memset( crr,0,sizeof( crr));
	for ( int i=0;i<101;i++)
		arr[i][0]=1;
	for (int i=1;i<=n;i++)
		cin>>brr[i][0]>>brr[i][1];
	for ( int i=1;i<=n;i++) {
		for ( int j=0;j<=w;j++){
			if ( j-brr[i][0]>=0&&arr[i-1][j-brr[i][0]]){
				crr[i][j]=max( crr[i][j],brr[i][1]+crr[i-1][j-brr[i][0]]);
				arr[i][j]=true;
			}
			if ( arr[i-1][j]){
				arr[i][j]=true;
				crr[i][j]=max( crr[i][j],crr[i-1][j]);
			}
		}
	}
	ll ma=0;
	for (int i=0;i<=w;i++)
		ma=max( crr[n][i],ma);
	cout<<ma<<'\n';



}

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

Measured memory_bytes: 89088
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<cctype>
using namespace std;
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;}
const long long INF = 1LL << 60;

int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	
	int m;
	cin>>m;
	cout<<24+24-m<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
using namespace std;
///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!!
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-5)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1000000007;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H & b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H & b) const { return x == b.x && y == b.y; }
	bool operator!=(const H & b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T & a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T & a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int h, w;
int a[2000][2000];
struct A {
	int x, y, t;
	bool operator<(A a) const{ return t < a.t; }
	bool operator>(A a) const{ return t > a.t; }
};
signed main() {
	cin >> h >> w;
	int sum = 0;
	priority_queue<A, vector<A>, greater<A>>q;
	for (int i = 0; i < h; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < w; j++) {
			if (s[j] == '#') {
				a[i][j] = 1;
				q.push(A{ i,j,1 });
			}
			else sum++;
		}
	}
	int ans = 1;
	while (!q.empty()) {
		A t = q.top(); q.pop();
		if (t.x > 0 && !a[t.x - 1][t.y]) {
			a[t.x - 1][t.y] = t.t + 1;
			q.push(A{ t.x - 1, t.y, t.t + 1 });
			ans = max(ans, t.t + 1);
		}
		if (t.x < h - 1 && !a[t.x + 1][t.y]) {
			a[t.x + 1][t.y] = t.t + 1;
			q.push(A{ t.x + 1, t.y, t.t + 1 });
			ans = max(ans, t.t + 1);
		}
		if (t.y > 0 && !a[t.x][t.y - 1]) {
			a[t.x][t.y - 1] = t.t + 1;
			q.push(A{ t.x, t.y - 1, t.t + 1 });
			ans = max(ans, t.t + 1);
		}
		if (t.y < w - 1 && !a[t.x][t.y + 1]) {
			a[t.x][t.y + 1] = t.t + 1;
			q.push(A{ t.x, t.y + 1, t.t + 1 });
			ans = max(ans, t.t + 1);
		}
	}
	cout << ans - 1 << endl;
}

Measured memory_bytes: 40036
import Control.Applicative
import Data.List
import qualified Data.ByteString.Char8 as BS
import Data.Maybe
readIntBS = fst . fromJust . BS.readInt

main = do
  [n,k] <- map read . words <$> getLine :: IO [Int]
  as <- sort . map readIntBS . BS.words <$> BS.getLine :: IO [Int]

  let
    m = maximum as
    d = foldl1 gcd as

  putStrLn $ if k <= m && k `mod` d == 0 then "POSSIBLE" else "IMPOSSIBLE"



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

using namespace std;

typedef long long ll;

const int N = 1001;
const ll E = 1e9 + 7;

int isprime[N], k[N];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 2; i < N; ++i) {
        int t = 1;
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                t = 0;
                break;
            }
        }
        isprime[i] = t;
    }
    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        int t = i;
        for (int j = 2; j <= i; ++j) {
            while (isprime[j] && t % j == 0) {
                t /= j;
                ++k[j];
            }
        }
    }
    ll ans = 1;
    for (int i = 2; i < N; ++i) {
        ans = ans * (k[i] + 1) % E;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int n=s.size();
	bool ok=(s[0]=='1' && s[n-1]=='0');
	for (int i=0;i<n-1;i++)
	ok&=(s[i]==s[n-i-2]);
	if (!ok)
	{
		printf("-1");
		return 0;
	}
	int p=n;
	for (int i=n-2;i>=0;i--)
	{
		printf("%d %d\n",i+1,p);
		if (s[i]=='1')
		p=i+1;
	}
}

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

int main() {
    long long n , a, b;
    cin >> n >> a >> b;

    //int ans = 0;
    long long c = a + b;
    long long ans = a * (n / c);
    ans += min(n % c, a);
    cout << ans << endl;
}

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

int dp1[502][2][10][500][3], dp2[502][2][10][500][3], m, len[2];
char S[2][550];

void solve(int dp[][2][10][500][3], int o) {
	dp[0][0][0][0][0] = 1;
	rep(i, len[o])rep(j, 2)rep(k, 10)rep(l, m)rep(d, 3) {
		if (dp[i][j][k][l][d] == 0)continue;
		int s, g, p = S[o][i] - '0';
		if (d == 1) { s = k + 1; g = (j ? 9 : p); }
		else if (d == 2) { s = 0; g = (j ? k - 1 : min(k - 1, p)); }
		else { s = 0; g = (j ? 9 : p); }
		for (int x = s; x <= g; x++) {
			if (x&&k == x)continue;
			int y;
			if (d == 1)y = 2;
			else if (d == 2)y = 1;
			else {
				if (k == 0)y = 0;
				else if (x < k)y = 1;
				else y = 2;
			}
			(dp[i + 1][j || x < p][x][(l * 10 + x) % m][y] += dp[i][j][k][l][d]) %= MOD;
		}
	}
}
int main() {
	scanf("%s%s%d", S[0], S[1], &m);
	rep(i, 2)len[i] = strlen(S[i]);
	int d = len[0] - 1;
	while (S[0][d] == '0') {
		S[0][d] = '9'; d--;
	}
	S[0][d]--;
	solve(dp1, 0); solve(dp2, 1);
	int sum1 = 0, sum2 = 0;
	rep(i, 2)rep(j, 10)rep(t, 3) {
		(sum1 += dp1[len[0]][i][j][0][t]) %= MOD;
		(sum2 += dp2[len[1]][i][j][0][t]) %= MOD;
	}
	printf("%d\n", (sum2 + MOD - sum1) % MOD);
}

Measured memory_bytes: 66960
n,m = map(int,input().split())
cnt = [[] for i in range(n+1)]

for i  in range(m):
    p,y = map(int,input().split())
    cnt[p].append((y,i))
buf = [None] * m
for p,l in enumerate(cnt):
    if not l:
        continue
    l.sort()
    for j,(y,i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p,j + 1)
print('\n'.join(buf))

"""
n, m = map(int, input().split())
cnt = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = map(int, input().split())
    cnt[p].append((y, i))
buf = [None] * m
for p, l in enumerate(cnt):
    if not l:
        continue
    l.sort()
    for j, (y, i) in enumerate(l):
        buf[i] = '{:06d}{:06d}'.format(p, j + 1)
print('\n'.join(buf))
"""

Measured memory_bytes: 38376
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
int n1,t;
int main()
{string c;
 int len,f=1;
 cin>>c;
 len=c.length();
 for(int i=0;i<len;i++)
  {if(c[i]!='A'&&c[i]!='C')
     if(isupper(c[i])) 
     f=0; 
  }
 int count=0; 
 for(int i=2;i<len-1;i++)
  if(c[i]=='C')
  count++;
  if(count!=1)
  f=0;
  if(c[0]!='A')
  f=0;
  if(f==1)cout<<"AC";
  else  cout<<"WA";
  return 0; 
   




} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ii pair<int, int>
#define iii tuple<int, int, int>
#define iiii tuple<int, int, int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define fi first
#define se second
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define uni(v) v.erase(unique(v.begin(), v.end()), v.end())
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (ll) a / __gcd(a, b) * b
#define rep(i, a, b) for (auto i = a; i != b; i += 1 - 2 * (a > b))

using namespace std;

void solve() {
    string n;
    int k;
    cin >> n >> k;
    vector<vector<vector<ll>>> dp(n.size() + 1,
                                  vector<vector<ll>>(k + 1, vector<ll>(2)));
    dp[0][0][true] = 1;
    for (int i = 0; i < n.size(); ++i) {
        for (int j = 0; j < k; ++j) {
            for (auto low : {false, true}) {
                for (int x = (k == 0); x <= (low ? n[i] - '0' : 9); ++x)
                    dp[i + 1][j + (x > 0)][low && x == n[i] - '0'] +=
                        dp[i][j][low];
            }
        }
        dp[i + 1][k][false] += dp[i][k][false];
        dp[i + 1][k][true] += dp[i][k][true];
    }
    cout << dp[n.size()][k][false] + dp[n.size()][k][true] << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // freopen("in", "r", stdin);

    int t = 1;
    // cin >> t;

    while (t--) solve();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define put(n) cout<<(n)<<endl
#define FOR(i,num,N) for(int(i)=(num);(i)<(N);++(i))
#define RFOR(i,num,N) for(int (i)=(num);(i)>(N);--(i))
#define all(v) (v).begin() , (v).end()
#define rall(v) (v).rbegin() , (v).rend()

int main(){
    int W,H,C,MIN =1e9;
    cin>>W>>H>>C;
   
    for(int i=1;i<=min(W,H);++i){
        if((W*H)%(i*i)==0 && W%i == 0 && H%i == 0){
            MIN = min((W*H)/(i*i),MIN);
        }
    }
    cout<<MIN*C<<endl;
}


Measured memory_bytes: 3072
package main

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

type TimeRecord struct {
	discoverTime int
	finishTime   int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	timeRecordMap := make([]TimeRecord, n)
	childrenMap := make([][]int, n)
	for i := 1; i <= n; i++ {
		node, err := nextInt(sc)
		if err != nil {
			panic(err)
		}
		timeRecordMap[node-1] = TimeRecord{-1, -1}

		childNum, err := nextInt(sc)
		if err != nil {
			panic(err)
		}
		childrenMap[node-1] = make([]int, childNum)
		for j := 0; j < childNum; j++ {
			child, err := nextInt(sc)
			if err != nil {
				panic(err)
			}
			childrenMap[node-1][j] = child
		}
	}

	timer := 1
	startNode := 1
	for {
		visit(startNode, &timer, childrenMap, timeRecordMap)
		startNode = findStartNode(childrenMap, timeRecordMap)
		if startNode < 0 {
			break
		}
	}
	for k, v := range timeRecordMap {
		fmt.Printf("%d %d %d\n", k+1, v.discoverTime, v.finishTime)
	}
}

func findStartNode(childrenMap [][]int, timeRecordMap []TimeRecord) int {
	x := -1
	for node, timeRecord := range timeRecordMap {
		if timeRecord.discoverTime < 0 {
			x = node + 1
			break
		}
	}
	return x
}

func visit(currentNode int, timer *int, childrenMap [][]int, timeRecordMap []TimeRecord) {
	if timeRecordMap[currentNode-1].discoverTime > 0 {
		return
	}
	children := childrenMap[currentNode-1]
	timeRecordMap[currentNode-1] = TimeRecord{*timer, timeRecordMap[currentNode-1].finishTime}
	(*timer)++
	for i := 0; i < len(children); i++ {
		visit(children[i], timer, childrenMap, timeRecordMap)
	}
	timeRecordMap[currentNode-1] = TimeRecord{timeRecordMap[currentNode-1].discoverTime, *timer}
	(*timer)++
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}



Measured memory_bytes: 1140
import math

N = int(input())
k = int(math.sqrt(N * 2)) + 1
if k * (k-1) == N*2:
    print("Yes")
    print(str(k))
    print_list = []
    used = 0
    for i in range(k):
        if i == 0:
            single_list = [str(k-1)] + [str(a+1) for a in range(k-1)]
            print(" ".join(single_list))
            print_list.append(single_list)
            used = k-1
        else:
            single_list = [str(k-1)] + [a[i] for j, a in enumerate(print_list)] + [str(a + used + 1) for a in range(k-1-i)]
            print(" ".join(single_list))
            print_list.append(single_list)
            used += k-1-i
else:
    print("No")

Measured memory_bytes: 11380
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int arr[n];
	for(int i=0; i<n; i++)
		cin>>arr[i];
	int dp[n];
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
	for(int i=2; i<n; i++)
	{
		dp[i]=INT_MAX;
		for(int j=1; j<=k; j++)
		{
			if(i-j>-1)
				dp[i] = min(dp[i],dp[i-j]+abs(arr[i]-arr[i-j]));
			else 
				break;
		}
	}
	cout<<dp[n-1];
}

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

int main(){
    int D, G; cin >> D >> G;
    vector<int> n;
    vector<int> b;
    for(int i=0; i<D; i++){
        int p, c; cin >> p >> c;
        n.push_back(p);
        b.push_back(c);
    }

    int ans = INT_MAX;
    for(int mask = 0; mask < (1<<D); mask++){
        int points=0, num=0, rest_max=-1;
        for(int i = 0; i < D; i++){
            if(mask>>i & 1){
                points += (i+1) * 100 * n[i] + b[i];
                num += n[i];
            } else {
                rest_max = i;
            }
        }
        if(points<G){
            int s1 = 100*(rest_max+1);
            int need_num = (G - points + s1 -1 )/s1;
            if( need_num < n[rest_max]) num += need_num;
            else continue;        
        }
        ans = min(ans, num);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20);
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define MOD 1000000007

long ans = 0;

void search(long &n,long &m,vl &a,vl &sum,long &maxi,long &mini,long &mid){
  mid = (maxi + mini) / 2;
  long tmp = 0;
  long add = 0;
  rep(i,n){
    long par = mid - a.at(i);
    long id = lower_bound(a.begin(),a.end(),par) - a.begin();
    //cout << par << " " << id << endl;
    long addnum = n - id;
    add += addnum;
    tmp += sum.at(id) + a.at(i) * addnum;
  }
  //if(mid == 111) cout << add << endl;
  if(add > m){
    mini = mid;
  }else{
    ans = max(tmp,ans);
    maxi = mid;
  }
}

int main(){
  long n,m;
  cin >> n >> m;
  vector<long> a(n);
  long A = 0;
  long B = 100000;
  rep(i,n){
    cin >> a.at(i);
    A = max(A,a.at(i));
    B = min(B,a.at(i));
  }
  sort(a.begin(),a.end());
  vector<long> sum(n+1,0);
  for(int i=n-1;i>=0;i--){
    sum.at(i) = sum.at(i+1) + a.at(i);
  }
  long maxi = A*2;
  long mini = B*2;
  long mid = (A + B)/2;
  while(maxi - mini > 1){
    //cout << maxi << " " << mini << endl;
    search(n,m,a,sum,maxi,mini,mid);
  }
  
  long tmp = 0;
  long add = 0;
  long rec;
  long near = 2000000;
  rep(i,n){
    long par = maxi - a.at(i);
    long id = lower_bound(a.begin(),a.end(),par) - a.begin();
    if(id < n){
      if(a.at(i) + a.at(id) >= mini) near = min(near,a.at(i) + a.at(id));
    }
    long addnum = n - id;
    //cout << i << ":" << addnum << endl;
    add += addnum;
    tmp += sum.at(id) + a.at(i) * addnum;
  }
  if(add <= m){
    ans = max(ans,tmp);
  }else{
    tmp -= near * (add - m);
    ans = max(ans,tmp);
  }
  
  rec = add;
  tmp = 0;
  add = 0;
  near = 2000000;
  rep(i,n){
    long par = mini - a.at(i);
    long id = lower_bound(a.begin(),a.end(),par) - a.begin();
    if(id < n){
      if(a.at(i) + a.at(id) >= mini) near = min(near,a.at(i) + a.at(id));
    }
    long addnum = n - id;
    add += addnum;
    tmp += sum.at(id) + a.at(i) * addnum;
  }
  if(add <= m){
    ans = max(ans,tmp);
  }else{
    if(rec < m && add > m){
      tmp -= near * (add - m);
      //cout << near << " " << add << " " << tmp << endl;
      ans = max(ans,tmp);
    }
  }
  
  cout << ans << endl;
  
  //cout << mini << maxi << endl;
  //cout << near << endl;
}


Measured memory_bytes: 1792