akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
struct PP {int k,t,x,y;};
int dx[9]={-1,-1,-1,0,0,0,1,1,1},dy[9]={-1,0,1,-1,0,1,-1,0,1};
bool check(int n,int m,int x,int y) {return x>=0&&x<n&&y>=0&&y<m;}
int main() {
  int h,w,n,sx,sy,ans=-1,t=0;
  cin >> h >> w >> n >> sx >> sy;
  sx--,sy--;
  vector<P> v[n];
  queue<PP> que;
  bool d[41][1<<n][h][w];
  memset(d,0,sizeof(d));
  for(int i=0,m; i<n; i++) {
    cin >> m;
    for(int j=0,x,y; j<m; j++) {
      cin >> x >> y;
      x--,y--;
      if(!j && x==sx && y==sy) t|=1<<i;
      v[i].push_back(P(x,y));
    }
  }
  d[0][t][sx][sy]=1;
  que.push((PP){0,t,sx,sy});
  while(!que.empty()) {
    PP p=que.front();que.pop();
    int kk=p.k,tt=p.t,nx=p.x,ny=p.y;
    if(tt==(1<<n)-1) {
      if(ans==-1) ans=kk;
      else ans=min(ans,kk);
      continue;
    }
    for(int i=0; i<9; i++) {
      int x=nx+dx[i],y=ny+dy[i],k=kk+1,t=tt,f=1;
      if(!check(h,w,x,y)) continue;
      for(int j=0; j<n; j++) {
        if(v[j][v[j].size()-1].first==x&&v[j][v[j].size()-1].second==y) f=0;
        if(t&(1<<j)) continue;
        if(v[j].size()-1<=k) f=0;
        else if(v[j][k].first==x&&v[j][k].second==y) t|=1<<j;
      }
      if(f && !d[k][t][x][y]) {
        d[k][t][x][y]=1;
        que.push((PP){k,t,x,y});
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3804
#include<bits/stdc++.h>
using namespace std;
int main(){
     string N ;
     cin >> N;
    int n = N.size();
    int count = 0;
    for(int i=0;i<n;i++){
        count += N[i]-'0';
    }

    if(count%9==0)cout<<"Yes";
    else cout <<"No";


}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int N, D, A;
pair<int, int> p[maxn];
int main() {
	cin>>N>>D>>A;
	for(int i = 1; i <= N; ++i) {
		cin>>p[i].first>>p[i].second;
		p[i].second = (p[i].second + A - 1) / A;
	}
	sort(p + 1, p + N + 1);
	int cnt = 0;
	long long ans = 0;
	for(int i = 1, j = 1; i <= N; ++i) {
		while(p[i].first - p[j].first > 2 * D) {
			cnt -= p[j].second;
			++j;
		}
		ans += max(0, p[i].second - cnt);
		p[i].second = max(0, p[i].second - cnt);
		cnt += p[i].second;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
res = []
import string
sam = string.ascii_lowercase

for mak in sam : res.append([mak,0])

import fileinput
for mak in fileinput.input() :
    for tem in mak.lower() :
        num = sam.find(tem)
        if num != -1 : res[num][1] += 1
        
for mak in range(26) : print('{} : {}'.format(res[mak][0],res[mak][1]))

Measured memory_bytes: 7972
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = long.Parse(Console.ReadLine());

        var array = Console.ReadLine().Split(' ');


        long amount = 0;
        long sum = 0;

        for(var i = 0; i< input; i++)
        {
            
            sum += long.Parse(array[i]);

            if (i % 2 == 1)
            {
                amount += long.Parse(array[i]);
            }
        }

        var list = new List<long>();
        var first = sum - (amount * 2);
        list.Add(first);

        for (var i = 1; i < input; i++)
        {
            list.Add((long.Parse(array[i - 1]) - (list[i - 1] / 2)) * 2);
        }

        

        Console.WriteLine(string.Join(" ", list));
        Console.ReadLine();

    }
}

Measured memory_bytes: 31836
n = int(input())
ans = 0
def mask(i): return 1 << ((i-3) >> 1)
def dfs(a, use):
    global ans
    if a > n: return
    if use == 0b111: ans += 1
    for i in [3, 5, 7]: dfs(a*10+i, use | mask(i))

dfs(0, 0)
print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define testing 1
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
string cts(char x) {string t(1,x); return t;}
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> void chmax(T& a, T b) { a = max(a, b); }
template <typename T> void chmin(T& a, T b) { a = min(a, b); }
const int MAXN = -1;
#if !testing
#define cerr if(0)cout
#endif

int32_t main() 
{
	IAMSPEED
   	ll k,a,b; cin >> k >> a >> b;
	FOR(i,a,b) {
		if(i%k == 0){
        	cout << "OK\n";
            return 0;
		}
    }
    cout << "NG";
}



Measured memory_bytes: 3644
# coding: utf-8

line = input().rstrip().split()
line.sort()
ans = " ".join(line)
print(ans)


# <?php

# $line = trim(fgets(STDIN));
# $num = explode(" ",$line);
# sort($num);
# $ans = implode(" ",$num);
# echo $ans . PHP_EOL;

# ?>


Measured memory_bytes: 5540
<?php /*atcoder.php*/

$t = new temp();
$t->main();
unset($t);

class temp{
	private function lineIn(){
		return fgets(STDIN);
	}

	public function main(){
		$max = $this->lineIn();
		
		$m = array();
		$a = array();
		$r = array();
		$c = array();
		$h = array();

		for($i = 0; $i < $max; $i++){
			$buf = $this->lineIn();
			
			switch ($buf[0]){
				case ("M"):
					$m[] = $buf;
					break;
				case ("A"):
					$a[] = $buf;
					break;
				case ("R"):
					$r[] = $buf;
					break;
				case ("C"):
					$c[] = $buf;
					break;
				case ("H"):
					$h[] = $buf;
					break;
				default:
					break;
			}
		}
		unset($buf);

		$m = array_unique($m);
		$a = array_unique($a);
		$r = array_unique($r);
		$c = array_unique($c);
		$h = array_unique($h);

		$cm = count($m);
		$ca = count($a);
		$cr = count($r);
		$cc = count($c);
		$ch = count($h);

		$fm = 0;
		$fa = 0;
		$fr = 0;
		$fc = 0;
		$fh = 0;
		
		if(0 != $cm){
			$fm++;	
		}
		if(0 != $ca){
			$fa++;	
		}
		if(0 != $cr){
			$fr++;	
		}
		if(0 != $cc){
			$fc++;	
		}
		if(0 != $ch){
			$fh++;	
		}

		if(3 > ($fm + $fa + $fr + $fc + $fh)){
			$ans = 0;
			echo $ans;
			return true;
		}

		$a1 = 0;
		$a2 = 0;
		$a3 = 0;
		$a4 = 0;
		$a5 = 0;
		$a6 = 0;
		$a7 = 0;
		$a8 = 0;
		$a9 = 0;
		$a0 = 0;

		if(3 == ($fm + $fa + $fr)){
			$a1 = $cm * $ca * $cr;
		}
		if(3 == ($fm + $fa + $fc)){
			$a2 = $cm * $ca * $cc;
		}
		if(3 == ($fm + $fa + $fh)){
			$a3 = $cm * $ca * $ch;
		}
		if(3 == ($fm + $fr + $fc)){
			$a4 = $cm * $cr * $cc;
		}
		if(3 == ($fm + $fr + $fh)){
			$a5 = $cm * $cr * $ch;
		}
		if(3 == ($fm + $fc + $fh)){
			$a6 = $cm * $cc * $ch;
		}
		if(3 == ($fa + $fr + $fc)){
			$a7 = $ca * $cr * $cc;
		}
		if(3 == ($fa + $fr + $fh)){
			$a8 = $ca * $cr * $ch;
		}
		if(3 == ($fa + $fc + $fh)){
			$a9 = $ca * $cc * $ch;
		}
		if(3 == ($fr + $fc + $fh)){
			$a0 = $cr * $cc * $ch;
		}

		$ans = $a1 + $a2 + $a3 + $a4 + $a5 + $a6 + $a7 + $a8 + $a9 + $a0;

		echo $ans;
		
	}
	
}
?>


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

#define R input[0][1]

using namespace std;

int input() {
	int input[51][2];
	cin >> input[0][0] >> input[0][1];								//まずnとr
	if (input[0][0] == 0 && input[0][1] == 0) {
		return 0;
	}
	for (char pos = 1; pos <= input[0][1]; pos++) {					//r回のシャッフルの仕方を入力
		cin >> input[pos][0] >> input[pos][1];
	}																//ここまで入力

	/*シャッフルもどし*/
	int whtop = 1;													//最後一番上にいるカードは、今何番目にいる？
	if (R==0)return input[0][0];									//一回もシャッフルしないならコレ

	whtop = input[input[0][1]][0];									//一回目のもどしだけ別枠
	R--;
	while (input[0][1] != 0) {	
		if (whtop <= input[R][1]) whtop = whtop + input[R][0] - 1;
		else if ((input[R][0] + input[R][1] - 1) < whtop) whtop = whtop;
		else whtop = whtop - input[R][1];
		R--;
	}
	return input[0][0] - whtop + 1;

}


int main()
{
	while (1) {
		int check;
		check = input();
		if (check == 0)break;
		else {
			cout << check << endl;
		}
	}
}


Measured memory_bytes: 2976
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B - Balance
 */

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

/* constant */

const int MAX_N = 100;
const int INF = 1 << 30;

/* typedef */

/* global variables */

int wsums[MAX_N + 1];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

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

  int mind = INF;
  for (int i = 1; i < n; i++) {
    int w0 = wsums[i], w1 = wsums[n] - w0;
    int d = abs(w1 - w0);
    if (mind > d) mind = d;
  }

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


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

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

    int n;
    cin >> n;
    vector<int> nums(n);

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

    int a, b;
    a = *max_element(nums.begin(), nums.end());

    if (a & 1) {
        int compA = a / 2, compB = a / 2 + 1;
        int diff = a;
        for (int i = 0; i < n; i++) {
            if (nums[i] == a)
                continue;
            if (abs(nums[i] - compA) < diff) {
                diff = abs(nums[i] - compA);
                b = nums[i];
            }
            if (abs(nums[i] - compB) < diff) {
                diff = abs(nums[i] - compB);
                b = nums[i];
            }
        }

    } else {
        int compA = a / 2;
        int diff = a;
        for (int i = 0; i < n; i++) {
            if (nums[i] == a)
                continue;
            if (abs(nums[i] - compA) < diff) {
                diff = abs(nums[i] - compA);
                b = nums[i];
            }
        }
    }

    cout << a << " " << b << '\n';

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
int h[1000005];
int main(){
	int n,k;long long ans=0;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",&h[i]);
	std::sort(h+1,h+n+1);
	for(int i=1;i<=n-k;++i)ans+=h[i];
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1024
n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]

ans, d = 0, {}
for i in range(n):
    if s[i] in d.keys():
        ans += d[s[i]]
        d[s[i]] = d[s[i]] + 1
    else:
        d[s[i]] = 1
print(ans)

Measured memory_bytes: 19400
import java.io.File;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		//task b battle
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); sc.nextLine();
		TreeSet<String> vals = new TreeSet<>();
		for(int i = 0; i< n; i++){
			vals.add(sc.nextLine());
		}
		System.out.println(vals.size());

	}
}


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

int main()
{
    int N;
    int A[200005];

    cin >> N;

    for ( int i = 0; i < N; i++ ) {
        cin >> A[i]; A[i] -= i;
    }

    int64_t sum = 0;
    sort ( A, A + N );
    for ( int i = 0; i < N; i++ ) {
        sum += abs(A[N / 2] - A[i]);
    }

    cout << sum << endl;

    return ( 0 );
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N, K; cin >> N >> K;
    vector<ll> h(N);
    rep(i, N){
        cin >> h[i];
    }
    sort(all(h));
    reverse(all(h));
    ll res=0;
    Rep(i, K, N){
        res += h[i];
    }

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 5888
#include <stdio.h>
#include <stdlib.h>

int main()
{
	char X[200001];
	scanf("%s", X);
	
	int i, count = 0, max = 0;
	for (i = 0; X[i] != 0; i++) {
		if (X[i] == 'T') count++;
		else count--;
		if (count > max) max = count;
	}
	
	printf("%d\n", max * 2);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 384
n,m,x,y = map(int,input().split())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
X.append(x)
Y.append(y)
X.sort()
Y.sort()

a = X[-1]+1

if a <= Y[0]:
    print("No War")
else:
    print("War")


Measured memory_bytes: 3060
package main

import (
	"fmt"
)

func main() {

	var n int
	fmt.Scan(&n)

	list := make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&list[i])
	}
	m := map[string]int{}

	for i := 0; i < n; i++ {
		_, ok := m[list[i]]
		if ok == false {
			m[list[i]] = 1
		} else {
			m[list[i]]++
		}
	}

	fmt.Println(len(m))
}


Measured memory_bytes: 27236
#include <stdio.h>

int main(void){
    long long int a;
    double b;
    scanf("%lld %lf",&a,&b);
    long long int ans = a*(int)b;
    long long int ans2 = a*((int)(b*1000)%1000);
    long long int ans3 = ans + ans2/1000;
    printf("%lld\n",ans3);

    return 0;
}

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

using namespace std;

int main(){
    int n,f;
    cin>>n>>f;
    map<pair<string,string>,int> mp;
    for (int i = 0; i < n; ++i) {
        int m;
        cin>>m;
        vector<string> t(m);
        for (int j = 0; j < m; ++j) {
            cin>>t[j];
        }
        sort(t.begin(),t.end());
        for (int j = 0; j < m-1; ++j) {
            for (int k = j+1; k < m; ++k) {
                auto tp=make_pair(t[j],t[k]);
                mp[tp]++;
            }
        }
    }
    vector<pair<string,string>> ans;
    for(auto i:mp){
        if(i.second>=f){
            ans.emplace_back(i.first);
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto i:ans)cout<<i.first<<" "<<i.second<<endl;
    return 0;
}


Measured memory_bytes: 3532
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  int n,a,b;
  cin >> n >> a >> b;
  cout << min(a, b) << " " << max(0, a + b - n) << endl;
}


Measured memory_bytes: 256
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
const ll mod = 1000000007;
ll max(ll a, ll b) {
	if (a < b)
		return b;
	else
		return a;

}
ll min(ll a, ll b) {
	if (a < b)
		return a;
	else
		return b;

}

ll Q;

int main() {

	
	ll A, B; 
	cin >> A >> B;

	if (abs(B + A) % 2 == 0)
		cout << abs(B + A) / 2 << endl;
	else
		cout << "IMPOSSIBLE" << endl;


	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int n, s=0, aux;
	scanf("%i", &n);
	aux=n;
	while(aux>0){
		s=s+(aux%10);
		aux=aux/10;
	}
	if(n%s==0)
	    printf("Yes\n");
	else
	    printf("No\n");

}


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

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	int N, M, T; cin >> N >> M >> T;
	vector<int> a(N); rep(i, 0, N) { cin >> a[i]; }
	int ans = T;
	rep(i, 1, N) {
		dump(ans);
		ans -= min(a[i] - a[i - 1], 2 * M);
	}
	dump(ans);
	ans -= M;
	dump(ans);
	ans -= min(T - a[N - 1], M);
	dump(ans);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3068
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1001001001;
const ll LONGINF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
int main() {
    int H, W, A, B; cin >> H >> W >> A >> B;
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            if(i < B) {
                if(j < A) cout << 0;
                else cout << 1;
            }
            else {
                if(j < A) cout << 1;
                else cout << 0;
            }
            if(j + 1 == W) cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1280
t=[]
for i in range(3):
    t.append([int(i) for i in input().split()])
n = int(input())
lst = []
for i in range(n):lst+=[int(input())]
def ligne(i):
    for j in range(3):
        if not t[i][j] in lst:
            return False
    return True
def col(j):
    for i in range(3):
        if not t[i][j] in lst:
            return False
    return True
def diag1():
    for i in range(3):
        if not t[i][i] in lst:
            return False
    return True
def diag2():
    for i in range(3):
        if not t[2-i][i] in lst:
            return False
    return True
ans = False
for i in range(3):
    ans = ans or ligne(i)
    ans = ans or col(i)
ans  = ans or diag1() or diag2()
if ans :
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

ll lcm(ll a, ll b) {
	ll c;
	c = a * b / gcd(a, b);
	return c;
}

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

const ll mod = 1000000007;


map<string, int> memo;

using P=pair<int, int>;




/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < (ll)a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}
ll nCr(ll n, ll r) {
	ll a = 1;
	for (ll i = n; i > n - r; --i) {
		a = a * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		a = a / i;
	}
	return a;
}

void comb(vector<vector <long long int> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (ll j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}


int main() {
	ll a, b, n;
	cin >> a >> b >> n;
	ll ans = 0;
	if (b > n) {
		cout << (a * n) / b;
	}
	else {
		cout << (a * (b - 1)) / b;
	}
	return 0;
}













Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll N;
  cin >> N;
  vl x(N),y(N),h(N);
  rep(i,N){
    cin >> x[i] >> y[i] >> h[i];
  }
  rep(cx,101){
    rep(cy,101){
      bool B=true;
      ll H=0,mxh=1e10;
      rep(i,N){
        ll z;
        if(h[i]==0){
          z=abs(x[i]-cx)+abs(y[i]-cy);
          mxh=min(z,mxh);
        }
        else{
          z=h[i]+abs(x[i]-cx)+abs(y[i]-cy);
          if((H!=0&&H!=z)||mxh<z){
            B=false;
          }
          else{
            H=z;
          }
        }
      }
      if(mxh<H){
        B=false;
      }
      if(B){
        cout << cx << " " << cy << " " << H << endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    char s[5];
    scanf("%s",s);

    int i;
    for (i = 0; i < 3; i++)
    {
        if(s[i] == s[i + 1])
        {
            break;
        }
    }
    if (i!= 3)
    {
        printf("Bad");
    }
    else
    {
        printf("Good");
    }
    
}

Measured memory_bytes: 128
from collections import defaultdict
h, w = map(int, input().split())

cnt = defaultdict(int)
for _ in range(h):
    for a in input():
        cnt[a] += 1

quartet = (h//2) * (w//2)
doublet = (h % 2)*(w//2)+(w % 2)*(h//2)
singlet = 1 if h & 1 and w & 1 else 0

for k, v in cnt.items():
    if not quartet:
        break
    if v < 4:
        continue
    x = min(quartet, v//4)
    quartet -= x
    cnt[k] -= 4*x

for k, v in cnt.items():
    if v < 2:
        continue
    doublet -= v//2
    cnt[k] = v % 2

singlet -= sum(v for v in cnt.values())
if singlet == doublet == quartet == 0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3316
#include <stdio.h>
#include <math.h>

using namespace std;

double a, b, x;

int main() {
    scanf("%lf%lf%lf", &a, &b, &x);
    double z;
    if (2*x<a*a*b) {
        // 1/2 b*a*z = x
        z = 2*x/(b*a);
        printf("%f", atan(b/z)* 180 / M_PI);
    } else {
        // a*a*b - 1/2 z*a*a = x
        // a*a (b-1/2z)=x
        // 2b - 2x/(a*a) =z
        z = 2*b - 2*x/(a*a);
        printf("%f", atan(z/a)* 180 / M_PI);
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int N = scanner.nextInt();
			int[] array = new int[N];
			for (int i = 0; i < N; i++) {
				array[i] = scanner.nextInt();
			}

			System.out.println(returnActionCnt(array,0));
		}
	}

	private static int returnActionCnt(int[] array,int  cnt) {
		boolean flg = true;
		for (int i = 0; i < array.length; i++) {
			if (array[i] % 2 == 1) {
				flg = false;
				return cnt;
			}
		}
		// すべてが偶数だったとき
		if (flg) {
			for (int i = 0; i < array.length; i++) {
				array[i] /= 2;
			}
			cnt++;
		}

		return returnActionCnt(array, cnt);
	}
}

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


int main(){
  int W,H,C;

  cin >> W >> H >> C;

  int size = 1;
  int result_size = 0;
  int num = 0;
  while(true){

    if(size > W || size > H) {
      break;
    }
    
    if(W % size == 0 && H % size == 0){
      result_size = size;
      num = (W / result_size) * (H / result_size);
    }
    
    ++size;
  }

  cout << num * C << endl;
  
  return 0;
}



Measured memory_bytes: 3100
#include<iostream>
using namespace std;
int main(){
    int h,w;
    string s[110];
    cin>>h>>w;
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    for(int i=0;i<h;i++){
     cout<<s[i]<<endl;
     cout<<s[i]<<endl;
    }
    
   
}

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

using namespace std;

u_int seed = 3;
u_int xor_shift()
{
    seed ^= seed << 1;
    seed ^= seed >> 3;
    seed ^= seed << 10;
    return seed;
}

chrono::system_clock::time_point start_time;
int elapsed()
{
    auto cur = chrono::system_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(cur - start_time).count();
}

// セグ木を使えば二分探索で一点をlog(n)で更新できる これ嘘で，後ろのスコアも変更する必要があるため
// 前からA*とかビームサーチもできそう
// とりあえず焼きなます
// 最初はCを考慮せずに焼きなます(いや，貪欲でいいだろ)
int score = 0;
int d;
vector<int> T, C;
vector<vector<int>> S, last;

// i日目をj番目に
int calc(int i, int to){
    int res = 0;
    int from = T[i];
    res -= S[i][from];
    int l = i == 0 ? -1 : last[i - 1][from];
    for (int j = i; j < d; j++){
        if (last[j][from] != i)
            break;
        res += C[from] * (j - last[j][from]);
        res -= C[from] * (j - l);
    }

    res += S[i][to];
    for (int j = i; j < d; j++){
        if (last[j][to] > i)
            break;
        res += C[to] * (j - last[j][to]);
        res -= C[to] * (j - i);
    }

    return res;
}

void change(int i, int to){
    int from = T[i];
    T[i] = to;
    int l = i == 0 ? -1 : last[i - 1][from];
    for (int j = i; j < d; j++){
        if (last[j][from] != i)
            break;
        last[j][from] = l;
    }

    for (int j = i; j < d; j++){
        if (last[j][to] > i)
            break;
        last[j][to] = i;
    }
}

int calc_overall(){
    int res = 0;
    for (int i = 0; i < d; i++){
        res += S[i][T[i]];
        for (int j = 0; j < 26; j++){
            res -= C[j] * (i - last[i][j]);
        }
    }

    return res;
}


int main(){
    cin >> d;
    start_time = chrono::system_clock::now();
    C.resize(26);
    copy_n(istream_iterator<int>(cin), 26, C.begin());
    S.assign(d, vector<int>(26));
    last.assign(d, vector<int>(26, -1));
    for (auto &s: S)
        copy_n(istream_iterator<int>(cin), 26, s.begin());

    T.resize(d);

    for (int i = 0; i < d; i++){
        // int to = max_element(S[i].begin(), S[i].end()) - S[i].begin();
        int to = xor_shift() % 26;
        T[i] = to;
        for (int j = i; j < d; j++){
            last[j][to] = i;
        }
    }

    auto ans = T;
    score = calc_overall();
    cerr << score << endl;
    int max_score = score;
    const double s_temp = 20000, e_temp = 1;
    const constexpr int L = 7e6;
    double delta = (s_temp - e_temp) / L;
    double temp = s_temp;
    const double sup = pow(2, 32) - 1;

    while (elapsed() < 1950){
        auto i = xor_shift() % d;
        auto to = xor_shift() % 26;
        if (T[i] == to)
            continue;
        auto cost = calc(i, to);
        if (cost > 0 or exp(cost / temp) > xor_shift() / sup){
            change(i, to);
            // cerr << "change: " << i << " " << to << " " << cost << " " << temp << endl;
            score += cost;
        }
        if (score > max_score){
            ans = T;
            max_score = score;
        }
        if (temp > e_temp)
            temp -= delta;
    }

    cerr << temp << endl;
    for (const auto &t: ans)
        cout << t + 1 << endl;

    cerr << max_score << endl;

}


Measured memory_bytes: 4512
# Problem A - CF

# input process
S = input()

# initialization
is_ok_1 = False
is_ok_2 = False

# str count process
for s in S:
    if s=="C":
        is_ok_1 = True

    if is_ok_1 and s=="F":
        is_ok_2 = True

# output process
if is_ok_2:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().run();
	}

	private void run() {
		Scanner scanner = new Scanner(System.in);
		int sum = 0;
		for (int i = 0; i < 10; i++)
			sum += scanner.nextInt();
		System.out.println(sum);
	}
}

Measured memory_bytes: 17328
#include<cstdio>
#include<cstring>

int fie[10][10];
int cnt_h[10][10];
int bomb[10][10];
int next[10];
int h;

void fall(int x){
	memset(next,0,sizeof(next));
	int cnt=h-1;
	for(int i=h-1;i>=0;i--){
		if(fie[x][i]!=0)next[i]=cnt,cnt--;
	}
	for(int i=h-1;i>=0;i--){
		if(fie[x][i]!=0)fie[x][next[i]]=fie[x][i];
	}
	for(int i=0;i<=cnt;i++)fie[x][i]=0;
}

void bomber(){
	for(int i=0;i<h;i++){
		for(int j=0;j<5;j++){
			if(bomb[j][i]==1)fie[j][i]=0;
		}
	}
	for(int i=0;i<5;i++)fall(i);
}

int main(void){
	while(1){
		scanf("%d",&h);
		if(h==0)break;
		memset(fie,0,sizeof(fie));
		int all=0;
		for(int i=0;i<h;i++){
			for(int j=0;j<5;j++){
				scanf("%d",&fie[j][i]);
				all+=fie[j][i];
			}
		}
		int flag=1,cnt=1;
		while(flag){
			flag=0;
			memset(cnt_h,0,sizeof(cnt_h));
			memset(bomb,0,sizeof(bomb));
			for(int i=0;i<h;i++){
				cnt=1;
				for(int j=1;j<5;j++){
					if(fie[j][i]==fie[j-1][i] && fie[j][i]!=0)cnt++;
					else cnt=1;
					cnt_h[j][i]=cnt;
				}
			}
			for(int i=0;i<h;i++){
				for(int j=2;j<5;j++){
					if(cnt_h[j][i]==3){
						bomb[j-2][i]=bomb[j-1][i]=bomb[j][i]=1;
						flag=1;
					}
					if(cnt_h[j][i]>3)bomb[j][i]=1;
				}
			}
			if(flag)bomber();
		}
		int rest=0;
		for(int i=0;i<5;i++){
			for(int j=0;j<h;j++)rest+=fie[i][j];
		}
		printf("%d\n",all-rest);
	}
	return 0;
}

Measured memory_bytes: 1028
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.container;

void main(){
    auto arr = readln.chomp.split.map!(to!int).array;
    int a = arr[0], b = arr[1];
    auto s = readln.chomp;
    auto t = readln.chomp;
    auto dp = new int[][][](a+2, b+2, 2);
    foreach(i; 0..a+1) foreach(j; 0..b+1) dp[i][j][0] = dp[i][j][1] = int.min;
    foreach(i; 0..a+1){
        foreach(j; 0..b+1){
            if(i != a){
                if(s[i] == 'I') dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][0] + 1, 1);
                else            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][1] + 1);
            }
            if(j != b){
                if(t[j] == 'I') dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][0] + 1, 1);
                else            dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][1] + 1);
            }
        }
    }
    int ans = int.min;
    foreach(i; 0..a+2) foreach(j; 0..b+2) ans = max(ans, dp[i][j][1]);
    writeln(ans);
}

