akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007
ll dp1[100003][103];
ll dp2[100003][103];
ll arr[103];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("test.txt","r",stdin);
	ll n,k;
	cin>>n>>k;
	for(ll i=1;i<=n;i++)
		cin>>arr[i];
	for(ll i=0;i<=n;i++){
		dp1[0][i]=1;
		dp2[0][i]=1;
	}
	for(ll i=0;i<=k;i++)
		dp1[i][0]=0;
	for(ll i=1;i<=n;i++){
		dp2[1][i]=i+1;
		dp1[1][i]=i;
	}
	bool flag=false;
	for(ll i=1;i<=k;i++)
	{
		if(i>arr[1])
			flag=true;
		if(flag==false)
			dp1[i][1]=1;
		else
			dp1[i][1]=0;
		dp2[i][1]=((dp1[i][1]%mod)+(dp2[i-1][1]%mod))%mod;
	}
	/*for(ll i=1;i<=k;i++)
	{
		for(ll j=1;j<=n;j++)
			cout<<dp1[i][j]<<" ";
		cout<<endl;
	}*/
	for(ll i=2;i<=k;i++)
	{
		for(ll j=2;j<=n;j++){
			if(i<=arr[j]){
				dp1[i][j]=dp2[i][j-1];
				dp2[i][j]=((dp2[i-1][j]%mod)+(dp1[i][j]%mod))%mod;
			}
			else{
				dp1[i][j]=(dp2[i][j-1]-dp2[i-arr[j]-1][j-1]+mod)%mod;
				dp2[i][j]=((dp2[i-1][j]%mod)+(dp1[i][j]%mod))%mod;
			}
		}
	}
	/*for(ll i=1;i<=k;i++)
	{
		for(ll j=1;j<=n;j++)
			cout<<dp1[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
	for(ll i=1;i<=k;i++)
	{
		for(ll j=1;j<=n;j++)
			cout<<dp2[i][j]<<" ";
		cout<<endl;
	}*/
	cout<<dp1[k][n]<<endl;

}

Measured memory_bytes: 161152
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include<queue>
#include <sstream>
#include <set>
#include<stack>
#include <utility>
#include <tuple>
#define INF 1000000000000
const long long MOD = 998244353;

using namespace std;
typedef long long llong;
#define debug cout << "Hello" << endl;
//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

void dfs(llong prev_node, llong node, map<llong, llong> &Table, vector<llong> &ans, vector<vector<llong> > &graph){
    ans[node] += ans[prev_node];
    ans[node] += Table[node];
    for(int i=0; i<graph[node].size(); i++){
        dfs(node, graph[node][i], Table, ans, graph);
    }
    return;
}

int main(){
    llong N,Q;
    cin >> N >> Q;
    llong a,b;
    vector<vector<llong> > graph(N);
    vector<vector<llong> > directed_graph(N);
    vector<llong> ans(N, 0);
    map<llong, llong> Table;
    llong p,x;
    queue<llong> Queue;
    vector<bool> visited(N, false);
    llong node;

    for(int i=0; i<N-1; i++){
        cin >> a >> b;
        graph[a-1].push_back(b-1);
        graph[b-1].push_back(a-1);
    }
    for(int i=0; i<Q; i++){
        cin >> p >> x;
        Table[p-1] += x;
    }

    ans[0] += Table[0];

    Queue.push(0);

    while(!Queue.empty()){
        node = Queue.front();
        Queue.pop();
        visited[node] = true;
        for(int i=0; i<graph[node].size(); i++){
            if(visited[graph[node][i]]){
                continue;
            }
            Queue.push(graph[node][i]);
            directed_graph[node].push_back(graph[node][i]);
        }
    }
    for(int i=0; i<directed_graph[0].size(); i++){
        dfs(0, graph[0][i], Table, ans, directed_graph);
    }   
    for(int i=0; i<ans.size()-1; i++){
        cout << ans[i] << " ";
    }
    cout << ans[ans.size()-1] << endl;
    return 0;
}

Measured memory_bytes: 51364
#include<bits/stdc++.h>
#define F(i,x,y) for(int i=x;i<y;i++)
#define ll long long;
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  int c1=0,t=0;
  char ch;
  while(cin>>ch)
  {
    if(ch=='R')
    {
      c1++;
      if(c1>t)
        t=c1;
    }
    else
    {
      c1=0;
    }
  }
  cout<<t;
}

Measured memory_bytes: 3564
<?php

$stdins = [];
while($line=fgets(STDIN)){
    $stdins[] = trim($line);
}

$params = explode(" ", $stdins[0]);
$N = $params[0];
$X = $params[1];
$ms = array_slice($stdins, 1);
sort($ms);

$count = 0;
foreach($ms as $m){
    if($X >= $m){
        $X -= $m;
        $count++;
    }else{
        break;
    }
}
$min = $ms[0];
$count += intval($X / $min);

print("{$count}\n");

