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

using namespace std;

int h, w, c;
int panel[2][8][8];
int visit[8][8];
int sq, ans;

void bfs(int x, int y, int cl, int pg)
{
	if( x < 0 || x >= w || y < 0 || y >= h || panel[pg][y][x] != cl || visit[y][x] == 1 )
		return;
	else
	{
		visit[y][x] = 1;
		sq++;
		bfs(x+1, y, cl, pg);
		bfs(x-1, y, cl, pg);
		bfs(x, y+1, cl, pg);
		bfs(x, y-1, cl, pg);
	}
	return;
}

void paint(int x, int y, int befc, int aftc, int pg)
{
	if( x < 0 || x >= w || y < 0 || y >= h || panel[pg][y][x] != befc || visit[y][x] == 1 )
		return;
	else
	{
		visit[y][x] = 1;
		panel[pg][y][x] = aftc;
		paint(x+1, y, befc, aftc, pg);
		paint(x-1, y, befc, aftc, pg);
		paint(x, y+1, befc, aftc, pg);
		paint(x, y-1, befc, aftc, pg);
	}

	return;
}

void setpanel(int pg)
{
		for(int j = 0; j < h; j++ )
			for(int i = 0; i < w; i++)
				panel[pg][j][i] = panel[pg-1][j][i];

		return;
}

