akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back      
#define F first
#define S second
#define SS stringstream
#define sqr(x) ((x)*(x))
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define CC(x) cout << (x) << endl
#define pw(x) (1ll<<(x))
#define buli(x) __builtin_popcountll(x)
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define M 1000000007
#define N 211111

#define TASK "1"

using namespace std;

int R, C, n;
vector<pair<int, int> > v[N], col[N];

vector<int> cur;

int was[N];
long long w[N];

vector<pair<int, int> > ed[N];

void rec(int x, long long d) {
	if (was[x] != -1) {
		if (w[x] != d) {
			cout << "No\n";
			exit(0);
		}		
		return;
	}
	cur.pb(x);
	was[x] = 1;
	w[x] = d;
	for (int i = 0; i < ed[x].size(); i++) rec(ed[x][i].F, d + ed[x][i].S);
}

int main(){
	#ifdef home
		freopen(TASK".in","r",stdin);	
		freopen(TASK".out","w",stdout);
	#endif		
	ios::sync_with_stdio(false);
	cin >> R >> C >> n;
	for (int i = 0; i < n; i++) {
		int x, y, a;
		cin >> x >> y >>a;
		x--;
		y--;
		v[x].pb(mp(y, a));

		col[y].pb(mp(x, a));
	}
	for (int i = 0; i < R; i++) if (v[i].size() > 1) {
		sort(v[i].begin(), v[i].end());
		for (int j = 1; j < v[i].size(); j++) {
			int x = v[i][j - 1].F;
			int y = v[i][j].F;
			int z = v[i][j].S - v[i][j - 1].S;

			ed[x].pb(mp(y, z));
			ed[y].pb(mp(x, -z));
		}
	}
	for (int i = 0; i < C; i++) was[i] = -1;
	for (int i = 0; i < C; i++) if (was[i] == -1) {
		cur.clear();

		rec(i, 0);

		long long mi = 1e18 + 1;
		for (int e : cur) mi = min(mi, w[e]);

		for (int c : cur) for (int j = 0; j < col[c].size(); j++) {
			int r = col[c][j].F;
			int val = col[c][j].S;

			long long t = w[c] - mi;
			if (val < t) {
				cout << "No\n";
				return 0;
			}
		}
	}
	cout << "Yes\n";
		
	return 0;
}

Measured memory_bytes: 23680
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second