Measured memory_bytes: 131132
void main() {
  problem();
}

void problem() {
  auto N = scan!long;
  const K = scan!long;

  long solve() {
    while(true) {
      real ratio = cast(real)N / cast(real)K;
      if (ratio <= 0.5) return N;
      if (ratio <  1.0) return K - N;
      N = N - (N/K)*K;
    }
  }

  solve().writeln;
}

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

import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; }
T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
void deb(T ...)(T t){ debug writeln(t); }
alias Point = Tuple!(long, "x", long, "y");

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

bool is_prime(const int n){
    switch(n) {
        case 0: // fall-through
        case 1: return false;
        case 2: return true;
    } // n > 2 が保証された

    if(n % 2 == 0) return false;

    // 上で i=2 相当は調べたので、i=3から奇数のみ調べる
    for(int i = 3; i * i <= n; i += 2) {
        if(n % i == 0) return false;
    }

    return true;
}

int main() {
    char a;
    cin >> a;
    int b = a;
    b -= 97;
    if (b < 0) {
        cout << 'A' << endl;
    } else {
        cout << 'a' << endl;
    }
}




Measured memory_bytes: 3564
n,m=input().split()
n=int(n)
m=int(m)
i=0
x=[]
y=[]
a=list(map(int,input().split()))

a=sorted(a)
while i!=m:
    i=i+1
    x=list(map(int,input().split()))
    y.append(x)