int main()
{
	int i,j,k,l,befc;

	while( cin >> h >> w >> c, (h||w||c))
	{
		ans = 0;

		for( j = 0; j < h ; j++)
			for( i = 0; i < w ; i++)
				cin >> panel[0][j][i];

		for( i = 1; i <= 6 ; i++)
		{
			if(panel[0][0][0] == i)
				continue;

			for( j = 1; j <= 6; j++ )
			{
				if( i == j )
					continue;

				for( k = 1; k <= 6; k++)
				{
					if( j == k )
						continue;

					for( l = 1; l <= 6; l++)
					{
						if( k == l )
							continue;

						setpanel(1);
						befc = panel[1][0][0];
						memset(visit, 0, sizeof(visit));
						paint( 0, 0, befc, i, 1);

						befc = panel[1][0][0];
						memset(visit, 0, sizeof(visit));
						paint( 0, 0, befc, j, 1);

						befc = panel[1][0][0];
						memset(visit, 0, sizeof(visit));
						paint( 0, 0, befc, k, 1);

						befc = panel[1][0][0];
						memset(visit, 0, sizeof(visit));
						paint( 0, 0, befc, l, 1);

						befc = panel[1][0][0];
						memset(visit, 0, sizeof(visit));
						paint( 0, 0, befc, c, 1);

						sq = 0;
						memset(visit, 0, sizeof(visit));
						bfs(0, 0, c, 1);
						ans = max(sq, ans);
					}
				}
			}
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 868
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;  
using namespace std;

typedef long long ll;

typedef tree<
pair <int, int>,
null_type,
less<pair <int, int>>,
rb_tree_tag,
tree_order_statistics_node_update>
os;

double getTime() {
  return clock() / (double) CLOCKS_PER_SEC;
}

void read() {};

template<typename T, typename... Args>
void read(T& a, Args&... args) {
  cin >> a;
  read(args...);
}

void print() {};

template <typename T, typename... Args>
void print(T a, Args... args) {
  cout << a << " \n"[sizeof...(args) == 0];
  print(args...);
}

const int N = 55;

int g[N][N];
int dp[N][N][2];
int n, m;

int get(int x, int y) {
  return x == 0 and y == 1;
}

int go(int x, int y, int last) {
  if(x == n - 1 and y == m - 1) {
    return get(last, g[x][y]);
  }
  if(dp[x][y][last] != -1) return dp[x][y][last];
  int gettis = get(last, g[x][y]);
  int cur = 1e9;
  if(x + 1 < n) cur = min(cur, gettis + go(x + 1, y, g[x][y]));
  if(y + 1 < m) cur = min(cur, gettis + go(x, y + 1, g[x][y]));
  return dp[x][y][last] = cur;
}

int main() {
  int n; cin >> n;
  vector <int> a(n + 2);
  a[0] = 0, a[n + 1] = 0;
  int tot = 0;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for(int i = 0; i < n + 1; i++) {
    tot += abs(a[i] - a[i + 1]);
  }
  for(int i = 1; i <= n; i++) {
    int l = i - 1, r = i + 1;
    int cur = tot;
    cur -= (abs(a[l] - a[i]) + abs(a[r] - a[i]));
    cur += abs(a[l] - a[r]);
    print(cur);
  }
}


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

if k > (n-1) * (n-2) // 2:
    print(-1)
else:
    print((n-1) * n // 2 - k)
    count = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            print(i,j)
            count += 1
            if count == (n-1) * n // 2 - k:
                exit()


Measured memory_bytes: 3608
"""
ALDS1_9_A
完全二分木を実装する
"""
import copy
import math

def get_parent(index):
    parent_index = math.floor((index-1)/2)
    return parent_index
    
def get_left(index):
    left_index = 2*index+1
    return left_index

def get_right(index):
    right_index = 2*index+2
    return right_index
    

n = int(input())
heap_list = list(map(int, input().split()))+[None]*(n+1)


for i in range(n):
    k = heap_list[i]
    k_sentence = 'key = '+str(k)+', '
    if heap_list[get_parent(i)]:
        p = heap_list[get_parent(i)]
        p_sentence = 'parent key = '+str(p)+', '
    else:
        p_sentence = ''
    if heap_list[get_left(i)]:
        l = heap_list[get_left(i)]
        l_sentence = 'left key = '+str(l)+', '
    else:
        l_sentence = ''
    if heap_list[get_right(i)]:
        r = heap_list[get_right(i)]
        r_sentence = 'right key = '+str(r)+', '
    else:
        r_sentence = ''

    print('node '+str(i+1)+': '+k_sentence+p_sentence+l_sentence+r_sentence)








Measured memory_bytes: 6396
N = int(input())
A = list(map(int, input().split()))
 
j = True
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] %3 == 0 or A[i] % 5 ==0:
            pass
        else:
            j = False
            
if j == True:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3060
const t={input:require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/),n:(arg:number=0):any=>{if(arg){const a=[];for(let i=0;i<arg;i++){a.push(t.n())}return a}else{const a=t.input[0];t.input.shift();return Number(a)}},s:(arg:number=0):any=>{if(arg){const a=[];for(let i=0;i<arg;i++){a.push(t.s())}return a}else{const a=t.input[0];t.input.shift();return String(a)}},c:(arg:number=0):any=>{if(arg){const a=[];for(let i=0;i<arg;i++){a.push(t.c())}return a}else{let a=t.input[0].split('');const b=a[0];a.shift();if(a.length>0){t.input[0]=a.join('')}else{t.input.shift()}return String(b)}},o:(...arg)=>{console.log(...arg)},abs:(a)=>{return Math.abs(a)},min:(...a)=>{return Math.min(...a)},max:(...a)=>{return Math.max(...a)},floor:(a)=>{return Math.floor(a)},asc:(ar:number[])=>{return ar.sort((a,b)=>{return a-b})},desc:(ar:number[])=>{return ar.sort((a,b)=>{return b-a})},sw:(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length;i+=2){if(eval(a+op+arr[i]))return arr[i+1];}return arr[arr.length-1]}};
const main=()=>{
  let n=t.n()
  let a=t.desc(t.n(n))
  let alice=0,bob=0
  for(let i=0;i<n;i++)i%2==0?alice+=a[i]:bob+=a[i]
  t.o(alice-bob)
}
main()

Measured memory_bytes: 7500
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	int dp[];
	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp = new int[n+1];
		int ans = fib(n);
		System.out.println(ans);
		sc.close();
	}
	
	private int fib(int n) {
		// TODO Auto-generated method stub
		if(n == 0 || n == 1) return dp[n] = 1;
		if(dp[n] != 0) return dp[n];
		return dp[n] = fib(n-1) + fib(n-2);
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 26336
#include<iostream>
#include<vector>
#include<queue>
#include <string>
#include <sstream>
#include <queue>
#include <complex>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

#define ll int64_t
const long MOD = 1e9 + 7;



int main()
{
  int a,b; //かっている数//最大100

  cin >> a ;

  int odd = (a+1)/2;
  int even = a/2;


  cout << odd*even;
  return 0;
}


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

class Dice {
	int *d;
public:
	Dice(int *pd);
	void roll(char dir);
	int me(int n);
	int top(int topn);
	int front(int frn);
};
Dice::Dice(int *pd) {
	d = pd;
}

void Dice::roll(char dir) {
	int tmp;
	if(dir=='E') {
		tmp = d[0];
		d[0] = d[3];
		d[3] = d[5];
		d[5] = d[2];
		d[2] = tmp;
		}
	else if(dir=='W') {
		tmp = d[0];
		d[0] = d[2];
		d[2] = d[5];
		d[5] = d[3];
		d[3] = tmp;
	}
	else if(dir=='S') {
		tmp = d[0];
		d[0] = d[4];
		d[4] = d[5];
		d[5] = d[1];
		d[1] = tmp;
	}
	else {
		tmp = d[0];
		d[0] = d[1];
		d[1] = d[5];
		d[5] = d[4];
		d[4] = tmp;
	}
}
int Dice::me(int n) {
	return d[n-1];
}
int Dice::top (int topn) {
	if(topn == d[1]) {
		roll('N');
		return 1;
	}
	else if(topn == d[2]) {
		roll('W');
		return 1;
	}
	else if(topn == d[3]) {
		roll('E');
		return 1;
	}
	else if(topn == d[4]) {
		roll('S');
		return 1;
	}
	else if(topn == d[5]) {
		roll('S');
		roll('S');
		return 1;
	}
	else return 0;	 
}
int Dice::front (int frn) {
	if(frn == d[2]) {
		roll('W');
		roll('S');
		roll('E');
		return 1;
	}
	else if(frn == d[3]) {
		roll('E');
		roll('S');
		roll('W');
		return 1;
	}
	else if(frn == d[4]) {
		roll('W');
		roll('S');
		roll('S');
		roll('E');
		return 1;
	}
	else return 0;
}
int main()
{
	int n, YN=1;
	int d1[6], d2[6];
	cin >> n;
	int *d = new int[n * 6];
	for (int i=0; i < n; i++)
		for (int j = 0; j < 6; j++)
			cin >> d[i * 6 + j];

	for (int j = 0; j <  n - 1; j++) {
		for(int k = j + 1; k < n; k++) {
			for (int i = 0; i < 6; i++) {
				d1[i] = d[j * 6 + i];
				d2[i] = d[k * 6 + i];
			}
			Dice dice1(d1), dice2(d2);
			for (int i = 0; i < 3; i++) {
				if(dice2.top(dice1.me(1))){}
				else {
					YN *= 1;
					break;
				}		
				if(dice2.front(dice1.me(2))){}
				else {
					YN *= 1;
					break;
				}
				if (
					(dice1.me(3) == dice2.me(3)) &&
					(dice1.me(4) == dice2.me(4)) &&
					(dice1.me(5) == dice2.me(5)) &&
					(dice1.me(6) == dice2.me(6))
				) {
					YN *= 0;
					break;
				}
				else {
					dice1.roll('N');
					dice1.roll('W');
				}
			}
		}
	}
	if(YN) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x, y;
    cin >> x >> y;
    if (!(x % y)) cout << -1 << endl;
    else cout << x  << endl;
    
    return 0;
}



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

using namespace std;
typedef long long ll;

int main() {
  ll N; cin >> N;
  ll M; cin >> M;
  vector<ll> A(N);
  for (ll j=0; j < N; ++j) cin >> A[j];
  vector<tuple<ll, ll> > BC(M);
  for (ll j=0; j < M; ++j) {
    ll B, C; cin >> B >> C;
    BC[j] = make_tuple(B, C);
  }

  sort(BC.begin(), BC.end(), [](auto x, auto y){
      ll Bx, Cx; tie(Bx, Cx) = x;
      ll By, Cy; tie(By, Cy) = y;
      return Cx > Cy;
      });

  ll rem = N;
  for (ll j=0; j < M && rem > 0; ++j) {
    ll B, C; tie(B, C) = BC[j];
    for (ll k=0; k < B && rem > 0; ++k) {
      rem -= 1;
      A.push_back(C);
    }
  }
  sort(A.rbegin(), A.rend());
  ll ans = 0;
  for (ll j=0; j < N; ++j) ans += A[j];
  cout << ans << endl;
  return 0;
}


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

// begin fast read template by CYJian (source: https://www.luogu.com.cn/paste/i11c3ppx)

namespace io {
	const int __SIZE = (1 << 21) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
	#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
	inline void gc (char &x) { x = Gc(); }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
	inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
		for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
	template <class I> inline bool gi (I &x) { _eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
	template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;

// end fast read template by CYJian

#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;

int psum[15][1005];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
	int H, W, K; gi(H), gi(W), gi(K);
	rep(i, H) rep(j, W+1) {
		char c; 
		if(j == W) c = '0';
		else {
			gc(c);
			while(c == ' ' || c == '\n') gc(c);
		}
		psum[i][j] = c-'0';
		if(i) psum[i][j] += psum[i-1][j];
		if(j) psum[i][j] += psum[i][j-1];
		if(i && j) psum[i][j] -= psum[i-1][j-1];
	}
	int opt = 10000;
	rep(mask, 1<<(H-1)) {
		if(__builtin_popcount(mask) >= opt) continue;
		int cnt = 0;
		int lastcol = -1;
		rep(col, W+1) {
			int last = -1;
			rep(row, H) {
				if(row != (H-1) && !(mask&(1<<row))) continue;
				int tot = psum[row][col];
				if(last != -1) tot -= psum[last][col];
				if(lastcol != -1) tot -= psum[row][lastcol];
				if(last != -1 && lastcol != -1) tot += psum[last][lastcol];
				if(tot > K) {
					if(lastcol == col-1) { cnt = -1; goto cont; }
					else {
						cnt++;
						lastcol = col-1;
					}
				}
				last = row;
			}
		}
		if(cnt != -1)
			opt = min(opt, __builtin_popcount(mask)+cnt);
		cont:;
	}
	print(opt);
}


Measured memory_bytes: 2304
#include<iostream>
using namespace std;
int a,b,c,d;

int main(){
	while(cin>>a>>b>>c>>d){
		int ans=0;
		for(int i=0;i<=100;i++)
		{
			if((i>=a && i<=b) && (i>=c && i<=d))ans++;
		}
		printf("%d\n",ans-1>=0?ans-1:0);
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
int a[101];
int dfs(int cnt,int sum){
  int rec=0;
  if(cnt==n&&sum%2==0)return 1;
  else if(cnt==n)return 0;
  rec+=dfs(cnt+1,sum*a[cnt]);
  rec+=dfs(cnt+1,sum*(a[cnt]+1));
  rec+=dfs(cnt+1,sum*(a[cnt]-1));
  return rec;
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  cout<<dfs(0,1)<<endl;
  return(0);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define fr(i,a,b) for(ll i=(a);i<(b);i++)
#define frd(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define endl "\n"
#define inf ((lng lng) 1e18 + 10)
#define ve vector<ll>
using namespace std;

int main() {
        std::ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        ll t;
        // cin>>t;
        t = 1;
        while(t--){
                ll n;
                cin>>n;
                ll count  = 0;
                ll temp = 1;
                ll val = 100;
                ll r;
                while(val <= n){
                        val += ((0.01) * val);
                        if(val < n)
                                count += 1;
                }
                cout<<count + 1<<endl;
        }
        return 0;
}


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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef long double LD;
typedef pair<LD, int> PLDI;
typedef pair<LD, LD> PLDLD;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
const LL MOD = 1e9+7;
const LL INF = (1e18);
const double EPS=1.0e-9;
const double PI=atan2(0,-1);



int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<int> a(q);
    REP(i,q)
        cin>>a[i];
    
    bool used[100001];
    vector<int> b;
    CLR(used);
    b.reserve(q);
    for(int i=q-1;i>=0;i--)
    {
        if(!used[a[i]])
        {
            b.push_back(a[i]);
            used[a[i]]=1;
        }
    }
    REP(i,m)
    {
        if(!used[i+1])
            b.push_back(i+1);
    }
    vector<int> c(m+1);
    REP(i,m)
        c[b[i]]=i+1;
    
    bool flag=1;
    vector<int> d(m+2);
    d[0]=n;
    for(int i=q-1;i>=0;i--)
    {
        d[c[a[i]]-1]--;
        if(d[c[a[i]]-1]<0)
        {
            d[c[a[i]]-1]=0;
            continue;
            //flag=0;
            //break;
        }
        d[c[a[i]]]++;
    }
    
    CLR(used);
    //used[0]=1;
        int k=1;
    REP(i,m+2)
    {
        if(d[i]==0)continue;
        
        for(int j=0;j<i;j++)
            used[b[j]]=1;
        
        FOR(j,i,m)
        {
            if(used[k])
            {
                k++; j--;
                continue;
            }
            if(k!=b[j])
            {
                flag=0;
                break;
            }
            k++;
        }
        
        break;
    }
    
    if(flag)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

Measured memory_bytes: 1920
def solve(string):
    n = int(string)
    p = []
    c = [True] * 101
    c[0] = c[1] = False
    for i, f in enumerate(c):
        if f:
            p.append(i)
            t = 2
            while i * t <= 100:
                c[i * t] = False
                t += 1
    d = {_p: 0 for _p in p}
    for _p in p:
        t = 1
        while _p**t <= n:
            d[_p] += n // (_p**t)
            t += 1
    ans = 0
    # x**75
    for v in d.values():
        if v >= 74:
            ans += 1
    # x**25y**3
    x, y = 0, 0
    for v in d.values():
        if v >= 24:
            x += 1
        if v >= 2:
            y += 1
    ans += x * (y - 1)
    # x**15y**5
    x, y = 0, 0
    for v in d.values():
        if v >= 14:
            x += 1
        if v >= 4:
            y += 1
    ans += x * (y - 1)
    # x**5y**5z**3
    x, y = 0, 0
    for v in d.values():
        if v >= 4:
            x += 1
        if v >= 2:
            y += 1
    ans += x * (x - 1) // 2 * (y - 2)
    return str(ans)


if __name__ == '__main__':
    print(solve(input()))


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

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

string s, t;
int dp[3333][3333];
int pre[3333][3333];

void lcs() {
  int n = s.size(), m = t.size();
  s = "+" + s;
  t = "*" + t;

  fill(dp[0], dp[1111], 0LL);
  fill(pre[0], pre[1111], 0LL);

  for (int si = 1; si <= n; si++) {
    for (int ti = 1; ti <= m; ti++) {
      if (s[si] == t[ti]) {
        dp[si][ti] = dp[si-1][ti-1] + 1;
        pre[si][ti] = 1;
      } else if (dp[si-1][ti] > dp[si][ti-1]) {
        dp[si][ti] = dp[si-1][ti];
        pre[si][ti] = 2;
      } else {
        dp[si][ti] = dp[si][ti-1];
        pre[si][ti] = 3;
      }
    }
  }
}

string solve() {
  string ans = "";

  int si = s.size() - 1;
  int ti = t.size() - 1;
  while (si >= 1 && ti >= 1) {
    if (pre[si][ti] == 1) {
      ans += s[si];
      si--, ti--;
    } else if (pre[si][ti] == 2) {
      si--;
    } else {
      ti--;
    }
  }

  reverse(all(ans));
  return ans;
}

signed main() {
  cin >> s >> t;
  lcs();
  cout << solve() << endl;

  return 0;
}

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

int main() {
    string s; cin >> s;
    string res;
    for (auto x : s) {
        if (x == 'S') res += x;
        else {
            if (!res.empty() && res.back() == 'S') res.pop_back();
            else res += x;
        }
    }
    cout << res.size() << endl;
    return 0;
}


Measured memory_bytes: 776
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=100005;
int n,num,head[maxn],t[maxn<<1],ne[maxn<<1],v[maxn<<1];
inline void addedge(int x,int y,int z){
	ne[++num]=head[x];head[x]=num;t[num]=y;v[num]=z;
	ne[++num]=head[y];head[y]=num;t[num]=x;v[num]=z;
}int sz[maxn],maxi[maxn],root;
inline void dfs(int x,int fa){
	sz[x]=1;
	forE(i,x)if(t[i]!=fa){
		dfs(t[i],x);sz[x]+=sz[t[i]];
		maxi[x]=max(maxi[x],sz[t[i]]);
	}maxi[x]=max(maxi[x],n-sz[x]);
	if(maxi[x]<maxi[root])root=x;
}
i64 res;
inline void dfs2(int x,int fa){
	sz[x]=1;
	forE(i,x)if(t[i]!=fa){
		dfs2(t[i],x);sz[x]+=sz[t[i]];
		res+=2ll*v[i]*sz[t[i]];
	}
}
int main(){
	read(n);maxi[0]=32132321;
	rep(i,1,n)head[i]=-1;
	rep(i,1,n-1){
		int x,y,z;read(x);read(y);read(z);
		addedge(x,y,z);
	}
	dfs(1,0);
	dfs2(root,0);
	// cout<<res<<endl;	
	if(maxi[root]==(n+1)/2){
		forE(i,root)if(sz[t[i]]==n/2)res-=v[i];
	}
	else{
		int mini=1e9;
		forE(i,root)mini=min(mini,v[i]);
		res-=mini;
	}
	cout<<res<<endl;
}


Measured memory_bytes: 5632
n, k = map(int, input().split())
v = list(map(int, input().split()))
mini = min(n, k)
value = 0
for a in range(mini + 1):
  for b in range(mini - a + 1):
    c = k - a - b
    j = v[:a] + v[n-b:]
    j.sort(reverse=True)
    for _ in range(c):
      if j and j[-1] < 0:
        j.pop()
      else:
        break
    value = max(value, sum(j))
print(value)

Measured memory_bytes: 3316
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    ll n;
    cin >> n;
    vector<ll> s(n);
    rep(i,0,n) cin >> s[i];
    ll q;
    cin >> q;
    vector<ll> t(q);
    rep(i,0,q) cin >> t[i];
 
    unordered_set<ll> hs, ht;

    rep(i,0,n) hs.emplace(s[i]);
    rep(i,0,q) ht.emplace(t[i]);

    ll cnt(0);
    for(auto elem: ht)
        if (hs.find(elem) != hs.end()) 
            cnt++;
 
    cout << cnt << endl;
 
    return 0;
}



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

using namespace std;
#define int long long
const int MOD = 1000000007;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<pair<int, int> > A(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i].first;
		A[i].second = i;
	}
	sort(A.rbegin(), A.rend());
	int INF = (int)1 << 60;
	vector<vector<int> > dp(N, vector<int>(N, -INF));
	dp[0][N - 1] = 0;
	for (int len = N - 1; len > 0; len--) {
		for (int i = 0; i + len < N; i++) {
			int j = i + len;
			int num = N - 1 - len;
			int val = A[num].first;
			int pos = A[num].second;
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + val * abs(pos - i));
			dp[i][j - 1] = max(dp[i][j - 1], dp[i][j] + val * abs(pos - j));
		}
	}
	for (int i = 0; i < N; i++) {
		res = max(res, dp[i][i] + A[N - 1].first * abs(A[N - 1].second - i));
	}
	cout << res << endl;
}

Measured memory_bytes: 34620
#include <stdio.h>


int main(void) {
    char bm[100][101];
    int d, n, i, j, x, y, k, l;

    scanf("%d", &d);
    while (d--) {
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            for (j = 1; j <= n; j++) {
                if (j != n) {
                    bm[i][j] = ' ';
                }
                else {
                    bm[i][j] = '\0';
                }
            }
        }
        for (i = n - 1; i >= 0; i--) {
            bm[i][0] = '#';
        }
        x = 0;
        y = 0;
        k = 1;
        for (l = n - 1; l > 0; l-=2, k*=-1) {
            for (i = 0; i < l; i++) {
                x += k;
                bm[y][x] = '#';
            }
            if (l > 1) {
                for (i = 0; i < l; i++) {
                    y += k;
                    bm[y][x] = '#';
                }
            }
        }

        for (i = 0; i < n; i++) {
            puts(bm[i]);
        }
        if (d) puts("");
    }
    return 0;
}

