akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
using namespace std;
const double EPS = 1e-9; const double INF = 1e10; const double PI = M_PI;
struct Point{
  Point(double x, double y ):x(x), y(y){}
  Point(){}
  double x,y;
};
Point operator+(const Point &a, const Point &b){ return Point(a.x + b.x, a.y + b.y); }
Point operator-(const Point &a, const Point &b){ return Point(a.x - b.x, a.y - b.y); }
double cross( const Point &a, const Point &b ){ return a.x * b.y - a.y * b.x; }
double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y; }
double norm( const Point &a ) { return dot( a, a ) ; }
int ccw( Point a, Point b, Point c ) {
  b = b - a;
  c = c - a;
  if ( cross( b, c ) > EPS ) return 1;
  if ( cross( b, c ) < -EPS ) return -1;
  return 0;
}
int main () {

  double xa, ya, xb, yb, xc, yc, xd, yd;
  char ch;
  while(cin >> xa >> ch >> ya >> ch >> xb >> ch >> yb >> ch >> xc >> ch >> yc >> ch >> xd >> ch >> yd){
    Point points[4] = {};

    points[0] = Point(xa, ya);
    points[1] = Point(xb, yb);
    points[2] = Point(xc, yc);
    points[3] = Point(xd, yd);
    
    bool same = true;
    bool already = false;
    int sign = 0;
    for(int i = 0; i < 4; i++){
      const int next = (i + 1) % 4;
      const int nnext = (next + 1) % 4;
      
      //cout << points[i].x << "," << points[i].y  << endl;
      if(!already){
	sign = ccw(points[i], points[next], points[nnext]);
	already = true;
      }else if(sign != ccw(points[i], points[next], points[nnext])){
	same = false;
	break;
      }
    }
    cout << (same ? "YES" : "NO") << endl;
  }

  return 0;

}

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

bool is_lower(char c) {
  return (c >= 'a') && (c <= 'z');
}

bool judge(std::string const& S) {
  size_t const N = S.length();

  if (S[0] != 'A') return false;
  if (! is_lower(S[1])) return false;

  size_t numC = 0;
  for (size_t i=2; i<N-1; i++) {
    if (S[i] == 'C')
      numC++;
    else if (! is_lower(S[i]))
      return false;

    if (numC > 1)
      return false;
  }

  if (numC != 1)
    return false;

  if (! is_lower(S[N-1]))
    return false;

  return true;
}

int main() {
  std::string S;
  std::cin >> S;

  std::cout << (judge(S) ? "AC" : "WA") << std::endl;

  return 0;
}


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

int main() {
  int d, n;
  cin >> d >> n;
  
  if(d==0) {
    if(n!=100) {
    cout << n << endl;
    return 0;
    }
    else {
    cout << 101 << endl;
    return 0;
    }
  }
  else {
    int x, ans;
    int count = 0;
    for(int i=100; ; i+=100) {
      x = i;
      for(int j=1; j<=d; j++) {
        if(x%100 != 0) break;
        x /= 100;
        if(j==d && x%100 != 0) count++; 
      }
      if(count==n) {
        ans = i;
        break;
      }
    }
    cout << ans << endl;
    return 0;
  }
}

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

using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> x(m);
    vector<int> diff(m-1);
    for(int i=0; i<m; i++){
        cin >> x[i];
    }

    if (n >= m){
        cout << 0 << endl;
        return 0;
    }

    sort(x.begin(), x.end());
    for(int i=0; i<m-1; i++){
        diff[i] = abs(x[i] - x[i+1]);
    }

    sort(diff.begin(), diff.end());
    reverse(diff.begin(), diff.end());
    diff.erase(diff.begin(), diff.begin() + n-1);

    int sum = 0;
    for(int i=0; i<m-n; i++){
        sum += diff[i];
    }
    cout << sum << endl;
    return 0;
}


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

int main(){
    string s,t;
    int n,k;
    int ans = 0;
    vector<int> v;
    cin >> s >> t;
    rep(i,s.size()){
        if(s[i]!=t[i]){
            ans++;
        }
    }
    cout << ans << endl;
}

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

const int MX = 605;
const int MD = 1000000007;

int mod_mult(int a, int b) {
	return (a * 1LL * b) % MD;
}

int dp[MX][MX];
int g[MX];

pair<int, int> p[MX];

bool in(int L, int R, int x) {
	return L <= x && x <= R;
}

int cnt[MX][MX];
bool taken[MX];

int main()
{
	g[0] = 1;
	for (int i = 2; i < MX; i += 2) {
		g[i] = mod_mult(g[i - 2], i - 1);
	}
	
	int n, k;
	ignore = scanf("%d %d", &n, &k);
	for (int i = 0; i < k; i++) {
		ignore = scanf("%d %d", &p[i].first, &p[i].second);
		taken[p[i].first] = true;
		taken[p[i].second] = true;
	}
	
	for (int i = 1; i <= 2 * n; i++) {
		for (int j = i; j <= 2 * n; j++) {
			cnt[i][j] = cnt[i][j - 1] + (1 - taken[j]);
		}
	}
	
	int ans = 0;
	
	for (int l = 1; l <= 2 * n; l++) {
		for (int i = 1; i + l <= 2 * n; i++) {
			int j = i + l;
			
			//printf("(%d %d):\n", i, j);
			
			bool ok = true;
			for (int t = 0; t < k; t++) {
				if (in(i, j, p[t].first) != in(i, j, p[t].second)) {
					ok = false;
					break;
				}
			}
			
			if (!ok) continue;
			
			int x, y;
			x = l + 1;
			y = 2 * n - x;
			for (int t = 0; t < k; t++) {
				if (in(i, j, p[t].first)) {
					x--;
				}
				else {
					y--;
				}
				
				if (in(i, j, p[t].second)) {
					x--;
				}
				else {
					y--;
				}
			}
			
			//printf("x = %d, y = %d\n", x, y);
			
			int sub = 0;
			
			//printf("before sub: %d\n", g[x]);
			
			for (int t = i + 1; t < j; t++) {
				sub = (sub + mod_mult(dp[i][t], g[cnt[t + 1][j]])) % MD;
			}
			
			dp[i][j] = (g[x] - sub + MD) % MD;
			
			//printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
			
			ans = (ans + mod_mult(dp[i][j], g[y])) % MD;
		}
	}
	
	printf("%d", ans);
}


