akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int solve(int a, int b)
{
    if (a == 0)
        return 0;
    if (a == b)
        return a;
    if (a > b)
        return solve(b, a);
    if (a == 1)
        return 2 * (b - 1) + 1;
    if (b % a == 0)
        return a * solve(1, b / a);
    return 2 * (b / a) * a + solve(a, b % a);
}

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

    int n, x;
    cin >> n >> x;
    cout << n + solve(n - x, x) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{

	long w, h, x, y, r;

	scanf("%ld %ld %ld %ld %ld", &w, &h, &x, &y, &r);

	if ((x - r) < 0 || (y - r) < 0 || (x + r) > w || (y + r) > h) {
		printf("No\n");
	}
	else {
		printf("Yes\n");
	}

	return 0;
}

Measured memory_bytes: 584
#include <stdio.h>

int main(void){
    int n;
    scanf("%d",&n);
    for(int unko=0;unko<n;unko++){
        
        
        int h,w;
        scanf("%d %d",&h,&w);
        char po[100][100];
        for(int i=0;i<h;i++)scanf("%s",po[i]);
        while(1){
            int hdrue[26][2];
            for(int i=0;i<26;i++){hdrue[i][0]=-1;hdrue[i][1]=-1;}
            int mgst[26][2];
            for(int i=0;i<26;i++){mgst[i][0]=-1;mgst[i][1]=-1;}
            for(int i=0;i<h;i++)for(int j=0;j<w;j++){
                if(po[i][j]!='.'&&po[i][j]!='#'){
                    int nari=po[i][j]%26;
                    if(hdrue[nari][0]==-1){
                        hdrue[nari][0]=i;
                        hdrue[nari][1]=j;
                        mgst[nari][0]=i;
                        mgst[nari][1]=j;
                    }
                    if(hdrue[nari][0]>i)hdrue[nari][0]=i;
                    if(hdrue[nari][1]>j)hdrue[nari][1]=j;
                    if(mgst[nari][0]<i)mgst[nari][0]=i;
                    if(mgst[nari][1]<j)mgst[nari][1]=j;
                }
            }
            int flag=1;
            for(int i=0;i<26;i++)if(hdrue[i][0]!=-1)flag=0;
            if(flag==1){printf("SAFE\n");break;}
            flag=0;
            for(int i=0;i<26;i++){if(hdrue[i][0]!=-1){
                int flag3=1;
                for(int k=0;k<h;k++)for(int l=0;l<w;l++){
                    if(hdrue[i][0]<=k&&mgst[i][0]>=k&&hdrue[i][1]<=l&&mgst[i][1]>=l){if(!(po[k][l]!='.'&&(po[k][l]%26==i||po[k][l]=='#'))){flag3=0;}}
                    else if(po[k][l]!='.'&&po[k][l]!='#'&&po[k][l]%26==i){flag3=0;}
                }
                if(flag3==1){
                    flag=1;
                    for(int k=hdrue[i][0];k<=mgst[i][0];k++)for(int l=hdrue[i][1];l<=mgst[i][1];l++)po[k][l]='#';
                }
            }}
            if(flag==0){printf("SUSPICIOUS\n");/*for(int i=0;i<h;i++)printf("%s\n",po[i]);*/break;}
        }
    }
    
    return 0;
}



Measured memory_bytes: 2104
#include<bits/stdc++.h>
#include <queue>
#include <cstring>
#define mp make_pair
#define pb push_back
#define p push

#define FOR(a,c) for(int a = 0;a<c;a++)
#define ll long long int

#define getI(a) scanf("%d",&a)
#define getII(a,b) scanf("%d%d",&a,&b)
#define getIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a,b) scanf("%lld%lld",&a,&b)
#define getLLl(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define BEND(c) (c).begin(),(c).end()
#define BEND2(c) (c).rbegin(),(c).rend()
#define fi first
#define se second
#define pi 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfi(a) printf("%d",a);
#define pfii(a,b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a,b) printf("%lld%lld",a,b);
#define pfd(a) printf("%lf",a);
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);

#define sag (sol|1)
#define sol (root<<1)
#define ort (bas+son)/2
#define SIZE 1000000007
#define MAXN 100005
using namespace std;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<vi> graph ;




int main(){

    ll n, l;
    cin >> n>> l;

    if ( l < 0  && l+n-1 <= 0){
        ll sum = 0;
        for (int i = 0; i <n-1 ; ++i) {
            sum+=l +i;
        }
        cout << sum ;
        return 0;
    }else if(l < 0 && l +n-1 > 0){
        ll sum = 0;
        for (int i = 0; i <n ; ++i) {
            sum+=l+i;
        }
        cout << sum;
        return 0;
    }else if ( l >= 0 && l +n-1 >= 0){
        ll sum = 0;
        for (int i = 1; i <n ; ++i) {
            sum+= l+i;
        }
        cout << sum;
        return 0;
    }
    while (1){}

    return 0;
}

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

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

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

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

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

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

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

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

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

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