Measured memory_bytes: 592
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<string>
using namespace std;
class dice{
public:
	int num[6], tmp;
	void moveS(){
		tmp = num[0];
		num[0] = num[4];
		num[4] = num[5];
		num[5] = num[1];
		num[1] = tmp;
	}
	void moveN(){
		tmp = num[0];
		num[0] = num[1];
		num[1] = num[5];
		num[5] = num[4];
		num[4] = tmp;
	}
	void moveW(){
		tmp = num[0];
		num[0] = num[2];
		num[2] = num[5];
		num[5] = num[3];
		num[3] = tmp;
	}
	void moveE(){
		tmp = num[0];
		num[0] = num[3];
		num[3] = num[5];
		num[5] = num[2];
		num[2] = tmp;
	}
};
int main(){
	dice a;
	for (int i = 0; i < 6; i++){
		cin >> a.num[i];
	}
	int n,c,b;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> c >> b;
		if (a.num[2] == b || a.num[3] == b){
			a.moveE();
		}
		while (1){
			a.moveN();
			if (a.num[1] == b)break;
		}
		while (2){
			a.moveE();
			if (a.num[0] == c)break;
		}
		cout << a.num[2] << endl;
	}
	
	return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
set<string> se;
string s;
int k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> k;
    int len = s.length();
    for(int i = 0; i < len; i++)
    {
        //长度
        int maxl = min(k, len - i);
        for(int j = 1; j <= maxl; j++)
        {
            string temp = s.substr(i, j);
            se.insert(temp);
        }
    }
    int cnt = 1;
    for(set<string>:: iterator i = se.begin(); i != se.end() && cnt <= k; i++, cnt++)
    {
        if(cnt == k) cout << *i << endl;
    }
}




