akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



int main()
{	
	char num[1010];
	char set[15] = "0123456789";
	
	while (true)
	{
		cin >> num;
		if (num[0] == '0') break;

		int ans = 0;

		for (int i = 0; i < strlen(num) ; i++)
		{
			for (int j = 0; j < 10; j++)
			{
				if (num[i] == set[j]) ans += j;
			}
		}

		cout << ans << endl;
	}

	return 0;
}



Measured memory_bytes: 3044
#include<iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include<map>	
#include<cstring>
#include<iomanip>
#include <string>
#include <vector>	
#include<unordered_map>
#include<unordered_set>
using namespace std;


typedef long long unsigned llu;
typedef long double ld;
#define ll long long
#define PI 3.14159265358979323846
#define For(i, a, b) for (int i = a, sz = (int)b; i < sz; i++)
#define rFor(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fill(a, b) memset(a, b, sizeof(a))
#define IO ios_base::sync_with_stdio(false), cin.tie(0),cout.tie(0)
const int mod = 1000000007;
const ll inf = 1000000000009;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);}

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdoutn

int main()
{
	IO;
	map<int,int>m;
	ll n{},k{},q{};
	cin>>n>>k>>q;
	For(i,1,q+1){int x{};cin>>x; m[x]++;}
	vector<int>p(n+1);
	For(i,1,n+1)p[i]=k;
	For(i,1,n+1)
	{
		if(m[i]>0)p[i]-=q-m[i];
		else if(!m[i])p[i]-=q;
	}
	For(i,1,n+1)
	{
		if(p[i]>0)cout<<"Yes\n";
		else cout<<"No\n";
	}
	//system("pause");	
	return 0;
}

Measured memory_bytes: 8352
/**
 * Combinatorial - Edit Distance (Levenshtein Distance)
 */

#include <iostream>

using namespace std;

int main() {

    string s1, s2;
    int len1, len2;

    cin >> s1 >> s2;
    len1 = (int) s1.length();
    len2 = (int) s2.length();

    int dp[len1 + 1][len2 + 1];

    dp[0][0] = 0;
    for (int i = 1; i <= len1; i++) dp[i][0] = i;
    for (int i = 1; i <= len2; i++) dp[0][i] = i;

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1));
        }
    }

    cout << dp[len1][len2] << endl;
}

Measured memory_bytes: 7068
N = int(input())
s = input()
t = input()
ans=maxlen=len(s)+len(t)

for i in range(len(s)):
  if len(s[i:]) <= len(t):
    complen = len(s[i:])
    if maxlen-complen>=N and s[i:] == t[0:complen]:
      ans=maxlen-complen
      break
      
      
print(ans)

Measured memory_bytes: 3060
N=int(input())
F=[list(map(int,input().split())) for _ in range(N)]
P=[list(map(int,input().split())) for _ in range(N)]
import math
profit=-math.inf
for i in range(1,2**10):
  temp=0
  i=format(i,'b').rjust(10,'0')
  e=[]
  for j in range(10):
    if i[j]=='1':
      e.append(j)
  for k in range(N):
    count=0
    for l in range(len(e)):
      if F[k][e[l]]==1:
        count+=1
    temp+=P[k][count]
  profit=max(temp,profit)
print(profit)

Measured memory_bytes: 74068
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K = int(input())
print(a[K-1])


Measured memory_bytes: 2940
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

