akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n, k; cin >> n >> k;
    int last = k + (3*n - 1);
    vector<vector<int>> result;

//    int ab = 0;
//    int c = 0;
//    for (int i = n; i <= last; ++i) {
//        if (i <= last - n)  {
//            ab += i;
//        } else {
//            c += i;
//        }
//    }
//    if (ab > c) {
//        cout << -1 << endl;
//        return 0;
//    }

    int curr = last - n + 1;
    int l = k;
    int r = last - n;
    int skip = 0;

    vector<int> v_skip;

    while (curr <= last && l < r) {
        if (l + r > curr) {
            ++skip;
            v_skip.push_back(r);
            r--;
            continue;
        }
        if (l + r < curr) {
            ++skip;
            v_skip.insert(v_skip.begin(), l);
            l++;
            continue;
        }

        vector<int> gg = vector<int>(3);
        gg[0] = l;
        gg[1] = r;
        gg[2] = curr;
        result.push_back(gg);

        l++;
        r--;
        curr++;
    }

    if (l == r && skip > 0) {
        v_skip.insert(v_skip.begin(), l);
    }
    if (skip > 0) {
        sort(v_skip.begin(), v_skip.end());
        l = 0;
        r = v_skip.size() - 1;
        while (curr <= last && l < r) {
            if (v_skip[l] + v_skip[r] > curr) {
                cout << -1 << endl;
                return 0;
            }

            vector<int> gg = vector<int>(3);
            gg[0] = v_skip[l];
            gg[1] = v_skip[r];
            gg[2] = curr;
            result.push_back(gg);

            curr++;
            l++;
            r--;
        }
    }

    if (result.size() == n) {
        for (int i = 0; i < n; ++i) {
            cout << result[i][0] << " " << result[i][1] << " " << result[i][2] << endl;
        }
    } else {
        cout << -1 << endl;
    }

    return 0;
}