Measured memory_bytes: 1664
import sys
sys.setrecursionlimit(15000)
n = int(input())

memo = {0:1,1:1}

def fib(n):
  if n < 2:
    return memo[n]
  if not n in memo:
    memo[n] = fib(n-1)+fib(n-2)
  return memo[n]

print(fib(n))


Measured memory_bytes: 5604
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define ld long double
#define mkp make_pair
#define sz(x) (int)x.size()
#define pi pair<long long, long long>
#define endl '\n'
#define _ << ' '
#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
#define clog2(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> idxset;
//find_by_order(i) : iterator to the value at index i, order_of_key(x) : the index of value x
const ll mod = (ll)1e9+7;
const ll INF = (ll)3e9+1;

int n;
int ans=0, a[2][100];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("D.txt", "r", stdin);
    #endif
    cin >> n;
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        int cur = 0;
        for(int j=0; j<n; j++)
        {
            if(j<i)
            {
                cur += a[0][j];
            }
            else if(j>i)
            {
                cur += a[1][j];
            }
            else
            {
                cur += a[0][j] + a[1][j];
            }
        }
        ans = max(ans, cur);
    }
    cout << ans;
}



Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<math.h>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<sstream>
#include<set>

using namespace std;

#define forn(i,n) for(int i=0;i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
#define esta(x,v) (find((v).begin(),(v).end(),(x)) !=  (v).end())
#define index(x,v) (find((v).begin(),(v).end(),(x)) - (v).begin())
#define debug(x) cout << #x << " = "  << x << endl
#define pb push_back
#define mp make_pair