Measured memory_bytes: 3072
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double r = sc.nextDouble();
        double pi = Math.PI;
        double area = r * r * pi;
        double circumference = 2 * r * pi;
        System.out.printf("%.10f %.10f", area, circumference);
        sc.close();
    }
}


Measured memory_bytes: 28204
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MAX_V 400

ll d[MAX_V][MAX_V];
ll inf = 1e9+7;
void init(int V){
    for(int i = 0; i < V; i++){
        for(int j = 0; j < V; j++){
            if(i == j){
                d[i][j] = 0;
            }
            else{
                d[i][j] = inf;
            }
        }
    }
}

void warshall_floyd(int V){
    for(int k = 0; k < V; k++){
        for(int i = 0; i < V; i++){
            for(int j = 0; j < V; j++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}


bool valid(int i, int j, P d2, int h, int w){
    if(i + d2.fs >= 0 && i + d2.fs < h && j + d2.sc >= 0 && j + d2.sc < w){
        return true;
    }
    else{
        return false;
    }
}


int main(){
    int h, w;
    cin >> h >> w;
    init(h * w);
    char s[20][20];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> s[i][j];
        }
    }
    vector<P> dir = {P(0, 1), P(1, 0), P(-1, 0), P(0, -1)};

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            for(int k = 0; k < 4; k++){
                if(valid(i, j, dir[k], h, w) && s[i][j] == '.' && s[i+dir[k].fs][j+dir[k].sc] == '.'){
                    int next = (i + dir[k].fs) * w + (j + dir[k].sc);
                    int no = i * w + j;
                    d[next][no] = 1;
                    d[no][next] = 1;
                }
            }
        }
    }

    warshall_floyd(h * w);
    ll res = 0;
    for(int i = 0; i < h * w; i++){
        for(int j = 0; j < h * w; j++){
//            cout << d[i][j] << " ";
            if(d[i][j] != inf){
                res = max(res, d[i][j]);
            }
        }
//        cout << endl;
    }
    cout << res << endl;


    return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define FOR(i, a, b) for(decltype(b) i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

using namespace std;

#ifdef INPUT
#include <sstream>
stringstream input(R"(
5
6
8
1
2
3
)");
#define cin input
#endif

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

	vector<int> a(n);

	for (auto& i : a)
		cin >> i;

	sort(a.begin(), a.end());


	int l1 = 0, l2 = 0;
	if (n % 2)
	{
		l1 = l2 = a[n / 2];
		a.erase(a.begin() + n / 2);
		--n;
	}

	//cout << '_' << l1;
	ll r1 = 0, r2 = 0;
	REP (i, n)
	{
		int j = i % 2 ? n - 1 - i / 2 : n / 2 - 1 - i / 2;
		if (l1)
			r1 += abs(a[j] - l1);
		//cout << ' ' << a[j];
		l1 = a[j];
	}
	//cout << endl;

	//cout << '_' << l2;
	REP (i, n)
	{
		int j = i % 2 ? i / 2 : n / 2 + i / 2;
		if (l2)
			r2 += abs(a[j] - l2);
		//cout << ' ' << a[j];
		l2 = a[j];
	}
	//cout << endl;

	cout << max(r1, r2) << endl;

	return 0;
}


Measured memory_bytes: 1272
#include <bits/stdc++.h> 
using namespace std;
#define pb push_back
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define vli vector<ll>
#define graph vector<vector< int > >
#define vpi vector<pair<int ,int> >
#define vpli vector<pair<ll ,ll> >
#define mp make_pair
#define F first
#define S second
#define mod 37
#define INF (ll)1e18
#define wh(a) cout<<#a<<"  is  "<<a<<endl;
#define INI(a) memset(a,0,sizeof(a))
#define LIMIT 40000010
#define PI 3.14159265358