y=sorted(y, key=lambda x: -x[1])

j=0
while True:
    try:
        t=y[0]
        del y[0]
        i=0
        while i!=t[0]:
            i=i+1
            if t[1]>a[j]:
                a[j]=t[1]
                j=j+1
            else:
                break
        if t[1] > a[j]:
            pass
        else:
            break

    except:
        break
ans=0
i=0
while True:
    try:
        ans=ans+a[i]
        i=i+1
    except:
        break
print(ans)


Measured memory_bytes: 36828
H,W=map(int,input().split())
m=[]
for _ in[0]*H:
  l=input()
  if l!='.'*W:m+=[l]
t=[]
for j in range(W):
  f=0
  for l in m:
    if l[j]!='.':f=1;break
  if f:t+=[j]
for l in m:
  print("".join([l[j] for j in t])) 

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s;
  cin >> s;
  
  string t = "";
  for (int i = 0; i < s.size(); i++) {
    if (i < s.size() - 1) {
      if (s.at(i) == 'B' && s.at(i + 1) == 'C') {
        t += 'D';
        i++;
        continue;
      }
    }
    t += s.at(i);
  }
  
  ll ans = 0, count = 0;
  for (int i = 0; i < t.size(); i++) {
    if (t.at(i) == 'B' || t.at(i) == 'C') count = 0;
    else if (t.at(i) == 'D') ans += count;
    else count++;
  }
  
  cout << ans << '\n';
}

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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

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

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