int main(){
    int s;
    cin >> s;
    vector<int> A;
    A.push_back(s);
    int m;
    while(true){
        int n = A[A.size()-1];
        if(n % 2 == 0) A.push_back(n / 2);
        else A.push_back(3 * n + 1);
        int N = A.size();
        for(int i = 0; i < N - 1; i++){
            if(A[i] == A[N - 1]){
                m = N;
                goto finish;
            }
        }
    }
    finish:
    cout << m << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int yes(){
	cout << "Yes" << endl;
	return 0;
}

int no(){
	cout << "No" << endl;
	return 0;
} 

int main(){
	int h, w; cin >> h >> w;
	map<char, int> mp;
	for( int i = 0; i < h; ++i ){
		string s; cin >> s;
		for( char c : s ) ++mp[c];
	}
	
	vector<int> valid;
	int a = 0, b = 0, c = 0, d = 0;
	if( h % 2 == 0 && w % 2 == 0 ){
		a = h*w/4;
	} else if( h % 2 == 0 && w % 2 == 1 ){
		a = (w-1)*h/4;
		b = h/2;
	} else if( h % 2 == 1 && w % 2 == 0 ){
		a = (h-1)*w/4;
		b = w/2;
	} else if( h % 2 == 1 && w % 2 == 1 ){
		a = (h-1)*(w-1)/4;
		b = (h+w-1)/2;
		c = 1;
	}
	for( int i = 0; i < a; ++i ) valid.push_back(4);
	for( int i = 0; i < b; ++i ) valid.push_back(2);
	for( int i = 0; i < c; ++i ) valid.push_back(1);	
	
	vector<int> candy;
	for( auto paar : mp ){
		int gs = paar.second;
		if( gs % 2 == 1 ){
			candy.push_back(1);
			gs -= 1;
		}
		if( gs % 4 == 2 ){
			candy.push_back(2);
			gs -= 2;
		}
		for( int i = 0; i < gs/4; ++i ) candy.push_back(4);
	}
		
	sort( valid.begin(), valid.end() );
	sort( candy.begin(), candy.end() );
	

	
	if( lower_bound( valid.begin(), valid.end(), 2 ) - lower_bound( valid.begin(), valid.end(), 1 ) != lower_bound( candy.begin(), candy.end(), 2 ) - lower_bound( candy.begin(), candy.end(), 1 ) ) return no();
	
	a = lower_bound( valid.begin(), valid.end(), 4 ) - lower_bound( valid.begin(), valid.end(), 2 );
	b = lower_bound( valid.begin(), valid.end(), 5 ) - lower_bound( valid.begin(), valid.end(), 4 );
	c = lower_bound( candy.begin(), candy.end(), 4 ) - lower_bound( candy.begin(), candy.end(), 2 );
	int bound = d = lower_bound( candy.begin(), candy.end(), 5 ) - lower_bound( candy.begin(), candy.end(), 4 );
	if( a == c && b == d ) return yes();
	for( int i = 0; i <= bound; ++i ){
		c += 2; --d;
		if( a == c && b == d ) return yes();
	}
	return no();
}

/*

h, w がともに偶数
4 つずつ文字を当てはめる
h*w/4 個

h が奇数なら
真ん中の行（列）が 2 つですむ
w/2 + (h-1)*w/4 個

h, w の両方が奇数なら
一番真ん中は 1 つですむ
(h-1)*(w-1)/4 + (h+w-1)/2 + 1 個

*/

Measured memory_bytes: 256
from itertools import product

def f(n):
    return 3**n - 3*(1 + 2**n - 2)

s = input()
n = int(s)
m = len(s)

ans=0

if m>=4:
    for i in range(3,m):
        ans+=f(i)

for s in product(['7','5','3'],repeat=m):
    if len(set(s))==3 and int(''.join(s))<=n:
        ans+=1

print(ans)


Measured memory_bytes: 3064
(* O(log(n)) (n = max {a, b}) *)
let rec gcd a b = if b = 0 then a else gcd b (a mod b)

(* O(n) *)
let rec fold_btw f a i n = if i >= n then a else fold_btw f (f a i) (i + 1) n
let fold_int f a n = fold_btw f a 0 n

(* O(|ns| * log(max ns)) *)
let gcd_info ns =
  let n = Array.length ns in
  let front = Array.make n 0 in
  let _ = fold_int (fun g i -> let g1 = gcd g ns.(i) in front.(i) <- g1; g1) 0 n in
  let back = Array.make n 0 in
  let _ = fold_int (fun g i -> let g2 = gcd g ns.(n - 1 - i) in back.(n - 1 - i) <- g2; g2) 0 n in
  (front, back)

(* O(log(m)) (m = max {max front, max back}) *)
let excluded_gcd i n front back =
  let front_g = if i <= 0 then 0 else front.(i - 1) in
  let back_g = if i >= n - 1 then 0 else back.(i + 1) in
  gcd front_g back_g

(* O(n * log(max a_s)) *)
let solve n a_s =
  let front, back = gcd_info (Array.of_list a_s) in
  let gcds = fold_int (fun acc i -> excluded_gcd i n front back :: acc) [] n in
  List.fold_left max 0 gcds

let read_ints () = read_line () |> Str.split (Str.regexp " ") |> List.map int_of_string

let _ = let n = read_int () in read_ints () |> solve n |> string_of_int |> print_endline

Measured memory_bytes: 19584
import java.util.*;

public class Main {
    public static void main(String args[]) {
        solve1142();
    }

    public static void solve1142() {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            String dataset = sc.next();
            HashSet<String> set = new HashSet<String>();

            for (int index = 0; index < dataset.length(); index++) {
                String zenhan = dataset.substring(0, index);
                String kouhan = dataset.substring(index);

                StringBuffer sb_zenhan = new StringBuffer(zenhan);
                StringBuffer sb_kouhan = new StringBuffer(kouhan);

                String rev_zenhan = sb_zenhan.reverse().toString();
                String rev_kouhan = sb_kouhan.reverse().toString();


                set.add(zenhan + kouhan);
                set.add(zenhan + rev_kouhan);
                set.add(rev_zenhan + kouhan);
                set.add(rev_zenhan + rev_kouhan);
                set.add(kouhan + zenhan);
                set.add(kouhan + rev_zenhan);
                set.add(rev_kouhan + zenhan);
                set.add(rev_kouhan + rev_zenhan);

            }
            System.out.println(set.size());
        }
    }

}