void solve(){
    double a,b,h,m;
    cin>>a>>b>>h>>m;
    double mx,my,hx,hy,mt,ht;
    mt=m*((2*PI)/60);
    ht=(h*60+m)*((2*PI)/(12*60));
    mx=b*cos(mt);
    my=b*sin(mt);
    hx=a*cos(ht);
    hy=a*sin(ht);

    cout<<fixed<<setprecision(9);
    cout<<sqrt((mx-hx)*(mx-hx)+(my-hy)*(my-hy));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // #endif
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 4104
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>

using namespace std;

bool isop(string &s){
	return s == "+" || s == "*" || s == "/" || s == "-";
}

int main(){
	string s;
	while(getline(cin,s)){
		istringstream iss(s);
		stack<double> s;
		string b;
		while(iss>>b){

			if(!isop(b)){
				double x;
				sscanf(b.c_str(),"%lf",&x);
				s.push(x);
				continue;
			}

			switch(b[0]){
			case '+':{
				double x = s.top(); s.pop();
				double y = s.top(); s.pop();
				s.push(x+y);
				break;}
			case '-':{
				double x = s.top(); s.pop();
				double y = s.top(); s.pop();
				s.push(y-x);
				break;}
			case '*':{
				double x = s.top(); s.pop();
				double y = s.top(); s.pop();
				s.push(x*y);
				break;}
			case '/':{
				double x = s.top(); s.pop();
				double y = s.top(); s.pop();
				s.push(y/x);
				break;}
			}
		}
		printf("%lf\n",s.top());
	}
    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define int long long int
#define ld long double
#define getFaster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define rev(i,n,init) for(int i=n;i>=init;i--)
#define MAXN 200005
#define MOD2 998244353
#define MOD1 1e9+7
#define f first
#define s second
#define ylol1 y1
#define endl '\n'
#define pii pair<int,int>
#define piii pair<pii,int>
#define precise(i) cout<<fixed<<setprecision(i)
#define codejam cout<<"Case #"<<ii+1<<": ";
#define impossible cout<<"IMPOSSIBLE"<<endl;
#define error(s) throw runtime_error(s)
using namespace std;
const long double PI = atan(1.0)*4;
const int64_t INF=1e14;
const int32_t LOG=21;
const int MOD=MOD1;

vector<int> vals[20];
int cost[20];
int algos[20];
int32_t main()
{ 
      getFaster;
      int tests=1;
      //cin>>tests;
      rep(ii,0,tests)
      {
           int n,m,lim;
           cin>>n>>m>>lim;
           rep(i,0,n)
           {
           	   cin>>cost[i];
           	   rep(j,1,m+1)
           	   {
           	   	  int x;
           	   	  cin>>x;
           	   	  vals[i].push_back(x);
           	   }
           }
           int ans=INF;
           rep(i,1,(1<<n))
           {
           	    fill(algos,algos+20,0);
           	    int tot=0;
           	    rep(j,0,n)
           	    {
           	    	if((1LL<<j)&i)
           	    	{
           	    		 tot+=cost[j];
                         rep(k,0,m)
                         algos[k]+=vals[j][k];
           	    	} 
           	    }
           	    bool g=true;
                rep(j,0,m)
                {
                	if(algos[j]<lim)
                	{
                		g=false;
                		break;
                	}
                } 
                if(g)ans=min(ans,tot);
           }
           if(ans==INF)ans=-1;
           cout<<ans<<endl;
      }
      return 0;                         
}

/*
 TIPS:
 1.) Check for corner cases (like 0 is exception case)
 2.) Check for global memory sizes,memory refreshments and its complexity 
 3.) Check for sorting criteria (if used 1-based indexing)
 4.) Check for numbers overflow (while multiplying and doing MOD)
 5.) Check for typecasting issues like int to float( while dividing numbers)
*/

Measured memory_bytes: 3656
x1,y1,x2,y2=map(int,input().split())

y3=y2+(x2-x1)
x3=x2-(y2-y1)
y4=y1+(x2-x1)
x4=x1-(y2-y1)

print(str(x3)+" "+str(y3)+" "+str(x4)+" "+str(y4))


Measured memory_bytes: 2940
from collections import deque
n=int(input())
S=input().split()
q=int(input())
T=input().split()
cnt=0
F=deque()
for i in range(0,n-1):
    if S[i] in F:
        cnt+=0
    elif S[i] in T:
        cnt+=1
        F.append(S[i])
print(cnt)


Measured memory_bytes: 6548
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
#define setp(x) fixed << setprecision(x)
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
 
}
void solve()
{
	int n, x;
	cin >> n >> x;
	int a[n];
	ll res = 0;
	rep(i, n) cin >> a[i];
	rep(i, n){
		if(i){
			int sum = a[i] + a[i - 1];
			int p = min(a[i], max(0, sum - x));
			a[i] -= p;
			sum -= p;
			res += 1ll * p;
			p = min(a[i - 1], max(0, sum - x));
			a[i - 1] -= p;
			sum -= p;
			res += 1ll * p;
		}
	}
	cout << res;
}	 

 
int main()
{
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
    Red;
  	int T = 1;
  	// cin >> T;
  	for(int i = 1; i <= T; ++i){
  		solve();
  	}
  	return 0;

}

Measured memory_bytes: 4036
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef MY_DEBUG_FLAG
template<typename T> void debug(T a) { cerr << a << ' '; }
template<typename T, typename U> void debug(pair<T, U> a) { cerr << a.first << ' ' << a.second << ' '; }
template<typename T> void debug(vector<T> a) { for(auto it : a) debug(it);}
template<typename T> void debug(set<T> a) { for(auto it : a) debug(it);}
#define db(a) cerr << "DEBUG ( " << #a << " == "; debug(a); cerr << ")\n"
#else
#define db(...)
#endif

#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false), cout.tie(nullptr), cin.tie(nullptr)
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define dec(i,n,a) for(int i=(n); i>=(a); i--)
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()

constexpr int inf = 0x3f3f3f3f;
constexpr int MAXN = 110;
constexpr int MAXK = 1e5 + 10;
constexpr int mod = 1000000007;

int main() {
	int n, K; scanf("%d %d", &n, &K);
	vi a(n+1); rep(i,1,n+1) scanf("%d", &a[i]);
	
	vector<ll> dp(K+1), new_dp(K+1), pref(K+1, 1);
	dp[0] = 1;

	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= K; j++) {
			// dp[i][j] gets the sum of the last a[i] values, because we can give
			// to that children any value between [0..a[i]]
			new_dp[j] = pref[j];
			if(j - a[i] - 1 >= 0) new_dp[j] -= pref[j - a[i] - 1];
			new_dp[j] = (new_dp[j] + mod)%mod;
		}
		swap(new_dp, dp);

		pref[0] = dp[0];
		rep(j,1,K+1) pref[j] = (pref[j-1] + dp[j])%mod;
	}

	// if(dp[K] < 0) dp[K] += mod;
	assert(dp[K] >= 0);
	printf("%lld\n", dp[K]);
}


Measured memory_bytes: 5644
#include <cstdio>
#include <cmath>

double r(double d){
  double a = roundl(d*1000);
  if(a==0) return +0.0;
  return a/1000;
}