n,p=map(int,input().split())
prime_list = factorization(p)
ans = 1
for x in prime_list:
  ans *= x[0]**(x[1]//n)
print(ans)

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

int main() {
    int n;
    cin>>n;
    int *L = new int [2*n];
    for(int i=0; i<2*n; ++i) {
        cin >> L[i];
    }
    sort(L, L + 2*n);
    int ans = 0;
    for(int i=0; i< 2*n; i+=2) {
        ans += min(L[i], L[i+1]);
    }
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include  <stdio.h>

int main(){
  int A[100],n,i,j,temp,count=0;

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

  
    for (i = 0; i < n - 1; i++) {
        for (j = n - 1; j > i; j--) {
            if (A[j - 1] > A[j]) {  
                temp = A[j];       
                A[j] = A[j - 1];
                A[j - 1]= temp;
		count++;
            }
        }
    }

  

    for(i=0;i<n;i++){
      printf("%d",A[i]);
      if(i != n-1){
	printf(" ");
      }
    }

    printf("\n");
    
    printf("%d\n",count);
    
    return 0;
    
}

Measured memory_bytes: 604
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

chars = "abcdefghij"
queue = deque()
queue.append(("a", 1))

while queue:
    s, num = queue.popleft()
    if len(s) == N:
        print(s)
    else:
        for i in range(num+1):
            ss = s + chars[i] 
            if i == num:
                queue.append((ss, num+1))
            else:
                queue.append((ss, num))

Measured memory_bytes: 64856
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define INF 1e18
ll MOD = 1e9+7;
ll a[403];
ll n,K;
vector<int> tr[100001];
ll dp[100001][2];//dp[i][1] colouring the subtree of i with i as black
//P a classic tree dp question
int dfs(int i,int p,int col){
	if(dp[i][col]!=(-1LL)) return dp[i][col];
	if(tr[i].size()==1&&tr[i][0]==p) return 1;
	ll ans=1;
	for(int j:tr[i]){
		if(j!=p){
			if(!col){
				ans*=(dfs(j,i,1)+dfs(j,i,0));
			}
			else ans*=dfs(j,i,0);
			ans = ans%MOD;
		}
	}
	// cout<<ans<<endl;
	return dp[i][col] = ans;
}
int main(){
	cin>>n;
	memset(dp,-1,sizeof dp);
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		a--;b--;
		tr[a].push_back(b);
		tr[b].push_back(a);
	}
	ll ans = (dfs(0,-1,0)+dfs(0,-1,1))%MOD;
	// for(int i=0;i<n;i++){
	// 	cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
	// }
	cout<<ans<<endl;
	return 0;
	//build the tree;
	//proceed to tree-dp
}

Measured memory_bytes: 17376
var
	deque:array[0..199999]of Longint;
	size:Longint=200000;
	qhead,qtail:Longint;
	k,i,u:Longint;
	d:array[0..99999]of Longint;
procedure pushf(a:Longint);
begin
	dec(qhead);
	if qhead<0 then qhead:=size+qhead;
	deque[qhead]:=a;
end;
procedure pusht(a:Longint);
begin
	deque[qtail]:=a;
	inc(qtail);
	if qtail>=size then qtail:=qtail-size;
end;
function popf():Longint;
var s:Longint;
begin
	s:=deque[qhead];
	inc(qhead);
	if qhead>=size then qhead:=qhead-size;
	popf:=s;
end;
begin
	read(k);
	for i:=0 to k-1 do d[i]:=1000000000;
	d[1]:=1;
	pusht(1);
	while qhead<>qtail do begin
		u:=popf();
		if d[10*u mod k]>d[u]then begin
			pushf(10*u mod k);
			d[10*u mod k]:=d[u];
		end;
		if d[(u+1)mod k]>d[u]+1 then begin
			pusht((u+1)mod k);
			d[(u+1)mod k]:=d[u]+1;
		end;
	end;
	writeln(d[0]);
end.


Measured memory_bytes: 896
main(b,r,g,c,s,t){for(;scanf("%d%d%d%d%d%d",&b,&r,&g,&c,&s,&t),t;printf("%d\n",100+b*77+r*51+g*4-c-3*(t-6*b-4*r-g-c-s)));exit(0);}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
 
int main(){
    int n[3];
    int i, t, tmp;
    cin >> n[0] >> n[1] >> n[2];

    for (t=2; t>0; t=t-1) {
        for (i=2; i>0; i=i-1) {
            if (n[i-1] > n[i]) {
                tmp = n[i];
                n[i] = n[i-1];
                n[i-1] = tmp;
            }
        }
    }

    cout << n[0] << ' ' << n[1] << ' ' << n[2] << endl;
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
using namespace std;
 
int main() {
	int i;
	int flag[26];
	char s;
	for (i = 0; i < 26; i++)flag[i] = 0;
	while (cin >> s) flag[(int)(s - 'a')] = 1;
	for (i = 0; i < 26; i++)if (flag[i] == 0) {
		cout << (char)(i + (int)'a') << endl;
		break;
	}
	if (i == 26)cout << "None" << endl;
	return 0;
}


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

#define REP(i,x,y) for(int i=(x);i<(y);i++)
#define RREP(i,x,y) for(int i=(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
// #define int long long

using namespace std;

// conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define eprintf(...) 42
#define dump(x) 42
#define debug(x) 42
#endif

typedef long long ll;

const ll MOD = 1e9 + 7;

void solve(int N, vector<double>& p) {
    vector<vector<double>> dp(N+1, vector<double>(N+1, 0));
    dp[0][0] = 1;
    REP(i,1,N+1) {
        dp[i][0] = dp[i-1][0] * (1 - p[i-1]);
    }

    REP(i,1,N+1) {
        REP(j,1,i+1) {
            dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1.0 - p[i-1]);
        }
    }
    double answer = 0;
    REP(i,(N+1)/2,N+1) {
        answer += dp[N][i];
    }

    stringstream ss;
    ss << setprecision(10) << answer;
    cout << ss.str() << '\n';

    return;
}

signed main() {
    int N;
    cin >> N;

    vector<double> A(N);
    REP(i,0,N) cin >> A[i];

    solve(N, A);

    return 0;
}



Measured memory_bytes: 70656
import sys
input=sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int,input().split()))
    ans = [0]*N
    ans[0] = sum(A)
    for i in range(1,N,2):
        ans[0] -= 2*A[i]
    for i in range(1,N):
        ans[i] = 2*A[i-1]-ans[i-1]
    print(*ans)

if __name__ == '__main__':
    main()


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