typedef long long tint;
typedef unsigned long long utint;
typedef long double ldouble;

typedef vector<int> vint;

int toNumber (string s)
{
	int Number;
	if ( ! (istringstream(s) >> Number) ) Number = 0; // el string vacio lo manda al cero
	return Number;
}

string toString (int number)
{
    ostringstream ostr;
    ostr << number;
    return  ostr.str();
}

bool isP(int a){
	if(a==2)return true;
	if(a%2==0)return false;
	for(int i=3; i*i<=a; i++){
		if(a%i==0)return false;
	}
	return true;
}

int main(){
	int n;
	cin>>n;
	tint pri[n+3];
	bool pri2[n+3];
	forn(i, n+3){
		pri2[i]=false;
		pri[i]=0;
	}
	forsn(i, 2, n+1){
		if(isP(i)){
			pri2[i]=true;
		}
	}
	forsn(i, 2, n+1){
		int o=i;
		for(int di=2; di<=o; di++){
			if(o%di==0 && pri2[di]){
				while(o%di==0){
					o/=di;
					pri[di]++;
				}
			}
		}
	}
	tint MOD=1000000007;
	tint ans=1;
	forn(i, n+1){
		if(pri2[i]){
			ans*=(pri[i]+1);
			ans%=MOD;
		}
	}
	cout<<ans<<endl;
}


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

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        var H = int.Parse(input[0]);
        var N = int.Parse(input[1]);
        var A = new int[N];
        input = Console.ReadLine().Split();
        for (int i = 0; i < N; i++)
            A[i] = int.Parse(input[i]);

        Console.WriteLine(A.Sum() >= H ? "Yes" : "No");
    }
}