Measured memory_bytes: 61712
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<set>
#include<map>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
const ll INF = 1e17;
const int MOD = 1e9 + 7;
ll dp[100005];
ll po[100005];
ll N,K;
int main(void) {
	
	
	cin >> N>>K;
	FOR(i, 0, N)dp[i] = INF;
	
	dp[0] = 0;
	FOR(i, 0, N)cin >> po[i];
	dp[1] = abs(po[0] - po[1]);
	FOR(i, 2, N) {
		
		for (int k = 1; (i - k) >= 0 && k <= K; k++) {
			dp[i] = min(dp[i], dp[i - k] + abs(po[i - k] - po[i]));
		}
		}
	ct(dp[N - 1]);
	return 0;
}

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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main() {
    // random_device rnd;
    // mt19937 mt(rnd());
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long int N;
    cin >> N;
    vector<long long int> monster (N+1);
    for(long long int i = 0;i < N+1;i++){
        cin >> monster[i];
    }
    vector<long long int> hero (N);
    for(long long int i = 0;i < N;i++){
        cin >> hero[i];
    }

    long long int ans = 0;
    for(long long int i = 0;i < N;i++){
        ans += min(monster[i],hero[i]);
        hero[i] = max(hero[i]-monster[i],0LL);
        ans += min(monster[i+1],hero[i]);
        monster[i+1] = max(monster[i+1]-hero[i],0LL);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include<stdio.h>
using namespace std;

int main()
{
	int a, b, s, i;
	while ((scanf("%d %d", &a, &b)) != EOF)
	{
		s = a + b;
		for (i = 0;s>0; i++)
		{
			s = s / 10;
		}
		printf("%d\n",i);
	}
	return 0;
}

Measured memory_bytes: 2708
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef long long LL;

int n;
VI a(3), l(10);
VI v(10);

int ans = INT_MAX;
VI A, B, C;
void check() {
	A.clear(), B.clear(), C.clear();
	rep(i, n) {
		if (v[i] == 1)A.pb(l[i]);
		if (v[i] == 2)B.pb(l[i]);
		if (v[i] == 3)C.pb(l[i]);
	}
	int costA = abs(a[0] - accumulate(all(A), 0)) + 10 * max(sz(A) - 1, 0);
	int costB = abs(a[1] - accumulate(all(B), 0)) + 10 * max(sz(B) - 1, 0);
	int costC = abs(a[2] - accumulate(all(C), 0)) + 10 * max(sz(C) - 1, 0);
	int cost = costA + costB + costC;

	bool flag = (A.empty() || B.empty() || C.empty());
	if (ans > cost && !flag)ans = cost;
}

void dfs(int d) {
	if (n == d) {
		check();
		return;
	}
	rep(i, 4) {
		v[d] = i;
		dfs(d + 1);
	}
}

int main() {
	cin >> n;
	rep(i, 3)cin >> a[i];
	rep(i, n)cin >> l[i];

	dfs(0);
	cout << ans << endl;
}

Measured memory_bytes: 256
T = input()
S = input()

n_s = len(S)
n_t = len(T)

MaxScore = 0

for i in range(n_t-n_s+1):
    tempT = T[i:i+n_s]
    score = 0
    for j in range(n_s):
        if S[j] == tempT[j]:
            score += 1
    MaxScore = max(score,MaxScore)

print(n_s-MaxScore)

Measured memory_bytes: 9056
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <iomanip>
using namespace std;
#define Would
#define you
const int INF = 999999999;
const int MOD = 1e9 + 7;

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

int main() {
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << endl;
}


Measured memory_bytes: 3124
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

// 単語の検索
func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	W := sc.Text()
	cnt := 0
	for {
		sc.Scan()
		s := sc.Text()
		if s == "END_OF_TEXT" {
			break
		}
		if W == strings.ToLower(s) {
			cnt++
		}
	}
	fmt.Println(cnt)
}



Measured memory_bytes: 1104
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> unagi[1000000];
pair<int,int> wolf[1000000];
int u_row[500];
int u_col[500];
int w_row[500];
int w_col[500];
int main(){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    for(int i=0;i<1000000;i++){
        unagi[i]=make_pair(-1,-1);
        wolf[i]=make_pair(-1,-1);
    }
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++){
            int p;
            scanf("%d",&p);
            unagi[p-1]=make_pair(i,j);
        }
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++){
            int p;
            scanf("%d",&p);
            wolf[p-1]=make_pair(i,j);
        }
    int UL=0;
    int UR=0;
    int WL=0;
    int WR=0;
    int u=0;int w=0;
    if(a==1){
        for(int i=0;i<d;i++){
            int e;
            scanf("%d",&e);e--;
            if(~unagi[e].first)u++;
            if(~wolf[e].first)w++;
        if(u>=b&&w>=c){
            printf("DRAW\n");
            return 0;
        }
        if(u>=b){
            printf("USAGI\n");
            return 0;
        }
        if(w>=c){
            printf("NEKO\n");
            return 0;
        }
        }
        printf("DRAW\n");
        return 0;
    }
    for(int i=0;i<d;i++){
        int e;
        scanf("%d",&e);e--;
        if(~unagi[e].first){
            u_row[unagi[e].first]++;
            if(u_row[unagi[e].first]==a)u++;
            u_col[unagi[e].second]++;
            if(u_col[unagi[e].second]==a)u++;
            if(unagi[e].first==unagi[e].second){
                UL++;
                if(UL==a)u++;
            }
            if(unagi[e].first+unagi[e].second==a-1){
                UR++;
                if(UR==a)u++;
            }
        }
        if(~wolf[e].first){
            w_row[wolf[e].first]++;
            if(w_row[wolf[e].first]==a)w++;
            w_col[wolf[e].second]++;
            if(w_col[wolf[e].second]==a)w++;
            if(wolf[e].first==wolf[e].second){
                WL++;
                if(WL==a)w++;
            }
            if(wolf[e].first+wolf[e].second==a-1){
                WR++;
                if(WR==a)w++;
            }
        }
        if(u>=b&&w>=c){
            printf("DRAW\n");
            return 0;
        }
        if(u>=b){
            printf("USAGI\n");
            return 0;
        }
        if(w>=c){
            printf("NEKO\n");
            return 0;
        }
    }
    printf("DRAW\n");
}

Measured memory_bytes: 16644
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

struct SegmentTree {
  using T = struct { int min, max; };
  static T op(const T& a, const T& b) { return {min(a.min, b.min), max(a.max, b.max)}; }
  static constexpr T e() { return {(int)1e9, (int)-1e9}; }