Measured memory_bytes: 3956
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int n = Integer.parseInt(sc.next());
    int[] a = new int[n];
    int[] b = new int[n];
    int[] c = new int[n - 1];
    for (int i = 0; i < n; i++) {
      a[i] = Integer.parseInt(sc.next());
    }
    for (int i = 0; i < n; i++) {
      b[i] = Integer.parseInt(sc.next());
    }
    for (int i = 0; i < n - 1; i++) {
      c[i] = Integer.parseInt(sc.next());
    }
    long ans = 0;
    int previous = -2;
    for (int i = 0; i < n; i++) {
      int an = a[i];
      ans += b[an - 1];
      if (previous + 1 == an) {
        ans += c[previous - 1];
      }
      previous = an;
    }
    pw.println(ans);
  }
}


Measured memory_bytes: 21716
import java.io.*;

class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// ??\????????????????????????
            String line = br.readLine();

            // ????????????????????´?????????
            // String line; // ??\???????????????????????\???
            // while ((line = br.readLine()) != null) {
            // processLine(line);
            // }
            
            double initialValue = 100000.0;

        	for( int i = 0 ; i < Integer.valueOf(line) ; i++ )
        	{
        	    double interest = initialValue * 0.05;
        	    initialValue = initialValue + interest;
        	    initialValue = initialValue / 1000;
        	    initialValue = Math.ceil(initialValue);
        	    initialValue = initialValue * 1000;
        	}
        	System.out.println((int)initialValue);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    // private static void processLine(String line) {
    // System.out.println(line);
    // }
}