Measured memory_bytes: 16992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
typedef pair<int, int> P;
const int INF=10000000;

int main() {
    string s;
    cin >> s;
    int sum=0;
    for(int i=0;i<4;++i) {
        if(s[i]=='+') ++sum;
        else --sum;
    }
    cout << sum << endl;
    
}


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

using namespace std;

map<string, int>mp;
int k, j;

int main() {
    string str;
    cin >> str;
    for(int i = 0; i < str.size(); ++i) {
        static string ss, lst;
        ss += str[i];
        if(lst != ss) {
            lst = ss;
            ss.clear();
            ++k;
        } 
    }
    cout << k << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    List<Integer> list = new ArrayList<Integer>();
    int n = 2;
    while (list.size() < N) {
      if (isPrime(n) && n%5 == 1) {
        list.add(n);
      }
      n++;
    }
    
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < N; i++) {
      ans.append(list.get(i)).append(' ');
    }
    
    System.out.println(ans.toString());
  }
  
  private static boolean isPrime(int a) {
    for (int i = 2; i*i <= a; i++) {
      if (a%i == 0) return false;
    }
    return true;
  }
}

Measured memory_bytes: 22100
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  cin>>s>>t;
  int n=s.size();
  for(int i=0;i<n;i++){
    s=s.back()+s.substr(0,n-1);
    if(s==t){cout<<"Yes"<<endl;exit(0);}
  }
  cout<<"No"<<endl;
}

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

#define int long long
#define mod 1000000007
#define p pair<int,int>
#define MAX 1000010

using namespace std;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    cout << 1110 - n << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void){
int l,f,i,r;
char t,c[110],s[110],u[110];
scanf("%s",c);
l=strlen(c);
t=getchar();
scanf("%s",s);
for(i=0;i<l;i++){
for(r=0;r<l;r++){
u[r]=c[(i+r)%l];
}
f=strstr(u,s);
if(f!='\0'){f=1;break;}
}
if(f==1){printf("Yes\n");}else{printf("No\n");}
return 0;
}

Measured memory_bytes: 528
import java.io.PrintWriter;
import java.util.Scanner;

class C {
    public static void main(String... args) {
        final Scanner sc = new Scanner(System.in);
        final int H = sc.nextInt();
        final int W = sc.nextInt();
        final int K = sc.nextInt();
        final char[][] s = new char[H][];
        for (int i = 0; i < H; i++)
            s[i] = sc.next().toCharArray();
        final int[][] ans = new int[H][W];
        for (int c = 0, i = 0; i < H; i++) {
            int first = 0;
            while (first < W && s[i][first] != '#')
                first++;
            if (first == W) {
                if (i > 0)
                    System.arraycopy(ans[i - 1], 0, ans[i], 0, W);
            } else {
                for (int j = 0; j < first; j++)
                    ans[i][j] = c + 1;
                for (int j = first; j < W; j++) {
                    if (s[i][j] == '#')
                        c++;
                    ans[i][j] = c;
                }
            }
        }
        for (int i = H - 1; i > 0; i--)
            for (int j = 0; j < W; j++)
                if (ans[i - 1][j] == 0)
                    ans[i - 1][j] = ans[i][j];
        final PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++)
                if (j > 0) {
                    pw.print(' ');
                    pw.print(ans[i][j]);
                } else
                    pw.print(ans[i][j]);
            pw.println();
        }
        pw.close();
    }
}
public class Main {
    public static void main(String... args) {
        C.main();
    }
}


Measured memory_bytes: 34676
n,m=map(int,input().split())
a=[input().split() for _ in range(n)]
s={}
for h in a:
    for r in h[1:]:
        if r in s:
            s[r]+=1
        else:
            s[r]=1
cnt=0
for r in s.values():
    if r==n:
        cnt+=1

print(cnt)

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include <string>
#include<cstdio>
#include<stack>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define D(n,retu) REP(i,n){cin>>retu[i];}
 
using namespace std;
typedef long long ll;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
 
//------------------変数-----------------------//
ll a[100000], n, cou = 0, kijun = 0, zero = 0, lar = 0, sma = 0;
typedef pair<ll, ll>p;
//-------------------関数----------------------//
 