  const int n;
  V<T> t;
  SegmentTree(int n) : n(n), t(2 * n, e()) {}
  T& operator[](int i) { return t[i + n]; }
  void build() { for (int i = n - 1; i; --i) t[i] = op(t[2 * i], t[2 * i + 1]); }
  T acc(int l, int r) const {
    T resl = e(), resr = e();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) resl = op(resl, t[l++]);
      if (r & 1) resr = op(t[--r], resr);
    }
    return op(resl, resr);
  }
  void set(int i, const T& a) {
    t[i += n] = a;
    while (i >>= 1) t[i] = op(t[2 * i], t[2 * i + 1]);
  }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, k; cin >> n >> k;
  V<> p(n);
  SegmentTree st(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    st[i] = {p[i], p[i]};
  }
  st.build();
  V<> c(n);
  for (int i = 0; i < n - 1; ++i) {
    c[i] = p[i] < p[i + 1];
  }
  for (int i = n - 1; i; --i) {
    c[i - 1] += c[i];
  }

  int res = 0;
  bool ex = false;
  for (int i = 0; i + k <= n; ++i) {
    if (c[i] - c[i + k - 1] == k - 1) {
      ex = true;
      continue;
    }
    if (i + k < n) {
      auto e = st.acc(i + 1, i + k);
      if (p[i] < e.min and e.max < p[i + k]) continue;
    }
    ++res;
  }
  res += ex;
  cout << res << '\n';
}

Measured memory_bytes: 4992
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
cnt=0
for i in range(0,n):
  if a[i]>=b[i]:
    cnt+=b[i]
    b[i]=0
  else:
    cnt+=a[i]
    if b[i]-a[i]<=a[i+1]:
      cnt+=b[i]-a[i]
      a[i+1]-=(b[i]-a[i])
    else:
      cnt+=a[i+1]
      a[i+1]=0
 
print(cnt)