int main(){
  double a,b,c,d,e,f;
  while(~scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f))
    printf("%.3f %.3f\n",r((c*e-b*f)/(a*e-b*d)),r((-c*d+a*f)/(a*e-b*d)));
}

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

#define COUNTOF(array) (sizeof(array) / sizeof(array[0]))    
#define OUT(P) cout << (P) << endl    
#define OUT2(P1, P2) cout << (P1) << " " << (P2) << endl    
#define PRINT_ARRAY(P) for(int i=0; i<P.size(); i++) cout << P[i] << endl;    
#define PRINT_ARRAY_INLINE(P) do { for(int i=0; i<P.size(); i++) cout << P[i] << " "; cout << endl; } while(0)    
#define PRINT_ARRAY_WITH_LABEL(L, P) do { cout << L << ": "; PRINT_ARRAY_INLINE(P); cout << endl; } while(0)    
typedef long long ll;    
const long DIVIDE = 1e9+7;

int sum_digits(int num);    
template <class T>    
vector<T> copy_vector(vector<T> vec);    
long gcd(long a, long b);    
long lcm(long a, long b);
// ****** print functions ****** //
template <class T, class U>
void print_pairs(const vector<pair<T, U>> pairs);
template <class K, class V>
void print_map(const map<K, V> m);


int main() {    
    int n, m;
    cin >> n >> m;
    vector<vector<int>> costs(n+1, vector<int>(3, -1));

    vector<vector<int>> g(n+1);
    for(int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    int start, goal;
    cin >> start >> goal;

    queue<pair<int, int>> que; // (point, state)
    que.push({start, 0}); // push start
    costs[start][0] = 0;

    // 幅優先探索
    while(!que.empty()) {
        const int node = que.front().first;
        const int state = que.front().second;
        que.pop();

        // 隣接頂点を探索
        for(int i=0; i<g[node].size(); i++) {
            int x = g[node][i];
            const int next_state = (state + 1) % 3;
            if(costs[x][next_state] != -1) {
                continue;
            }
            costs[x][next_state] = costs[node][state] + 1;
            que.push({ x, next_state });
        }
    }
    if(costs[goal][0] != -1) {
        costs[goal][0] /= 3;
    }
    cout << costs[goal][0] << endl;

    return 0;    
}    

/******************************/    
/***** DECRARED FUNCTIONS *****/    
/******************************/    

int sum_digits(int num) {    
    int rtn = 0;    
    while(num != 0) {    
        int tmp = num % 10;    
        rtn += tmp;    
        num /= 10;    
    }    
    return rtn;    
}    

// vectorのコピー    
template <class T>    
vector<T> copy_vector(vector<T> vec) {    
    vector<T> rtn;    
    rtn.reserve(vec.size());    
    copy(vec.begin(), vec.end(), back_inserter(rtn));    
    return rtn;    
}    

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

long lcm(long a, long b) {
    long gcd_ = gcd(a, b);
    return (a * b) / gcd_;
}

template <class T, class U>
void print_pairs(const vector<pair<T, U>> &pairs) {
    for(int i=0; i<pairs.size(); i++) { 
        cout << "(" << pairs[i].first << ", " << pairs[i].second << ")" << " "; 
    } 
    cout << endl;
}

template <class K, class V>
void print_map(const map<K, V> &m) {
    for(auto it=m.cbegin(); it!=m.cend(); it++) {
        cout << it->first << ": " << it->second << endl;
    }
}


Measured memory_bytes: 11264
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

template<typename T, class F, const T I>
struct SegmentTree {
    const F op = F();
    int n; vector<T> dat;
    T operator [](int i) const { return dat[n + i]; }
    void init(int n_) { n = 1; while (n < n_) n *= 2; dat.assign(n * 2, I); }
    void build(const vector<T>& v) {
        int n_ = v.size(); init(n_); for (int i = 0; i < n_; ++i) dat[n + i] = v[i];
        for (int i = n - 1; i; --i) dat[i] = op(dat[i * 2], dat[i * 2 + 1]);
    }
    void update(int k, T v) { dat[k += n] = v; while (k /= 2) dat[k] = op(dat[k * 2], dat[k * 2 + 1]); }
    T query(int a, int b) {
        T vl = I, vr = I;
        for (int l = a + n, r = b + n; l < r; l /= 2, r /= 2) { if (l & 1) vl = op(vl, dat[l++]); if (r & 1) vr = op(dat[--r], vr); }
        return op(vl, vr);
    }
    template<class C> int find(int a, int b, C& check);
private:
    template<class C> int find(int a, int b, C& check, int k, int l, int r) {
        if (!check(dat[k]) || r <= a || b <= l) return -1; else if (k >= n) return k - n;
        int m = (l + r) / 2; int vl = find(a, b, check, k * 2, l, m);
        if (~vl) return vl; else return find(a, b, check, k * 2 + 1, m, r);
    }
};

template<typename T = int> struct max_of { constexpr T operator ()(T& lhs, T& rhs) const { return max<T>(lhs, rhs); } };
extern constexpr int identity = 0;

int main() {
    int N;
    cin >> N;
    vector<int> h(N), a(N);
    rep(i, N) cin >> h[i];
    rep(i, N) cin >> a[i];

    SegmentTree<ll, max_of<ll>, identity> stmax;
    stmax.build(vector<ll>(N + 1));

    rep(i, N) {
        ll b = stmax.query(0, h[i]);
        stmax.update(h[i], b + a[i]);
    }

    write(stmax.query(0, N + 1));
}

Measured memory_bytes: 7552
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000

int x[MAX], y[MAX];

int main(){
	int n;
	double dist;
	cin >> n;
	
	for(int i=0; i<n; i++) cin >> x[i];
	for(int i=0; i<n; i++) cin >> y[i];
	
	cout << fixed << setprecision(8);
	
	dist = 0;
	for(int i=0; i<n; i++) dist += abs(x[i] - y[i]);
	cout << dist << "\n";
	
	dist = 0;
	for(int i=0; i<n; i++) dist += pow( (double)abs(x[i] - y[i]) , 2);
	cout << pow(dist, 1./2) << "\n";
	
	dist = 0;
	for(int i=0; i<n; i++) dist += pow( (double)abs(x[i] - y[i]) , 3);
	cout << pow(dist, 1./3) << "\n";
	
	dist = 0;
	for(int i=0; i<n; i++) dist = max(dist, (double)abs(x[i] - y[i]));
	cout << dist << "\n";
	
	cout << flush;
	
	return 0;
}


Measured memory_bytes: 3440
#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define mat vector<vec>

using namespace std;

const ll mod=1000000007;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

int main(){

  ll a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a,a+3);
  cout << a[2]*10+a[1]+a[0] << endl;

}