int main() {
	int N,K,Q;
	cin >> N>>K>>Q;
	vector<int> Count(N);
	for (int n = 0; n <Q; ++n) {
		int num;
		cin >> num;
		num--;
		Count[num]++;
	}
	for (int n = 0; n < N; ++n) {
		if ((K-Q + Count[n] )> 0) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No"<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3756
using System;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace AtCoder {
    class Practice {
        static void Main() => CustomMain();

        static void Solve() {
            var n = ReadString();

            var ans = 0;
            for (int i = 0; i < n.Length; i++) {
                ans += int.Parse(n[i].ToString());
            }

            if (ans == 1) {
                ans = 10;
            }

            WriteAnswer(ans);
        }

        static void CustomMain() {
#if DEBUG
            // ファイルからテストケースを読み込む
            global::Common.ChangeStdIn();
            // 時間計測
            var stopwatch = new Stopwatch();
            stopwatch.Start();
#endif
            // 出力高速化
            var streamWriter = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            Console.SetOut(streamWriter);
            // 回答
            Solve();
#if DEBUG
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
#endif
            Console.Out.Flush();
        }

        static string ReadString() => Console.ReadLine().Trim();
        static int ReadInt() => int.Parse(ReadString());
        static long ReadLong() => long.Parse(ReadString());
        static float ReadFloat() => float.Parse(ReadString());
        static double ReadDouble => double.Parse(ReadString());

        static string[] ReadStringArray() => ReadString().Split(' ');
        static int[] ReadIntArray() => Array.ConvertAll(ReadString().Split(' '), int.Parse);
        static long[] ReadLongArray() => Array.ConvertAll(ReadString().Split(' '), long.Parse);
        static float[] ReadFloatArray() => Array.ConvertAll(ReadString().Split(' '), float.Parse);
        static double[] ReadDoubleArray() => Array.ConvertAll(ReadString().Split(' '), double.Parse);

        static T TypeConversion<T>(string s) {
            if (typeof(T) == typeof(int)) {
                return (T) Convert.ChangeType(int.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(long)) {
                return (T) Convert.ChangeType(long.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(double)) {
                return (T) Convert.ChangeType(double.Parse(s), typeof(T));
            } else {
                return (T) Convert.ChangeType(s, typeof(T));
            }
        }

        static void ReadMulti<T, U>(out T a, out U b) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
        }

        static void ReadMulti<T, U, V>(out T a, out U b, out V c) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
            c = TypeConversion<V>(str[2]);
        }

        static void WriteAnswer(object ans) => Console.WriteLine(ans);

        static bool IsOdd(long num) {
            return (num & 1) == 1;
        }

        static bool IsEven(long num) {
            return (num & 1) == 0;
        }

        static long GCD(long a, long b) {
            return b != 0 ? GCD(b, a % b) : a;
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int N;
cin >> N;
vector<int64_t> vec(N);
for (int i = 0; i < N ;i++){
  cin >> vec.at(i);}
int64_t a = 1;
int64_t k = 1;
bool right = true;
for ( int i = 0 ; i < N ; i++){
 if ( vec.at(i) == 0 ) {
   a = 0 ;
   cout << 0 << endl;
   return 0;}
 }
for ( int i = 0 ; i < 18 ; i++){
k *= 10;}
for (int i = 0; i < N ; i++){
  a *= vec.at(i);
  if ( a > k ) {
    right = false ;
    break;}
} 
if (0 < a && right) {cout << a << endl;}
else {cout << -1 << endl;}
}

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

int main()
{
	ios::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0);
	int n;
	cin>>n;
	int a[n+1];
	for(int i=1;i<=n;i++)cin>>a[i];
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(i%2 && a[i]%2==1)cnt++;
	}
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define rsort(x) sort(all(x));reverse(all(x))
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool debug=false;
/*---------------------------------------------------*/

int main(){
  int city[55]={0};
  int n,m,a,b;
  cin>>n>>m;
  rep(i,m){
    cin>>a>>b;
    city[a]++;city[b]++;
  }
  REP(i,1,n+1)cout<<city[i]<<endl;
  return 0;
}


Measured memory_bytes: 256
import collections

n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]

s_counter = collections.Counter(s)
t_counter = collections.Counter(t)
t_keys = list(t_counter.keys())
ans = []

for key in s_counter.keys():
    if key in t_keys:
        ans.append(int(s_counter[key]) - int(t_counter[key]))
    else:
        ans.append(s_counter[key])
max_ans = max(ans)
if max_ans < 0:
    print(0)
else:
    print(max_ans)


Measured memory_bytes: 9448
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	static int mod = (int) 1e9 + 7;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] ins = br.readLine().split(" ");
		int h = Integer.parseInt(ins[0]), w = Integer.parseInt(ins[1]);
		char tb[][] = new char[h][w];
		for ( int r = 0; r < h; r++ ) {
			char[] temp = br.readLine().toCharArray();
			tb[r] = temp;
		}
		br.close();

		int dp[][] = new int[h][w];
		for ( int r = 0; r < h; r++ ) {
			if ( tb[r][0] == '#' ) break;
			dp[r][0] = 1;
		}
		for ( int c = 0; c < w; c++ ) {
			if ( tb[0][c] == '#' ) break;
			dp[0][c] = 1;
		}

		for ( int r = 1; r < h; r++ ) {
			for ( int c = 1; c < w; c++ ) {
				if ( tb[r][c] == '#' ) continue;
				dp[r][c] = (dp[r - 1][c] + dp[r][c - 1]) % mod;
			}
		}
		System.out.println(dp[h - 1][w - 1] % mod);
	}
}