Measured memory_bytes: 19156
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int main()
{
	string str;
	int i, ans = 0, ksu1 = 0, gsu1 = 0, ksu0 = 0, gsu0 = 0;
	cin >> str;
	for (i = 0; i < str.size(); i++) {
		if (str[i] == '1') {
			if (i & 1) {
				ksu1++;
			}
			else {
				gsu1++;
			}
		}
		if (str[i] == '0') {
			if (i & 1) {
				ksu0++;
			}
			else {
				gsu0++;
			}
		}
	}
	/*if (ksu1 > gsu1) {
		ans = gsu1 + ksu0;
	}
	else {
		ans = ksu1 + gsu0;
	}*/
	ans = min(gsu1 + ksu0, ksu1 + gsu0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    def fin():
        print("INF")
        exit()

    N, M = map(int, input().split())
    X = set()
    X.add(-10**9-1)
    X.add(0)
    X.add(10**9+1)
    Y = set()
    Y.add(-10**9-1)
    Y.add(0)
    Y.add(10**9+1)
    ABC = []
    DEF = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        X.add(a)
        X.add(b)
        Y.add(c)
        ABC.append((a, b, c))
    for _ in range(M):
        d, e, f = map(int, input().split())
        X.add(d)
        Y.add(e)
        Y.add(f)
        DEF.append((d, e, f))
    X = sorted(list(X))
    Y = sorted(list(Y))
    x2i = {x: i for i, x in enumerate(X)}
    y2j = {y: j for j, y in enumerate(Y)}
    LX = len(X)
    LY = len(Y)
    ABCwall = [set() for _ in range(LY)]
    for a, b, c in ABC:
        i0 = x2i[a]
        i1 = x2i[b]
        j = y2j[c]
        for i in range(i0, i1):
            ABCwall[j].add(i)
    DEFwall = [set() for _ in range(LX)]
    for d, e, f in DEF:
        i = x2i[d]
        j0 = y2j[e]
        j1 = y2j[f]
        for j in range(j0, j1):
            DEFwall[i].add(j)

    ii = x2i[0]
    jj = y2j[0]
    que = deque()
    que.append((ii, jj))
    seen = [[0] * (LY-1) for _ in range(LX-1)]
    seen[ii][jj] = 1
    ans = 0
    while que:
        i, j = que.popleft()
        ans += (X[i+1] - X[i]) * (Y[j+1] - Y[j])

        # x inc
        if j not in DEFwall[i+1]:
            if i == LX - 2:
                fin()
            if not seen[i+1][j]:
                que.append((i+1, j))
                seen[i+1][j] = 1

        # x dec
        if j not in DEFwall[i]:
            if i == 1:
                fin()
            if not seen[i-1][j]:
                que.append((i-1, j))
                seen[i-1][j] = 1

        # y inc
        if i not in ABCwall[j+1]:
            if j == LY - 2:
                fin()
            if not seen[i][j+1]:
                que.append((i, j+1))
                seen[i][j+1] = 1

        # y dec
        if i not in ABCwall[j]:
            if j == 1:
                fin()
            if not seen[i][j-1]:
                que.append((i, j-1))
                seen[i][j-1] = 1
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
  long k,n;
  cin >> k >> n;
  vector<long>data(n);
  for(int i = 0;i < n;i++) cin >> data[i];
  long ans = 0;
  for(int i = 0;i < n-1;i++){
    if(data[i+1]-data[i] > ans) ans = data[i+1]-data[i];
  }
  if(data[0]+k-data[n-1] > ans) ans = data[0]+k-data[n-1];
  cout << k-ans << endl;
}


Measured memory_bytes: 1792
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 10 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;

void solve() {
    int k;
    cin >> k;
    int cur = 7%k , ans = 1 , t = 1e7;
    while(cur != 0) {
        t --;
        if(t == 0) {
            cout << -1;
            return;
        }
        ans ++;
        cur *= 10;
        cur += 7;
        cur %= k;
    }
    cout << ans;

}
/*
*/
main() {
    ios;
    int tt = 1;
    //cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3656
//2019/9/28

#include <stdio.h>

int main (void) {
    double num;
    int mum;
    scanf("%lf",&num);
    mum=num;
    if (mum%2==0) {
        mum=mum/2;
    }
    else {
        mum=mum/2+1;
    }
    printf("%.10lf\n",mum/num);
    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	char c;
	cin>>c;
	if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
	{
		printf("vowel\n");
	} 
	else
	{
		printf("consonant\n");
	}
	return 0;
} 

Measured memory_bytes: 256
nmlist = list(map(int, input().split()))
svote = list(map(int, input().split()))
allvote = sum(svote)
maxvote = max(svote)
svote.sort(reverse=True)
n0 = nmlist[1] - 1
n1 =  svote[n0] / allvote
n2 = 1 / (4 * nmlist[1])
if n1 >= n2:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int n;
vector<int> anscandy;
int a, b, c;
int l[8];

void dfs( int x, int y, int z, int k, int mp ){
	if( k == n ){
		if( x != 0 && y != 0 && z != 0 ){
			anscandy.push_back( abs(a-x) + abs(b-y) + abs(c-z) + 10*(mp-3) );
		}
		return;
	}
	dfs( x+l[k], y, z, k+1, mp+1 );
	dfs( x, y+l[k], z, k+1, mp+1 );
	dfs( x, y, z+l[k], k+1, mp+1 );
	dfs( x, y, z, k+1, mp );
}

int main(){
	cin >> n >> a >> b >> c;
	for( int i = 0; i < n; ++i ) cin >> l[i];
	dfs( 0, 0, 0, 0, 0 );
	sort( anscandy.begin(), anscandy.end() );
	cout << anscandy[0] << endl;
	return 0;
}

Measured memory_bytes: 640
/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

// const ll MAX_N = 1e5;
// ll N;
// ll h[MAX_N];
// ll dp[MAX_N+1]; // メモ化テーブル
 
// // i番目以降の品物から重さの総和がj以下になるように選ぶ
// void rec(ll i){
// 	if (i==0) dp[i] = 0;
// 	else if (i==1) dp[i] = abs(h[1]-h[0]);
// 	else dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
// 	return;
// }
 
 
int main() {
	// 入力
	ll A[5];
	for (ll i = 0; i < 5; ++i) cin >> A[i];
	ll k; cin>>k;
	// 解法
	
	//出力
	if (A[4]-A[0]<=k) printf("Yay!\n");
	else printf(":(\n");
}


Measured memory_bytes: 256
<?php
	list($a,$b) = explode(" ",trim(fgets(STDIN)));
	//$a = trim(fgets(STDIN));
	//$b = trim(fgets(STDIN));
	if($a%3 == 0){
		echo "Possible";
	}elseif(($b % 3) == 0){
   		echo "Possible";
   	}elseif(($a+$b)%3==0){
   		echo "Possible";
   	}else{
   		echo "Impossible";
   	}
   	//echo $b%3;
   	//echo $a&3;
   	//echo $b
?>

Measured memory_bytes: 3828
#include <stdio.h>

int main(void){
    int n;
    int d[100];
    int ans;
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &d[i]);
    }
    ans = n;
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            if (d[i] == d[j] && d[i]) {
                ans -= 1;
                d[j] = 0;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define eps LDBL_EPSILON
#define mod 1000000007
#define int long long
#define double long double
#define INF INT_MAX
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, x, l[110];
signed main() {
	cin >> n >> x;
	rep(i, n)cin >> l[i];
	int now = 0, ans = 0;
	rep(i, n) {
		if (now <= x)ans++;
		now += l[i];
	}
	if (now <= x)ans++;
	cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
ab = []
for i in range(n):
    a, b = map(int, input().split(' '))
    ab.append([a+b, a, b])
ab.sort(reverse = True)
result = 0
for i in range(n):
    if i%2 == 0:
        result += ab[i][1]
    else:
        result -= ab[i][2]
print(result)

Measured memory_bytes: 23260
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
	int k,a,b;
	scanf("%d%d%d",&k,&a,&b);
	if(a>=b){
		printf("%d\n",k+1);
	}
	else{
		if(b-a<=1){
			printf("%d\n",k+1);
		}
		else{
			if(k+1<=a){
				printf("%d\n",k+1);
			}
			else{
				if((k-a+1)&1){
					cout<<(long long)a+(long long)(b-a)*1ll*(long long)((k-a+1)/2ll)+1ll<<endl;
				}
				else{
					cout<<(long long)a+(long long)(b-a)*1ll*(long long)((k-a+1)/2ll)<<endl;
				}
			}
		}
	}
	return 0;
}


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

int main() {
	long long  N,ans,k;
	ans = 0;
	cin >> N;
	if ((N % 2) == 0) {
		k = N;
		k = k / 10;
		ans = k;
		while (k> 0) {
			k = k / 5;
			ans += k;
		}
	}
	cout<< ans <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* * * *   * * *   	* * * */
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ms(a,v) memset(a,v,sizeof a)
/* * * *   * * *   	* * * */
/* *
 *
 * Author: Hamkor a.k.a. OakenSh1eld
 *
 * */
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string a, b; cin>>a>>b;
	int n = (int)a.size(), m = (int)b.size();
	vector<vector<int>> lcs(n+1, vector<int> (m+1, 0));
	for(int i=0; i<=n; ++i) for(int j=0; j<=m; ++j){
		if (i == 0 || j == 0) lcs[i][j] = 0;
		else if (a[i-1] == b[j-1]) lcs[i][j] = 1+lcs[i-1][j-1];
		else lcs[i][j] = max(lcs[i][j-1] , lcs[i-1][j]);
	}
	string ans = "";
	int cnt = lcs[n][m];
	while(cnt && n && m){
		if(lcs[n][m] == cnt && lcs[n][m] == lcs[n-1][m-1] + 1 && a[n-1] == b[m-1]){
			ans+=a[n-1];
			cnt--;
			n--; m--;
		}else if (lcs[n-1][m] >= lcs[n][m-1])n--;
		else m--;
	}
	reverse(ans.begin(), ans.end());
	cout<<ans;
	return 0;
}


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

int main() {
  int A, B;
  int sum;
  cin >> A >> B;
  sum = A + B;
  
  if(sum == 3) {
    cout << 3 << endl;
  } else if(sum == 4) {
    cout << 2 << endl;
  } else if(sum == 5) {
    cout << 1 << endl;
  }
  
}


Measured memory_bytes: 256
#n , m , l = map(int , input().split())

# list_n = list(map(int , inpuut().split()))<Paste>

#n = input()
# list = [input() for i in range(N)

#list = [[i for i in range(N)] for _ in range(M)]


import math
s = int(input().replace(" ", ""))
n = math.sqrt(s)
if n == int(n):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9072
#include <bits/stdc++.h>
using namespace std;
// #define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
#define ITR(v,c) for(auto v=begin(c);v!=end(c);v++)
#define FOR(v,a,n) for(int v=a;v<(int)(n);v++)
#define FORE(x,arr) for(auto &x:arr)
#define REP(v,n) FOR(v,0,n)
#define RREP(v,n) for(int v=((int)(n)-1);v>=0;v--)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define DUMP(x) cerr<<#x<<":="<<(x)<<endl
const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0};
const int INF=1e9; const long long INFLL=1e18;
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){
    ITR(i,v)os<<*i<<(i==end(v)-1?"":" ");return os;}