Measured memory_bytes: 3548
N = gets.to_i
W = gets.split(' ').map(&:to_i)
min = 10 ** 9

(1..N - 1).each do |i|
  diff = (W[0, i].inject(:+) - W[i, N - 1 + i].inject(:+)).abs
  min = diff if diff < min
end

p min

Measured memory_bytes: 1788
k = 26
D = gets.to_i
c = gets.split.map(&:to_i)
s = D.times.map { gets.split.map(&:to_i) }
D.times do |d|
  max_e = -1
  max_i = -1
  k.times do |i|
    e = s[d][i] + c[i] * 50
    if e > max_e
      max_e = e
      max_i = i
    end
  end
  puts max_i + 1
end


Measured memory_bytes: 14456
import sys
input = sys.stdin.readline

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

def gcd(a, b):
    if b > a:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)

l, r = 1, 1

for x, y in L:
    c = max(l // x, r // y)
    while True:
        xx = x * c
        yy = y * c
            
        if l <= xx and r <= yy:
            l, r = xx, yy
            break
        else:
            c += 1

print(l + r)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> plll;
typedef pair<pll,pll> ppll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fst first
#define snd second
#define ins insert
#define pb push_back
template< typename T,typename V>ostream &operator<< (ostream &out,const pair<T,V> x){ out << "{" << x.fst << " : " << x.snd << "}"; return out;}template< typename T>ostream &operator<< (ostream &out,const set<T> x){ for(auto &it : x){ out << it << " "; } return out;}template< typename T>ostream &operator<< (ostream &out,const multiset<T> x){ for(auto &it : x){ out << it << " "; } return out;}template< typename T,typename V>ostream &operator<< (ostream &out,const map<T,V> x){ for(auto &it : x){ out << "[" << it.fst << "]" << " = " << it.snd << "\n"; } return out;}template< typename T>ostream &operator<< (ostream &out,const vector<T> x){ for(int i = 0;i < x.size() - 1; ++i){ out << x[i] << " "; } out << x.back(); return out;}template< typename T>ostream &operator<< (ostream &out,const vector<vector<T> > x){ for(int i = 0;i < x.size() - 1; ++i){ out << "[" << i << "]" << " = {" << x[i] << "}\n"; } out << "[" << x.size() - 1 << "]" << " = {" << x.back() << "}\n"; return out;}

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
ll dp[N];
ll a[N],b[N];
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    ll h,n;
    cin >> h >> n;
    for(int i = 0;i < n; ++i)cin >> a[i] >> b[i];
    memset(dp,0x31,sizeof(dp));
    dp[0] = 0;
    for(int i = 0;i < n; ++i){
        for(int j = 1;j <= h; ++j){
            dp[j] = min(dp[j],dp[max(j - a[i],0LL)] + b[i]);
        }
    }
    cout << dp[h];
    return 0;
}



Measured memory_bytes: 11392
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
      int n;
      
      Scanner sc = new Scanner(System.in);
      while (sc.hasNext()) {
        n = sc.nextInt();
        int x[] = new int[n];
        int y[] = new int[n];
        double total = 0;
        double max =(double)0;
        for (int i=0; i<n; i++) {
          x[i] = sc.nextInt();
        }
        for (int i=0; i<n; i++) {
          y[i] = sc.nextInt();
        }
        for (int i=0; i<n; i++) { //p = 1
          double a = Math.abs((double)x[i] - y[i]);
          total += a;
          if (a - max > 0 ) {
            max = a; //p = ∞
          }
        }
        System.out.println(total);
        total = 0;
        for (int i=0; i<n; i++) { //p = 2
          total += Math.abs((double)x[i] - y[i]) * Math.abs((double)x[i] - y[i]); 
        }
        System.out.println(Math.sqrt(total));
        total = 0;
        for (int i=0; i<n; i++) { //p = 3
          total += Math.abs((double)x[i] - y[i]) * Math.abs((double)x[i] - y[i]) * Math.abs((double)x[i] - y[i]);
        }
        System.out.println(Math.cbrt(total));
        System.out.println(max);
      }
    }
}


Measured memory_bytes: 26504
while True:
    H,W=map(int,input().split())
    if H==0 and W==0:
        break
    for j in range(H):
        for k in range(W):
            if (j+k)%2==0:
                print("#",end="")
            else:
                print(".",end="")
        print()    
    print()


Measured memory_bytes: 7008
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+10;
int n,a[N];
signed main(){
	scanf("%lld",&n);
	for (int i=1;i<=n;++i) scanf("%lld",a+i);
	int lp=2,rp=2;
	for (int i=n;i;--i){
		int x=a[i];
		lp=(lp-1)/x*x+x;
		rp=rp/x*x+x-1;
		if (lp>rp) return puts("-1"),0;
	}
	printf("%lld %lld\n",lp,rp);
	return 0;
}


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