Measured memory_bytes: 24088
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <math.h>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

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

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


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

	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector<int> l(q), r(q);
	rep(i, q) {
		cin >> l[i] >> r[i];
	}

	// 累積和
	vector<int> sum(n, 0);
	sum[0] = 0;
	Rep(i, 1, n) {
		if (s[i] == 'C' && s[i - 1] == 'A') {
			sum[i] = sum[i - 1] + 1;
		}
		else {
			sum[i] = sum[i - 1];
		}
	}


	rep(i, q) {
		int ans = 0;
		if (l[i] - 2 < 0) {
			ans = sum[r[i] - 1];
		}
		else {
			ans = sum[r[i] - 1] - sum[l[i] - 1];
		}
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 2256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <vector>

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

using namespace std;

int main(void) {
	int s=700;
	int i;
	char a;
	REP(i,3) {
		scanf("%c", &a);
		if (a == 'o') s+=100;
	}
	printf("%d\n",s);
	return 0;
}


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

using namespace std;

int main(void) {
  int n;
  cin >> n;
  int l[n];
  int r[n];
  for(int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
  }

  long long sum = 0;
  for(int i = 0; i < n; i++) {
    sum += r[i] - l[i] + 1;
  }
  cout << sum << endl;
}

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

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

using namespace std;
using ll = long long;
using P = pair<int,int>;


void calc_primefactorization(long long in, vector<vector<long long> >& out){
	
	long long N = in, Ntmp;
	long long p,e,p_init = 2;
	vector<long long> out_tmp(2);
	
	if( in == 1 ){
		out_tmp[0] = 1;
		out_tmp[1] = 1;
	}
	else{
		while( 1 ){

			Ntmp = N;
				
			p = N;
			e = 1;

			for(long long i = p_init;i * i <= N;i++){
						
				if( Ntmp % i == 0 ){
					e = 0;
					while( 1 ){
						if( Ntmp % i != 0 ){
							break;
						}
						else{
							Ntmp = Ntmp / i;
							e++;
						}
					}
					p = i;
					break;
				}
				
			}
			
			out_tmp[0] = p;
			out_tmp[1] = e;
			out.push_back(out_tmp);
			
			for(int i = 0;i < e;i++){
				N = N / p;
			}
			
			if( N == 1 ){
				break;
			}
			
		}
	}
	
}


int main(){
	
	int N;
	
	cin >> N;
	
	if( N % 1000 == 0 ){
		cout << 0;
	}
	else{
		cout << 1000 - N % 1000;
	}
	
	
	return 0;
	
}


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

int main() {
    int n;
    int a[110];
    double b = 1;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b *= a[i];
    }

    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += b / a[i];
    }

    double result = b / sum;
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll s[100000];
ll t[100000];
int sL[100000], sR[100000];
int tL[100000], tR[100000];
int main() {
	int A, B, Q;
	cin >> A >> B >> Q;
	for (int i = 0; i < A; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < B; i++) {
		cin >> t[i];
	}
	for (int i = 0; i < A; i++) {
		sL[i] = upper_bound(t, t + B, s[i]) - t - 1;
		sR[i] = lower_bound(t, t + B, s[i]) - t;
	}
	for (int i = 0; i < B; i++) {
		tL[i] = upper_bound(s, s + A, t[i]) - s - 1;
		tR[i] = lower_bound(s, s + A, t[i]) - s;
	}
	for (int i = 0; i < Q; i++) {
		ll ans = 1LL << 60;
		ll x;
		cin >> x;
		int idx = lower_bound(s, s + A, x) - s;
		if (idx < A) {
			if (sL[idx] >= 0) ans = min(ans, abs(x - s[idx]) + abs(s[idx] - t[sL[idx]]));
			if (sR[idx] < B) ans = min(ans, abs(x - s[idx]) + abs(s[idx] - t[sR[idx]]));
		}
		idx = upper_bound(s, s + A, x) - s - 1;
		if (idx >= 0) {
			if (sL[idx] >= 0) ans = min(ans, abs(x - s[idx]) + abs(s[idx] - t[sL[idx]]));
			if (sR[idx] < B) ans = min(ans, abs(x - s[idx]) + abs(s[idx] - t[sR[idx]]));
		}
		idx = lower_bound(t, t + B, x) - t;
		if (idx < B) {
			if (tL[idx] >= 0) ans = min(ans, abs(x - t[idx]) + abs(t[idx] - s[tL[idx]]));
			if (tR[idx] < A) ans = min(ans, abs(x - t[idx]) + abs(t[idx] - s[tR[idx]]));
		}
		idx = upper_bound(t, t + B, x) - t - 1;
		if (idx >= 0) {
			if (tL[idx] >= 0) ans = min(ans, abs(x - t[idx]) + abs(t[idx] - s[tL[idx]]));
			if (tR[idx] < A) ans = min(ans, abs(x - t[idx]) + abs(t[idx] - s[tR[idx]]));
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 4480
import java.util.*;
import java.lang.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int xi[] = new int[n];
        int yi[] = new int[m];
        for(int i = 0; i < n; i++){
            xi[i] = sc.nextInt();
        }
        for(int i = 0; i < m; i++){
            yi[i] = sc.nextInt();
        }
        int xmax = -100;
        for(int i = 0; i < n; i++){
            xmax = Math.max(xi[i], xmax);
        }
        int ymin = 100;
        for(int i = 0; i < m; i++){
            ymin = Math.min(yi[i], ymin);
        }
        if (x < y) {
            if (xmax < ymin && xmax < y && ymin > x) {
                System.out.println("No War");
            }
            else{
                System.out.println("War");
            }
        }else{
            System.out.println("War");
        }
    }
}

Measured memory_bytes: 23892
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
int i,j,k,n,m;
string s;

int main() {
  cin>>s;
  int out =0;
  for(i=0;i<s.size()-1;++i)if(s.substr(i,1)!=s.substr(i+1,1)) ++out;
  cout << out << endl;
  return 0;
}


Measured memory_bytes: 512
list = [int(input()) for i in range(5)]
kList = []
for j in range(0,10):
    for i in list:
         if (i+j) % 10 == 0:
            if len(kList) < 4:
                kList.append(i+j)
            else:
                kList.append(i)
print(sum(kList))

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

typedef long long ll;
#define PI 3.1415926535897932384626433
#define MOD 1000000007

int main(){
    int n;
    cin >> n;
    int p[n];
    for (int i = 0; i < n; i++){
        cin >> p[i];
    }

    int cnt = 0;
    for (int i = 1; i < n - 1; i++){
        if(p[i] > p[i-1] && p[i] < p[i+1]){
            cnt++;
        }
        if(p[i] < p[i-1] && p[i] > p[i+1]){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
'use strict'

function Main(input){
  input=input.trim().split(/\s+/).map(x=>x-0);
  var N=input.shift();
  var abs=input.map(x=>Math.abs(x));
  var sign=input.reduce((a,c)=>a*Math.sign(c),1);
  var ans=abs.reduce((a,c)=>a+c)-2*((sign===-1)?abs.reduce((a,c)=>Math.min(a,c)):0);
  console.log(ans);
}

Main(require('fs').readFileSync('/dev/stdin','utf8'));


Measured memory_bytes: 26776
#pragma region header
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define ts to_string
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector <string>
#define vvs vector <vector<string>>
#define pq  priority_queue<int>
using ll = long long;
/* ----------------よく使う数字や配列----------------- */
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
const int INF = 2000000000;
constexpr ll mod = 1e9 + 7;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
bool isprime(ll a)//素数判定、primeならtrue,違うならfalse
{
    if (a < 2) return false;
    else if (a == 2) return true;
    else if (a % 2 == 0) return false;
    double m = sqrt(a);
    for (int i = 3; i <= m; i += 2)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    // 素数である
    return true;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
ll kind(vi SYURUI) {//vector<int>型の配列の要素の種類数
    int size = SYURUI.size();
    sort(all(SYURUI));
    int cnt = 1;
    rep(i, size-1) {
        if (SYURUI[i] != SYURUI[i + 1])cnt++;
    }
    return cnt;
}
/* ----------------------end----------------------- */
#pragma endregion
signed main() {
    int A, B, C, D; cin >> A >> B >> C >> D;
    vi N = { A,B,C,D };
    int a=0, b=0, c=0, d=0;
    rep(i, 4) {
        if (N[i] == 1)a++;
        else if (N[i] == 9)b++;
        else if (N[i] == 7)c++;
        else if (N[i] == 4)d++;
    }
    if (a == 1 && b == 1 && c == 1 && d == 1)puts("YES");
    else puts("NO");
}






Measured memory_bytes: 3692
import java.util.*;
import java.lang.*;


public class Main {
    static int a[];
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int q = sc.nextInt();
        int com[] = new int[q];
        int x[] = new int[q];
        int y[] = new int[q];
        for (int i = 0; i < q; i++) {
            com[i] = sc.nextInt();
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        int m = 0;
        while (Math.pow(2, m) < n) {
            m++;
        }
        n = (int)Math.pow(2, m);
        a = new int[2 * n - 1];
        for (int i = 0; i < 2 * n - 1; i++) {
            a[i] = 2147483647;
        }

        for (int i = 0; i < q; i++) {
            if (com[i] == 0) {
                update(x[i], y[i]);
            } else {
                System.out.println(find(x[i], y[i] + 1, 0, n, 0));
            }
        }
    }
    static void update (int i, int x) {
        a[i + n - 1] = x;
        int k = i + n - 1;
        while (k > 0) {
            a[(k - 1) / 2] = Math.min(a[(k - 1) / 2 * 2 + 1], a[(k - 1) / 2 * 2 + 2]);
            k = (k - 1) / 2;
        }
    }
    static int find (int s, int t, int c, int d, int k) {
        if (t <= c || s >= d) {
            return 2147483647;
        }
        if (s <= c && t >= d) {
            return a[k];
        }
        int m = (c + d) / 2;
        return Math.min(find(s, t, c, m, 2 * k + 1), find(s, t, m, d, 2 * k + 2));
    }
}



Measured memory_bytes: 103892
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int K = sc.nextInt();
    int X = sc.nextInt();

    if(500*K >= X){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
   
}
}


Measured memory_bytes: 21460
#include<iostream>
#include<string>

using namespace std;

int main()
{
	string str;
	int n,i,j;
	
	cin >> n;
	
	for(i=0;i<=n;i++)
	{
		getline(cin,str);
		
		if(i!=0)
		{
			for(;;)
			{
				if(str.find("Hoshino")<str.size())
					str[str.find("Hoshino")+6]='a';
				else
					break;
			}
			cout << str << endl;
		}
	}
}

Measured memory_bytes: 0
#include<stdio.h>

int main(void) {
    int n;
    int i;
    scanf("%d", &n);
    int a[n];
    int kind[8];
    int master = 0;
    int target;
    for(i - 0; i < 8; i++) {
        kind[i] = 0;
    }
    for(i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for(i = 0; i < n; i++) {
        target = a[i] / 400;
        switch(target) {
            case 0:
                kind[0] = 1;
                break;
            case 1:
                kind[1] = 1;
                break;
            case 2:
                kind[2] = 1;
                break;
            case 3:
                kind[3] = 1;
                break;
            case 4:
                kind[4] = 1;
                break;
            case 5:
                kind[5] = 1;
                break;
            case 6:
                kind[6] = 1;
                break;
            case 7:
                kind[7] = 1;
                break;
            default:
                master++;
                break;
        }
    }
    int counter = 0;
    for(i = 0; i < 8; i++) {
        if(kind[i] == 1) {
            counter++;
        }
    }
    if(counter == 0) {
        counter++;
        master--;
    }
    printf("%d %d\n", counter, counter + master);
}


Measured memory_bytes: 128
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(m)]

if m % 2 == 1:
    print(-1)
    exit()

E = [[] for i in range(n + 1)]
used_e = [False] * m
ans = []

for i, (a, b) in enumerate(A):
    E[a].append((b, i))
    E[b].append((a, i))

used = [False] * (n + 1)

def dfs(prev, v):
    if used[v]:
        return
    used[v] = True
    cnt = 0

    for to, i in E[v]:
        dfs(v, to)
        if not used_e[i]:
            cnt += 1

    for to, i in E[v]:
        if cnt % 2 == 1 and to == prev:
            continue
        if not used_e[i]:
            ans.append((v, to))
            used_e[i] = True

dfs(0, 1)

for a in ans:
    print(*a)

Measured memory_bytes: 141024
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void){
	
	char a[10], b[10], c[10];
	int n, m;
	int i, flag;
	
	scanf("%s",a);
	scanf("%s",b);
	scanf("%d",&n);
	scanf("%d",&m);
	scanf("%s",c);
	
	flag = 0;
	
 while(a[i]!='\0' && c[i]!='\0'){
    if(a[i]!=c[i]){
      flag=1;
      break;
    }
    i++;
  }	
	
	if(flag == 0) n -= 1;
	else m -= 1;
	
	printf("%d\t%d\n",n,m);	
	return 0;
}



Measured memory_bytes: 128
def main():
    T = input()
    T = T.replace('?', 'D')
    print(T)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Measured memory_bytes: 9324
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;

typedef long long ll;


long long fac[MAX], finv[MAX], inv[MAX];


void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}







int main(){
int N,K; cin >> N >> K;
  COMinit();

  for(int i = 1; i <= K; i++){

   cout <<  (COM(K-1,i-1) * COM ( N-K + 1, i)) % MOD << endl;}
   
  
   return 0;}

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

#define LSOne(S) ((S) & (-S))

#define EPS 1e-6
#define MOD 1000000007

#define fi first
#define se second
#define pb push_back
#define ende '\n'

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mset(x, y) memset(&x, (y), sizeof(x))

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
	vector<vi> A = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
	int n;
	int bi;
	vi m;
	m.assign(9, 0);
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			cin >> A[i][j];
	cin >> n;
	while (cin >> bi) {
		int flag = 0;
		for (int i = 0; i< 3; i++)
			for (int j = 0; j < 3; j++)
				if (A[i][j] == bi)
					m[i*3+j] = 1;
	}
	if ((m[0]+m[1]+m[2] == 3) ||
			(m[0]+m[3]+m[6] == 3) ||
			(m[0]+m[4]+m[8] == 3) ||
			(m[1]+m[4]+m[7] == 3) ||
			(m[2]+m[4]+m[6] == 3) ||
			(m[2]+m[5]+m[8] == 3) ||
			(m[3]+m[4]+m[5] == 3) ||
			(m[6]+m[7]+m[8] == 3))
		cout << "Yes" << ende;
	else
		cout << "No" << ende;
  return 0;
}


Measured memory_bytes: 256
local t = {}
while true do
	local c = io.read(1)
	if c == 'B' or c == 'W' then
		table.insert(t, c)
	else
		break
	end
end
local rmax = #t
local count = 0
for i=#t,1,-1 do
	local c = t[i]
	if c == 'B' then
		count = count + rmax - i
		rmax = rmax - 1
	end
end
print(count)


Measured memory_bytes: 4724
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

n = ni()
d = list(li())

mod = 998244353
dcnt = Counter(d)

# 正常か判断
def judge(n, d, dcnt):
    # 頂点1が0でないならNG
    for i in range(n):
        if i == 0 and d[i] != 0:
            return False
        if i > 0 and d[i] == 0:
            return False

    # keyが連続でなければNG
    dcnt_keys = sorted(list((dcnt.keys())))
    for i in range(len(dcnt_keys) - 1):
        if dcnt_keys[i+1] - dcnt_keys[i] != 1:
            return False

    return True

# dp
def dp(dcnt, mod):
    maxdepth = max(dcnt.keys())
    dp = [0]*(maxdepth+1)
    dp[0] = 1
    for depth in range(1, maxdepth+1):
        dp[depth] = dp[depth-1] * pow(dcnt[depth-1], dcnt[depth], mod)
        dp[depth] %= mod

    return dp[maxdepth]

if judge(n, d, dcnt):
    print(dp(dcnt, mod))
else:
    print(0)

Measured memory_bytes: 20000
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using namespace std;
int main(){
    int n,rcon=0,wcon=0;
    cin>>n;
    char s[n];
    rep(i,n){
        cin>>s[i];
        if(s[i]=='R')rcon++;
    }
    rep(i,rcon){
        if(s[i]=='W')wcon++;
    }
    cout<<min(rcon,wcon)<<endl;
    }

Measured memory_bytes: 3780
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
	int a,b,mato[1000];
	vector<int> nums;
	while(scanf("%d%d",&a,&b),a,b){
		int res=0;
		for(int i=0;i<a;i++){scanf("%d",mato+i);}
		nums.clear();
		for(int i=0;i<=a;i++){
			for(int j=0;j<=a;j++){
				int r=0;
				if(i!=a)r+=mato[i];
				if(j!=a)r+=mato[j];
				nums.push_back(r);
			}
		}
		sort(nums.begin(),nums.end());
		vector<int>::iterator it=nums.begin();
		while(it!=nums.end()){
			if(b-*it<0)break;
			vector<int>::iterator itt=upper_bound(nums.begin(),nums.end(),b-*it);
			itt--;
			res=max(res,*it+*itt);
			it++;
		}
		printf("%d\n",res);
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(void)
{
	int i;
	int num;
	int money = 100000;
	
	scanf("%d", &num);
	
	for(i=0; i<num; i++){
		money = money * 1.05;
		if((money % 1000) > 0) money = (money - (money % 1000)) + 1000;
		//
		
		
	}

	printf("%d\n", money);

	return 0;
}

Measured memory_bytes: 592
from math import *

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

def lcm(x,y):
    return x*y//gcd(x,y)
n = int(input())
a = [int(x) for x in input().split()]

mod = 1000000000+7

k = 1
for x in a:
    k = lcm(k,x)

ans = 0

for x in a:
    ans += k//x

print(ans%mod)


Measured memory_bytes: 10112
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 1e9
typedef long long ll;

int main()
{
    int n;
    cin>>n;
    vector<int> h(n);
    REP(i,n) cin>>h[i];

    h.push_back(0);

    int v=0;
    REP(i,n) if(h[i]>h[i+1]) v+=h[i]-h[i+1];

    cout<<v<<endl;

	return 0; 
}


Measured memory_bytes: 256
program main
  implicit none
  integer :: n, k, j
  real(8) :: res
  read (*, *) n, k
  res = 0.0d0
  do j = 1, n
    res = res + 0.5d0 ** d(j, k)
  end do
  write (*, "(f12.10)") res / dble(n)
  contains
  pure integer function d(j, k)
    integer, intent(in) :: j, k
    do d = 0, 100
      if (2 ** d * j >= k) return
    end do
  end function d
end program main



Measured memory_bytes: 384
S = input()
first_half = int(S[:2])
second_half = int(S[2:])

if 1 <= first_half <= 12 and 1 <= second_half <= 12:
    print('AMBIGUOUS')
elif not 1 <= first_half <= 12 and 1 <= second_half <= 12:
    print('YYMM')
elif 1 <= first_half <= 12 and not 1 <= second_half <= 12:
    print('MMYY')
else:
    print('NA')


Measured memory_bytes: 2940
n, a, b = map(int, input().split())
list_ans = []
for i in range(n+1):
	list1 = []
	d = i
	while i >= 1:
		c = i % 10
		i = i//10
		list1.append(c)
	counter = sum(list1)
	if a <= counter <= b:
		list_ans.append(d)
print(sum(list_ans))

Measured memory_bytes: 3292
#include<iostream>
using namespace std;
int main(){
	int n,m;
	cin>>n;
	int t[n];
	for(int i=1;i<=n;i++)
	{
		cin>>t[i];
	}
	cin>>m;
	int p,x;
	while(m--){
		cin>>p;
		cin>>x;
		
			int result=0;
			for(int i=1;i<=n;i++)
			{
				result=result+t[i];
			}
			cout<<result-t[p]+x<<endl;	
	}


	return 0;
}

Measured memory_bytes: 256
XS = list(map(int, open(0).read().split()))
for i in range(0, len(XS), 2):
    H = XS[i]
    W = XS[i+1]
    if H == 0 and W == 0:
        break
    print("#"*W)
    for _ in range(H-2):
        print("#{}#".format("." * (W-2)))
    print("#"*W)
    print("")


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

int main(){
    int n,a[100];
    cin >> n ;
    
    for(int i=0; i<n; i++) cin >>a[i];
    
    for(int j=n-1; j>=0; j--){
        if(j!=n-1) cout<< " ";
           cout << a[j] ; 
        
        
    }
    cout << endl;
    return 0;
}


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

int main() {
  int x, a, b;
  cin >> x >> a >> b;
  int ans = (x -a) % b;
  cout << ans << endl;
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323
#define ll long long int
#define vi vector <int>
#define vl vector <ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define MOD 1000000007
ll power(ll a, ll b) { //a^b
	ll res = 1;
	a = a % MOD;
	while (b > 0) {
		if (b & 1) {res = (res * a) % MOD; b--;}
		a = (a * a) % MOD;
		b >>= 1;
	}
	return res;
}

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

int main() {
#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a,b,c;
	cin>>a>>b>>c;
	ll d,k;
	cin>>k;
	d=0;
	while(b<=a){
		b=b*2;
		d++;
	}
	while(c<=b){
		c=c*2;
		d++;
	}
	if(d<=k)
		cout<<"Yes";
	else
		cout<<"No";
}

Measured memory_bytes: 3608
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            Point[] points = new Point[n];

            double sum = 0.0;
            for (int i = 0; i < n; i++)
            {
                double[] input = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse);
                points[i] = new Point(input[0], input[1]);

                if (i != 0) sum += (points[i - 1] - points[0]).Cross(points[i] - points[0]);
            }
            Console.WriteLine("{0:f1}", sum / 2);
        }
    }

    class Point : IComparable<Point>
    {
        static readonly double EPS = 1E-10;

        internal double x, y;

        public Point(double x, double y)
        {
            this.x = x;
            this.y = y;
        }

        public double Abs { get { return Math.Sqrt(Norm); } }
        public double Norm { get { return x * x + y * y; } }

        public double Dot(Point p) { return x * p.x + y * p.y; }
        public double Cross(Point p) { return x * p.y - y * p.x; }

        public static Point operator +(Point a, Point b) { return new Point(a.x + b.x, a.y + b.y); }
        public static Point operator -(Point a, Point b) { return new Point(a.x - b.x, a.y - b.y); }
        public static Point operator *(Point p, double d) { return new Point(p.x * d, p.y * d); }
        public static Point operator /(Point p, double d) { return new Point(p.x / d, p.y / d); }
        public static bool operator <(Point a, Point b) { return Math.Abs(a.x - b.x) > EPS ? a.x < b.x : a.y < b.y; }
        public static bool operator >(Point a, Point b) { return Math.Abs(a.x - b.x) > EPS ? a.x > b.x : a.y > b.y; }
        public static bool operator ==(Point a, Point b) { return Math.Abs(a.x - b.x) < EPS && Math.Abs(a.y - b.y) < EPS; }
        public static bool operator !=(Point a, Point b) { return Math.Abs(a.x - b.x) >= EPS || Math.Abs(a.y - b.y) >= EPS; }

        public int CompareTo(Point other)
        {
            return x != other.x ? (int)(x - other.x) : (int)(y - other.y);
        }

        public override bool Equals(object obj)
        {
            Point other = obj as Point;
            return Math.Abs(x - other.x) < EPS && Math.Abs(y - other.y) < EPS;
        }

        public override int GetHashCode()
        {
            return x.GetHashCode() ^ y.GetHashCode();
        }

        public override string ToString()
        {
            return string.Format("{0:f10} {1:f10}", x, y);
        }
    }

    class Segment
    {
        internal Point p1, p2;

        public Segment(Point p1, Point p2)
        {
            this.p1 = p1;
            this.p2 = p2;
        }
    }

    class Circle
    {
        internal Point p;
        internal double r;

        public Circle(Point p, double r)
        {
            this.p = p;
            this.r = r;
        }
    }
}