const ll INF = TEN(18);
ll A, B, C, D;
map<ll, ll> dp;

ll calc(ll x) {
    if (dp.count(x)) return dp[x];
    dp[x] = INF;
    if (x < INF / D) {
        dp[x] = x * D;
    }
    if (x == 0) {
        return dp[x] = 0;
    }
    if (x % 2 == 0) {
        chmin(dp[x], calc(x / 2) + A);
    } else {
        chmin(dp[x], calc((x - 1) / 2) + A + D);
        chmin(dp[x], calc((x + 1) / 2) + A + D);
    }
    if (x % 3 == 0) {
        chmin(dp[x], calc(x / 3) + B);
    } else {
        int m = x % 3;
        if (m <= 1) {
            chmin(dp[x], calc(x / 3) + B + D);
        } else {
            chmin(dp[x], calc(x / 3 + 1) + B + D);
        }
    }
    if (x % 5 == 0) {
        chmin(dp[x], calc(x / 5) + C);
    } else {
        int m = x % 5;
        if (m <= 2) {
            chmin(dp[x], calc(x / 5) + C + m * D);
        } else {
            chmin(dp[x], calc(x / 5 + 1) + C + D * (5 - m));
        }
    }
    if (dp[x] < 0) {
        debug(x);
        debug(dp.size());
        exit(-1);
    }
    return dp[x];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        dp.clear();
        ll N;
        cin >> N >> A >> B >> C >> D;
        cout << calc(N) << endl;
    }
    return 0;
}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> P1;
typedef pair<P, P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i, x) for (long long i = 0; i < x; i++)
#define repn(i, x) for (long long i = 1; i <= x; i++)
#define SORT(x) sort(x.begin(), x.end())
#define ERASE(x) x.erase(unique(x.begin(), x.end()), x.end())
#define POSL(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin())
#define POSU(x, v) (upper_bound(x.begin(), x.end(), v) - x.begin())
vector<pair<string, P> > vec;
// vector<vector<int>> data(3, vector<int>(4));
ll g[201][201];