Measured memory_bytes: 8360
#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char nc()
{
    // return getchar();
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
    x=0; int f=1,ch=nc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
    while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
    x*=f;
}
int n;
int main()
{
    read(n);
    int sg=0;
    for(int i=1;i<=n;++i)
    {
        int a,k; read(a),read(k);
        while(a%k)
        {
            int t=a/k*k;
            int d=a/k+1;
            a-=(a-t)/d*d;
            if(a!=t) a-=d;
        }
        sg^=a/k;
    }
    puts(sg?"Takahashi":"Aoki");
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

int max(int a, int b);

int min(int a, int b);

int main()
{
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    int start, end;
    start = max(a, c);
    end = min(b, d);
    if(start > end){
        std::cout << 0 << std::endl;
    }
    else{
        std::cout << end - start << std::endl;
    }
    return 0;
}

int max(int a, int b)
{
    if(a > b){
        return a;
    }
    else{
        return b;
    }
}

int min(int a, int b)
{
    if(a > b){
        return b;
    }
    else{
        return a;
    }
}

Measured memory_bytes: 256
import scala.io._

object Main extends App {
  val n = StdIn.readInt
  // ??\????????????????????§(?????§,????°?)??????????????????????????????(??????????????§)?????????
  val (max,min) = Iterator.continually(readLine()).takeWhile(_ != null)
    .foldLeft((Int.MinValue, Int.MaxValue)){
      case ((preMax,preMin),in) =>
        val inNum = in.toInt
        val max = Math.max(preMax, inNum - preMin)
        val min = Math.min(preMin, inNum)
        (max, min)
  }
  // ???????????????max????????????
  println(max)
}

Measured memory_bytes: 70044
S = input()
T = input()
ans = 1000000  # 
for i in range(len(S) - len(T) + 1):
    score = 0
    U = S[i:i + len(T)] 
    for j in range(len(T)):
        if U[j] != T[j]:
            score += 1
    ans = min(ans, score)

print(ans)

Measured memory_bytes: 9044
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <set>

using ll = long long;

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    set<int> s;
    for (int i=1; i<=n; i++) s.insert(i);
    for (int i=0, di; i<k; i++) {
        cin >> di;
        for (int j=0, aij; j<di; j++) {
            cin >> aij;
            s.erase(aij);
        }
    }
    cout << s.size() << '\n';
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <memory.h>
#include <cassert>

using namespace std;


#define all(c) ((c).begin()), ((c).end())
#define debug(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)

#define mp make_pair
#define fst first
#define snd second
#define pb push_back


const double EPS = 1e-10;


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


void go(int x, int y, vector<string> &m) {
	m[y][x] = '0';
	rep(i, 3) {
		if (y - i - 1 >= 0) if (m[y - i - 1][x] == '1') go(x, y - i - 1, m);
		if (y + i + 1 < 8) if (m[y + i + 1][x] == '1') go(x, y + i + 1, m);
		if (x - i - 1 >= 0) if (m[y][x - i - 1] == '1') go(x - i - 1, y, m);
		if (x + i + 1 < 8) if (m[y][x + i + 1] == '1') go(x + i + 1, y, m);
	}
}

int main() {
	int nCases; cin >> nCases;
	rep(iCase, nCases) {
		vector<string> m(8);
		rep(i, 8) cin >> m[i];
		int x, y; cin >> x >> y;
		x--;
		y--;
		go(x, y, m);
		cout << "Data " << iCase + 1 << ":" << endl;
		rep(i, 8) cout << m[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

int main() {
    int a[100000];
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> a[i];

    map<int, int> mp;
    for(int i=0; i<N; i++) mp[a[i]]++;

    int ans = 0;
    for(auto p: mp) {
        int x = p.first;
        int n= p.second;
        if(n < x) ans += n;
        else ans += n-x;
    }
    cout << ans << endl;
}

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

int main(){
    ll N,ans = 0;
    cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
        ans ^= A[i];
    }

    if (ans == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define RREP(i, a, n) for(int i=n-1; i>=a; i--)

int n;
int a[100001];
int main()
{
	cin >> n;
	REP(i, 0, n) cin >> a[i];

	sort(a, a + n);

	int ans = 0;
	int cnt = 0;
	int now = a[0];
	REP(i, 0, n) {
		if (a[i] == now) {
			cnt++;
		}
		else {
			if (cnt < now) ans += cnt;
			else if (now < cnt) ans += (cnt - now);
			cnt = 0;
			now = a[i];
			i--;
		}
	}
	if (cnt < now) ans += cnt;
	else if (now < cnt) ans += (cnt - now);
  
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
N, T = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = [0]
while Q:
    i = Q.pop()
    for a in X[i][::-1]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            Q.append(a)

C = [[] for i in range(N)]
for i in range(1, N):
    C[P[i]].append(i)
CT = [0] * N
XX = []
i = 0
while i >= 0:
    if CT[i] >= len(C[i]):
        XX.append(i)
        i = P[i]
    else:
        CT[i], i = CT[i] + 1, C[i][CT[i]]

A = [0] * N
for _ in range(T):
    p, x = map(int, input().split())
    A[p-1] += x

for i in XX[::-1]:
    if i: A[i] += A[P[i]]

print(*A)


Measured memory_bytes: 118656
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);
    static int n, x;
    static int[] A;

    public static void main(String[] args) {
        read();
        int i = partition(A, 0, n - 1);
        out(i);
    }

    static void out(int j) {
        for (int i = 0; i < n; i++) {
            if (i == j) {
                System.out.print(String.format("[%d] ", A[i]));
            } else if (i == n - 1) {
                System.out.println(String.format("%d", A[i]));
            } else {
                System.out.print(String.format("%d ", A[i]));
            }
        }
    }

    static int partition(int[] A, int p, int r) {
        x = A[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (A[j] <= x) {
                i++;
                int tmp = A[j]; A[j] = A[i]; A[i] = tmp;
            }
        }
        int tmp = A[i + 1]; A[i + 1] = A[r]; A[r] = tmp;

        return i + 1;
    }

    static void read() {
        n = sc.nextInt();
        A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = sc.nextInt();
        }
    }
}

Measured memory_bytes: 113668
#include <stdio.h>

int main()
{
  int n;
  scanf("%d",&n);
  int a[n];
  int i = 0;
  long diff = 0;
  long sum = 0;
  while (i < n)
  {
    scanf("%ld",&a[i]);
    if (i > 0)
    {
      if (a[i-1] > a[i])
      {
        diff = a[i-1] - a[i];
        sum += diff;
        a[i]+= diff;
      }
    }
    i++;
  }
  printf("%ld",sum);
}

Measured memory_bytes: 2496
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const int INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<int, int>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()

const int MAX_N = 100002;
ll dp[MAX_N][2];
//dp[i][smaller = true]
//: A and Bのi桁目まで確定させ，その時点でA+BがL以下であることが確定しているような(A, B)の個数

void modadd(ll &a, ll b) {
    a = (a + b) % MOD;
}

int main() {
    string L; cin >> L;
    dp[0][0] = 1;
    rep(i, L.size()) {
        modadd(dp[i + 1][1], 3 * dp[i][1]);
        if(L[i] == '1') {
            modadd(dp[i + 1][1], dp[i][0]);
            modadd(dp[i + 1][0], 2 * dp[i][0]);
        }else {
            modadd(dp[i + 1][0], dp[i][0]);
        }
    }
    cout << (dp[L.size()][0] + dp[L.size()][1])%MOD << endl;
}


Measured memory_bytes: 2048
a, b, c, d = map(int, input().split())

e = 0
while True:
    if e % 2 == 0:
      c -= b
      e += 1
    elif e % 2 == 1:
      a -= d
      e += 1

    if a <= 0:
      print("No")
      exit()

    if c <= 0:
      print("Yes")
      exit()


Measured memory_bytes: 9184
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX_N=100;
string S,T;
int main(){
    cin >> S >>T;
    int count =0;
    for(int i=0;i<S.length();i++){
        if(S[i]!=T[i]){
            count++;
        }
    }
    printf("%d\n",count);
}

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

bool is_prime(int n)
{
    if (n == 0 || n == 1)
        return (false);
    if (n % 2 == 0 && n != 2)
        return (false);
    for (int i = 3; i * i < n + 1; i += 2)
    {
        if (n % i == 0)
        {
            return (false);
        }
    }
    return (true);
}

int main()
{
    int q;
    cin >> q;
    vector<int> l(q), r(q);
    for (int i = 0; i < q; i++)
    {
        cin >> l[i] >> r[i];
    }
    vector<int> cum(1e5 + 1, 0);
    for (int i = 0; i < 1e5 + 1; i++)
    {
        if (is_prime(i) && is_prime((i + 1) / 2) && i % 2 == 1)
        {
            cum[i + 1] = cum[i] + 1;
        }
        else
        {
            cum[i + 1] = cum[i];
        }
    }

    for (int i = 0; i < q; i++)
    {
        cout << cum[r[i] + 1] - cum[l[i]] << '\n';
    }
    return 0;
}


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

int main() {
    int n, cnt = 0;
    cin >> n;
    rep(i,n) {
        int a;
        cin >> a;
        if (i % 2 == 0 && a % 2 == 1) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

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

int main(){
    int N; cin >> N;
    int t[110000], x[110000], y[110000];
    t[0]=x[0]=y[0]=0;
    for (int i=0; i < N ; i++) cin >> t[i+1] >> x[i+1] >> y[i+1];

    bool can=true;

    for (int i=0; i < N ; i++){
        int dt=t[i+1]-t[i], dx=x[i+1]-x[i], dy=y[i+1]-y[i];
        int dist=abs(dx)+abs(dy);
        if( dt < dist ) can=false;
        if ( dt%2 != dist%2) can=false;
    }

    if (can == true) cout << "Yes" << endl;
    else cout << "No" << endl;

}

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

int main() {
    int N, M; cin >> N >> M;
    string ans(N,'0');
    map<int, int> m;
    for (int i = 0; i < M; i++)
    {
        int x, y; cin >> x >> y;
        if(m.count(x)!=0 && m[x] != y){
            cout << -1 << endl;
            return 0;
        }
        m[x] = y;
    }
    
    for (auto iter = m.begin(); iter != m.end(); iter++)
    {
        if(iter->first-1 == 0 && iter->second==0 && N!=1){
            cout << -1 << endl;
            return 0;
        }
        ans[iter->first-1] = iter->second + '0';
    }
    if(ans[0]=='0' && N !=1) ans[0] = '1';
    cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::*;

fn read<T: std::str::FromStr>() -> T {
    let stdin = stdin();
    let mut buf = String::new();
	stdin.lock().read_line(&mut buf);
	buf.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
	read::<String>().trim().split_whitespace()
        .map(|w| w.parse().ok().unwrap()).collect()
}

fn read_vec_char() -> Vec<char> {
    read::<String>().chars().collect()
}

fn read_mat<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_mat_char(n: usize) -> Vec<Vec<char>> {
    (0..n).map(|_| read_vec_char()).collect()
}

fn main() {
    let v = read_vec::<i64>();
    let mut ans = v[0] - v[1];
    if v[3] % 2 == 1 {
        ans *= -1;
    }
    println!("{}",ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define INF 2147483647
#include <math.h> /* M_PI */
int main()
{
    string s;
    cin >> s;
    ll k = 0;
    cin >> k;
    //文字列の部分列を取り除く。ここでk＝5というのが最大のヒント
    string t = s;
    map<char, ll> boku;
    rep(i, s.size())
    {
        boku[s[i]] = 1;
    }
    string lk;
    for (auto x : boku)
    {
        lk += x.first;
    }
    sort(lk.begin(), lk.end());
    vector<ll> store;
    int h = 0;
    string g;
    int flag = 1;
    while (1)
    {
        if (flag == 1)
        {

            rep(i, s.size())
            {
                if (s[i] == lk[h])
                {
                    store.push_back(i);
                }
            }
        }
        //つぎのindexの値の比較をする。
        int u = s.size();

        if (store[0] > u - k)
        {
            k -= s.size() - store[0];
            vector<ll> store3;
            store = store3;
            h += 1;
            continue; //その文字だけに着目してもダメな時
        }
        /*if (store.size() == 1)
        {
        }*/
        //これで最悪、端っこでも成立するはず、(最悪の場合でもk=1まで減らせた。)
        if (k == 1)
        {
            cout << g + s[store[0]];
            break;
        }
        char j;
        rep(i, store.size())
        {
            if (store[i] != s.size() - 1) //末尾は無視する。
            {
                if (i == 0)
                {
                    j = s[store[i] + 1];
                }
                else
                {
                    j = min(j, s[store[i] + 1]); //より、小さいものを選択する。
                }
            }
        }
        vector<ll> store2;
        rep(i, store.size())
        {
            if (store[i] != s.size() - 1) //末尾は無視する。
            {
                if (s[store[i] + 1] == j)
                {
                    store2.push_back(store[i] + 1); //一番低いものを選択した。
                }
            }
        }

        k -= 1; //その文字の探索は終わった。次は、store2をstore1にコピーしてやる
        g = g + s[store[0]];
        store = store2;
        flag = 0;
    }
}


Measured memory_bytes: 384
n = int(input())
print(str(n) + ':', end='')
while n > 1:
    for p in range(2, n+1):
        if n % p == 0:
            n //= p
            print(' ' + str(p), end='')
            break
        elif p * p > n:
            print(' ' + str(n), end='')
            n = 1
            break
print()


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

#define ll long long
#define REP(x,a,b) for(int x=a;x<=b;x++)
#define rep(x,n) for(int x=0;x<n;x++)
#define cint(x) int x;cin>>x;
#define cins(x) string x;cin>>x;
#define pb push_back
#define repv(x,v) for(int x=0;x<v.size();x++)
typedef pair<int,int> P;

vector<int>child[1001];
map<int,string>name;
void dfs(int id, int depth){
	if(depth>=0){
		rep(i,depth)cout<<".";
		cout<<name[id]<<endl;
	}
	repv(i,child[id]){
		dfs(child[id][i],depth+1);
	}
}

int main(){
	
	cint(n);
	REP(i,1,n){
		cint(t);
		cins(s);
		name[i]=s;
		child[t].pb(i);
	}
	dfs(0,-1);
	
	return 0;
}


Measured memory_bytes: 1508
def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      for i in range(s+1,0):#以降の項を全て同じ値に
        array[i] = array[s]

  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
 
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
  
array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
  array = next_array(array)#次の配列へ
    
print(max_scr)

Measured memory_bytes: 9252
'use strict'

const main = input => {
	const args = input.split('\n').map(arg => arg.split(' '))
	const S = args[0][0]
	let cnt = 0
	if (S[0] === '+') cnt++
	if (S[1] === '+') cnt++
	if (S[2] === '+') cnt++
	if (S[3] === '+') cnt++
	console.log( cnt - (4 - cnt) )
}

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


Measured memory_bytes: 7372
#include <iostream>
#define N 1000001
using namespace std;


int main(){
  int a,b,n, sum;
  bool flag[N];
  int c, aa,bb;

  while( cin>>n>>a>>b && (n||a||b) ){

    for( int i=1;i<=n;i++ )
      flag[i] = false;

    if( b>a ){
      sum=b; b=a; a=sum;
    }
    sum=0;
    for( int i=b;i<=n;i++ ){
      if( flag[i] ){
	sum++;
	continue;
      }
      c=0;
      for( int n_ai=i; n_ai>=0 ;n_ai-=a ){
	if( n_ai % b==0 ){
	  ++sum;
	  //	  aa = c;
	  //	  bb = n_ai/b;
	  aa = a*c;
	  bb = n_ai;

	  c = aa+bb;
	  /*
	  cout << "i="<<i<< "\ta="<<a<<" b="<<b
	       <<" aa="<<aa<<" bb="<<bb 
	       << "\tn_ai="<<n_ai
	       << endl;
	  */
	  for( int j=2*c; j<=n;j+=c )
	    flag[j] = true;
	  break;
	}
	c++;
      }

    }
    cout << (n-sum) << endl;
  }

  return 0;
}

Measured memory_bytes: 1848
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int N = 210;

int n;

ll a[N];

string s;

void solve() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	cin >> s;
	vector<ll> vv;
	for (int i = n - 1; i >= 0; --i) {
		ll x = a[i];
		for (ll y : vv) {
			x = min(x, x ^ y);
		}
		if (s[i] == '0') {
			if (x != 0) {
				vv.push_back(x);
				sort(ALL(vv));
				reverse(ALL(vv));
			}
		} else {
			if (x != 0) {
				cout << 1 << "\n";
				return;
			}
		}
	}
	cout << 0 << "\n";
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	int tt;
	cin >> tt;
	for (int i = 0; i < tt; ++i) {
		solve();
	}
	return 0;
}




Measured memory_bytes: 3572
//
//  main.cpp
//  ProblemSolving
//
//  Created by Mac mini on 1/7/20.
//  Copyright © 2020 Mac mini. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
long long int  dp[51][51][1275];
int x[52], n, a;

long long int call(int idx, int cnt, int amount) {
	if(idx >= n) {
		if((double)amount / cnt == a)
			return 1;
		return 0;
	}

	if(dp[idx][cnt][amount] != -1) return dp[idx][cnt][amount];

	long long int  ret1 = 0, ret2 = 0;

	ret1 = call(idx + 1, cnt + 1, amount + x[idx]);
	ret2 = call(idx + 1, cnt, amount);

	dp[idx][cnt][amount] = ret1 + ret2;

	return dp[idx][cnt][amount];
}

int main() {
	cin >> n >> a;

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

	memset(dp, -1, sizeof(dp));

	cout << call(0, 0, 0) << "\n";

}


Measured memory_bytes: 29452
# -*- coding: utf-8 -*-
"""
X : 一度に焼ける最大個数
T : 焼く時間
N : 必要個数
N個のたこ焼きを作るのに何分必要か？
"""

N, X, T = [int(i) for i in input().split()]
#print(N,X,T)
print(-(-N // X) * T)

Measured memory_bytes: 9156
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

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

	if (n == 1) {
		cout << "Hello World" << endl;
	}
	else {
		int A, B;
		cin >> A >> B;
		cout << A + B << endl;
	}
}

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

int main(){
    int n, k; cin >> n >> k;
    int64_t ans = -1e9, max_score = -1e9; bool flg = true;
    vector<int64_t> p(n), c(n);
    vector<bool> used(n, false);
    vector<vector<int64_t>> scores;
    for (auto i = 0; i < n; i++) { cin >> p[i]; p[i]--; }
    for (auto i = 0; i < n; i++) {
        cin >> c[i]; max_score = max(c[i], max_score);
        if(c[i] >= 0) flg = false;
    }
    for (auto i = 0; i < n; i++) {
        if(used[i]) continue;
        scores.emplace_back(0);
        int index = i; int64_t sum = 0;
        while(not used[index]) {
            used[index] = true;
            index = p[index];
            scores.back().emplace_back(c[index]);
            sum += c[index];
        }
        if(sum < 0) sum = 0;
        auto size = (int)scores.back().size();
//        cout << sum << " " << size << endl;
        for (auto j = 0; j < size; j++) {
            int64_t res = scores.back()[j];
//            cout << j << " " << res << endl;
            for (auto l = 0; l <= min(k - 1, size); l++) {
//                cout << l << " " << res << " " << ans << endl;
                ans = max(ans, res + sum * ((k - l - 1) / size));
                res += scores.back()[(j + l + 1) % size];
            }
        }
    }
    if(flg) ans = max_score;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3788
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
struct node{
	int s,v;
}Node[100010];
bool cmp(node a,node b){
	if(a.v!=b.v)return a.v<=b.v;
	else return a.s<b.s;
}
int main() {
	int n,m,a,b,now=0;
	
	long long value=0;
	scanf("%d %d",&n,&m);
//	vector<node> ve;
	for(int i=0;i<n;i++){
		scanf("%d %d",&Node[i].v,&Node[i].s);
//		ve.push_back(Node);
	}
	sort(Node,Node+n,cmp);
	for(int i=0;i<n;i++){
		if(now+Node[i].s>=m){
			value+= (long long)(m-now)*Node[i].v;
			break;
		}else{
			value+=(long long)Node[i].s*Node[i].v;
			now+=Node[i].s;
		}
	}
	printf("%lld\n",value);
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long a[100000 + 100][3],b[100000+100][3];
long long sol(int n, int i, int j)
{
	if (i == n - 1)
	{
		long long m = -8;
		for(int t = 0; t < 3; t++)
		{
			if (t != j)
				m = max(m, a[i][t]);
			
		}
		return m;
	}
	long long m = -8,s=0;
	for (int t = 0; t < 3; t++)
	{
		if (t != j)
		{
			if (m < a[i][t])
				s = t;
			m = max(m, a[i][t]);

		}

	}
	if(b[i][s]==-1)
	b[i][s]= m + sol(n, i + 1, s);
	return b[i][s];
}
int main()
{
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
		{
			cin >> a[i][j];
			b[i][j] = -1;
		}
	b[n - 1][0] = a[n - 1][0];
	b[n - 1][1] = a[n - 1][1];
	b[n - 1][2] = a[n - 1][2];
	for (int i = n - 2; i > -1; i--)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				if (k != j)
				{
					b[i][j] = max(a[i][j] + b[i + 1][k], b[i][j]);
				}
			}
		}
	}
	cout << (max(max(b[0][0], b[0][1]), b[0][2]))<<endl;
	
	return 0;
}

Measured memory_bytes: 4992
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(a){return a?cin[cid++]:+cin[cid++];}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var BIT = (function(){
  function f(n){return new BIT(n);}
  function BIT(n){
    this.a = Array(n+1).fill(0);
  }
  BIT.prototype.add = function(x,i){
    for(;i<this.a.length;i+=i&-i)this.a[i]+=x;
  };
  BIT.prototype.get = function(i){
    for(var r=0;i;i-=i&-i)r+=this.a[i];
    return r;
  };
  return f;
})();

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next();
  var s = next(1).split("");
  var q = next();
  var bit = Array(26).fill().map(a=>new BIT(n));
  for(var i = 0; i < n; i++){
    bit[s[i].charCodeAt()-97].add(1,i+1);
  }
  var ans = [];
  for(var i = 0; i < q; i++){
    if(next() === 1){
      var j = next(), c = next(1);
      bit[s[j-1].charCodeAt()-97].add(-1,j);
      bit[c.charCodeAt()-97].add(1,j);
      s[j-1] = c;
    }else{
      var l = next()-1, r = next();
      var cnt = 0;
      for(var j = 0; j < 26; j++){
        if(bit[j].get(r) - bit[j].get(l))cnt++;
      }
      ans.push(cnt);
    }
  }
  return ans.join("\n");
}

Measured memory_bytes: 122652
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();  // input Integer
    int b = sc.nextInt();  // input Integer
//    String a = sc.next();  // input String
    if (a<b){
      System.out.println(0);
    } else {
      System.out.println(10);
    }
  }
}

Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
#include "stdio.h"
using namespace std;

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

using ll = long long;
using Pii = pair<int, int>;

const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const long long mod_const = 1e9+7;

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

using MIte = multimap<ll, ll, greater<ll> >::iterator;

//2040
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// long long?
	string S;
	ll K;
	cin >> S >> K;

	string ans = "1";
	for (ll i = 0; i != K; ++i) {
		if (S[i] != '1') {
			ans = S[i];
			break;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
    int a,b,c,sum=0;
    cin>>a>>b>>c;
    sum=a+b+c;
    if(sum>=22)
    {
        cout<<"bust\n";
    }
    else
    {
        cout<<"win\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
    double a, b, C, S, L, h;
    cin >> a >> b >> C;
    S = a*b*sin(C*M_PI/180)/2;
    L = sqrt(a*a + b*b - cos(C*M_PI/180)*2*a*b) + a + b;
    h = 2*S/a;
    printf("%lf\n", S);
    printf("%lf\n", L);
    printf("%lf\n", h);
    return 0;
}


Measured memory_bytes: 3620
n, d = gets.split.map(&:to_i)
x, y = 0, 0
count  = 0
n.times {
  x, y = gets.split.map(&:to_i)
  if Math.sqrt( (x.abs)*(x.abs) + (y.abs) * (y.abs) ) <= d
#    puts Math.sqrt( (x.abs)*(x.abs) + (y.abs) * (y.abs) )
    count += 1
  end
}


puts count


Measured memory_bytes: 14288
N = int(input())

evidences = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x - 1, y))

result = 0
for i in range(1, 2 ** N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)


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


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

    int ans = 0;
    for (int i = 0;i < N;i++){
      int l,r;cin >> l >> r;
      ans += (r-l)+1;
    }
    
    cout << ans << endl;
    
  }       

Measured memory_bytes: 256
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,A = map(int,input().split())
X = [0] + list(map(int,input().split())) # 1枚も選ばない場合として 0 を足しておく

# dp[n][k][d] : n枚からk枚選んで合計dにする選び方
dp = [[[0 for _ in range(50*N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for n in range(N+1):
    for k in range(n+1):
        for d in range(50*k+1):
            # 目指す "合計の数 : d" がn枚目のカードより小さい場合, そのカードは使えない
            if d < X[n]:
                dp[n][k][d] = dp[n-1][k][d]
            # そうでない場合
            else:
                # k==0のときはカードを選べないことに注意
                if k >= 1:
                    dp[n][k][d] = dp[n-1][k][d] + dp[n-1][k-1][d-X[n]]
                    # dp[n-1][k][d] : k枚目のカードを選ばない場合
                    # dp[n-1][k-1][d-X[n]] : k枚目のカードを選ぶ場合。n-1枚目までで合計 d-X[n] であれば良い。

ans = 0
for i in range(1,N+1): # 0を除く、0のときは「0枚から0枚選んで0にする」で1通りになるが、これは答えには含まれない
    # N枚からi枚選んで平均がA,つまり合計がA*i
    ans += dp[N][i][A*i]

print(ans)

Measured memory_bytes: 65504
import sys
import itertools as it
input = sys.stdin.readline

N, M, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

AS = list(it.accumulate(A))
BS = list(it.accumulate(B))
AS.insert(0,0)
BS.insert(0,0)
max = 0
j = M
for i in range(N+1):
    if AS[i] > K:
        break
    while i + j > max:
        if AS[i] + BS[j] <= K:
            if max < i + j:
                max = i + j
            break
        j -= 1

print(max)

Measured memory_bytes: 124128
#include<bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    int sum=0;
    for(auto a:s){
        sum+=(int)(a-'0');
    }
    if(sum%9==0){
        cout << "Yes";
    }
    else cout << "No";
    return 0;
}


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

#define ll long long
ll dp[111111];
ll arr[111111];

int main()
{
    ll n;
    cin >> n;
    for(ll i = 1;i <= n;i++){
        cin >> arr[i];
    }
    dp[1] = 0;
    dp[2] = abs(arr[2] - arr[1]);
    for(int i = 3;i <= n;i++){
        dp[i] = min(dp[i-1] + abs(arr[i-1] - arr[i]),dp[i-2]+ abs(arr[i-2] - arr[i]));
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
LL S[100011];
int X[100011], cnt;

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%lld", S+i);

    LL ans = 0;
    for (int D=1; D<N-1; D++) {
	LL tmp = 0;
	int l = 0, r = N-1;
	cnt++;

	while (l != r && D < r && l < N-1 && X[r] != cnt && X[l] != cnt) {
	    tmp += S[l];
	    tmp += S[r];
	    X[l] = X[r] = cnt;
	    l+=D; r-=D;
	    amax(ans, tmp);
	}
    }
    printf("%lld\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cout << a[n - 1 - i];
    if (i != n - 1) cout << " ";
  }
  cout << endl;
}


Measured memory_bytes: 3088
#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

//long long
struct node {
	int v;
	long long c;
	node *next;
} pool[8100000] , *g[810000];
struct tree {
	int l , r , nd;
	tree *ll , *rr;
} poolt[810000] , *t1 , *t2;
struct so {
	int i;
	long long c;
};
int topn , topt;
int n , m;
int index;
long long dis[610000] , f[610000];
bool operator < ( so x1 , so x2 ) {
	return x1.c > x2.c;
}
priority_queue < so > q;
void add ( int u , int v , long long c ) {
	node *tmp = &pool[++topn];
	//printf ( "  %lld %lld %lld\n" , u , v , c );
	tmp -> v = v; tmp -> c = c; tmp -> next = g[u]; g[u] = tmp;
}
void buildtree ( tree *id , int l , int r , int f ) {
	id -> l = l; id -> r = r; id -> nd = ++index;
	if ( l == r ) {
		if ( f == 1 ) add ( id -> nd , l , 0 );
		else add ( l , id -> nd , 0 );
		return ;
	}
	int mid = (l+r)/2;
	id -> ll = &poolt[++topt];
	id -> rr = &poolt[++topt];
	buildtree ( id -> ll , l , mid , f );
	buildtree ( id -> rr , mid + 1 , r , f );
	if ( f == 1 ) {
		add ( id -> nd , id -> ll -> nd , 0 );
		add ( id -> nd , id -> rr -> nd , 0 );
	}
	else {
		add ( id -> ll -> nd , id -> nd , 0 );
		add ( id -> rr -> nd , id -> nd , 0 );
	}
}
void change ( tree *id1 , tree *id2 , int l , int r , long long c , int num ) {
	if ( id1 -> l == l && id1 -> r == r ) {
		add ( num , id1 -> nd , c );
		add ( id2 -> nd , num , 0 );
		return ;
	}
	int mid = (id1->l+id1->r)/2;
	if ( r <= mid ) change ( id1 -> ll , id2 -> ll , l , r , c , num );
	else {
		if ( l > mid ) change ( id1 -> rr , id2 -> rr , l , r , c , num );
		else {
			change ( id1 -> ll , id2 -> ll , l , mid , c , num );
			change ( id1 -> rr , id2 -> rr , mid + 1 , r , c , num );
		}
	}
}
void spfa () {
	int i;
	so k , tmp;
	for ( i = 1 ; i <= n + m + n * 4 ; i++ ) {
		dis[i] = 2147483647777777ll;
		f[i] = 0;
	}
	dis[1] = 0;
	k.i = 1; k.c = 0;
	q.push ( k );
	while ( q.size () ) {
		k = q.top(); q.pop();
		if ( f[k.i] ) continue;
		//printf ( "%lld %lld\n" , k , dis[k] );
		f[k.i] = 1;
		for ( node *j = g[k.i] ; j ; j = j -> next ) {
			if ( dis[j->v] > dis[k.i] + j -> c ) {
				dis[j->v] = dis[k.i] + j -> c;
				tmp.i = j -> v; tmp.c = dis[j->v];
				q.push ( tmp );
			}
		}
	}
}
void work () {
	int i , l , r;
	long long c;
	scanf ( "%d%d" , &n , &m );
	//n = m = 100000;
	index = n + m;
	t1 = &poolt[++topt];
	buildtree ( t1 , 1 , n , 1 );
	t2 = &poolt[++topt];
	buildtree ( t2 , 1 , n , 2 );
	for ( i = 1 ; i <= m ; i++ ) {
		scanf ( "%d%d%lld" , &l , &r , &c );
		/*l = rand () * rand () % n + 1 ;
		r = rand () * rand () % n + 1 ;
		if ( l > r ) swap ( l , r );
		c = rand () * rand ();*/
		change ( t1 , t2 , l , r , c , n + i );
	}
	spfa ();
	if ( dis[n] == 2147483647777777ll ) dis[n] = -1;
	printf ( "%lld\n" , dis[n] );
}
int main () {
	work ();
	return 0;
}


Measured memory_bytes: 117868
object Main extends App {
  //  val file = new File("targetfile")
  val testdata =
    """
1200"""
// 出力例1
// 3
//   val sc = new java.util.Scanner(testdata)
 val sc = new java.util.Scanner(System.in)

  val _x = sc.nextInt

  if (_x % 1000 > 0) {
    println(1000 - _x % 1000)
  } else {
    println(0)
  }
}


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

int N;
using psii = pair<pair<string, int>, int>;

int main() {
  cin>>N;
  vector<psii> vec(N);
  rep(i, N){
    cin>>vec[i].first.first>>vec[i].first.second;
    vec[i].second=i+1;
    vec[i].first.second*=-1;
  }
  sort(vec.begin(), vec.end());

  for(auto v: vec){
    cout<<v.second<<endl;
  }
}

Measured memory_bytes: 3548
// #include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define trace(x) cerr << #x << ": " << x << " " << endl;
 
typedef int64_t ll;
 
#define endl '\n'
#define int ll
ll mod=1e9+7;
ll mod1=1e9+5;
ll power(ll a,ll b)
{
    if(b==0) return 1;
    else if(b%2==0)
        return power(((((a)%mod)*((a)%mod))%mod),b/2)%mod;
    else return (((a)%mod)*(power(((((a)%mod)*((a)%mod))%mod),b/2)%mod))%mod;
}
inline ll inverse(ll a) {
  a %= mod;
  if (a < 0) a += mod;
  ll b = mod, u = 0, v = 1;
  while (a) {
    ll t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += mod;
  return u;
}
  
  
 //using namespace __gnu_pbds;
 //#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
//find_by_order(k)  returns iterator to kth element starting from 0;
//order_of_key(k) returns count of elements strictly smaller than k;
//erase,insert same as normal set
// mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count()); for randomized solution
ll fastmod(ll x)
{
    return x<mod?x:x%mod;
}
int32_t main()
{
    IOS
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
   
    int n,k;
    cin>>k;
    n=3;
    int dp[k+1];
    memset(dp,0,sizeof(dp));
    for(int i=k;i>=1;--i)
    {
        dp[i]=power(k/i,n);
        for(int j=2*i;j<=k;j+=i)
        {
            dp[i]-=dp[j];
            dp[i]+mod;
            dp[i]%=mod;
        }
    }        
    int ans=0;
    for(int i=1;i<=k;i++)
    {
        ans+=dp[i]*i;
        ans%=mod;
    }
    cout<<ans<<endl;

}       

Measured memory_bytes: 3536
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N, M; cin >> N >> M;
    vl X(N), Y(N), Z(N);
    REP(i, N) cin >> X[i] >> Y[i] >> Z[i];
    
    ll ans = 0;
    for(int p=-1; p<=1; p+=2){
        for(int q=-1; q<=1; q+=2){
            for(int r=-1; r<=1; r+=2){
                vl sum(N);
                REP(i, N) sum[i] = p * X[i] + q * Y[i] + r * Z[i];
                sort(sum.begin(), sum.end(), greater<ll>());
                ll tmp = 0;
                REP(i, M) tmp += sum[i];
                ans = max(ans, tmp);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

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

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

int main()
{
    cout << fixed << setprecision(15);
    ll N;
    cin >> N;
    
    map<string, ll> Blue;
    REP(i, N){
        string s;
        cin >> s;
        Blue[s]++;
    }

    ll M;
    cin >> M;
    
    map<string, ll> Red;
    REP(i, M){
        string s;
        cin >> s;
        Red[s]++;
    }

    ll ans = 0;

    for(auto iter=Blue.begin(); iter!=Blue.end(); iter++){
        ll temp = iter->second;
        if(Red.count(iter->first)){
            temp -= Red[iter->first];
        }
        ans = max(ans, temp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

P = (A1 - B1) * T1
Q = (A2 - B2) * T2

if P > 0:
    P *= -1
    Q *= -1

if P + Q < 0:
    print(0)
elif P + Q == 0:
    print('infinity')
else:
    S, T = divmod(-P, P+Q)
    if T != 0:
        print(S * 2 + 1)
    else:
        print(S * 2)


Measured memory_bytes: 3064
import itertools

s = input()

lis = list(itertools.product(["","+"], repeat = len(s)-1))

ans = 0
for i in range(len(lis)):
    evalu = ""
    for j in range(len(s)-1):
        evalu += s[j] +lis[i][j]
    evalu += s[-1]
    ans += eval(evalu)
print(ans)

Measured memory_bytes: 67936
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)
Ans = [-1] * (N-1)
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u!=p:
            if col == p_col:
                col += 1
            Ans[idx] = col
            dfs(u, v, col)
            col += 1
dfs()
print("\n".join(map(str, Ans)))



Measured memory_bytes: 85652
#include<bits/stdc++.h>
using namespace std; 
using ll=long long;
#define endl "\n"
#define F(i,n) for(ll i=0;i<n;i++)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repp(i,a,b) for(ll i=a;i>=b;i--)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define mp make_pair
#define vll vector<ll>
#define f first
#define s second
#define pll pair<ll,ll>
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()

void solve(){
 
    ll n,ans=0,x,k;
    cin>>n;
    
    vll a(n+1);

    F(i,n+1)  cin>>a[i];

    F(i,n){
        cin>>x;
        k=min(x,a[i]);
        ans+=k;
        x=x-k;
        a[i]-=k;
        k=min(x,a[i+1]);
        a[i+1]-=k;
        ans+=k;
    }

    cout<<ans;

}
signed main(){
    fast;
     
    solve();
 
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define itn int
#define REP(i, n) for (int i = 0; i < n; i++)
#define IREP(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(a, b) for (int i = a; i < b + 1; i++)
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main(){
  string s;
  cin >> s;
  string t;
  cin >> t;
  vector<int> v;
  if(s.size()<t.size()){
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  REP(i,s.size()-t.size()+1){
    bool flag=true;
    for(int j=0;j<t.size();j++){
      if(s[j+i]==t[j]){
        continue;
      }
      else if(s[j+i]=='?'){
        continue;
      }
      else{
        flag=false;
      }
    }
    if(flag){
      v.push_back(i);
    }
  }
  if(v.empty()){
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  sort(v.begin(),v.end(),greater<int>());
  int tmp=v[0];
  REP(i,s.size()){
    if(s[i]=='?'){
      if(i>=tmp&&i<tmp+t.size()){
        s[i]=t[i-tmp];
      }
      else{
        s[i]='a';
      }
    }
  }
  cout << s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sidha(i,a,b) for(int i=a;i<b;i++)
#define vi vector<int> 
#define pb push_back
#define st string
#define pairi pair<int,int>
#define INF 1000000007

int solve(string a,string b) 
{ 
  int n=a.size(),m=b.size(); 
  int ans=INT_MAX;
  for (int i=0;i<m-n+1;i++){ 
    int mn=0;  
  	for (int j=0;j<n;j++){ 
      if (a[j] != b[i + j]){ 
        mn++; 
      } 
    } 
    ans=min(mn,ans); 
  } 
  return ans; 
} 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
	string a,b;cin>>a>>b;
	cout<<solve(b,a)<<endl;
}

Measured memory_bytes: 3660