Measured memory_bytes: 37076
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define mp make_pair
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vstr=vector<string>;
void yes(bool c) { if (c)print("Yes"); else print("No"); };

int H,W,N,a[10001],ans[101][101];

void draw(){
    int color = 1;
    int color_cnt = a[0];
    rep(i,H){
        rep(j,W){
            int k = (i%2)?W-1-j:j;
            ans[i][k] = color;
            color_cnt--;
            if(color_cnt==0) {
                color_cnt = a[color++];
            }
        }
    }
    rep(i,H){
        rep(j,W){
            if(j!=0) cout << " ";
            cout << ans[i][j];
        }
        print("");
    }
}

void solve() {
    cin >> H >> W;
    cin >> N;
    rep(i,N){
        cin >> a[i];
    }
    draw();
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
    //int q; cin >> q;
	//while (q--)
		solve();
    return 0;
}


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

const double PI = 3.14159265358979323846;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<ll> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}


bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//const ll mod = 1e10;
//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;



unordered_map<string, ll> check(int n, string &s) {
    unordered_map<string, ll> ans;
    rep(i, 1 << n) {
        string a, b;
        rep(j, n) {
            if ((i >> j) & 1) a.push_back(s[j]);
            else b.push_back(s[j]);
        }
        ans[a + ' ' + b]++;
    }
    return ans;
}

int main() {
    int n;
    string s;
    cin >> n >> s;

    string a = s.substr(0, n);
    string b = s.substr(n);

    unordered_map<string, ll> m1 = check(n, a);
    reverse(b.begin(), b.end());
    unordered_map<string, ll> m2 = check(n, b);

    ll ans = 0;
    for (auto &e : m1) {
        ll now = e.second * m2[e.first];
        ans += now;
    }
    cout << ans << endl;


}


Measured memory_bytes: 101136
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include<math.h>
using namespace std;

#define int long long
#define endl "\n"
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define mod 1000000007
#define all(v)  v.begin(),v.end()
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define all(v)  v.begin(),v.end()
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}

int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}