void solve(long long K) {
    repn(i, 200) {
        repn(j, 200) { g[i][j] = gcd(i, j); }
    }

    ll res = 0;
    repn(i, K) {
        repn(j, K) {
            ll l = g[i][j];
            repn(k, K) { res += g[l][k]; }
        }
    }
    cout << res << endl;
}

int main() {
    long long K;
    scanf("%lld", &K);
    solve(K);
    return 0;
}


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

import static java.lang.Character.isUpperCase;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        String S = in.next();
        for(int i = 0; i<S.length(); i++)
        {
            int x = S.charAt(i) + N;
            char c = (char) (((S.charAt(i) - (int) 'A') + N) % 26 + (int) 'A');
            System.out.print((char) c);
        }



    }

}















Measured memory_bytes: 39928
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int gcd(int a, int b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main()
{
	int x, y;
	cin >> x >> y;

	int ans = x + y;

	int g = gcd(x, y);

	int w = x / g, h = y / g, _x = w, _y = h;
	while (true)
	{
		if (_x < x && _y < y)
		{
			ans--;
		}
		else
		{
			break;
		}

		_x += w;
		_y += h;
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 3108
#include<iostream>

auto CalculateState(const std::string& s, std::uint64_t i) {
    constexpr auto f = [](const auto& c) { return static_cast<std::uint64_t>(c - '0'); };
    auto result = std::uint64_t(0);
    auto target = f(s[0]);

    for (auto j = std::size_t(1); j < s.length(); ++j) {
        if (i % 2 == 0) {
            target = target * 10 + f(s[j]);
        } else {
            result += target;
            target = f(s[j]);
        }

        i /= 2;
    }

    result += target;

    return result;
}

int main() {
    auto s = std::string();
    std::cin >> s;

    auto sum = std::uint64_t(0);

    for (auto i = std::size_t(0); i < (1 << (s.length() - 1)); ++i) {
        sum += CalculateState(s, i);
    }

    std::cout << sum << std::endl;
    return 0;
}

Measured memory_bytes: 256
N, M = [int(_) for _ in input().split()]
A = [0 for i in range(N+1)]

ac = 0
pen = 0
for i in range(M):
    p, S = input().split()
    p = int(p)
    if A[p] == -1:
        continue
    if S == 'AC':
        ac += 1
        pen += A[p]
        A[p] = -1
    else:
        A[p] += 1
print(ac, pen)


Measured memory_bytes: 3888
#include <iostream>
//#include <vector>
//#include <iomanip>

using namespace std;

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

	bool isGood = true;
	for (int i = 1; i < 4; i++)
	{
		if (s[i] == s[i - 1])
		{
			isGood = false;
			break;
		}
	}

	cout << (isGood ? "Good" : "Bad") << endl;

	return 0;
}


Measured memory_bytes: 256
unittest
{

assert( q"INPUT
14
9 7 5 9
9 7 6 9
14 10 7 12
14 10 8 12
14 10 9 12
14 10 7 11
14 10 8 11
14 10 9 11
9 10 5 10
10 10 5 10
11 10 5 10
16 10 5 10
1000000000000000000 17 14 999999999999999985
1000000000000000000 17 15 999999999999999985
INPUT".split( '\n' ).parse.expand.solve.format!( "%s\n" ) == q"OUTPUT
No
Yes
No
Yes
Yes
No
No
Yes
No
Yes
Yes
No
No
Yes
OUTPUT" );

assert( q"INPUT
24
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
INPUT".split( '\n' ).parse.expand.solve.format!( "%s\n" ) == q"OUTPUT
No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
OUTPUT" );

}



import std.algorithm;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto t = input.front.to!( long );
	auto abcds = new long[ 4 ][ t ];
	foreach( ref abcd; abcds )
	{
		input.popFront;
		abcd = input.front.split.to!( long[] );
	}
	return tuple( abcds );
}

auto solve( long[ 4 ][] abcds )
{
	auto anss = new bool[ abcds.length ];
	foreach( ref ans, abcd; lockstep( anss, abcds ) )
	{
		if( abcd[ 0 ] < abcd[ 1 ] )
		{
			// 在庫の初日本数(A)より購入本数(B)のほうが多いので絶対ダメ
			ans = false;
		}
		else if( abcd[ 3 ] < abcd[ 1 ] )
		{
			// 仕入れの本数(D)より購入本数(B)のほうが多いので絶対ダメ
			ans = false;
		}
		else if( abcd[ 1 ] <= abcd[ 2 ] )
		{
			// 購入本数(B)より在庫の最低本数(C)のほうが多いので絶対大丈夫
			ans = true;
		}
		else
		{
			// 購入本数(B)より仕入れの本数(D)のほうが多いが、在庫の最低本数(C)は購入本数(B)より少ない
			auto r = abcd[ 0 ] % abcd[ 1 ];
			auto d = abcd[ 3 ] % abcd[ 1 ];
			if( d == 0 )
			{
				// 仕入れの本数(D)と購入本数(B)が釣り合ってるので、最初の仕入れの前に在庫が無くならなければ大丈夫
				ans = ( r <= abcd[ 2 ] );
			}
			else
			{
				// 在庫の残り本数が 在庫の最低本数(C)超 かつ 購入本数(B)未満 になるタイミングがなければ大丈夫
				long[ long ] rs;
				do
				{
					rs[ r ] = true;
					r += ( cast( long )( ( abcd[ 2 ] - r + 1.0L ) / d ).ceil * d ) - abcd[ 1 ];
				}
				while( 0 <= r && r !in rs );
				ans = ( 0 <= r );
			}
		}
	}
	return anss.map!( ( a ) => a ? "Yes" : "No" ).join( "\n" );
}


Measured memory_bytes: 508
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[11][11];
int main()
{
    int n;   int i,k;
    cin>>n;
    for(i=0; i<10; i++)
        a[1][i]=1;
    for( i=2; i<=10; i++)
    {
        for( k=0; k<10; k++)
        {
            if(k==0)
                a[i][k]=a[i-1][k]+a[i-1][k+1];
            else  if(k==9)
                a[i][k]=a[i-1][k]+a[i-1][k-1];
            else
                a[i][k]=a[i-1][k]+a[i-1][k-1]+a[i-1][k+1];

        }
    }
    int qdwz=0;
int flag=0;
    for(i=1; i<=10; i++)
    {
        for(k=1; k<10; k++)
        {
            qdwz+=a[i][k];
            if(qdwz>=n)
               {flag=1;break;}
        }
        if(flag==1)
            break;
    }
    //cout<<qdwz<<endl;
    qdwz-=a[i][k];
    cout<<k;
n-=qdwz;
    int j;
    while(--i)
    {

        if(k==9)
        {
            if(a[i][k-1]>=n)
            {
                cout<<k-1;
                k=k-1;
            }
            else
            {
                cout<<k;
                n-=a[i][k-1];
            }

        }
        else
        {
            if(a[i][k-1]>=n)
            {
                cout<<k-1;
                k=k-1;
            }
            else if(a[i][k-1]+a[i][k]>=n)
            {
                cout<<k;
                n-=a[i][k-1];
            }
            else
            {
                 cout<<k+1;
                n-=a[i][k-1]+a[i][k];
                k+=1;
            }
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace std;

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

const int N = 110;
int l[3][N] , r[3][N] , a[3][N];

int main(){

	ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

	int n , ans = 0;
	cin >> n;

	for(int i = 0 ; i < 2 ; i++){
	   for(int j = 1 ; j <= n ; j++){
		  cin >> a[i][j];
		  l[i][j] = a[i][j] + l[i][j-1];
	   }

	   for(int j = n ; j >= 1 ; j--)
		  r[i][j] = r[i][j+1] + a[i][j];
	   
	}

	for(int i = 1 ; i <= n ; i++)
		ans = max(ans , l[0][i] + r[1][i]);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
line = input().split()
number = int(line[0])
distance = int(line[1])
import math
cnt =0
for i in range(number):
  position = input().split()
  x = int(position[0])
  y = int(position[1])
  origin_dis = math.sqrt(x*x+y*y)
  if origin_dis <=distance:
    cnt +=1
print(cnt)

Measured memory_bytes: 9176