using namespace std;

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

    int n, g;
    cin >> n >> g;

    for (int i = 1, a; i < n; ++i) {
        cin >> a;
        g = gcd(g, a);
    }
    cout << g << endl;

    return 0;
}


Measured memory_bytes: 256
s=list(input())
l=len(s)
k=int(input())
dic={'a':0,'b':25,'c':24,'d':23,'e':22,'f':21,'g':20,'h':19,'i':18,'j':17,'k':16,'l':15,'m':14,'n':13,'o':12,'p':11,'q':10,'r':9,'s':8,'t':7,'u':6,'v':5,'w':4,'x':3,'y':2,'z':1}
for i in range(l):
  if k-dic[s[i]]>=0:
    k=k-dic[s[i]]
    s[i]='a'
if k%26==0:
  ans=''
  for c in s:
    ans+=c
  print(ans)
else:
  s[-1]=chr(ord('a')+(ord(s[-1])-ord('a')+k)%26)
  ans=''
  for c in s:
    ans+=c
  print(ans)

Measured memory_bytes: 4152
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    static class A9x9
    {
        static void Main(string[] args)
        {
            var ab = Console.ReadLine().Split(' ').Select(y => int.Parse(y)).ToList();
            int a = ab[0];
            int b = ab[1];

            int answer = -1;
            if (a.ToString().Length == 1 && b.ToString().Length == 1)
            {
                answer = a * b;
            }

            Console.WriteLine(answer);
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 13268
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ull = unsigned long long;

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


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
a=[-1]*n
for i in range(m):
    s,c=map(int,input().split())
    s-=1
    if a[s]==-1:
        a[s]=c
    else:
        if a[s]!=c:
            print(-1)
            exit()
if n==1:
    print(max(0,a[0]))
    exit()

if a[0]==0:
    print(-1)
    exit()

ans=""
for i in range(n):
    if a[i]==-1:
        if i==0:
            ans+="1"
        else:
            ans+="0"
    else:
        ans+=str(a[i])
print(ans)


Measured memory_bytes: 38456
#include <iostream>
#include <string>
using namespace std;
int main()
{
int a,b;
  cin>>a>>b;
  string s1,s2;
  for(int i=1;i<=a;i++)
  {s1+=to_string(b);}
   for(int j=1;j<=b;j++)
  {s2+=to_string(a);}
  int x=s1.compare(s2);
  if (x<=0)
       cout<<s1;
  else 
    cout<<s2;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
int main(void){
    int a,b,c;
    cin >> a >> b >> c;
    if(a <= c && c <= b){
        cout << "Yes" << endl;
        return 0;
    }else if(b <= c && c <= a){
        cout << "Yes" << endl;
        return 0;
    }else{
        cout << "No" << endl;
        return 0;
    }
}


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

typedef long long ll;
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define REP(i,n) for (int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
 
using namespace std;

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

    int ans = 0;
    REP(i,4){
        if(n[i] == '+') ans++;
        else ans--;
    }

    cout << ans;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1e9+7;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
/*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll modpow(ll a,ll n, ll mod){ll res = 1;while(n>0){if (n%2==1){res = res * a % mod;}a = a * a % mod;n/=2;}return res;}
int main() {
    ll n;
    cin >> n;
    vector<int>a(n),b(n);
    for(int i=0;i<n;i++){
        cin >>a.at(i);
    }
    for(int j=0;j<n;j++){
        cin >>b.at(j);
    }
    vector<int>c(n);
    for(int i=0;i<n;i++){
        c.at(i)=a.at(i)-b.at(i);
    }
    ll x=0,y=0,ans=0;
    for(int i=0;i<n;i++){
        if(c.at(i)>0){
            ans+=c.at(i);
        }
    }
    cout << ans << endl;
}
    



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int A, B, N;
    cin >> N >> A >> B;
    string s;
    cin >> s;
    int a = 0;
    int b = 0;
    for (int i = 0; i < N; i++) {
        int j = 0;
        if ( s[i] == 'a' ) {
            if ( a + b < A + B ) {
                a ++;
                j = 1;
            }
        }else if ( s[i] == 'b' ) {
            if ( a + b < A + B ) {
                if ( b < B ) {
                    b ++;
                    j = 1;
                }
            }
        }
        if ( j == 1 ) {
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 896
def main():
    n = int(input())
    a = list(map(int,input().split()))
    rui = [0]*(n+1)

    rui[0] = abs(a[0])
    rui[-1] = abs(a[-1])
    for i in range(1,n):
        rui[i] += abs(a[i]-a[i-1])
    sr = sum(rui)

    for i in range(n):
        if i == 0:
            print(sr-rui[i]-rui[i+1]+abs(a[i+1]))
        elif i == n-1:
            print(sr-rui[i+1]-rui[i]+abs(a[i-1]))
        else:
            print(sr-rui[i]-rui[i+1]+abs(a[i-1]-a[i+1]))
 
if __name__ == '__main__':
    main()


Measured memory_bytes: 56684
#include <bits/stdc++.h>
const int INF = 500000;
using namespace std;

int main(void){
  bool used[100];
  int n, G[100][100];
  cin >> n;
  for(int i=0; i < 100; i++){
    used[i] = false;
    for(int j=0; j < 100; j++){
      G[i][j] = INF;
    }
  }
  for(int i=0; i < n; i++){
    int vtmp, k;cin >> vtmp >> k;
    for(int j=0; j < k; j++){
      int v, c; cin >> v >> c;
      G[vtmp][v] = c;   
    }
  }

  int d[100];
  for(int i=0; i < n; i++){
    d[i] = INF;
  }
  d[0] = 0;

  for(int i=0; i < n; i++){
    int mind = INF;
    int minind = -1;
    for(int j=0; j < n; j++){
      if(used[j] == false && d[j] < mind){
        mind = d[j]; minind = j;
      }
    }
    if(minind == -1) break;
    used[minind] = true;
    for(int j=0; j < n; j++){
      if(used[j] == false && G[minind][j] != INF){
        if(d[minind] + G[minind][j] < d[j]){
          d[j] = d[minind] + G[minind][j];
        }
      }
    }
  }
  for(int i=0; i < n; i++){
    cout << i << " " << d[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 1200
import java.util.Scanner;

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

        long h = stdIn.nextLong();

        long monster = 1;
        long attack = 0;
        while (!(monster == 0)) {
            if (h / 2 == 0) {
                attack += monster;
                monster = 0;
            } else {
                h = h / 2;
                attack += monster;
                monster *= 2;
            }
        }
        System.out.println(attack);
    }
}


Measured memory_bytes: 21844
item_count, select_count = map(int, input().split())

total = 0
votes = list(map(int, input().split()))

for score in votes:
    total += score

selected = 0
div = total / (4 * select_count)
for score in votes:
    if div <= score:
        selected += 1

if select_count <= selected:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9192
# -*- coding: utf-8 -*-
"""
Binary Search - Includes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_6_B&lang=jp

"""
_ = input()
A = set(input().split())
_ = input()
B = set(input().split())
print(int(A & B == B))



Measured memory_bytes: 61268
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE =0;
static const int GRAY =1;
static const int BLACK = 2;

int n, N[MAX][MAX];

void dijkstra(){
  int minv;
  int d[MAX],color[MAX];
  int i=0;

  for(i=0;i<n;i++)
    {
      d[i]=INFTY;
      color[i]=WHITE;
    }

  d[0] = 0;
  color[0]=GRAY;
  while(1)
    {
      minv = INFTY;
      int u =-1;
      int v=0;
      
      for(int i = 0; i<n ; i++)
	{
	  if(minv>d[i]&&color[i]!=BLACK)
	    {
	      u=i;
	      minv = d[i];
	    }
	}
      if(u==-1)
	{
	  break;
	}
      color[u]=BLACK;
      for(v=0;v<n;v++)
	{
	  if(color[v]!=BLACK && N[u][v]!=INFTY)
	    {
	    if(d[v]>d[u] +N[u][v])
	      {
		d[v]=d[u]+N[u][v];
		color[v]= GRAY;
	      }
	    }
	}
    }
  for(i=0;i<n;i++)
    {
      cout << i << " "<<(d[i] == INFTY ? -1 : d[i])<<endl;
    }
}

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

  int k,c,u,v;
  for(i=0;i<n;i++)
    {
      for(j=0;j<n;j++)
	{
	  N[i][j] =INFTY;
	}
    }

  for(i=0;i<n;i++)
    {
      cin>>u>>k;
      for(j=0;j<k;j++)
	{
	  cin>>v>>c;
	  N[u][v]=c;
	}
    }

  dijkstra();

  return 0;
}



Measured memory_bytes: 3136
n = int(input())
a = sorted([list(map(int, input().split())) for _ in range(n)])
cnt = a[0][0] - 1 + n + a[-1][1]

for i in range(n - 1):
    cnt += min(a[i + 1][0] - a[i][0], a[i][1] - a[i + 1][1]) - 1
print(cnt)

Measured memory_bytes: 28972
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>

static const int di4[]={-1, 0, 1, 0};
static const int dj4[]={0, -1, 0, 1};
static const int INF=1e9;

int bfs(std::vector<std::vector<int>> maze) {
    int H=(maze.size()+1)/2, W=maze[0].size();
    std::vector<std::vector<int>> dp(H, std::vector<int>(W, INF));
    std::queue<std::pair<int, int>> q;

    dp[0][0] = 1;
    q.emplace(0, 0);

    while (!q.empty()) {
        std::pair<int, int> tmp=q.front();
        q.pop();
        int i=tmp.first, j=tmp.second;

        for (int k=0; k<4; ++k) {
            int di=di4[k], dj=dj4[k];
            if (!(0 <= i+di && i+di < H && 0 <= j+dj && j+dj < W))
                continue;

            if (dp[i+di][j+dj] <= dp[i][j] + 1) continue;
            if (maze[2*i+di][j+(dj<0? dj:0)]) continue;

            dp[i+di][j+dj] = dp[i][j] + 1;
            q.emplace(i+di, j+dj);
        }
    }

    int res=dp[H-1][W-1];
    return res<INF? res:0;
}

int solve_testcase() {
    size_t W, H;
    scanf("%zu %zu", &W, &H);

    if (H == 0 && W == 0)
        return 1;

    std::vector<std::vector<int>> maze(2*H-1, std::vector<int>(W));

    for (size_t i=0; i<maze.size(); ++i) {
        size_t j_ub=W-(i+1)%2;
        for (size_t j=0; j<j_ub; ++j)
            scanf("%d", &maze[i][j]);
    }

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

int main() {
    while (!solve_testcase()) {}

    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e18
#define mod 1000000007

ll n,m,a,b,p,q;

int main(){
  cin>>n>>m>>a>>b>>p>>q;
  ll res=m;
  if(a==1&&b==1){
    ll cnt=min(m/(p+q),n);
    minch(res,m-cnt*(p+q));
    cnt=min(cnt+1,n);
    if(cnt*(p+q)-m>=0)minch(res,cnt*(p+q)-m);
    cout<<res<<endl;
    return 0;
  }
  ll crt1=p,crt2=q;
  vector<ll> cs,cs1;
  rep(k,n){
    if(2*m<crt1+crt2)break;
    cs.push_back(crt1+crt2);
    if(2*m/a<crt1||2*m/b<crt2)break;
    crt1*=a;
    crt2*=b;
  }
  ll n1=cs.size()/2;
  ll n2=cs.size()-n1;
  rep(S,1<<n1){
    ll sum=0;
    rep(i,n1){
      if((S>>i)&1)sum+=cs[i];
    }
    cs1.push_back(sum);
  }
  sort(all(cs1));

  rep(S,1<<n2){
    ll sum=0;
    rep(i,n2){
      if((S>>i)&1)sum+=cs[n1+i];
    }
    if(sum>=m){
      minch(res,sum-m);
    }else{
      ll idx=lower_bound(all(cs1),m-sum)-cs1.begin();
      if(idx<cs1.size()){
        minch(res,sum+cs1[idx]-m);
      }
      if(idx>0){
        minch(res,m-(sum+cs1[idx-1]));
      }
    }
  }
  cout<<res<<endl;
  return 0;
}



Measured memory_bytes: 11184
n,k = map(int,input().split())
A = list(map(int,input().split()))

b = 1
c = 0
while b <= k:
  b *= 2
  c += 1

B = [0]*(c)
for a in A:
  for i in range(c):
    if a>>i & 1 :      
      B[i] += 1
      
x = 0
for b in range(c,-1,-1):
  if x + (1<<b) > k:
    continue
  if B[b] < (n+1)//2:
    x += 1<<b
    
ans = 0
for a in A:
  ans += x^a
print(ans)  
  

Measured memory_bytes: 14620
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val n = sc.nextInt()
  val s = sc.next()

  var x = 0
  val ans = mutableListOf<Int>()
  ans.add(x)
  for (i in 0 until n) {
    val c = s.get(i)
    if (c == 'I') x++
    if (c == 'D') x--
    ans.add(x)
  }

  println(ans.max())
}


Measured memory_bytes: 31640
#!/usr/bin/env python3
N = int(input().strip())
xyh = [[int(str) for str in input().strip().split()] for _ in range(N)]

def f(x, y, cx, cy, H):
    return max(H - abs(x - cx) - abs(y - cy), 0)

def check(cx, cy, H):
    return all([f(x, y, cx, cy, H) == h for x, y, h in xyh])

for cx in range(101):
    for cy in range(101):
        hs = [h + abs(x - cx) + abs(y - cy) for x, y, h in xyh if h != 0]
        if len(set(hs)) == 1 and check(cx, cy, hs[0]):
            print(cx, cy, hs[0])

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include<queue>
#include<set>
using namespace std;

int main()
{
  int n;
  cin >> n;
  int nap[n + 1][3];

  nap[0][0] = 0;
  nap[0][1] = 0;
  nap[0][2] = 0;

  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      cin >> nap[i][j];
    }
  }

  for (int i = 1; i <= n; i++)
  {
    long long dt = nap[i][0] - nap[i-1][0];
    long long dx = abs(nap[i][1] - nap[i-1][1]);
    long long dy = abs(nap[i][2] - nap[i-1][2]);
    if (dx + dy <= dt && (dt - (dx + dy)) % 2 == 0)
    {
      if(i == n)
      {
      cout << "Yes" << endl;
      exit(0);
      }
    }
  }

  cout << "No" << endl;

}


Measured memory_bytes: 1408
#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
#define ip(arr, n) for(int i=0; i<n; i++) cin>>arr[i];
#define op(arr, n) for(int i=0; i<n; i++) cout<<arr[i]<<" ";
#define fstIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MAX 3005

int n;
ll *arr, dp[MAX][MAX];

ll solve(int i, int j){
    if(i>j) return 0;
    if(dp[i][j] != -1) return dp[i][j];

    ll opt1 = arr[i]-solve(i+1, j);
    ll opt2 = arr[j]-solve(i, j-1);

    return dp[i][j] = max(opt1, opt2);
}

void topDown(){
    memset(dp, -1, sizeof(dp));
    cout<<solve(0, n-1)<<endl;
}

int main(){
    fstIO;
    cin>>n;
    arr = new ll[n+1];
    ip(arr, n);
    topDown();
    return 0;
}


Measured memory_bytes: 71040
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll n,k;
  cin>>n>>k;

  ll ans=0,a,b,z[100010]={};
  for(ll i=0;i<n;i++){
    cin>>a>>b;
    z[a]+=b;
  }
  ll tmp=0;
  for(ll i=0;i<100010;i++){
    tmp+=z[i];
    if(tmp>=k){
      ans=i;
      break;
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

#define _u(i,a,b) for(int i=a;i<=b;++i)
#define _d(i,a,b) for(int i=a;i>=b;--i)
#define endl "\n"
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define FIO() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FI(task) freopen(task".inp","r",stdin)
#define FO(task) freopen(task".out","w",stdout)

using namespace std;

const int N = 1e3+7;
const int M = 1e9+7;

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

int d[N][N];
int n, m;
char a[N][N];

void bfs(){
    queue<ii>q; q.push({1, 1}); d[1][1] =1;
    while(q.size()){
        auto uu = q.front(); q.pop();
        _u(i,0,1){
            int u =uu.fi + dx[i];
            int v =uu.se + dy[i];
            if(u<1||u>m||v<1||v>n||a[u][v]=='#') continue;
            if(d[u][v] == -1){
                d[u][v] = 0;
                q.push({u, v});
            }
            d[u][v] = (d[u][v] + d[uu.fi][uu.se]) % M;
        }
    }
}

#define task "test"

int main(){
    FIO();
    //FI(task);
    ///FO(task);

    cin >> m >> n;
    _u(i,1,m) _u(j,1,n) cin >> a[i][j];
    memset(d, -1, sizeof d);
    bfs();
    if(d[m][n] == -1) d[m][n] = 0;
    cout << d[m][n];
    return 0;
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, m;
  cin >> n >> m;

  vector<int> count(n, 0);
  for(int i=0;i<m*2;i++){
  	int c;
  	cin >> c;
  	count.at(c-1)++;
  }
  for(int i=0;i<n;i++)
  	cout << count.at(i) <<endl;
}  

Measured memory_bytes: 256