//------------------------------------------------------------------------------

signed main() {
    string s;
    cin>>s;
    REP(i,4) {
        putchar(s[i]);
    }
    putchar(' ');
    FOR(i,4,12) {
        putchar(s[i]);
    }
    putchar('\n');
    return 0;
}


Measured memory_bytes: 764
#include <stdio.h>

int main(void) {
	long int x = 1;
	
	int i=1;
	while(x != 0){
		
	scanf("%d",&x);
	if(x == 0){
		break;
	}

	printf("Case %d: %d\n",i,x);
	i++;
	}
		
	
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int N;
	cin >> N;
	vector<vector<int>> ans( N );
	for( int i = 0; i < N - 1; i++ ) {
		int A;
		cin >> A;
		A--;
		ans[A].push_back( i + 1 );
	}

	for( int i = 0; i < N; i++ ) {
		cout << ans[i].size() << endl;
	}
}

Measured memory_bytes: 14032
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define mod ((int)1e9+7)
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
typedef pair<double,double> pdd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a,ll b) {
   ll res=1;
   while(b){
      if(b%2==1) res=(res*a)%mod;
      a=(a*a)%mod;
      b>>=1;
   }
   return res;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)2e5+5;
const int M = (int)3e3+5;
const int Q = 301;
const int logN = 19;

void solve() {
    int n;
    cin>>n;
    vector<int> ans(n+1);
    REP(i,2,n) {
        int a;
        cin>>a;
        ans[a]++;
    }
    REP(i,1,n) {
        cout<<ans[i]<<"\n";
    }
}
int main() {
    //freopen("output.txt","r",stdin);
    //freopen("output.txt","w",stdout);

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

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        //cout<<"\n";
    }
}


Measured memory_bytes: 3968
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  
  string s;
cin >>s;
  ll x=s.size();
  ll charnum=0;
 string S;
  rep(i,x) {
    if((s.at(i)=='0') ||(s.at(i)=='1')){ 
      S+=s.at(i);
    }
  
     
      if(s.at(i)=='B') {
        if(S.size()>0) {
          string h;
          rep(j,S.size()-1) {
            h+=S.at(j);
          }
          S=h;
          
            
            
          
          
          
          
          
          
        }
      }
     
      
      
  }

      
      
      
      
      
      
      
      

    
    

cout<<S<<endl;
    
    
    
    
  }
    
    
 

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let (n,m) = get!(usize, usize);
    let mut a = get!([usize]);
    let mut bc = get!(usize, usize;m);

    a.sort();
    bc.sort_by(|&(_,c1),&(_,c2)| c2.cmp(&c1));

    let mut vec = vec![0; n];
    let mut length = 0;
    for (b,c) in bc {
        for i in length..min!(length+b, n) {
            vec[i] = c;
        }
        length += b;
    }

    let mut sum = 0;
    for i in 0..n {
        sum += max!(a[i], vec[i]);
    }
    println!("{}", sum);
}