signed main() {
	int n, k, a;
	cin >> n >> k;
	vector<int>vec(n);
	rep(i, n) {
		cin >> vec[i];
		if (vec[i] == 1) {
			a = i;
		}
	}
	if ((n - 1) % (k - 1) == 0) {
		cout << (n - 1) / (k - 1) << endl;
	}
	else {
		cout << (n - 1) / (k - 1)+1 << endl;
	}
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr ll INF = (1LL << 55);

int main(){
  int n, p;
  cin >> n >> p;
  string s;
  cin >> s;

  if (10 % p == 0) {
    ll res = 0;
    for (int i = 0; i < n; i++) {
      if ((s[i] - '0') % p == 0) res += i + 1;
    }
    cout << res << endl;
    return 0;
  }

  vector<int> cum(n+1,0);
  int now = 1;
  for (int i = n-1; i >= 0; i--) {
    int d = s[i] - '0';
    (d *= now) %= p;
    (cum[i] = cum[i + 1] + d) %= p;
    (now *= 10) %= p;
  }

  ll res = 0; 
  vector<int> cnt(p,0);
  /*ある区間がpで割り切れる = mod p　が等しい*/
  for (int i = n; i >= 0; i--) {
    res += cnt[cum[i]];
    cnt[cum[i]]++;
  }
  cout << res << endl;

  return 0;
} 

Measured memory_bytes: 1412
/*input
1234
150
100
*/
#include <bits/stdc++.h>
using namespace std;

long long int arr[1123456],brr[1123456];
int main(){
    int x,a,b, ans = 0;
    cin>>x>>a>>b;
    if(x > a){
        x -= a;
        ans++;
    }
    cout<<x%b<<endl;
}
   

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

#define real() cout<<"\n";

#define debug(arguments...) {string pri=#arguments;replace(pri.begin(),pri.end(),',',' ');stringstream prii(pri);istream_iterator<string> _iterat(prii);error(_iterat,arguments);}
void error(istream_iterator<string> _iterat) {}
template<typename T,typename...args>
void error(istream_iterator<string> _iterat,T a,args...arguments)
{
    cerr<<*_iterat<<"="<<a<<"\n";
    error(++_iterat,arguments...);
}

#define debugmp(z) {string pri=#z;error(pri,z);}
template<typename T,typename V>
void error(string pri,const pair<T,V> &z)
{
    cerr<<pri<<"="<<"{"<<z.first<<","<<z.second<<"}"<<"\n";
}
template<typename T,typename V>
void error(string pri,const map<T,V> &z)
{
    cerr<<pri<<" is={";
    for(auto it=z.begin();it!=z.end();++it)
    {
        cerr<<it->first<<":"<<it->second;
        auto _it=z.end();
        _it--;
        if(it!=_it) cerr<<",";
    }
    cerr<<"}";
    cerr<<"\n";
}

#define debugc(z,st,ed) {string pri=#z;error(pri,z,st,ed);}
template<typename T>
void error(string pri,const vector<T> &z,long long st,long long ed)
{
    cerr<<pri<<" in range["<<st<<","<<ed<<")=[";
    for(long long i=st;i<ed;++i)
    {
        cerr<<z[i];
        if(i!=ed-1) cerr<<" ";
    }
    cerr<<"]";
    cerr<<"\n";
}
template<typename T>
void error(string pri,const set<T> &z,long long st,long long ed)
{
    cerr<<pri<<" in range["<<st<<","<<ed<<")=[";
    long long tempcount=0;
    for(auto it=z.begin();it!=z.end();++it)
    {
        if(tempcount>=st and tempcount<ed)
        {
            cerr<<*it;
            if(tempcount!=ed-1) cerr<<" ";
        }
        tempcount++;
    }
    cerr<<"]";
    cerr<<"\n";
}
template<typename T>
void error(string pri,const T z[],long long st,long long ed)
{
    cerr<<pri<<" in range["<<st<<","<<ed<<")=[";
    for(long long i=st;i<ed;++i)
    {
        cerr<<z[i];
        if(i!=ed-1) cerr<<" ";
    }
    cerr<<"]";
    cerr<<"\n";
}

void logic()
{
    int a,b;
    cin>>a>>b;
    if(a<=8 and b<=8) cout<<"Yay!";
    else cout<<":(";
    cout<<"\n";
    //incase of wrong answer...stress test your code...do not stress test yourself
    //overflow,bounds,size,constraints
    //sample tests,corner case/special case(n==0 or n==1 or negative numbers...),some hand written tests
    //read statement carefully
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long t;
    //cin>>t;
    //while(t--)
    {
        logic();
    }
}


Measured memory_bytes: 3640
import sys
sys.setrecursionlimit(20000)
def solve(h,w,count,c):
    if 0 <= h < H and 0 <= w < W and A[h][w] == c:
        A[h][w] = count
        for dh,dw in zip([1,0,-1,0],[0,1,0,-1]):
            solve(h+dh,w+dw,count,c)
while 1:
    H,W = map(int,raw_input().split())
    if H == W == 0: break
    A = [list(raw_input()) for _ in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if type(A[h][w]) is not int:
                solve(h,w,count,A[h][w])
                count += 1
    print count

Measured memory_bytes: 17420
#include<bits/stdc++.h>
#define ll long long
#define mo 1000000007
#define N 200010
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
ll jie[N],nj[N],n,A,B,C,ansn;
ll c(ll x,ll y){return (jie[x]*nj[y]%mo)*nj[x-y]%mo;}
ll po(ll x,ll y){ll z=1;while (y){if (y%2)z=x*z%mo;x=x*x%mo;y/=2;}return z;}
ll add(int x,int y){
	if (x==n)return (((c(x+y-1,x-1)*po(A,x)%mo)*po(B,y)%mo)*C%mo)*(x+y)%mo;
	else return (((c(x+y-1,y-1)*po(A,x)%mo)*po(B,y)%mo)*C%mo)*(x+y)%mo;
}
int main(){
	read(n);read(A);read(B);read(C);
	ll su=A+B;
	A=A*po(su,mo-2)%mo;B=B*po(su,mo-2)%mo;C=100*po(100-C,mo-2)%mo;
	jie[0]=1;
	for (int i=1;i<=n*2;i++)jie[i]=jie[i-1]*i%mo;
	nj[n*2]=po(jie[n*2],mo-2);for (int i=n*2-1;i>=0;i--)nj[i]=nj[i+1]*(i+1)%mo;
	for (int i=0;i<n;i++)ansn=(ansn+add(i,n)+add(n,i))%mo;
	cout<<ansn<<endl;
	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

int const N = 200001;

int main(){
    string s; 
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5])puts("Yes");
    else puts("No");

} 

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

ll dfs(ll &p, vector<string> &S) {
  if('0' <= S[p][0] && S[p][0] <= '9') {
    ll ret = 0;
    REP(i, 0, S[p].length()) ret = ret * 10 + (S[p][i] - '0');
    p++;
    return ret;
  }

  char op = S[p++][0];
  ll op2 = dfs(p, S);
  ll op1 = dfs(p, S);
  if(op == '+') return op1 + op2;
  if(op == '-') return op1 - op2;
  if(op == '*') return op1 * op2;
}

vector<string> split(string s, string p) {
  vector<string> ret;
  int h = 0;
  REP(i, 0, s.size() - p.size() + 1) if(s.substr(i, p.size()) == p) {
    ret.push_back(s.substr(h, i - h));
    h = i + p.size();
    i += (signed) p.size() - 1;
  }
  ret.push_back(s.substr(h, (signed) s.size() - h));
  return ret;
}

int main(void) {
  string line;
  getline(cin, line);

  vector<string> S = split(line, " ");
  reverse(S.begin(), S.end());

  ll p = 0;
  cout << dfs(p, S) << endl;
}

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

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli n,m;
	cin>>n>>m;

	map<lli,vector<lli>> k;
	REP(i,0,m){
		lli k1,s;
		cin>>k1;
		REP(j,0,k1){
			cin>>s;
			k[i].push_back(s-1);
		}
	}
	vector<lli> p(m);
	REP(i,0,m)cin>>p[i];

	lli sum=0;
	/*bitによる全探索をする*/
	for(lli i=0;i<(1LL)<<n;i++){
		/*bitに対応するところがON*/
		lli dp[20]={0};
		if(DEBUG)cout<<"i="<<i<<endl;
		for(lli b=0;b<10;b++){
			if(i&(1LL)<<b){
				if(DEBUG)cout<<"bitON="<<b<<endl;
				dp[b]=1;
			}
		}

		/*ONになっているスイッチを出したので、どれが光るかを確認する*/
		lli ans = 0;
		for(auto e:k){
			lli nowK = e.first;
			lli size = e.second.size();
			lli cnt=0;
			if(DEBUG)cout<<"nowK="<<nowK<<endl;
			for(lli j=0;j<size;j++){
				lli pos = e.second.at(j);
				if(dp[pos]==1){
					if(DEBUG)cout<<"Pos="<<pos<<endl;
					cnt++;
				}
			}
			if(cnt%2==p[nowK])ans++;
		}
		if(ans == m)sum++;
	}
	cout<<sum<<endl;

	return 0;
}