int main() {
	cin >> n;//代入
	REP(i, n) {
		cin >> a[i];
		if (a[i]) { lar += a[i]; }
		else { sma -= a[i]; }
	}
	REP(i, n - 1) {
		a[i + 1] += a[i];//累積和
	}
	ll saishuu = 5437235443845985897;
	REP(i, 2) {
		kijun = 0; cou = 0;
		REP(i, n) {
			if (i % 2 == zero) {//余りがzero(0or1)のとき
				if (a[i] <= kijun) {//もし、基準以下の時（変えなければならない）
					cou += abs(1 - a[i] + kijun);//基準からa[i]を引いた値＋１をカウントに加える
					kijun -= 1 - a[i] + kijun;//基準は、和がそれぞれhoge増えたらhoge減る
				}
			}
			else {
				if (a[i] >= kijun) {//もし基準より低くなってほしいのに基準以上だったら
					cou += a[i] - kijun + 1;//countに足しておく
					kijun += a[i] - kijun + 1;//和がhogeひかれるはずなら、基準はhoge増える
				}
			}
		}zero = 1;
		saishuu = min(saishuu, cou);
	}
	cout << saishuu << endl;//出力
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
char s[100000];
int  z[100000];
int main()
{
    int i;
    int N;
    int Q;
    int m;
    int a,b;
    scanf("%d%d",&N,&Q);
    getchar();
    gets(s);
    int t=0;
    for(i=0; i<N-1; i++)
    {
        if(s[i]=='A'&&s[i+1]=='C')
        {
            z[i]=t;
            t++;
            z[i+1]=t;
            i++;
        }
        else
        {

            z[i]=t;
        }
    }
    z[i]=z[i-1];

    for(i=0; i<Q; i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",z[b-1]-z[a-1]);
    }

    return 0;
}


Measured memory_bytes: 1280
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int q = in.nextInt();
		
		init(n);
		for (int i=0;i<q;i++) {
			if(in.nextInt()==0) {
				// add
				add(in.nextInt(), in.nextInt());
			} else {
				// getSum
				System.out.println(sum(in.nextInt(), in.nextInt()));
			}
		}
	}
	
	// 1-indexed
	static int[] nodes;
	static int size;

	static void init(int n) { // n:data size
		size=1;
		while (size<n) size*=2;
		nodes = new int[size+1];
	}
	
	static void add(int target, int value) {
		while (target<nodes.length) {
			nodes[target] += value;
			target += target&(-target);
		}
	}
	
	static int sum(int s, int t) { // sum in range s<=i<=t
		return sum(t) - sum(s-1);
	}
	static int sum(int t) { // sum from 0 to t
		int res=0;
		while (t>0) {
			res += nodes[t];
			t -= t&(-t);
		}
		return res;
	}
}

Measured memory_bytes: 102660
N = gets.to_i
a_list = gets.strip.split(/ /).collect{|n| n.to_i}

count_p_list = [0] * N
count_p = 0
prev_p = a_list[-1]
gap_p_list = []

count_n_list = [0, 1]
count_n = 1
prev_n = a_list[0] * -2
gap_n_list = []

(1...N).each{|i|
	a_p = a_list[N - 1 - i]
	while prev_p < a_p
		if gap_p_list.length > 0
			gap = gap_p_list[-1]
			gap_i, gap_n = gap
			count_p += (i - gap_i) * 2
			if gap_n == 1
				gap_p_list.pop
			else
				gap[1] = gap_n - 1
			end
		else
			count_p += i * 2
		end
		prev_p *= 4
	end
	n = 0
	t = 4
	while prev_p >= a_p * t
		t *= 4
		n += 1
	end
	if n > 0
		gap_p_list << [i, n]
	end
	prev_p = a_p
	count_p_list[N - 1 - i] = count_p
	
	a_n = a_list[i] * -2
	count_n += 1
	while prev_n > a_n
		if gap_n_list.length > 0
			gap = gap_n_list[-1]
			gap_i, gap_n = gap
			count_n += (i - gap_i) * 2
			if gap_n == 1
				gap_n_list.pop
			else
				gap[1] = gap_n - 1
			end
		else
			count_n += i * 2
		end
		prev_n *= 4
	end
	n = 0
	t = 4
	while prev_n <= a_n * t
		t *= 4
		n += 1
	end
	if n > 0
		gap_n_list << [i, n]
	end
	prev_n = a_n
	count_n_list << count_n
}

#p count_p_list
#p gap_p_list
#p count_n_list
#p gap_n_list

min = nil
(0...N).each{|i|
	count = count_n_list[i] + count_p_list[i]
	if min == nil || count < min
		min = count
	end
}
puts min



Measured memory_bytes: 23060
a =str(input()).split(" ")
h = int(a[0])
w = int(a[1])
maps= []

for i in range(h):
    maps.append(list(input()))

for i in range(h):
    for j in range(w):
        if maps[i][j] == "#":
            if j - 1 >= 0 and maps[i][j - 1] == "#":
                continue
            elif j + 1 < w and maps[i][j + 1] == "#" :
                continue
            elif i + 1 < h and maps[i + 1][j] == "#" :
                continue
            elif i - 1 >= 0 and maps[i - 1][j] == "#":
                continue
            else:
                print("No")
                exit()
        else:
            pass
print("Yes")



Measured memory_bytes: 3188
abcd = list(input())
a, b, c, d = abcd
sign = ['+', '-']
for i in range(2**3):
    s = a
    for j in range(3):
        if (i>>j) & 1:
            s += sign[0]
        else:
            s += sign[1]
        s += abcd[j+1]
    if eval(s) == 7:
        print(s + "=7")
        exit()