Measured memory_bytes: 13080
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

  int n,m; cin >> n >> m;
  vector<int> dp(n+1,0);
  for(int i = 0; i < m; i++){
    int l,r; cin >> l >> r;
    dp[l]++;
    dp[r+1]--;
  }

  int ans = 0;
  for(int i = 0; i <= n; i++){
    if(i) dp[i] += dp[i-1];
    if(dp[i] >= m) ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

string dp[10010];       // dpはn文字目までの最大値

const string MININF = "-";

// string の大小は　・sizeがデカい方がデカい　・同サイズなら辞書順にデカいほうがデカい　を使う。
// しかし、サイズがデカくても辞書順にソートしたら 11111より9の方がデカいことに注意。
void csmax(string& a,const string& b){
    int as = a.size();
    int bs = b.size();

    if(a == MININF)a = b;
    else if(as == bs)a = max(a,b);
    else if(as < bs)a = b;
}


int main(){
    int N,M;cin >> N >> M;
    vector<int> A(M);
    rep(i,M)cin >> A[i];
    LL match[10] = {2,5,5,4,5,6,3,7,6};

    rep(i,10010)dp[i] = MININF;
    dp[0] = "";

    rep(i,N+1){
        if(dp[i] == MININF)continue;
        for(auto a : A)csmax(dp[i + match[a-1]] , dp[i]+(char)('0' + a));
    }

    cout << dp[N] << endl;
}



Measured memory_bytes: 43776
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
void sleep( double sec = 1021 ){
  clock_t s = clock();
  while( clock() - s < CLOCKS_PER_SEC * sec );
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
#define N 202020
#define K 30
void build(){

}
int n , a[ 2 ][ N ];
int c[ 2 ][ K ][ 2 ];
int v[ K ];
void init(){
  n = getint();
  for( int j = 0 ; j < 2 ; j ++ ){
    for( int i = 0 ; i < n ; i ++ ){
      a[ j ][ i ] = getint();
      for( int b = 0 ; b < K ; b ++ )
        if( (a[ j ][ i ] >> b) & 1 )
          c[ j ][ b ][ 1 ] = 1 - c[ j ][ b ][ 1 ];
        else
          c[ j ][ b ][ 0 ] = 1 - c[ j ][ b ][ 0 ];
    }
  }
}
int b[ 2 ][ N ];
int count( int goal ){
  for( int i = 0 ; i < n ; i ++ ){
    b[ 0 ][ i ] = a[ 0 ][ i ] & (goal - 1);
    b[ 1 ][ i ] = a[ 1 ][ i ] & (goal - 1);
  }
  sort( b[ 0 ] , b[ 0 ] + n );
  sort( b[ 1 ] , b[ 1 ] + n );
  int ptr = n;
  int ret = 0;
  for( int i = 0 ; i < n ; i ++ ){
    while( ptr > 0 and b[ 1 ][ ptr - 1 ] + b[ 0 ][ i ] >= goal )
      ptr --;
    ret = (ret + n - ptr) % 2;
  }
  return ret;
}
void solve(){
  for( int i = 0 ; i < K ; i ++ )
    v[ i ] = ( (c[ 0 ][ i ][ 0 ] * c[ 1 ][ i ][ 1 ] % 2) ) ^
             ( (c[ 0 ][ i ][ 1 ] * c[ 1 ][ i ][ 0 ] % 2) );
  for( int i = 1 ; i < K ; i ++ )
    v[ i ] ^= count( (1 << i) );
  //for( int i = 0 ; i + 1 < K ; i ++ )
    //v[ i + 1 ] ^= ( c[ 0 ][ i ][ 1 ] * c[ 1 ][ i ][ 1 ] % 2 );
  int vl = 0;
  for( int i = 0 ; i < K ; i ++ )
    if( v[ i ] )
      vl |= (1 << i);
  printf( "%d\n" , vl );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 3328
n,k = map(int,input().split())

ab = []
for i in range(1,n+1):
    a,b=0,0
    if(n%2==1):
        if(i%2==1):
            a,b = i, n + 1 + (n-i)//2
        else:
            a,b = i, 2*n - (i-2)//2
    elif(n%2==0):
        if(i%2==0):
            a,b = i, n + 1 + (n-i)//2
        else:
            a,b = i, 2*n - i//2
    a += k-1
    b += k-1
    ab.append((a+b,a,b))

ab.sort()

ans = []
for i in range(n):
    c = k+2*n+i
    tot,a,b = ab[i]
    if(tot > c):
        print(-1)
        exit()
    ans.append((a,b,c))

print('\n'.join(map(lambda x: ' '.join(map(str,x)), ans) ))

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()

ll GCD(ll a, ll b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }


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

    vector<ll> H(N);
    rep(i, N) cin >> H[i];

    if (K >= N) {
        cout << 0 << endl;
        return 0;   
    }

    ll ans = 0;
    sort(all(H));
    rep(i, (N-K)) {
        ans += H[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;
#define int long long
#define test int t; cin >> t; while (t--)
#define deb(x) cerr << #x << " " << x << endl;
#define debb(x, y) cerr << #x << " = " << x << "," << #y << " = " << y << endl <<endl;
#define pb push_back
#define pp pop_back
#define mkp make_pair 
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define MAX 50000

typedef long double ld;
const int N = 1e5 + 10;
const int maxn = 2e6 + 10;
const long double Pie = acos(-1);
 
signed main() {
    int n;	cin >> n;
    string str;	cin >> str;
    
    int cntW = 0, cntR = 0;
    for (char ch : str)	
		if (ch == 'W')	cntW++;
		else 			cntR++;
   
	int ans = 0;
	for (int i = 0; i < cntR; i++)
		if (str[i] == 'R')	ans++;
    
    int swaps = cntR - ans; 
    cout << min (cntW, swaps);
    
    return 0;
}


Measured memory_bytes: 3752
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100010;
const int inf = 0x0fffffff;
#define LL long long
const long long mod = 1000000007;

int in[maxn];
int de[maxn], a[maxn];
int main()
{
	int n, i;
	cin >> n;
	for (i = 0; i < n; i ++)
		cin >> a[i];
	in[0] = de[0] = 1;
	for (i = 1; i < n; i ++)
	{
		de[i] = in[i] = inf;
		if (a[i] == a[i - 1])
		{
			de[i] = de[i - 1]; 
			in[i] = in[i - 1];
		}
		else if (a[i] > a[i - 1])
		{
			in[i] = min(in[i - 1], de[i - 1] + 1);
			de[i] = min(in[i - 1] + 1, de[i - 1] + 1);
		}
		else
		{
			in[i] = min(in[i - 1] + 1, de[i - 1] + 1);
			de[i] = min(in[i - 1] + 1, de[i - 1]);
		}
	}
	cout << min(in[n - 1], de[n - 1]);
	return 0;
}

Measured memory_bytes: 1408
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
INF = 10 ** 9

N = int(input())

AB = [tuple(map(int, input().split())) for _ in range(N)]
CD = [tuple(map(int, input().split())) for _ in range(N)]

G = [[] for _ in range(2 * N + 2)]

def dfs(v, t, f):
    if v == t:
        return f
    used[v] = True
    for i in range(len(G[v])):
        e = G[v][i]
        if (not used[e[0]]) and e[1] > 0: #辺が使われていなくてかつ残量が0より多い
            d = dfs(e[0], t, min(f, e[1]))
            if d > 0: #更新できるとき
                e[1] -= d
                G[e[0]][e[2]][1] += d
                return d
    return 0

def max_flow(s, f):
    flow = 0
    while True:
        global used
        used = [False] * (2 * N + 2)
        t = dfs(s, f, INF)
        if t == 0:
            return flow
        flow += t

def add_edge(fr, to, cap):
    G[fr].append([to, cap, len(G[to])])
    G[to].append([fr, 0, len(G[fr]) - 1])

for i in range(N):
    add_edge(2 * N, i, 1)
    add_edge(N + i, 2 * N + 1, 1)

for i, (a, b) in enumerate(AB):
    for j, (c, d) in enumerate(CD):
        if a < c and b < d:
            add_edge(i, j + N, 1)
 
print (max_flow(2 * N, 2 * N + 1))


Measured memory_bytes: 3700
#include<cstdio>

long long int min(long long int x, long long int y) {
    return x < y ? x : y;
}

int main(void) {
    long long int n,a,b,c,d,e;
    scanf("%lld%lld%lld%lld%lld%lld", &n,&a,&b,&c,&d,&e);

    long long int k[6] = {n, 0, 0, 0, 0, 0};

    long long int m = 1e16;

    m = min(m, a);
    m = min(m, b);
    m = min(m, c);
    m = min(m, d);
    m = min(m, e);
    printf("%lld\n", (n+m-1) / m + 4);
}


Measured memory_bytes: 128
#include<stdio.h>
#define MAX 100005
#define NIL -1

typedef struct {
  int p, l, r;
}  Node;

Node T[MAX];
int n,D[MAX];

  void print(int u) {
    int i,c;
    printf("node %d: ", u);
    printf("parent = %d, ", T[u].p);
    printf("depth = %d, ", D[u]);

    if(T[u].p == NIL) printf("root, ");
    else if (T[u].l == NIL) printf("leaf, ");
    else printf("internal node, ");

    printf("[");

    for(i = 0,c = T[u].l;c != NIL; i++, c = T[c].r) {
      if(i) printf(", ");
      printf("%d", c);
    }
    printf("]\n");
  }

void rec(int u , int p) {
  D[u] = p;
  if(T[u].r != NIL) rec(T[u].r , p);
  if(T[u].l != NIL) rec(T[u].l , p+1);
}

int main() {
 int i,j,d,v,c,l,r;
scanf("%d\n", &n);
for(i=0;i<n;i++) T[i].p = T[i].l = T[i].r = NIL;

for(i = 0; i < n; i++) {
  scanf("%d%d\n", &v,&d);
  for(j=0;j<d;j++) {
    scanf("%d",&c);
    if(j == 0) T[v].l = c;
    else T[l].r = c;
     l = c;
     T[c].p = v;
  }
}
for(i = 0;i < n;i++) {
  if(T[i].p == NIL) r = i;
}
 rec(r , 0);
 for( i = 0; i < n; i++) print(i);

 return 0;
}

Measured memory_bytes: 5300
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

vector<int> to[200005];
vector<int> ans;
void dfs(int v, int p=-1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u,v);
	}
}
int main() {
	int n, q;
	cin >> n >> q;
	rep(i,n-1) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	ans.resize(n);
	rep(i,q) {
		int p, x;
		cin >> p >> x;
		--p;
		ans[p] += x;
	}
	dfs(0);
	rep(i,n) {
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 23552