fn main() {
    input! {
        n: usize,
        q:usize,
        s: String,
        mut lr: [(usize, usize);q],
    }
    let sb = s.as_bytes();
    let l = s.len();
    let mut table = vec![0; l + 1];
    for i in 2..l + 1 {
        if sb[i - 2] as char == 'A' && sb[i - 1] as char == 'C' {
            table[i] = table[i - 1] + 1;
        } else {
            table[i] = table[i - 1];
        }
    }
    for (l, r) in lr {
        println!("{}", table[r] - table[l]);
    }
}


Measured memory_bytes: 6908
n=int(input())
a=[int(i) for i in input().split()]

dp=[0]*(n+2)
for i in a:
    if i>n:
        dp[-1]+=1
    else:
        dp[i]+=1

ans=dp[-1]
for i in range(1,n+1):
    if dp[i]>=i:
        ans+=dp[i]-i
    else:
        ans+=dp[i]
print(ans)


Measured memory_bytes: 20700
#include <algorithm>
#include <iostream>
#include <queue>
#include <stdio.h>
#include <string>

using namespace std;

long long f(long long A, long long B) {
  long long ans;
  if (A % 2 == 0) {
    if (B % 2 == 0) {
      ans = ((B - A) / 2) % 2;
    } else {
      ans = ((B - A + 1) / 2) % 2;
    }
  } else {
    if (B % 2 == 0) {
      ans = ((B - A - 1) / 2) % 2;
    } else {
      ans = ((B - A) / 2) % 2;
    }
  }
  return ans;
}

void solve(long long A, long long B) {
  long long ans;
  if (A == B) {
    ans = A;
  } else if (A % 2 == 0 && B % 2 == 0) {
    ans = f(A, B) ^ B;
  } else if (A % 2 == 0 && B % 2 == 1) {
    ans = f(A, B);
  } else if (A % 2 == 1 && B % 2 == 0) {
    ans = (A ^ f(A, B)) ^ B;
  } else {
    ans = A ^ f(A, B);
  }
  printf("%lld\n", ans);
}