Measured memory_bytes: 61692
#include<bits/stdc++.h>
using namespace std;
const int N=100005,mod=1e9+7;
int dp[2][N],sum[2][N],a[N],n,k;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int j=0;j<=k;j++)
		sum[0][j]=1;
	for(int i=1;i<=n;i++)
	{
		int p=i&1;
		for(int j=0;j<=k;j++)
			dp[p][j]=(sum[p^1][j]-(j>a[i]?sum[p^1][j-a[i]-1]:0)+mod)%mod;
		for(int j=0;j<=k;j++)
			sum[p][j]=((j?sum[p][j-1]:0)+dp[p][j])%mod;
	}
	printf("%d\n",dp[n&1][k]);
	return 0;
}

Measured memory_bytes: 1920
#include <stdio.h>

int a[2][128];
int d[2][128];
int n;

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

Measured memory_bytes: 128
N=int(input())
S=list(map(str, input()))
li=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
answer=[]
for i in range(len(S)):
  for j in range(len(li)):
    if S[i]==li[j] and j<len(li)-N:
      answer.append(li[j+N])
    elif S[i]==li[j] and j>=len(li)-N:
      answer.append(li[j+N-len(li)])
print("".join(answer))

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

int main() {
  ll n; cin >> n;
  vector<ll> v(n);
  rep(i,n) cin >> v[i];
  
  rep(i, n-1){
    if(v[i]-1 == v[i+1]) v[i+1]++;
    else if(v[i]-1 > v[i+1]){ cout << "No" << endl; return 0; }
  }
  
  cout << "Yes" << endl;
}

Measured memory_bytes: 4024
#include<bits/stdc++.h>
using namespace std;
#define debug(x)        cout<<#x<<" :"<<x<<endl;
#define ff              first
#define ar              array
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define f(i,n)          for(int i=0;i<n;i++)
#define MOD             1000000007
#define pi              3.14159265
#define umii            unordered_map<int,int>
#define umci            unordered_map<char,int>
#define umsi            unordered_map<string,int>

void k_007()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
	freopen("ip1.txt", "r", stdin);
	freopen("op1.txt", "w", stdout);
#endif
}
bool sortbysec(const pair<int, int> &a,
               const pair<int, int> &b);
int gcd(int a, int b) ;
int prime(int n);
int power(int x, int y);
int lcm(int a, int b);
int32_t main()
{
	k_007();
	int n;
	cin >> n;
	int a[n];
	int pre[n + 1] = {0};
	int suf[n + 2] = {0};
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		pre[i + 1] = pre[i] ^ a[i];
	}
	for (int i = n - 1; i >= 0; i--) {
		suf[i + 1] = suf[i + 2] ^ a[i];
	}
	for (int i = 1; i <= n; i++) {
		int k = pre[i - 1] ^ suf[i + 1];
		cout << k << " ";
	}
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b)
{
	return (a.second < b.second);
}
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int prime(int n) {
	int flag = 1;
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {flag = 0; break;}
	}
	return flag;
}
int power(int x, int y)
{
	if (y == 0)
		return 1;
	else if (y % 2 == 0)
		return ((power(x, y / 2) % MOD) * ( power(x, y / 2) % MOD)) % MOD;
	else
		return ((x % MOD) * (power(x, y / 2) % MOD) * (power(x, y / 2) % MOD)) % MOD;
}
int lcm(int a, int b)
{
	return (a * b) / gcd(a, b);
}

Measured memory_bytes: 8316
#include<stdio.h>

int main()
{
  int x,y,temp,res[3000][2],count=0,i;

  while(1){
    scanf("%d %d",&x,&y);
    if(x==0 && y==0)
      break;
    if(x>y){
      temp=x;
      x=y;
      y=temp;
    }
    
    res[count][0]=x;
    res[count][1]=y;
    count++;
  }

  for(i=0;i<count;i++)
    printf("%d %d\n",res[i][0],res[i][1]);

  
  return 0;
}

Measured memory_bytes: 620
N, L, T=map(int, input().split())
XW=[list(map(int, input().split())) for _ in range(N)]
X_=[(XW[i][0]+T)%L if XW[i][1]==1 else (XW[i][0]-T)%L for i in range(N)]
X_.sort()
A0_=(XW[0][0]+T)%L if XW[0][1]==1 else (XW[0][0]-T)%L
P0_=X_.index(A0_)
if P0_>0:
    X_=X_[P0_:]+X_[:P0_]
    
if XW[0][1]==1:
    C0_=round(sum([(T-(XW[i][0]-XW[0][0])/2)//(L/2)+1 if XW[i][1]!=1 and (XW[i][0]-XW[0][0])/2<=T else 0 for i in range(1, N)])%N)
else:
    C0_=round(N-sum([(T-(XW[0][0]+L-XW[i][0])/2)//(L/2)+1 if XW[i][1]!=2 and (XW[0][0]+L-XW[i][0])/2<=T else 0 for i in range(1, N)])%N)
    
if N>1 and X_[0]==X_[1] and XW[0][1]==1:
  C0_=round((C0_-1)%N)

if C0_>0:
  X_=X_[N-C0_:]+X_[:N-C0_]

print(*X_, sep='\n')

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

using namespace std;
typedef long long ll;

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

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

    cout << (a + b) % 24 << '\n';
    return 0;
}


Measured memory_bytes: 3584
def generateit(s, n):
	m = n
	ans = s[0]
	for i in range(0, 3):
		if m % 2 == 1:
			ans = ans + '+' + s[i+1]
		else:
			ans = ans + '-' + s[i+1]
		m //= 2
	return ans

S = input()
for i in range(0, 8):
	n = i
	sum = int(S[0])
	for j in range(0, 3):
		if n % 2 == 1:
			sum += int(S[j+1])
		else:
			sum -= int(S[j+1])
		n //= 2
	if sum == 7:
		print(generateit(S, i)+'=7')
		break

Measured memory_bytes: 38256