Measured memory_bytes: 256
// ALDS1_4_A Linear Search

#include <iostream>
#include <vector>

int main(int argc, char *argv[]){
	std::vector<int> S, T;
	int n, q, v;
	int c = 0;

	std::cin >> n;
	for(int i=0 ; i<n ; i++){
		std::cin >> v;
		S.push_back(v);
	}

	std::cin >> q;
	for(int i=0 ; i<q ; i++){
		std::cin >> v;
		T.push_back(v);
	}


	for(auto itr_t=T.begin() ; itr_t!=T.end() ; itr_t++){
		for(auto itr_s=S.begin() ; itr_s!=S.end() ; itr_s++){
			if(*itr_s == *itr_t){
				c++;
				break;
			}
		}
	}

	std::cout << c << std::endl;

	return 0;
}



Measured memory_bytes: 3192
#153_E
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
dp = [10 ** 10 for _ in range(h+1)]
dp[0] = 0
for i in range(1, h+1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
print(dp[h])

Measured memory_bytes: 42416
#include<stdio.h>
  
int par[100001];
int sib[100001];
int deg[100001];
int n;
  
int depth(int);
int height(int);
  
int main(int argc,char *argv[]) {
  int i,j;
  scanf("%d", &n);
  for(i = 0; i < n; ++i) {
    par[i] = -1;
    sib[i] = -1;
    deg[i] = 0;
  }
  for(i = 0; i < n; ++i) {
    int id, left, right;
    scanf("%d %d %d", &id, &left, &right);
    if(left != -1) {
      par[left] = id;
      sib[left] = right;
      deg[id]++;
    }
    if(right != -1) {
      par[right] = id;
      sib[right] = left;
      deg[id]++;
    }
  }
  
  for(i = 0; i < n; ++i) {
    int dep = depth(i);
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",
           i, par[i], sib[i], deg[i], dep, height(i));
    if(dep == 0) {
      printf("root\n");
    } else if(deg[i] == 0) {
      printf("leaf\n");
    } else {
      printf("internal node\n");
    }
  }
  return 0;
}
 
int depth(int i) {
  if(par[i] == -1) return 0;
  return depth(par[i]) + 1;
}
  
int height(int i) {
  int j, h = 0;;
 
  for(j = 0; j < n; ++j) {
    if(par[j] == i) {
      int tmp = height(j) + 1;
      if(tmp > h) h = tmp;
    }
  }
  return h;
}

Measured memory_bytes: 620
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int count = 0;
			for(int i=1;i<=10;i++){
				if(i!=a && i!=b && i!=c && a+b+i>20) count++;
			}
			if(count<=3) System.out.println("YES");
			else System.out.println("NO");	
		}
	}	
}