int main() {
  long long A, B;
  cin >> A >> B;
  solve(A, B);
  return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<math.h>
#include<unordered_map>

using namespace std;
using ll = long long;
using vec = vector<int>;
using mat = vector<vec>;
using lst = list<int>;

const int MOD = 1000000007;

int main()
{
	int N, M;
	cin >> N >> M;
	vec F(N+1);
	F[0] = F[1] = 1;
	for (int i = 2; i < N+1; ++i)
	{
		F[i] = (F[i - 2] + F[i - 1]) % MOD;
	}

    ll ans = 1;
	int pre = 0;
	for (int i = 0; i < M; ++i)
	{
		int a; cin >> a;
		if (pre == a)
		{
			cout << 0 << endl; return 0;
		}
		ans = (ans * F[a - 1 - pre]) % MOD;
		pre = a + 1;
	}

	
	ans = (ans * F[N - pre]) % MOD;


	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdio>
using namespace std;


int n, m, y;

main(){
	int i,j;
	cin >> n;
	while(n--){
		double st;
		string s;
		cin >> st >> y >> m;
		int ans = 0;
		for(i=0;i<m;i++){
			int type, cost;
			double rate;
			cin >> type >> rate >> cost;
			int money = st;
			if(type){
				for(j=0;j<y;j++){
					money *= 1 + rate;
					money -= cost;
				}
			}else{
				int risi=0;
				for(j=0;j<y;j++){
					risi += money * rate;
					money -= cost;
				}
				money += risi;
			}
			ans = max(ans, money);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1232
// #include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <string>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <ctime>
#include <cassert>
#include <fstream>
#include <stack>
#include <random>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

template<typename T>
void vdeb(std::vector<T> &bb) {
    for (int i = 0;i < bb.size();i++) {
        if (i == bb.size() - 1) std::cout << bb[i];
        else std::cout << bb[i] << ' ';
    }
    std::cout << '\n';
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &bb) {
    for (int i = 0;i < bb.size();i++) {
        std::cout << i << ' ';
        vdeb(bb[i]);
    }
    std::cout << '\n';
}

using namespace std;

int main() {
    ll n, x, m; cin >> n >> x >> m;
    vector<ll> da(m);
    rip(i,m,0) da[i] = i*i%m;
    vector<bool> used(m, false);
    ll now = x, cnt = 0;
    ll ans = 0;
    while(!used[now]&&cnt<n) {
        ans += now;
        cnt++;
        used[now] = true;
        now = now*now%m;
        // cout << now << endl;
    }
    if(cnt == n) {
        cout << ans << endl;
        return 0;
    }
    ll subsum = 0, subnow = now, subcnt = 0;
    n -= cnt;
    used = vector<bool>(m, false);
    while(!used[subnow]) {
        subsum += subnow;
        subcnt += 1;
        used[subnow] = true;
        subnow = subnow*subnow%m;
        // cout << subnow << endl;
    }
    // cout << ans MM subcnt MM subsum << endl;
    ans += n/subcnt*subsum;
    n %= subcnt;
    while(n) {
        ans += now;
        now = now*now%m;
        --n;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4048
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

        

        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            var n = Read();
            var s = new string[n];
            var ch = new char[n][];
          
            var count = new long[] { 0, 0, 0, 0, 0 };

            for (int i = 0; i < n; i++)
            {
                ch[i] = Console.ReadLine().ToCharArray();
                if (ch[i][0] == 'M')
                    count[0]++;
                if (ch[i][0] == 'A')
                    count[1]++;
                if (ch[i][0] == 'R')
                    count[2]++;
                if (ch[i][0] == 'C')
                    count[3]++;
                if (ch[i][0] == 'H')
                    count[4]++;
            }
            long ans = 0;
            for (int i = 0; i <5; i++)
            {
                for (int j = i+1; j < 5; j++)
                {
                    for (int k = j+1; k < 5; k++)
                    {
                        ans += count[i] * count[j] * count[k];
                    }
                }
            }
            Console.WriteLine(ans);
           
          


            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 25180
def ContinueCnt(A):
	Datas, Cnts = [A[0]], [1]
	index = 0
	for i in range(1, len(A)):
		if A[i] == Datas[index]:
			Cnts[index] += 1
		else:
			Datas.append(A[i])
			Cnts.append(1)
			index += 1
	return Datas, Cnts

N = int(input())
*a, = map(int, input().split())
Nums, Cnts = ContinueCnt(a)
ans = 0
for j in range(len(Cnts)):
	if Cnts[j] > 1:
		ans += Cnts[j] // 2
print(ans)


Measured memory_bytes: 3064
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
using namespace std;
typedef long long ll;

int bs[200000+10];
char buf[200000+10];

int main(void) {
  scanf("%s", buf);
  int n = strlen(buf);
  REP(i, n) {
    bs[i+1] = bs[i] + (buf[i] == 'B');
  }
  ll res = 0;
  REP(i, n) {
    if(buf[i] == 'W') {
      res += bs[i];
    }
  }
  cout << res << endl;
  
  return 0;
}


Measured memory_bytes: 1280
#include "bits/stdc++.h"

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;

ll N;
ll A[100010];
ll X[100010];
int main(){
	cin >> N;
	REP(i,0,N){
		cin>>A[i];
	}

	REP(i,0,N){
		if(i%2){
			X[0]-=A[i];
		}else{
			X[0]+=A[i];
		}
	}
	REP(i,0,N-1){
		X[i+1] = 2*A[i] - X[i];
	}

	REP(i,0,N){
		cout << X[i];
        if(i < N-1) cout << " "; 
	}
	cout<<endl;
	return 0;
}

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

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> pena(N,0);
    vector<ll> ok(N,0);
    ll res1=0;
    ll res2=0;
    for (int i = 0; i < M; i++)
    {
        ll p;
        string status;
        cin >> p >> status;--p;
        if(status=="AC"){
            if(!ok[p]){
                ++res1;res2+=pena[p];ok[p]=true;
            }
        }
        else pena[p]++;
    }
    cout<<res1<<" "<<res2;
    return 0;
}

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

int main() {
  string abcd;
  cin >> abcd;
  int a = (int)abcd.at(0) - '0';
  int b = (int)abcd.at(1) - '0';
  int c = (int)abcd.at(2) - '0';
  int d = (int)abcd.at(3) - '0';

  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        int sum = 0;
        string exp = "";
        if (i == 0) {
          sum = a + b;
          exp = to_string(a) + "+" + to_string(b);
        }
        else {
          sum = a - b;
          exp = to_string(a) + "-" + to_string(b);
        }
        if (j == 0) {
          sum += c;
          exp += "+" + to_string(c);
        }
        else {
          sum -= c;
          exp += "-" + to_string(c);
        }
        if (k == 0) {
          sum += d;
          exp += "+" + to_string(d);
        }
        else {
          sum -= d;
          exp += "-" + to_string(d);
        }
        if (sum == 7) {
          cout << exp << "=7" << endl;
          return 0;
        }
      }
    }
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <array>
#include <string>
#include <iomanip>
#include <cmath>
#define _USE_MATH_DEFINES
using namespace std;

typedef long long int ll;

int main(){
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll n, m;
	cin >> n >> m;
	ll a[m];
	for(ll i=0; i<m; i++){
		cin >> a[i];
		n -= a[i];
	}
	if(n < 0)
		cout << -1;
	else
		cout << n;
	return 0;
}

Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
 
#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
 
lli ans[300100];
lli ans2[300100];
 
void func(long long N, long long K, long long C, std::string S){
 
    lli cnt=0;
    REP(i,0,N){
        if(DEBUG)cout<<"i="<<i<<endl;
        if(S.at(i)=='o'){
            ans[i]=1;
            cnt++;
            i+=C;
        }
    }
 
    lli cnt2=0;
    for(lli i=N-1;i>=0;i--){
        if(DEBUG)cout<<"i="<<i<<endl;
        if(S.at(i)=='o'){
            ans2[i]=1;
            cnt2++;
            i-=C;
        }
    }
 
    if(cnt>K || cnt2>K)return;
    REP(i,0,N){
        if(ans[i] && ans2[i])cout<<i+1<<endl;
    }
 
}
 
int main(){
    // cout << fixed << setprecision(5);
 
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    long long C;
    scanf("%lld",&C);
    std::string S;
    std::cin >> S;
    func(N, K, C, S);
    return 0;
}

Measured memory_bytes: 5636
n = int(input())
m = n

max = 0
max2 = 0
if n < 10:
    print(n)
else:
    while m > 0:
        max += int(m % 10)
        m = m/10
    m=n
    while True:
        if m >= 10:
            max2 += int(9)
        else:
            max2 += int(m % 10 - 1)
            break
        m = m / 10
    if max > max2:
        print(max)
    else:
        print(max2)

Measured memory_bytes: 3060
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using static System.Math;
using System.Linq;
using static System.Array;

namespace ConsoleApp2
{
    class Program
    {
        //static int N;
        //static long mod = 1000000007;
        //static char[] az = Enumerable.Range('a', 'z' - 'a' + 1).Select(i => (Char)i).ToArray();
        static void Main(string[] args)
        {
            //var A = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            var N = long.Parse(Console.ReadLine());
            var A = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();

            Sort(A);
            var B = new long[N];
            for (int i = 0; i < N; i++)
            {
                B[i] = Abs(A[i]);
            }

            if (A[0] < 0 && A[N -1] < 0)
            {
                Reverse(A);
                Reverse(B);
                long sum = A[0];
                Console.WriteLine(B.Sum() - 2 * B[0]);
                for (int i = 1; i < N; i++)
                {
                    if (i == N - 1)
                    {
                        Console.WriteLine(sum + " " + A[i]);
                    }
                    else
                    {
                        Console.WriteLine(sum + " " + A[i]);
                        sum -= A[i];
                    }
                }

            }
            else if (A[0] >= 0 && A[N - 1] >= 0)
            {
                Console.WriteLine(B.Sum() - 2 * B[0]);
                long sum = A[0];
                for (int i = 1; i < N; i++)
                {
                    if (i == N - 1)
                    {
                        Console.WriteLine(A[i] + " " + sum);
                    }
                    else
                    {
                        Console.WriteLine(sum + " " + A[i]);
                        sum -= A[i];
                    }
                }

            }
            else
            {
                Console.WriteLine(B.Sum());
                long summ = A[0];
                long sumu = A[N-1];
                for (int i = 1; i < N; i++)
                {
                    if (i == N-1)
                    {
                        Console.WriteLine(sumu + " " + summ);
                        
                    }
                    else if (A[i] >= 0)
                    {
                        Console.WriteLine(summ + " " + A[i]);
                        summ -= A[i];
                    }else if (A[i] < 0)
                    {
                        

                        Console.WriteLine(sumu + " " + A[i]);
                        sumu -= A[i];
                    }
                }
            }

        }
    }
}


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

const double pi=3.14159265;
int main(){
  int n;
  cin>>n;
  if(n==0){
    cout<<0<<endl;
    return 0;
  }
  string s;
  int p=n;
  int q;
  while(p!=1){
    q=abs(p%(-2));
    if(p<0) p--;
    p/=(-2);
    s+=q+'0';
  }
  cout<<1;
  rep(i,s.size()){
    cout<<s[s.size()-i-1];
  }
}

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	auto s = to_string(n);
	int sum = 0;
	for (auto&& c : s) sum += c - '0';
	cout << (n % sum == 0 ? "Yes" : "No") << endl;
	return 0;
}


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

using namespace std;

const int MAX_N = 1e5 + 5;
const int INF = 1e9 + 7;

typedef long long ll;

int n, s[MAX_N];
ll ans = 0;

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

    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];

    // ab = a - b (a > b)
    for (int ab = 1; ab <= n; ab++) {
        ll cur = 0;
        for (int k = 0; k * ab < n - 1; k++) {
            int l = k * ab; // 0, ab, 2ab, …, kab
            int r = n - 1 - k * ab; // A, A+ab, A+2ab, …, A+kab
            if ((n - 1) % ab == 0 && l >= r) break;
            if (r <= ab) break;
            cur += s[l] + s[r];
            ans = max(ans, cur);
        }
    }
    cout << ans;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef long double ll;

int main(){
    ll a, b, h, m;
    cin >> a >> b >> h>> m;

    ll angle = M_PI*2*((double)h/12.0 + ((double)m/60.0)/12.0 - (double)m/60.0);

    ll c = sqrt((long double)(b*b) + (long double)(a*a) - 2*b*a*cos(angle)); 
    std::cout << std::setprecision(10);
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 4156
#include<bits/stdc++.h>
using namespace std;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-ff;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar(aa%10+'0');
	return;
}
const int mod=1e9+7;
int n,m,K,N,ff,ans;
int mp[25][25],F[2][1<<20];
int up(int aa,int bb)
{
	if(aa&bb) return aa;
	int A=aa%bb;aa/=bb;
	if(aa) aa-=(aa&-aa);
	return aa*bb+bb+A;
}
int main()
{
	n=read(),m=read(),K=read(),N=(1<<(n-1))-1;
	for(int i=1;i<=K;++i) 
	{
		int x=read(),y=read(),z=read();
		mp[x][y]=z+1;
	}
	F[1][0]=1;
	for(int a=1;a<=m;++a)
	for(int b=1,wz=1;b<n;++b,wz<<=1,ff^=1)
	for(int i=0;i<=N;++i) if(F[ff^1][i])
	{
		if(!(i&wz)&&mp[a][b]!=2) (F[ff][i]+=F[ff^1][i])%=mod;
		if(mp[a][b]!=1) (F[ff][up(i,wz)]+=F[ff^1][i])%=mod;
		F[ff^1][i]=0;
	}
	for(int i=0;i<=N;++i) ans=(ans+F[ff^1][i])%mod;
	write(ans);
	return 0;
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int inf = 1e9;
double pi = 3.14159265359;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, b, a) for (int i = a - 1; i >= b; i--)
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dxx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dyy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    int n;
    cin >> n;
    int p[n + 1];
    rep (i, 1, n + 1) cin >> p[i - 1] >> p[i];
    int dp[n + 1][n + 1]; // i->jまでの計算をする時の最小回数
    rep (i, 0, n + 1) dp[i][i] = 0;
    rep (i, 2, n + 1) {
        rep (j, 1, n - i + 2) {
            int k = i + j - 1;
            dp[j][k] = inf;
            rep (l, j, k) {
                dp[j][k] = min (dp[j][k], dp[j][l] + dp[l + 1][k] +
                                              p[j - 1] * p[l] * p[k]);
            }
        }
    }
    cout << dp[1][n] << "\n";
}


Measured memory_bytes: 3092
N = int(input())
S = input()

alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ans = ""
for i in range(len(S)):
    ind = alph.index(S[i]) + N
    if ind >= len(alph):
        ans += alph[ind-len(alph)]
    else:
        ans += alph[ind]
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <list>
#include <set>
using namespace  std;

constexpr int INF = std::numeric_limits<int>::max();

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    K--;

    string S;
    cin >> S;

    S[K] = tolower(S[K]);

    cout << S << endl;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    a = LI()
    r = 0
    dp = [0] * (s+1)
    dp[0] = 1
    for i in range(n):
        ai = a[i]
        if ai > s:
            dp[0] += 1
            continue
        dp[s] += dp[s-ai] * (n-i)
        dp[s] %= mod2
        for j in range(s-1, ai-1, -1):
            dp[j] += dp[j-ai]
            dp[j] %= mod2
        dp[0] += 1

    return dp[-1] % mod2


print(main())





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

int main() {
	ios_base::sync_with_stdio( false );

	int N, M, C;
	cin >> N >> M >> C;

	vector<int> B( M );
	for( auto& v: B ) { cin >> v; }

	int result = 0;
	for( int i = 0; i < N; ++i ) {
		int x = 0;

		for( int j = 0; j < M; ++j ) {
			int a;
			cin >> a;
			x += a * B[j];
		}

		if( x+C > 0 ) { result += 1; }
	}

	cout << result << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

//------------------------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    ld ans = 0.0;
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        int ii = i;
        while (ii < k) {
            cnt++;
            ii *= 2;
        }
        ld pow2 = 1.0;
        rep(i, cnt) pow2 *= 2.0;
        ans += 1 / pow2 / (ld) n;
    }
    cout << setprecision(30) << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <climits>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
#include <map>

using namespace std;

int main() {
	int n;
	cin >> n;
	double res = 0.0;
	int odds = n % 2 == 0 ? n / 2 : (n / 2) + 1;
	cout << (double)odds / (double)n << endl;
}


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

int a,b,c,x,y,ans;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> a >> b >> c >> x >> y;
	if (x>y){
		swap(a,b);
		swap(x,y);
	}
	ans=a*x+b*y;
	if (2*c<a+b){
		ans-=x*(a+b-2*c);
		if (2*c<b){
			ans-=(y-x)*(b-2*c);
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int MAX = 2e5+4;
int dp[MAX][4];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		int p = a+max(dp[i-1][1],dp[i-1][2]);
		int q = b+max(dp[i-1][0],dp[i-1][2]);
		int r = c+max(dp[i-1][0],dp[i-1][1]);
		dp[i][0]=p;
		dp[i][1]=q;
		dp[i][2]=r;
	}
	cout << max({dp[n][0],dp[n][1],dp[n][2]});
	return 0;
}

Measured memory_bytes: 1792
def maybe_prime(d,s,n):
    for a in (2,3,5,7):
        p = False
        x = pow(a,d,n)
        if x==1 or x==n-1:
            continue
        for i in range(1,s):
            x = pow(x,2,n)
            if x==1: return False
            elif x == n-1:
                p = True
                break
        if not p: return False
    return True

def is_prime(n):
    if n in (2,3,5,7): return True
    elif 0 in (n%2,n%3,n%5,n%7): return False
    else:
        d = n-1
        s = 0
        while not d%2:d,s = d>>1,s+1
        return maybe_prime(d,s,n)

cnt = 0
n = int(input())
for i in range(n):
  n = int(input())
  if is_prime(n): cnt+=1

print(cnt)

Measured memory_bytes: 7696
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>

/// Bismillahir Rahmanir Rahim


int main(void)
{   
    char ch;
    
    scanf("%c", &ch);
    
    printf("%c\n", ch+1);





    return 0;
}



Measured memory_bytes: 128
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

template<ll MOD>
struct rolloing_hash {
    int n;
    ll b;
    vector<ll> pow, hash;

    rolloing_hash() {}

    rolloing_hash(const string &s, ll b_ = 10007) {
        set(s, b_);
    }

    void set(const string &s, ll b_ = 10007) {
        n = s.size();
        b = b_;
        calc_pow();
        calc_hash(s.c_str());
    }

    void calc_pow() {
        pow.resize(n + 1); pow[0] = 1;
        for (int i = 0; i < n; ++i) {
            pow[i + 1] = pow[i] * b % MOD;
        }
    }

    void calc_hash(const char *s) {
        hash.resize(n + 1);
        hash[0] = 0;
        for (int i = 0; i < n; ++i) {
            hash[i + 1] = (s[i] + hash[i] * b) % MOD;
        }
    }

    ll get(int i) const {
        return hash[i];
    }

    ll get(int i, int j) const {
        return (get(j) - get(i) * pow[j - i] % MOD + MOD) % MOD;
    }
};

// 1000000007, 1000000009, 1000000021, ...
using RH = rolloing_hash<1000000007>;

int main() {
    string s;

    while (cin >> s) {
        int n = s.size();
        int a = n % 2 == 0 ? 2 : 1;
        int b = n % 2 == 0 ? n / 2 - 1 : n / 2;
        int c = b + a;
        int d = n - a;
        RH rh(s);
        int ans = n;
        while (a < b) {
            int A = rh.get(0, a);
            if (rh.get(b, c) == A && rh.get(d, n) == A && rh.get(a, b) == rh.get(c, d)) {
                ans = min(ans, b);
            }
            a += 2;
            b -= 1;
            c += 1;
            d -= 2;
        }
        if (ans != n) {
            cout << "Love " << s.substr(0, ans) << '!';
        } else {
            cout << "mitomerarenaiWA";
        }
        cout << '\n';
    }
}

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

vector<ll> ans;

ll S(ll x) {
	ll d = 0;
	while (x) {
		d += x % 10;
		x /= 10;
	}
	return d;
}

int main() {
	int K;
	cin >> K;

	set<ll> ss;

	for (int i = 1; i <= 9; ++i) {
		ans.pb(i);
		ss.insert(i);
	}

	ll x = 1;

	for (int i = 2; i <= 17; ++i) {
		x *= 10;
		for (int j = 2; j <= 10; ++j) {
			ans.pb(x * j - 1);
			ss.insert(x * j - 1);
		}
		if (i >= 5) {
			for (int j = 1000; j <= 9999; ++j) {
				ss.insert(x / 10000 * j + x / 10000 - 1);
			}
		}
	}

	rep(i, K) {
		ll x;

		while (true) {
			ll u = *ss.begin();
			ss.erase(ss.begin());
			ll t = -1;
			ll za = u;
			ll c = 1;

			while (za) {
				if (za % 10 != 9) {
					t = c;
					break;
				}
				za /= 10;
				c *= 10;
			}

			if (t == -1) {
				x = u;
				break;
			} else {
				if (u <= S(u) * t) {
					x = u;
					break;
				}
			}
		}
		cout << x << endl;
	}

	return 0;
}

Measured memory_bytes: 5760
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static long top = 1;
    static long n = 1;
    static ArrayList<Long> stack = new ArrayList<Long>();
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        long k = stdIn.nextLong();

        int[] n = new int[20];
        n[0] = 1;
        for(int i=0; i<k-1; i++){
            n = nextLunLun(n);
        }

        int index = n.length-1;
        while(n[index] == 0){
            index--;
        }
        while(index >= 0){
            System.out.print(n[index]);
            index--;
        }
    }

    static int[] nextLunLun(int[] n){
        int maxIndex = n.length-1;
        while(n[maxIndex] == 0){
            maxIndex--;
        }
        int index = 0;
        while(n[index+1] < n[index] || n[index] == 9){
            index++;
        }
        if(index > maxIndex && n[maxIndex] != 9){
            index--;
        }

        if(isFin(n)){
            index = maxIndex;
            n[index+1] = 1;
            n[index] = 0;
        }else{
            n[index]++;
        }
        index--;
        while(index >= 0){
            n[index] = n[index+1]-1;
            if(n[index] < 0){
                n[index] = 0;
            }
            index--;
        }

        return n;
    }

    static boolean isFin(int[] n){
        int index = n.length-1;
        while(n[index] == 0){
            index--;
        }

        while(index >= 0 && n[index] == 9){
            index--;
        }

        return (index == -1);
    }
}

