akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
	int H; int W;
	while (~scanf("%d%d", &H, &W)) {
		const int A = 26;
		array<int, A> cnt = {};
		rep(i, H) {
			char buf[101];
			scanf("%s", buf);
			rep(j, W)
				++ cnt[buf[j] - 'a'];
		}
		int cnt4 = (H / 2) * (W / 2),
			cnt1 = (H % 2) * (W % 2),
			cnt2 = ((H + 1) / 2) * ((W + 1) / 2) - cnt4 - cnt1;
		rep(a, A) {
			int t = min(cnt4, cnt[a] / 4);
			cnt[a] -= 4 * t;
			cnt4 -= t;
		}
		rep(a, A) {
			int t = min(cnt2, cnt[a] / 2);
			cnt[a] -= 2 * t;
			cnt2 -= t;
		}
		bool ans = cnt4 == 0 && cnt2 == 0;
		puts(ans ? "Yes" : "No");
	}
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  int a=n/100;
  int b=n%100;
  if(a==0&&1<=b&&b<=12) cout << "YYMM" << endl;
  else if(b==0&&1<=a&&a<=12) cout << "MMYY" << endl;
  else if(a==0||b==0) cout << "NA" << endl;
  else if(a<=12){
    if(b<=12) cout << "AMBIGUOUS" << endl;
    else cout << "MMYY" << endl;
  }
  else{
    if(b<=12) cout << "YYMM" << endl;
    else cout << "NA" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
#define INF __INT32_MAX__
#define LINF __LONG_LONG_MAX__

int main() {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    int w, h, w2, h2;
    if (tx - sx <= 1) {
        w = 1;
    } else {
        w = tx - sx;
    }
    if (ty - sy <= 1) {
        h = 1;
    } else {
        h = ty - sy;
    }
    w2 = w + 2;
    h2 = h + 2;

    rep(i, h) {
        cout << 'U';
    }
    rep(i, w) {
        cout << 'R';
    }
    rep(i, h) {
        cout << 'D';
    }
    rep(i, w) {
        cout << 'L';
    }

    cout << 'L';
    rep(i, h2 - 1) {
        cout << 'U';
    }
    rep(i, w2 - 1) {
        cout << 'R';
    }
    cout << "DR";
    rep(i, h2 - 1) {
        cout << 'D';
    }
    rep(i, w2 - 1) {
        cout << 'L';
    }
    cout << 'U';

    cout << endl;
}

Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <numeric>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair <int,int> P;

int main(){
    int H,W;
    cin >> H >> W;
    int h,w;
    cin >> h >> w;
    cout << (H-h) * (W - w) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

#define max 100

int main()
{
    long int a, b, k;
    
    scanf("%ld %ld %ld", &a, &b, &k);
    
    if(a+b<=k){
        a=b=0;
    }else if(a<=k) {
        b=b-(k-a);
        a=0;
    }else{
        a=a-k;
    }
    
    printf("%ld %ld", a, b);
    
    return 0;
}


Measured memory_bytes: 128
/*
 * b.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  bool ok = (a < b && b < c);
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 1156
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))

ans = [1, 2, 3]
ans.remove(ini())
ans.remove(ini())
print(ans[0])

Measured memory_bytes: 9188
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
cost=[[float("inf")]*N for _ in range(N)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1][b-1]=c
    cost[b-1][a-1]=c

def dijkstra(S,N,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[S]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

dist=[]
for s in range(N):
    dist.append(dijkstra(s,N,cost))

checked=[[False]*N for _ in range(N)]
ans=M
for s in range(N):
    for i in range(s,N):
        for j in graph[i]:
            if checked[i][j]:
                continue
            
            if dist[s][i]+cost[i][j]==dist[s][j]:
                ans-=1
                checked[i][j]=True
                checked[j][i]=True
print(ans)

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

int main() {
  int N, L; cin >> N >> L;
  deque<int> a(N); for (int i = 0; i < N; i++) cin >> a[i];
  int ans {};
  for (int i = 1; i < N; i++) {
    if (a[i - 1] + a[i] >= L) {
      ans = i;
      break;
    }
  }
  if (!ans) {
    cout << "Impossible" << endl;
  } else {
    cout << "Possible" << endl;
    for (int i = 1; i < ans; i++) cout << i << endl;
    for (int i = N - 1; i > ans; i--) cout << i << endl;
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int mod = 1000000007;

P front_tail(int a);

int main() {

    int N; cin >> N;

    map<P, int> freq;
    for (int i = 1; i <= N; i++)
        freq[front_tail(i)]++;

    ll ans = 0;
    for (auto& x:freq) {

        P key = x.first;
        int value = x.second;
        P rev(key.second, key.first);
        ll value_rev = freq[rev];
        ans += value * value_rev;
    }

    cout << ans << '\n';

}

P front_tail(int a) {

    string s = to_string(a);
    P p(int(s.front()), int(s.back()));
    return p;

}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  string s;
  int h,w;cin>>h>>w;
  for(int i=1;i<=h;i++){
    for(char c='A';c<'A'+w;c++){
      cin>>s;
      if(s=="snuke")cout<<c<<i<<endl;
    }
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[310][310][310],n;
char s[310];
int dfs(int l,int r,int k){
	if(k<0)return -1000000007;
	if(l>r)return 0;
	else if(l==r)return 1;
	if(~dp[l][r][k])return dp[l][r][k];
	dp[l][r][k]=max(dfs(l+1,r,k),dfs(l,r-1,k));
	dp[l][r][k]=max(dp[l][r][k],dfs(l+1,r-1,k-(s[l]!=s[r]))+2);
//	printf("{%d,%d,%d,%d}",l,r,k,dp[l][r][k]);
	return dp[l][r][k];
}
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%s%d",s+1,&n);
	printf("%d\n",dfs(1,strlen(s+1),n));
}

Measured memory_bytes: 116608
#include "iostream"
#include "cmath"

using namespace std;

int main()
{
	int x,a=1,b=1,max=1;
	cin >> x;
	for (a = 2;a<=sqrt(x); a++) {
		for (b = 2;pow(a,b)<=x; b++) {
			if (pow(a, b) > max)max = pow(a, b);
		}
	}
	cout << max << endl;
	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
int n,a,b;
cin>>n>>a>>b;
int a1=n*a;
if(a1<=b)
cout<<a1;
else
cout<<b;
return 0;  
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

void mod( ll &n, ll m=MOD ){ n%=m,n+=m,n%=m; }

const int MAXN = 55;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int a[MAXN];
ll dp[2*MAXN][MAXN][MAXN];

ll solve( int moves, int left, int right )
{
    if( moves < 0 )
        return -1e16;
    if( moves == 0 || left > right )
        return 0;
    ll &ans = dp[moves][left][right];
    if( ans != -1 )
        return ans;
    ans = 0;
    max_self(ans,solve(moves-1,left,right)); // do nothing
    max_self(ans,solve(moves-2,left+1,right)); // take left put left
    max_self(ans,solve(moves-2,left,right-1)); // take right put right
    max_self(ans,a[left]+solve(moves-1,left+1,right));
    max_self(ans,a[right]+solve(moves-1,left,right-1));
    return ans;
}

int main() 
{
    fastio();

    memset(dp,-1,sizeof(dp));
    ll n,k;
    cin>>n>>k;
    loop(i,0,n) cin>>a[i];

    cout<<solve(k,0,n-1);

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

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

int n,w,sol=0;
int weight[101];
int value[101];
ll dp[101][100005];

int main() {
    cin >> n >> w;
    for (int i=1;i<=n;i++) {
        cin >> weight[i];
        cin >> value[i];
    }

    for (int i=1;i<=n;i++) {
        for (int j=1;j<=w;j++) {
            dp[i][j]=dp[i-1][j];
            if(j>=weight[i]) {
                dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i]);
            }
        }
    }
        cout << dp[n][w] << endl;
}




Measured memory_bytes: 81660
using System;
using System.Collections.Generic;
using System.Linq;
class Scanner //標準入力
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int Int() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Long() + add;
        }
        return Array;
    }
}
class Program {
    static Scanner cin = new Scanner();
    static void Main(string[] args) {
        int N = cin.Int();
        int M = cin.Int();

        var dic = new Dictionary<int, int>();
        int i = 2;
        int MM = M;
        while(i * i <= M) {
            if(MM % i == 0) {
                if (dic.ContainsKey(i)) dic[i]++;
                else dic[i] = 1;
                MM /= i;
            }
            else i++;
        }
        if (MM > 1) dic[MM] = 1;

        long ans = 1;
        foreach (var val in dic.Values) {
            ans = ans % 1000000007 * mod_combination(val + N - 1, val);
        }
        Console.WriteLine(ans % 1000000007);
        Console.ReadLine();
    }
    static int mod_combination(int n, int r) {
        int mod = 1000000007;
        long res = 1;
        long den = 1;
        for (int i = 1; i <= n; i++) {
            res = (res * i) % mod;
            if (i == n - r || i == r) {
                den = (den * res) % mod;
                if (n - r == r) den = (den * res) % mod;
            }
        }
        long rev = mod_power((int)den, mod - 2);
        return (int)((res * rev) % mod);
    }
    static int mod_power(int n, int m) {
        const int mod = 1000000007;
        long pow = n;
        long res = 1;
        while (m > 0) {
            if ((m & 1) == 1) res = (res * pow) % mod;
            pow = (pow * pow) % mod;
            m >>= 1;
        }
        return (int)res;
    }

}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI (acos(-1))
#define ct cout<<
#define cn cin>>
#define spc <<" "<<
#define nl puts("")
#define _fl(x) puts("FLAG " #x);
#define  _(x)  cout<< #x <<" is "<< x <<endl;
#define fs first
#define sc second
#define pb push_back
#define all(v)  (v).begin(), (v).end()
#define _109 (1000000000)
#define _0(arr) memset(arr,0,sizeof ( arr ) )
#define _1(arr) memset(arr,-1,sizeof ( arr ) )
#define _ninp(n,arr) for(int i=0; i<n;i++)cin>>arr[i];
#define _nout(n,arr) for(int i=0; i<n;i++)cout<<arr[i]<<" \n"[i==n-1];
double _eps=1e-6;


int main() {

    int r;
    cn r;
    

    printf("%.10f", 2*PI*r);nl;

    return 0;
}


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

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(){
  ll n;
  cin >> n;
  map<ll,ll>mp;
  rep(i,n){
    ll a;
    cin >> a;
    mp[a]++;
  }

  ll ans = 0;
  vector<bool> list(1000005,true);
  for(auto it : mp){
    
    if(it.second==1&&list[it.first]){
      ans ++;
    }
    if(!list[it.first]){
      continue;
    }else{
      // cout << it.first << endl;
      for(ll i = 1; i*it.first <= 1000000; i++){
        list[i*it.first] = false;
      }
    }
  }

  cout << ans << endl;

  return 0;
} 



Measured memory_bytes: 16196
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
const double pi = acos(-1);
typedef pair<int, int> P;
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
#define OUTPUT(i) (cout << (ll)i << endl)
#define ALL(a) ((a).begin(), (a).end())

bool operator<(const pair<ll, ll> &a, const pair<ll, ll> &b)
{

    if (a.first == b.first)
        return a.second < b.second;

    return a.first < b.first;
}

ll a[5];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    //cout << fixed << setprecision(15);

    int N;
    cin >> N;

    REP(i, N)
    {
        string s;
        cin >> s;
        if (s[0] == 'M')
            a[0]++;
        if (s[0] == 'A')
            a[1]++;
        if (s[0] == 'R')
            a[2]++;
        if (s[0] == 'C')
            a[3]++;
        if (s[0] == 'H')
            a[4]++;
    }
    ll sum = 0;
    for (int i = 0; i < 5; ++i)
    {
        for (int j = i + 1; j < 5; ++j)
        {
            for (int k = j + 1; k < 5; ++k)
            {
                sum += a[i] * a[j] * a[k];
            }
        }
    }
    cout << sum << endl;
    return 0;
}


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

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

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

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

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

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

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

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

fn main() {
    input! {
        a: i64,
        b: i64,
    }

    let h = b - a;
    let mut j = 0;
    for i in 1..h + 1{
        j+=i;
    }

    println!("{}", j - b);
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
typedef pair<ll,string> Pls;
const ll INF=10000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	ll x,cost;
};
int main() {

	string s,t;
	int w;
	cin>>s;
	cin>>w;
	rep(i,s.size()){
		if(i%w==0)t+=s[i];
	}
	cout<<t<<endl;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int long long
#define moder (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % moder;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), moder - 2, moder) % moder * mod_pow(kai(y), moder - 2, moder) % moder;
}
/*--------Library Zone!--------*/

int n, a[300005], sum[300005];
int le[300005], ri[300005];
signed main() {
	cin >> n;
	rep(i, 3 * n) {
		if (i)sum[i] = sum[i - 1];
		cin >> a[i];
		sum[i] += a[i];
	}
	multiset<int>st, st2;
	rep(i, n)st.insert(a[i]);
	REP(i, n + 1) {
		st.insert(a[n - 1 + i]);
		le[n - 1 + i] = le[n - 2 + i];
		le[n - 1 + i] += *st.begin();
		st.erase(st.begin());
	}
	rep(i, n)st2.insert(a[2 * n + i]);
	REP(i, n + 1) {
		st2.insert(a[2 * n - i]);
		auto it = st2.end();
		it--;
		ri[2 * n - i - 1] = ri[2 * n - i];
		ri[2 * n - i - 1] += *it;
		st2.erase(it);
	}
	int ans = -inf;
	for (int i = n - 1; i < 2 * n; i++) {
		int left = sum[i] - le[i];
		int right = sum[3 * n - 1] - sum[i] - ri[i];
		ans = max(ans, left - right);
	}
	cout << ans << endl;
}


Measured memory_bytes: 17792
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,k,ok;

int a[100];

int dp[100][10][2];

int dfs(int bit,int pre,bool limit,bool zero)
{   
    if(bit == -1) return 1;
    if(!limit && dp[bit][pre][zero] != -1) return dp[bit][pre][zero];
    int ans = 0;
    int up = limit?a[bit]:9;
    if(zero)
    {
        for(int i = 0; i <= up; i++) 
        {
            ans += dfs(bit-1,i,limit&&(i==a[bit]),zero&&(i==0));
        }
    }
    else
    {
        for(int i = -1; i <= 1; i++)
        {
            if(pre+i >= 0 && pre+i <= up)
            {
                ans += dfs(bit-1,pre+i,limit&&(pre+i == a[bit]),0);
            }
        }
    }
    if(!limit) dp[bit][pre][zero] = ans;
    return ans;
}

int solve(int x)
{
    int bit = 0;
    while(x)
    {
        a[bit++] = x%10;
        x /= 10;
    }
    return dfs(bit-1,0,1,1)-1;
}

signed main()
{
#ifdef ONLINE_JUDGE
#else
    //freopen("data.in", "r", stdin);
#endif
    cin>>k;
    mem(dp,-1);
    int l = 1,r = 3234566667,ans = 0;
    while(l <= r)
    {   
        int mid = (l+r)/2;
        if(solve(mid) >= k)
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main() {
  int A;
  long long B;
  long long N;
  cin >> A >> B >> N;

  long long mx = 0;
  /*
  for (long long i = 0; i <= N; i++) {
    long long fl = A * i / B - i / B * A;
    if (mx < fl) mx = fl;
    cout << fl << endl;
  }
  */

  long long i = std::min(N, B-1);
  mx = A * i / B;

  cout << mx << endl;

  return 0;
}


Measured memory_bytes: 3636
import numpy as np

H, W = map(int, input().split())
C = []
for i in range(10):
    C.append(list(map(int, input().split())))
CT = np.array(C).T
W = [0] * 10
for i in range(H):
    for j in map(int, input().split()):
        if j != -1:
            W[j] += 1

D = [0] * 10
Open = list(CT[1])
Open[1] = -1
for j in range(9):
    p = min([l for l in enumerate(Open) if l[1] != -1], key=lambda x: x[1])
    D[p[0]] = p[1]
    Open[p[0]] = -1
    for i in range(10):
        Open[i] = min(Open[i], CT[p[0]][i] + p[1])
ans = 0
for i in range(10):
    ans += D[i] * W[i]
print(ans)


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


public class Main {

  public static void main(String[] args)  {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int D = sc.nextInt();
    int X = sc.nextInt();
    for(int i =1; i<=N; i++){
      int ai = sc.nextInt();
      for(int d = 1; d<=D; d+=ai){
         X++;
      }
    }
    System.out.println(X);
  }
}


Measured memory_bytes: 35992
#include <iostream>
#include <string>
#include <stdio.h>
#include <numeric>
#include <algorithm>
using namespace std;
int main(){
    string s,a;
    int m;
    while(true){
        cin>>s;
        if(s=="-"){
            return 0;
        }
        cin>>m;
        int h;
        for(int i=0;i<m;++i){
            cin>>h;
            a=s.substr(0,h);
            s.erase(0,h);
            s+=a;
        }
        cout<<s<<endl;
    }
}


Measured memory_bytes: 3196
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1005;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll a,b,c,k;cin>>a>>b>>c>>k;
    ll take = min(a,k);
    a-=take;
    k-=take;

    ll bla = min(b,k);
    b-=bla;
    k-=bla;

    ll lol = min(c,k);
    c-=lol;
    k-=lol;

    cout<<take - lol;
}


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

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<long> vll;
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvll;
typedef vector<string> vs;
typedef map<int, int> mi;
typedef map<long long, long long> mll;
typedef map<string, int> msi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define B begin()
#define E end()
// for (auto it = .B; it < .E; it++) {

int main() {
    ll n, m, a, b, ha, hb;
    cin >> n >> m;

    ll hv[n];
    int val[n] = {0};
    for (int i = 0; i < n; i++) {
        cin >> hv[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--;
        b--;
        ha = hv[a];
        hb = hv[b];
        if (ha == hb) {
            val[a] = 1;
            val[b] = 1;
        } else if (ha > hb) {
            val[b] = 1;
        } else {
            val[a] = 1;
        }
    }
    ll tot = 0;
    for (int v : val) {
        if (v == 0) {
            tot++;
        }
    }
    cout << tot << "\n";

    return 0;
}


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

int m=-1,N,c=0,arr[100000];
int main(){
  cin >> N;
  for (int i=0;i<N;i++){
    cin >> arr[i];
  }
  //Count the consecutive decreasing sequence
  for (int i=0;i<N-1;i++){
    if (arr[i+1]>arr[i]){
      if (c > m){
        m = c;
      }
      c = 0;
    }
    else{
      c += 1;
    }
  }
  if (c>m){
    m = c;
  }
  cout << m;
   
  return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        String S = sc.next();
        String tmp;
        if(S.length() > K) {
            tmp = S.substring(0,K);
            tmp = tmp + "...";
        } else {
            tmp = S;
        }
        System.out.println(tmp);
    }
}

Measured memory_bytes: 38740
#include<bits/stdc++.h>
using namespace std;
typedef long long L;
#define mx 346920
L n;
L mark[mx],prime[mx],idx;
void sieve(){
    mark[1]=1;
    prime[idx++]=2;
    L lim=sqrt(mx)+2;
    for(L i=3;i<=mx;i+=2){
        if(!mark[i]){
            prime[idx++]=i;
            mark[i]=1;
            if(i<=lim){
                for(L j=i*i;j<=mx;j+=i*2){
                    mark[j]=1;
                }
            }
        }
    }
}
int main()
{
    sieve();
    while(scanf("%lld",&n)&&n){
        L n2=n*2,l=0,r=0;
        l=upper_bound(prime, prime+idx,n)-prime;
        r=upper_bound(prime, prime+idx,n2)-prime;
        cout<<r-l<<"\n";
    }
    return 0;
}



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

using namespace std;
typedef long long ll;

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;

  vector<int> X(N);
  for(int i=0; i<N; i++)
    cin >> X[i];

  ll minv=1e18;
  sort(X.begin(), X.end(), greater<int>());
  for(int i=1; i<X[0]+1; i++)
    {
      ll tmp=0;
      for(int j=0; j<N; j++)
	{
	  tmp += (X[j]-i)*(X[j]-i);
	}
      if(tmp<minv)
	minv = tmp;
    }

  cout << minv << endl;


  return 0;
}


//cout << setprecision(13);
//next_permutation();
//__gcd();
//reverse();
//set ,tuple ,pair;
//bitset
//vector.find
//vector.count



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

#define bitGet(a, i) a & (1 << i)
#define bitOn(a, i) a != (1 << i)
#define bitOff(a, i) a &= ~(1 << i)
#define bitMake(a, i) a = (1 << N)
#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define ull unsigned long long
#define ll long long
#define ld long double
#define pri(a) cout << a << " "
#define pril(a) cout << a << " "
#define pb push_back
#define mp make_pair
#define vi vector<int> 
#define pi pair<int, int>
#define oo INT_MAX
#define maxN

using namespace std;

ll dp[2005], mod = 1000000007;

int main() {
    #ifndef ONLINE_JUDGE
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    #endif // !ONLINE_JUDGE

    int s;
    cin >> s;
    fto(j, 3, s) dp[j] = 1;

    fto(i, 3, s) fto(j, 3, s) if(i+j <= s) dp[i+j] = (dp[i+j] + dp[i]) % mod;

    cout << dp[s];
            
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpii = vector<pll>;

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

  list<char> SL;
  rep(i, S.size()){
    SL.push_back(S[i]);
  }
  ll dir = 1;
  
  ll Q;
  cin >> Q;

  ll T, F;
  char C;

  rep(i, Q){
    cin >> T;

    if(T == 1){
      dir *= -1;
    } else{
      cin >> F >> C;
      if((dir*F == 1) || (dir*F == -2)){
		SL.push_front(C);
      } else{
		SL.push_back(C);
      }
    }
  }

  if(dir == -1){
    reverse(SL.begin(), SL.end());
  }

  for(auto itr = SL.begin(); itr != SL.end(); itr++){
    cout << *itr;
  }

  cout << endl;
  
  return 0;
}

Measured memory_bytes: 9984
#include<bits/stdc++.h>
#define ALL(c) (c).begin(), (c).end()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6+6;


int main(){
	//freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);//cout.precision(12);cout<<fixed;
	
	int k,x;
	cin>>k>>x;
	
	int m = 1e6;
	for(int i=max(-m,x-k+1); i<=min(m,x+k-1); ++i) cout<<i<<' ';
	
	
	
	
	return 0;
}


Measured memory_bytes: 256
s = input()
cnt, cnt_ = 0, 0
a = "10" * (len(s)//2+1)
for i in range(len(s)):
    if s[i] != a[i]:
        cnt += 1
    if s[i] != a[i + 1]:
        cnt_ += 1
print(min(cnt, cnt_))

Measured memory_bytes: 3188
#include <bits/stdc++.h> 
using namespace std;
///////////////////////////////////////////
const long long int INF = INT32_MAX;
const long long int Mod = 1000000007;
const long long int mod = 100000;//10^5
using ll = long long int; //long long int は64bit
using ci = const int; using vi = vector<int>; using Vi = vector<long long int>; using pii = pair<int,int>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
#define np nullptr
template<class T>bool chmax(T &former, const T &b) { if (former<=b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define fill(x,num) memset(x,num,sizeof(x));
typedef vector<vector<ll> > matrix;
//       cin.tie(0);ios::sync_with_stdio(false);
void cinit(){cin.tie(0);ios::sync_with_stdio(false);}
//////////////////////////^^ *Emile ^^^//////////////////////////////////////////////////////

ll a,b,c;
ll d;

int main(){
	vi v;
	ll a;
	rep(i,4){
		cin>>a;
		v.pb(a);
	}
	sort(all(v));
	if(v[0]==1&&v[1]==4&&v[2]==7&&v[3]==9){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define DUMP(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<": "<<(x)<<" (L"<<__LINE__<<")"<<endl
using namespace std;
using vint = vector<int>;
using vdouble = vector<double>;
using vstring = vector<string>;
using ll = long long;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int main() {
    int n; cin >> n;
    vstring S(n);
    rep(i, n) cin >> S[i];
    int cnt[30], cnt2[30];
    fill(all(cnt), 100);
    rep(i, n) {
        fill(all(cnt2), 0);
        for(char c: S[i]) cnt2[c - 'a']++;
        rep(j, 30) chmin(cnt[j], cnt2[j]);
    }
    rep(i, ('z'-'a')+1) {
        rep(j, cnt[i]) cout << (char)('a' + i);
    }
    cout << endl;
    return 0;
}


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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())
#define pqasc priority_queue<long long, vector<long long>, greater<long long>>

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ul = unsigned long;

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

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { return a * b / GCD(a, b); }

const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

class UnionFind{
private:
  vector<int> Parent; 
public:  
  UnionFind(int N){
    Parent = vector<int>(N, -1);
  }
  
  int root(int A){
    if(Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }
  
  int size(int A){
    return -Parent[root(A)]; 
  }
  
  bool connect(int A, int B){
    A = root(A);
    B = root(B);
    if(A == B){
      return false;
    }
    
    if(size(A) < size(B)) swap(A, B);
    
    Parent[A] += Parent[B];
    Parent[B] = A;
    
    return true;
  }
  
  bool isSame(int A, int B){
    return root(A) == root(B);
  }
};

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int n,k,l; cin>>n>>k>>l;
  
  UnionFind uf1(n), uf2(n);
  rep(i,k){
    int a,b; cin>>a>>b; a--,b--;
    uf1.connect(a,b);
  }
  rep(i,l){
    int a,b; cin>>a>>b; a--,b--;
    uf2.connect(a,b);
  }
  
  map<pii, int> m;
  rep(i,n){
    pii p(uf1.root(i), uf2.root(i)); // 都市iの道路と線路のroot
    m[p]++;
  }
  rep(i,n){
    pii p(uf1.root(i), uf2.root(i));
    cout<<m[p];
    if(i==n-1) cout<<endl;
    else cout<<" ";
  }
}


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

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& e : a) cin >> e;
  vector<int> b(a);
  sort(b.begin(), b.end());
  int d = 0, ans = -1;
  for (int i = 0; i < n; i++) {
    if (a[i] != b[i]) d++;
  }
  if (d == 0) ans = 0;
  int q;
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int x, y;
    cin >> x >> y;
    if (ans != -1) continue;
    x--;
    y--;
    if (a[x] == b[x] && a[y] != b[x]) d++;
    if (a[x] != b[x] && a[y] == b[x]) d--;
    if (a[y] == b[y] && a[x] != b[y]) d++;
    if (a[y] != b[y] && a[x] == b[y]) d--;
    if (d == 0) ans = i;
    swap(a[x], a[y]);
  }
  cout << ans << "\n";
}


Measured memory_bytes: 5260
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
//constexpr ll MOD = 998244353;
//constexpr ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

int main()
{
  ll H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (ll i = 0; i < H; i++)
  {
    cin >> S.at(i);
  }

  vector<vector<ll>> dp(H, vector<ll>(W, INF));
  dp.at(0).at(0) = (S.at(0).at(0) == '#');

  for (ll d = 1; d < H + W - 1; d++)
  {
    for (ll i = 0; i < H; i++)
    {
      ll j = d - i;
      if (!(0 <= j && j < W))
        continue;
      
      if (i != 0)
      {
        bool b = (S.at(i - 1).at(j) == '.' && S.at(i).at(j) == '#');
        chmin(dp.at(i).at(j), dp.at(i - 1).at(j) + b);
      }
      if (j != 0)
      {
        bool b = (S.at(i).at(j - 1) == '.' && S.at(i).at(j) == '#');
        chmin(dp.at(i).at(j), dp.at(i).at(j - 1) + b);
      }
    }
  }

  ///*
  for (ll i = 0; i < H; i++)
  {
    for (ll j = 0; j < W; j++)
    {
      cerr << dp.at(i).at(j) << " ";
    }
    cerr << endl;
  }
  //*/

  ll ans = dp.at(H - 1).at(W - 1);
  cout << ans << endl;
}

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

void countDivisors(int a , int b , int x)
{
    int C = 0 ;
    vector <int> v ;
    for(int i = 1 ; i <= sqrt(x) ; i++)
    {
        if(x%i == 0)
        {
            if(x/i == i) v.push_back(i) ;
            else
            {
                v.push_back(i) ;
                v.push_back(x/i) ;
            }
        }
    }
    sort(v.begin() , v.end()) ;
    for(int i = 0 ; i < v.size() ; i++)
    {
        if(v[i] > b) break ;
        else if(v[i] >= a) C++ ;
    }
    cout << C << endl ;
}

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


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

int main(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];

    //
    sort(a , a + 3);

    int cnt = 0;
    if((a[1]-a[0])%2==0){
        cnt = (a[1]-a[0])/2;
    }else{
        cnt = (a[1]-a[0])/2 + 1;
        a[2] = a[2] + 1;
    }

    cnt += (a[2] - a[1]);

    cout << cnt << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * Main
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String S = sc.next();
        String T = sc.next();
        int L;

        L = S.length();

        if(T.substring(0,L).equals(S)){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 26960
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int a = Integer.parseInt(s.next());
		int b = Integer.parseInt(s.next());

		if(a < b){
			System.out.println("a < b");
		} else if(a > b){
			System.out.println("a > b");
		} else {
			System.out.println("a == b");
		}
	}

}

Measured memory_bytes: 25996
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
int main(){
    stack<int> densha;
    for(int a; cin >> a; ){
        if(a == 0){
            cout << densha.top() << endl;
            densha.pop();
        }else
          densha.push(a);
    }
    return 0;
}

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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n + 1);
  int last_zero = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] == 0) last_zero = i;
    if (i > k) {
      if (a[i] > a[i - k] && last_zero <= i - k) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 4048
#include<iostream>
#define N 1000000007
using namespace std;
typedef long long ll;

int mod_pow(int m,int n){
  ll a=1,x=m;
  for(int i=0;i<30;i++){
    if(n&(1LL<<i))a=a*x%N;
    x=x*x%N;
  }
  return a;
}

int main(){
  int m,n;
  cin>>m>>n;
  cout<<mod_pow(m,n)<<endl;
  return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>

using namespace std;

int main(){
  string s;
  cin>>s;
  for (char x:s){
    if (x=='1') cout<<'9';
    else cout<<'1';
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(v) (v).size()
#define debug(x) cerr << #x << "_=_" << x << "\n";
#define sum(n) ((n)*((n)+1)>>1)
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<pair<int, int>, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;

const int MAXN = 3e3+5;
int dp[MAXN][MAXN];
string s, t;


int lcs(int i, int j){
    if(i<0 || j<0) return 0;
    if(~dp[i][j]) return dp[i][j];
    int ans = max({lcs(i-1, j), lcs(i, j-1), lcs(i-1, j-1) + (int)(s[i]==t[j])});
    return dp[i][j] = ans;
}

string ans="";
void build(int i, int j){
    if(i<0 || j<0) return ;
    if(dp[i][j] == lcs(i-1, j-1) + (int)(s[i]==t[j])){
        build(i-1, j-1);
        if(s[i]==t[j])
            ans += s[i];
    }else if(dp[i][j] == lcs(i, j-1)){
        build(i, j-1);
    }else{
        build(i-1, j);
    }
}


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


    cin >> s >> t;
    memset(dp, -1, sizeof dp);
    lcs(sz(s)-1, sz(t)-1);
    build(sz(s)-1, sz(t)-1);
    cout << ans << "\n";




    return 0;
}

/*
1
9 3
111100000
 */

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

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

const int N = 1001000;

bool p[N],q;
int n,a[N],g,e[N];
set <int> s;

void seive()
{
    memset(p,1,sizeof p);

    p[0] = p[1] = 0;

    for(ll i=2;i<N;i++)
        if( p[i] )
        {
            int cnt = 0;
            for(ll j=i;j<N;j+=i)
            {
                p[j] = 0;
                cnt += e[j];
            }

            if( cnt >= 2 )
                q = 1;
        }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        e[a[i]]++;
    }

    g = a[1];
    for(int i=1;i<=n;i++)
        g = __gcd(g,a[i]);

    if( g != 1 )
    {
        printf("not coprime\n");
        return 0;
    }

    seive();

    if( q )
        printf("setwise coprime\n");
    else
        printf("pairwise coprime\n");
}


Measured memory_bytes: 12308
# include <bits/stdc++.h>
# define rr register
const int N=100010,INF=0x3f3f3f3f;
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int main(void){
	int n,m;
	n=read(),m=read();
	printf("%d",n*(n-1)/2+m*(m-1)/2);
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;

#define pb push_back
#define ff first
#define ss second
#define SIZE 20
#define INF int(2e9 + 9)
#define BIG_INF ll(1e18 + 9)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sqr(x) (x) * (x)
#define cube(x) (x) * (x) * (x)

//#pragma GCC optimize("Ofast")


int n, m, x, c[SIZE];

vector<vector<int> > price;


int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);


    cin >> n >> m >> x;

    for(int i = 0; i < n; i++)
    {
        cin >> c[i];
        price.pb(vector<int>(m, 0));
        for(int j = 0; j < m; j++)
        {
            cin >> price[i][j];
        }
    }

    int ans = INF;

    for(int i = 0; i < (1LL << n); ++i)
    {
        int curPrice = 0;
        vector<int> curSum(m, 0);
        for(int b = 0; b < n; b++)
        {
            if(i & (1LL << b))
            {
                curPrice += c[b];
                for(int lst = 0; lst < m; lst++)
                {
                    curSum[lst] += price[b][lst];
                }
            }
        }
        bool ok = 1;
        for(int p: curSum)
            if(p < x)
                ok = 0;

        if(!ok) continue;

        ans = min(ans, curPrice);

    }
    if(ans == INF)
        cout << "-1";
    else
        cout << ans;

    return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);

#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector< vector<long long>>
#define mi map<int,int>
#define pi pair<int,int>

#define Fori(i,a,b) for(int i=a; i<b; i++)
#define Ford(i, a, b) for(int i=a; i>=b; i--)

#define pb push_back
#define mp make_pair

#define read(a, n) for(int i=0; i<n; i++) cin >> a[i];
#define print(x) cout << "X: == " << x << endl;
#define printMap(a) for(auto it=a.begin() ; it!= a.end() ; it++) {cout << it->first << "  " << it->second << endl; }
#define printVector(a) for(auto it = a.begin() ; it!= a.end() ;it++) {cout << *it << endl;}

#define MOD 1000000007
using namespace std;
int main() {
    IOS
    string s;
    int cnt = 0, ans = 0;
    getline(cin >> ws, s);
    Fori(i, 0, s.size()) {
        if(s[i] == 'R'){
            cnt++;
        } else {
            ans = max(ans,  cnt);
            cnt = 0;
        }
    }
    ans = max(ans, cnt);
    cout << ans << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define int long long

struct Stop {
    int s;
    int t;
    int x;
    Stop(int s, int t, int x): s(s), t(t), x(x) {}
};

signed main(){
    int n, q;
    cin >> n >> q;
    vector<Stop> stop;
    rep(i, n) {
        int s, t, x;
        cin >> s >> t >> x;
        s -= x;
        t -= x;
        stop.emplace_back(s, t, x);
    }
    auto comp1 = [](Stop a, Stop b) {
        return a.s < b.s;
    };
    sort(whole(stop), comp1);
    auto comp2 = [](Stop a, Stop b) {
        return a.x > b.x;
    };
    priority_queue<Stop, vector<Stop>, decltype(comp2)> que{comp2};
    int id = 0;
    
    rep(i, q) {
        int d;
        cin >> d;
        while (id<n && stop[id].s<=d) {
            if (stop[id].t<=d) {
                id++;
            }
            else {
                que.push(stop[id]);
                id++;
            }
        }
        int ans = -1;
        while (!que.empty()) {
            auto now = que.top();
            que.pop();
            if (now.s<=d && now.t>d) {
                ans = now.x;
                que.push(now);
                break;
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}


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

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

  int m = n;
  double ret = 0;
  for (double p = 1; ; k = (k + 1) >> 1, p *= 0.5) {
    if (m < k)
      continue;
    ret += p * (m - k + 1) / n;
    m = k - 1;
    if (k == 1)
      break;
  }
  printf("%.12f\n", ret);

  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

int main(void)
{
	int S;

	int h, m, s;

	h = 3600;
	m = 60;
	s = 1;

	scanf("%d", &S);

	printf("%d:", S/h);

	S = S % h;

	printf("%d:", S/m);

	S = S % m;

	printf("%d\n", S / s);

	return 0;
}


Measured memory_bytes: 2768