Measured memory_bytes: 17200
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std ;

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

	vector<int> v(3) ;

	cin >> v[0] >> v[1] >> v[2] ;

	sort(v.begin(), v.end()) ;

	if(v[2] == v[0]+v[1])
		cout << "Yes" ;
	else
		cout << "No" ;

	
	return 0;
} 

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    int H[100000];
    for(int i=0;i<N;i++)
        cin >> H[i];

    for(int i=1;i<N-1;i++){
        if(H[i-1] < H[i])
            H[i]--;
        if(H[i] > H[i+1]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
 
}

Measured memory_bytes: 640
from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if (a[0] + a[1] - X) != A * 2 or A > a[0] or A < 0 or X & A: 
	print(-1)
	exit()
res = A
for i in range(42, -1, -1):
	if (X >> i) & 1:
		if res + (1 << i) <= a[0]:
			res += (1 << i)
if res == 0:
	print(-1)
	exit()
print(a[0]-res)

Measured memory_bytes: 61880
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

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


int main(){
    int N, H, W, cnt(0); cin >> N >> H >> W;
    REP(i, N){
        int A, B; cin >> A >> B;
        if(H <= A && W <= B) ++cnt;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stack>
#include <math.h>

using namespace std;

int main(){

	int n,table[183];
	int* dp = new int[1000000];
	int* odd_dp = new int[1000000];

	for(int i=0; i < 183; i++)table[i] = i*(i+1)*(i+2)/6;

	for(int i=0; i < 1000000; i++){
		odd_dp[i] = 20000000;
		dp[i] = 20000000;
	}

	dp[0] = 0;
	dp[1] = 1;

	odd_dp[0] = 0;
	odd_dp[1] = 1;

	for(int i = 2; i < 1000000; i++){
		for(int k = 1; table[k] <= i; k++){
			dp[i] = min(dp[i], dp[i-table[k]]+1);
			if(table[k]%2 == 1){
				odd_dp[i] = min(odd_dp[i],odd_dp[i-table[k]]+1);
			}
		}
	}


	while(true){
		scanf("%d",&n);
		if(n == 0)break;

		printf("%d %d\n",dp[n],odd_dp[n]);
	}

    return 0;
}

Measured memory_bytes: 10488
#include<bits/stdc++.h>
#define N 200005
using namespace std;
bool cur1;
int n;
int a[N],dp[N];
int stk[N],top;
inline void Rd(int &res){
	char c;res=0;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
	return;
}
bool cur2;
int main(){
//	printf("%lf MB\n",(&cur2-&cur1)/1024.0/1024);
	Rd(n);
	for(int i=1;i<=n;i++)Rd(a[i]);
	bool flag=0;
	for(int i=n;i>=1;i--){
		int sm=0;
		for(int j=i+i;j<=n;j+=i)sm^=dp[j];
		if(a[i]==sm)dp[i]=0;
		else dp[i]=1,stk[++top]=i;
	}
	if(flag)puts("-1");
	else{
		printf("%d\n",top);
		for(int i=top;i>=1;i--)printf("%d ",stk[i]);puts("");
	}
	return 0;
}

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

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

    ll n; cin >> n;
    vector<ll> v(n,0);

    for (ll i=0;i<n;i++) cin >> v[i];

    sort(v.begin(), v.end());

    if (v[0] == 0) {
        cout << 0 << "\n";
        return 0;
    }

    ll ans = 1;
    for (ll i=0;i<n;i++) {
        if (v[i] <= 1000000000000000000 / ans) {
            ans *= v[i];
        }
        else {
            cout << -1 << "\n";
            return 0;
        }
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

ll dp[2000000];
ll dp2[2000000];
const ll INF = 1e9;
int main() {
  vl A;
  ll x = 0;
  int m = 1;
  while(x<=1000000){
    x = m*(m+1)*(m+2)/6;
    A.push_back(x);
    m++;
    //if(x<100)show(x);
  }
  int k = sz(A);
  fill(dp,dp+2000000,INF);
  fill(dp2,dp2+2000000,INF);
  dp[0] = 0;
  dp2[0] = 0;
  srep(i,1,1000001){
    rep(j,k){
      if((i - A[j])< 0) break;
      dp[i] = min(dp[i],dp[i - A[j]]+1);
      if(A[j]%2)dp2[i] = min(dp2[i],dp2[i - A[j]]+1);
    }  
  }
  //rep(i,100)cout<<i << " " << (dp2[i]) << endl;
  while(1){
    int n;
    cin >> n;
    if(n == 0){
      return 0;
    }
    cout<<dp[n]<<" "<< dp2[n]<<endl;
  }
  
  return 0;
}


Measured memory_bytes: 34244
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long,long long> ii; 	
typedef complex<long double> com;

const ll mod = 1e9+7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
   ll n;
   cin >> n;
   vector <ll> arr(n);
   ll lol = 0;
   for (int z=0;z<n;z++){
      cin >> arr[z];
      lol ^= arr[z];
   }
   for (int z=0;z<n;z++){
      cout << (arr[z]^lol) << " ";
   } cout << endl;
} 

Measured memory_bytes: 4760
#include <bits/stdc++.h>
 
#define gcd(m,n) __gcd(m,n)
#define lcm(m,n) m*(n/gcd(m,n))
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pi acos(-1.0)
#define endl '\n'
#define MOD 1000000007
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define dbg(x) cout << #x << "  " << x << endl;
 
ll power(ll base, ll exp) 
{ll res=1;while(exp>0) {if(exp%2==1) res=(res*base);base=(base*base);exp/=2;}return res;}
 
ll mod(ll a, ll b) {return (a % b + b) % b;}
 
ll powerm(ll base,ll exp,ll mod) 
{ll ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}

using namespace std;

int main()
{
	fast;
	ll a,b; cin>>a>>b;
	cout << a * b << endl;
	return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define dummy (int)(2000000002)
using namespace std;

struct data {
  int num, lef, righ, par;
};

int t;
string s;
vector<data> v;
vector<int> pre, in, pos;

void insert(int x);
void print();
void rec(int p);
bool find(int x);
void del(int x);

int main() {
  cin >> t;
  v.push_back({dummy, dummy, dummy, dummy});
  while(t--) {
    cin >> s;
    if(s == "print")
      print();
    else if(s == "find") {
      int x;
      cin >> x;
      if(find(x))
        cout << "yes" << endl;
      else
        cout << "no" << endl;
    }
    else if(s == "delete") {
      int x;
      cin >> x;
      del(x);
    }
    else {
      int x;
      cin >> x;
      insert(x);
    }
  }
  return 0;
}

void insert(int x) {
  int id = 0;
  while(!v.empty() && v[id].num != dummy) {
    int nownum = v[id].num;
    if(nownum > x) {
      if(v[id].lef == dummy) {
        v[id].lef = v.size();
        v.push_back({dummy, dummy, dummy, id});
      }
      else
        id = v[id].lef;
    }
    else if(nownum < x) {
      if(v[id].righ == dummy) {
        v[id].righ = v.size();
        v.push_back({dummy, dummy, dummy, id});
      }
      else
        id = v[id].righ;
    }
  }
  v[id].num = x;
}

void print() {
  pre.clear();
  in.clear();
  pos.clear();
  rec(0);
  for(int i = 0; i < pos.size(); ++i) cout << " " << in[i];
  cout << endl;
  for(int i = 0; i < pre.size(); ++i) cout << " " << pre[i];
  cout << endl;
}

void rec(int p) {
  pre.push_back(v[p].num);
  if(v[p].lef != dummy) rec(v[p].lef);
  in.push_back(v[p].num);
  if(v[p].righ != dummy) rec(v[p].righ);
  pos.push_back(v[p].num);
}

bool find(int x) {
  int id = 0;
  while(id != dummy && v[id].num != dummy) {
    if(v[id].num == x) return 1;
    if(v[id].num > x)
      id = v[id].lef;
    else if(v[id].num < x)
      id = v[id].righ;
  }
  return 0;
}

void del(int x) {
  int id = 0;
  while(id != dummy && v[id].num != dummy) {
    if(v[id].num == x) {
      int par = v[id].par;
      if(v[id].lef == v[id].righ && v[id].lef == dummy) {
        v[id].num = dummy;
        if(v[par].lef == id)
          v[par].lef = dummy;
        else
          v[par].righ = dummy;
      }
      else if(v[id].lef == dummy) {
        int chil = v[id].righ;
        v[chil].par = par;
        if(v[par].lef == id)
          v[par].lef = chil;
        else
          v[par].righ = chil;
        v[id].num = dummy;
      }
      else if(v[id].righ == dummy) {
        int chil = v[id].lef;
        v[chil].par = par;
        if(v[par].lef == id)
          v[par].lef = chil;
        else
          v[par].righ = chil;
        v[id].num = dummy;
      }
      else {
        pre.clear();
        in.clear();
        pos.clear();
        rec(0);
        auto it =
            upper_bound(in.begin(), in.end(), v[id].num);
        if(it == in.end()) cerr << "a";
        long long num = *it;
        del(num);
        v[id].num = num;
      }
      return;
    }
    if(v[id].num > x)
      id = v[id].lef;
    else if(v[id].num < x)
      id = v[id].righ;
  }
  return;
}


Measured memory_bytes: 16428
#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<math.h>
#include<vector>
#include<cctype>
#include<string>
#include<set>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::string line;
typedef long long ll;

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

   int res = b-a;

   if(res <= x && res > 0) cout << "safe" << endl;
   else if(res <=0) cout << "delicious" << endl;
   else cout << "dangerous" << endl;


   return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String ans = "No";
	if (N % 7 == 4) {
      ans = "Yes";
    } else if (N % 7 == 0) {
      ans = "Yes";
    } else if (N % 4 == 0) {
      ans = "Yes";
    } else if (N % 7 == 1 && N > 1) {
      ans = "Yes";
    } else if (N % 7 == 5 && N > 5) {
      ans = "Yes";
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 23764
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

using namespace std;

typedef long long ll ;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pair<int,int> > vii;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define mp			make_pair
#define fi			 first
#define se			 second
#define for0(i,n)        for(int i=0;i<n;i++)
#define for1(i,n)        for(int i=1;i<=n;i++)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)    cout<<"Case "<<z<<": "<<x<<"\n"
int main()
{
	int n,p;
	cin>>n;
	map<int,int>m;
	for0(i,n){
		cin>>p;
		if(m[p]==1) m.erase(p);
		else m[p]=1;
		}
		cout<<m.size()<<nw;
	return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define inf 1000000000 //1E+9
using namespace std;

int main(){
	int n; long long k; cin>>n>>k;
	vector<pair<int,int>> p; p.resize(n);
	for(int i=0;i<n;i++)cin>>p[i].first>>p[i].second;
	sort(p.begin(),p.end());
	
	for(int i=0; i<n; i++){
		if(p[i].second >= k){ cout<<p[i].first<<endl; return 0; }
		k -= p[i].second;
	}

	return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define ull unsigned long long int
#define ll long long int
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define IO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
using namespace std;

const ll maxn = 1e5;
const ll inf = 1e18;
const double pi = acos(-1);

int main(){

    FAST;
    int n, k; cin >> n >> k;
    int arr[n]; ll dp[n];
    for(int i=0; i<n; i++)
        cin >> arr[i];

    for(int i=0; i<n; i++)
        dp[i]=0;

    for(int i=1; i<n; i++)
        {    
            ll cost=inf;
            for(int j=1; j<=k && j<=i; j++)
                cost=min(dp[i-j]+abs(arr[i]-arr[i-j]), cost);
            dp[i]=cost;
        }
    cout << dp[n-1];
    return 0;
}

Measured memory_bytes: 1408