Measured memory_bytes: 23892
#include<bits/stdc++.h>  
using namespace std;
typedef long long int64;

int main(){
  int N;
  while(cin >> N, N){
    int ret = 0;
    bool flag = false;
    while(N--){
      int k;
      cin >> k;
      if(k > 0) ret++;
      if(k > 1) flag = true;
    }
    if(flag)
      cout << ret + 1 << endl;
    else
      puts("NA");
  }
}
  

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n;
  cin>>n;
  int a[n];
  rep(i,n) cin>>a[i];
  int cnt = 0;
  rep(i,n) {
    if(a[i] % 2 == 1) cnt++;
  }
  if(cnt % 2 == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;

}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e;
int main(){
    scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
    printf("%d\n",max((c-a)*60+d-b-e,0));
    return 0;
}

Measured memory_bytes: 3828
L = list(input())
LARGE = 10**9 + 7

res = 0
cum_one = 0
for i in range(len(L)):
    if L[i] == '1':
        res += pow(2, cum_one, LARGE) * pow(3, len(L) - i - 1, LARGE)
        res = res % LARGE
        cum_one += 1
# last
res += pow(2, cum_one, LARGE)
res = res % LARGE
print(res)


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

string to_string(string s) {
    return '"' + s + '"';
}
string to_string(char ch) {
    string s(1, ch);
    return '\'' + s + '\'';
}
string to_string(const char *s) {
    return to_string((string)s);
}
string to_string(bool b) {
    return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

typedef long long int ll;
#define int ll
#define pb          push_back
#define pll         pair<int,int>
#define mll	        map<int,int>
#define F           first
#define S           second
#define lbnd(v,val) lower_bound(v.begin(),v.end(),val)
#define ubnd(v,val) upper_bound(v.begin(),v.end(),val)
#define bs(v,val)   binary_search(v.begin(),v.end(),val)
#define mp          make_pair
#define f(i,x,n)    for(int i=x;i<n;i++)
#define isup		isupper
#define islow 		islower
#define max3(a,b,c)	max(a,max(b,c))
#define endl        "\n"
#define countbits(n)	 __builtin_popcountll(n)
#define all(ar) ar.begin(), ar.end()
#define rall(ar) (ar).rbegin(), (ar).rend()
const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX;
const ll N = 2e5 + 10;

typedef vector<vector<ll>> matrix;
typedef vector<ll> vll;


void solve(){
	string s,t;
	cin>>s>>t;
	int dp[s.size()+1][t.size()+1];
	f(i,0,s.size()+1){
		f(j,0,t.size()+1){
			if(i==0 || j==0){
				dp[i][j]=0;
			}else{
				if(s[i-1]==t[j-1]){
					dp[i][j] = 1+dp[i-1][j-1];
				}else{
					dp[i][j]= max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
	}
	vector<char> v;
	int i=s.size(),j=t.size();
	while(i>0 and j>0){
		if(s[i-1]==t[j-1]){
			v.pb(s[i-1]);
			i--;
			j--;
		}else{
			if(dp[i][j-1]>dp[i-1][j]){
				j--;
			}else{
				i--;
			}
		}
	}
	reverse(all(v));
	f(i,0,v.size()){
		cout<<v[i];
	}
	cout<<endl;
	// cout<<dp[s.size()][t.size()]<<endl;
}

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

    

    int t=1;
    // cin>>t;
    while(t--){
    	solve();
    }
    return 0;
}


Measured memory_bytes: 70656
#include<stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
int main(void)
{
  int n,p[11],max=0,sum=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&p[i]);
    max=max(max,p[i]);
    sum+=p[i];
  }
  printf("%d",sum-max/2);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int a,b,c=10,ans;
int main(void){
    for(int i=0;i<5;i++){
        cin>>a;
        ans+=a/10*10;
        b=a%10;
        if(b==0)b=10;
        else ans+=10;
        c=min(c,b);
    }
    ans-=10-c;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
#input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

#    strs=""
#    sss=[]
    for i in range(n):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
            if root(gi)==rooti:
                ss-=1
        for xi in x[i]:
            if root(xi)==rooti:
                ss-=1
#        strs=strs+" "+str(ss)
#        sss.append(ss)
        print(ss,end=" ")
    print(" ")
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()
    

Measured memory_bytes: 107476
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int sum=0;
	int p=n;
	while(p!=0)
	{	
		sum+=p%10;
		p=p/10;
	}
	if(n%sum==0)cout<<"Yes";
	else cout<<"No";	
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class B
{
	public static void Main() => (new Solver()).Solve();
}

public class Solver
{
	public void Solve()
	{
		WriteLine(new String('x', GetString().Length));
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => Enumerable.Range(0, (int)N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(long N) => Enumerable.Range(0, (int)N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDouble()).ToArray();
	public static decimal[] GetDecimals(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDecimal()).ToArray();
	public static string[] GetStrings(long N) => Enumerable.Range(0, (int)N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}

Measured memory_bytes: 11092
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
	String add = "+";
	String subtract = "-";
	String multiply = "*";
	String division = "/";
		Scanner scan = new Scanner(System.in);
		int q = scan.nextInt();
		String value = scan.next();
		int w = scan.nextInt();
	int answer = 20;
	while (true) {
	if (value.equals(add)) {
		answer = q + w;
	} else if (value.equals(subtract)) {
		answer = q - w;
	}else if (value.equals(multiply)) {
		answer = q * w;
	} else if (value.equals(division)){
		answer = q / w;
	} else {
		break;
	}

	System.out.println(answer);
		q = scan.nextInt();
		value = scan.next();
		w = scan.nextInt();
}
} 
}




Measured memory_bytes: 26352
#include<bits/stdc++.h>
#define LiangJiaJun main
#define INF 1999122700
using namespace std;
int a[204],n;
int calc(int x){
    int G=0;
    while(x%2==0){
        x/=2;++G;
    }
    return G;
}
int LiangJiaJun(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int ge=INF;
    for(int i=1;i<=n;i++){
        ge=min(ge,calc(a[i]));
    }
    printf("%d\n",ge);
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

int n, A[50];

// 入力値の M から選んだ要素を引いていく再帰関数
int solve(int i, int m) {
  if ( m == 0 ) return 1;
  if ( i >= n ) return 0;
  int res = solve(i + 1, m) || solve(i + 1, m - A[i]);
  return res;
}

int main() {
  int q, M, i;

  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) scanf("%d", &A[i]);
  scanf("%d", &q);
  for ( i = 0; i < q; i++ ) {
    scanf("%d", &M);
    if ( solve(0, M) ) printf("yes\n");
    else printf("no\n");
  }

  return 0;
}


Measured memory_bytes: 2620