Measured memory_bytes: 9324
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  n = int(input())

  for i in range(9, 0, -1):
    if n % i == 0 and n // i < 10:
      print('Yes')
      return

  print('No')


if __name__ == '__main__':
  main()


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

int main(){
    int N;
    cin >> N;
    int count = 0;
    for(int i = 1; i <= N; i++){
        string s = to_string(i);
        if(s.size() % 2 == 1){
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>


int main(){
  int K; cin >> K;
  queue<ll> Q;
  rep(i,9) Q.push(i+1);

  ll x;
  for (int i=1;i<=K;i++) {
    x = Q.front(); Q.pop();
    if (i==K) break;
    if (x%10!=0) Q.push(10*x+x%10-1);
    Q.push(10*x+x%10);
    if (x%10!=9) Q.push(10*x+x%10+1);
  }
  cout << x << endl;

  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 5100
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007

using namespace std;
typedef long long ll;

int main()
{
	int n;
	cin >> n;
	
	int cards[n];
	
	for (int i = 0; i < n; i++)
	{
		cin >> cards[i];
	}
	
	sort(cards, cards + n);
	reverse(cards, cards + n);
	
	int ans = 0;
	
	for (int i = 0; i < n; i++)
	{
		if (i % 2 == 0)
		{
			ans += cards[i];
		}
		else
		{
			ans -= cards[i];
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

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

	int main() {
	#ifdef LOCAL_DEFINE
		// freopen("data.in", "rt", stdin);
		// freopen("data.out", "w", stdout);
		auto _start = chrono::high_resolution_clock::now();
	#endif

		ios::sync_with_stdio(false);
		cin.tie(0);
		cout << fixed << setprecision(15);
		int n, m;
		cin >> n >> m;
		vector<vector<int>> g(n);
		for(int i = 0; i < m; i++) {
			int x, y;
			cin >> x >> y;
			x--; y--;
			g[x].push_back(y);
		}
		vector<int> dp(n), vis(n);
		vector<int> topo;
		function<void(int)> dfs = [&](int u) {
			vis[u] = 1;
			for(int v : g[u]) {
				if(vis[v]) continue;
				dfs(v);
			}
			topo.push_back(u);
			vis[u] = 2;
		};
		for(int i = 0; i < n; i++) {
			if(vis[i]) continue;
			dfs(i);
		}
		reverse(topo.begin(), topo.end());
		int ans = 0;
		for(int i = 0; i < n; i++) {
			int u = topo[i];
			for(int v : g[u]) {
				dp[v] = max(dp[v], dp[u] + 1);
			}
		}
		for(int i = 0; i < n; i++) {
			ans = max(ans, dp[i]);
		}
		cout << ans << '\n';

	#ifdef LOCAL_DEFINE
		auto _end = chrono::high_resolution_clock::now();
		cerr << "elapsed time: " << chrono::duration<double, milli>(_end - _start).count() << " ms\n";
	#endif
		return 0;
	}

Measured memory_bytes: 9212
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    Al,Aa,Bl,Ba = map(int,input().strip().split())
    while True:
        Bl -= Aa
        if Bl<=0:
            print("Yes")
            return
        Al -= Ba
        if Al <= 0:
            print("No")
            return

if __name__ == '__main__':
    main()

Measured memory_bytes: 78380
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    name = {}
    for al in range(ord('A'), ord('Z') + 1):
        name[chr(al)] = 0
    for n in range(N):
        name[iss()[0]] += 1
    print(sum([name[a] * name[b] * name[c] for a, b, c in itertools.combinations(['M', 'A', 'R', 'C', 'H'], 3)]))


if __name__ == '__main__':
    main()


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

int main(){
  map<string,int> count;
  string blue;
  int N;
  cin>>N;
  for (int i=0;i<N;i++){
    cin>>blue;
    count[blue]++;
  }
  cin>>N;
  string red;
  for (int i=0;i<N;i++){
    cin>>red;
    count[red]--;
  }
  int point=0;
  for (auto itr = count.begin(); itr != count.end(); ++itr) {
        point=max(point,itr->second);
  }
  cout<<point<<endl;
}

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

using namespace std;

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// 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();
}

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

const int MAX = 1000100;

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

  vector<int> dp(MAX, INF), odddp(MAX, INF);
  dp[0] = odddp[0] = 0;
  for (int i = 1;; i++) {
    int num = i * (i + 1) * (i + 2) / 6;
    if (num >= MAX) break;
    for (int j = num; j < MAX; j++) {
      dp[j] = min(dp[j], dp[j - num] + 1);
      if (num & 1) odddp[j] = min(odddp[j], odddp[j - num] + 1);
    }
  }

  int n;
  while (cin >> n) {
    if (n == 0) break;
    cout << dp[n] << " " << odddp[n] << "\n";
  }

  return 0;
}


Measured memory_bytes: 10584
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = long long;
using ldb = long double;
using pa = pair < ll, ll >;
using vec = vector < ll >;
 
template < typename T > using index_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#define pb push_back
#define po pop_back
#define mp make_pair
#define mt make_tuple
#define F  first
#define S  second
#define f(i,x,n) for(ll i=x;i<n;i++) 
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))
#define all(c) c.begin(),c.end()
#define str string
#define edl "\n"
#define add insert
#define cot continue
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


const int MOD = 1e9 + 7, INF = INT_MAX, N = 1e5 + 10;
const double PI = acos(-1);
const ll LINF = LLONG_MAX;
vec dp(100002,INT_MAX);ll q[100001],n,k;




int main() 
{

    fast();
      
    // #ifndef ONLINE_JUDGE
    //         freopen("input.txt", "r", stdin);
    //         freopen("output.txt","w",stdout);
    // #endif
    cin>>n>>k;
    f(i,0,n)
    {
        cin>>q[i];
    }
    dp[0]=0;
    f(i,0,n)
    {
        for(ll j=i+1;j<=i+k&&j<n;j++)
        {
            dp[j]=min(dp[j],dp[i]+abs(q[i]-q[j]));
        }
    }
    cout<<dp[n-1];


  

    cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
    return 0;
}


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

int n, x, sol;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        if(x % 2 && i % 2) {
            sol++;
        }
    }
    cout << sol;
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
typedef vector<int> VI;
typedef vector<ll> VLL;

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

    if(abs(a-b)% 2 != 0 ){
        cout << "IMPOSSIBLE" << endl;
        return 0; 
    }else{
        ll mi = min(a,b);
        ll tmp = abs(a-b)/2;
        cout << mi + tmp << endl;
        return 0;
    }

}

Measured memory_bytes: 256
a,b,c,d = list(map(int, input().split()))
if c%b==0:
    x=c//b
else:
    x=c//b+1
if a%d==0:
    y=a//d
else:
    y=a//d+1
if y<x:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 9120
#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define BIT(b, i) (((b) >> (i)) & 1)
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

ll pow(int x, int n){
  return n == 0 ? 1 : x * pow(x, n - 1);
}


/*
n
a1 ... an

n 10^5
ai 10^9

Yes
No
 */
int n,a[100000];
int b[3]; //0:odd 1:even 2:multi4

int main(){
  cin>>n;
  REP(i,n){
    cin>>a[i];
    if(a[i]%4==0){
      b[2]++;
    } else if(a[i]%2==0){
      b[1]++;
    } else {
      b[0]++;
    }
  }

  if(b[0]<=b[2] || (b[0]==b[2]+1 && b[1]==0)){
    cout<<"Yes\n";
  }  else {
    cout <<"No\n";
  }

  return 0;
}


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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

int main() {

    long long int n, m;
    cin >> n >> m;

    long long int s = 0;
    for ( long long int i = 0; i < m; i++ ) {
        long long int in;
        cin >> in;
        s += in;
    }
    if ( s > n ) {
        cout << -1 << endl;
    } else {
        cout << n - s << endl;
    }

    return 0;

}


Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main(){
	int price, priceAll;
	while(cin >> priceAll){
		if(priceAll==0) break;
		for(int i=0; i<9; i++){
			cin >> price;
			priceAll-=price;
		}
		cout << priceAll << endl;
	}
	return 0;
}

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

using namespace std;

#define pb push_back
const int maxi = 1e6 + 10;
int a[maxi];
string s;
int n;
int p[maxi];
int cnt[maxi];
set<pair<int,int>> st;
set<int> st1;
int ob[maxi];
int ans[maxi];
vector<int> v[maxi];

int lex()
{
    if (ans[1]==0) return 1;

    for (int i=1;i<=n;i++)
        if (ans[i]>p[i]) return 1; else
            if (ans[i]<p[i]) return 0;
    return 0;
}
int main()
{
    cin>>n;

    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
        v[a[i]].pb(i);
    }


   for (int i=1;i<=n;i++)
   {
       st.insert({-cnt[i], i});
       st1.insert(i);
   }

   int cur = 0;
   int pr = 0;

   if (n==2) return !printf("-1\n");

   while(!st1.empty())
   {
       pair<int,int> node = *st.begin();
       if (-node.first == n - cur - 1)
       {
           p[++cur]  = node.second;
           st.erase(node);
           st1.erase(node.second);
       } else
       {
           int node1 = *st1.begin();
           st1.erase(node1);
           int node2 = 0;

           if (a[pr] ==  node1)
           {
              if (!st1.empty()){
              int node2 = *st1.begin();
              st1.erase(node2);
              st1.insert(node1);
              node1 = node2;
           }
          }

           p[++cur] = node1;
           st.erase({-cnt[node1], node1});
       }

       ob[p[cur]] = 1;

      if (!ob[a[p[cur]]])
      {
          st.erase({-cnt[a[p[cur]]], a[p[cur]]});
          cnt[a[p[cur]]]--;
          st.insert({-cnt[a[p[cur]]], a[p[cur]]});
      }

      pr = p[cur];
   }

   do
   {
       int ok = 1;
      for (int i=1;i<n;i++)
        if (p[i+1] == a[p[i]]) ok = 0;

     if (lex() && ok)
     {
         for (int i=1;i<=n;i++)
            ans[i] = p[i];
     }

   } while(next_permutation(p+n-2, p+n+1));

    for (int i=1;i<=n;i++)
        printf("%d ",ans[i]);

    return 0;
}
//A ja bih se s tobom topila,
//al ne bih ti to priznala,
//da nisam popila.
//A ti,bas je dobro sto si tu,
//daj slobodno pokazi mi,
//taj skriveni tattoo.


Measured memory_bytes: 46080
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define COUT(a) cout << a;
#define ENDL cout << "\n";
int main() {
    int a,b;
    char s;
    scanf("%d %c %d\n",&a, &s,&b);
    if(s == '+') COUT(a+b)
    else if(s == '-') COUT(a-b)
}

Measured memory_bytes: 888