akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに実装したソースコード
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), k = scanner.nextInt();
			int[] a = new int[n];
			// left必ず達成できない、right必ず達成できる
			int left = 0, right = IntStream.range(0, n).map(i -> a[i] = scanner.nextInt()).max().getAsInt();
			while (right - left > 0) {
				int mid = (left + right) / 2;
				if ((left == mid) || (right == mid)) {
					break;
				}
				if (ok(n, k, a, mid)) {
					right = mid;
				} else {
					left = mid;
				}
			}
			System.out.println(right);
		}
	}

	/**
	 * 目標値をk回まで切ることで達成できるかを計算する
	 * 
	 * @param n      丸太の数
	 * @param k      切る回数の上限
	 * @param a      丸太の長さの配列
	 * @param target 目標値
	 * @return 目標値をk回のカットで達成できるか
	 */
	private static boolean ok(int n, int k, int[] a, int target) {
		return IntStream.range(0, n).map(i -> (int) (((long) a[i] + target - 1) / target - 1)).sum() <= k;
	}
}


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

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;


signed main() {
    int N;
    cin >> N;
    int ans = N * (N + 1) * (N + 2) / 6;
    rep(i, N - 1) {
        int l, r;
        cin >> l >> r;
        if (l > r)swap(l, r);
        ans -= l * (N + 1 - r);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3608
import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

void main(){
	long n = read.to!long;
	long[] as = readln.chomp.split.to!(long[]);
	
	long sum = 0;
	long[long] xs;
	xs[sum] = 1;
	foreach(a; as){
		sum += a;
		if(sum in xs) xs[sum] += 1;
		else xs[sum] = 1;
		}
	
	debug xs.writeln;
	
	long ans;
	foreach(k; xs.keys){
		auto v = xs[k];
		ans += v * (v - 1) / 2;
		}
	
	ans.writeln;
	}

Measured memory_bytes: 26636
#include<iostream>

using namespace std;

int main(){
	long a, b, c, k, max=0;
  
  cin>>a>>b>>c>>k;
  
  if(a<k){
    max=a;
  	if(b<k-a){
      for(int i=0;i<k-(a+b);i++){
    	max--;
      }
    }
  }
  
  if(a>=k){
  	for(int i=0;i<k;i++){
    	max++;
    }
  }
  cout<<max<<endl;
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if(D==1) cout << 1 << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 256
def acinput():
    return list(map(int, input().split(" ")))

a,b=acinput()

dp={}
dp[1]=a
dp[0]=1
for i in range(1,100):
    dp[i]=dp[i-1]+a-1

res=0
for i in range(0,100):
    if dp[i]>=b:
        res=i
        break
print(res)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p){os<<"("<<p.first<<","<< p.second<<")";return os;}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v){os<<"{";REP(i,(int)v.size()){if(i)os<<",";os<<v[i];}os<<"}";return os;}
template <typename T, size_t S> void printArray(const T (&array)[S]){for(auto val : array)std::cout << val << ", ";std::cout << "\n";}
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
const double PI=acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;
//const int dx[4] = {1, 0, -1, 0};
//const int dy[4] = {0, 1, 0, -1};
//const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve(){
    ll x; cin >> x;
    ll res = 100;
    ll cnt = 0;
    while(true){
        res += res/100;
        cnt++;
        if(res >= x){
            break;
        }
    }
    cout << cnt << endl;
}

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

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

#ifdef LOCAL
    #include "debug.h"
    #define input freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#else
    #define debug(...) 4
    #define input 4
#endif

using ll = long long;
constexpr int N = 2e5 + 5;
constexpr int mod = 1e9 + 7;
int ans[N], modulo1[N], modulo2[N];
int main()
{
    input;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= 200000; i++) {
        int ii = i, cnt = 0;
        while(ii) {
            ii = ii % __builtin_popcount(ii);
            cnt++;
        }
        int p = __builtin_popcount(i);
        ans[i] = cnt;
    }
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    int pop = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '1')
            pop++;
    }
    int pop1 = pop + 1;
    int pop2 = pop - 1;
    modulo1[0] = 1 % pop1;
    if(pop2)
        modulo2[0] = 1 % pop2;
    for(int i = 1; i < n; i++) {
        modulo1[i] = (modulo1[i - 1] * (2 % pop1)) % pop1;
        if(pop2)
            modulo2[i] = (modulo2[i - 1] * (2 % pop2)) % pop2;
    }
    int total_mod1 = 0, total_mod2 = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '1') {
            total_mod1 += modulo1[i];
            total_mod2 += modulo2[i];
            total_mod1 %= pop1;
            if(pop2)
                total_mod2 %= pop2;
        }
    }
    vector<int> v;
    for(int i = 0; i < n; i++) {
        
        if(s[i] == '1') {
            int x = total_mod2;
            x -= modulo2[i];
            x += pop2;
            if(pop2)
                x %= pop2;
            if(pop2)
                v.push_back(1 + ans[x]);
            else
                v.push_back(0);
        }
        else {
            int x = total_mod1;
            x += modulo1[i];
            x %= pop1;
            v.push_back(1 + ans[x]);
        }
    }
    reverse(v.begin(), v.end());
    for(int x : v)
        cout << x << "\n";
}
//asdasdlkjl

Measured memory_bytes: 6772
#include<stdio.h>
int main(){
	int a,b,c,t;
	scanf("%d%d%d",&a,&b,&c);
	if(a>=b){
		t=a;
		a=b;
		b=t;
	}
	if(a>=c){
		t=a;
		a=c;
		c=t;
	}
	if(b>=c){
		t=b;
		b=c;
		c=t;
	}
	if(a==5&&b==5&&c==7){
		printf("YES\n");
	}
	else{
		printf("NO\n");
	}
	return 0;
}


Measured memory_bytes: 128
/*
   THE DARK NIGHT RISES
I LOVE YOU 72 AND WILL FOREVER DO SO
Patience, Persistence, Perseverance, Passion, Purpose
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
const int N = 2e5 + 20 ;
#define F first
#define S second
# define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define mk make_pair
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,a,b) for(ll i=a;i<b;i++)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define sz(x)       (int)x.size()
const long long int mod=1e9 + 7;
const long double EPS=1e-12;
#define mem( a, val ) memset(a, val, sizeof( a ) )
#define deci( x ) cout<<fixed<<setprecision( x );
#define bitcount( x ) __builtin_popcountll( x )

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

int solve()
{
	ld a ,b ,x ;
	cin >> a >> b >> x ;
	ld h = x /(a*a) ;
	ld hl = b /2.0000000 ;
	if(h >=(hl))
	{
		ld the = 2.000*(b-h)/(a) ;
		ld ang = atan(the)*180.00000000/(M_PI) ;
		cout << fixed << setprecision(10) << ang ;
	}
	else 
	{
		ld  the = (2*x)/(b*b*a) ;
		ld ang = atan(the)*180.00000000/(M_PI) ;
		ang = 90.00000000- ang ;
		cout << fixed << setprecision(10) << ang ;

	}
	

}
int main()
{
	fast;
	ll t;
	t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}

	return 0;
}
// Patience, Persistence, Perseverance, Passion, Purpose
// I LOVE YOU 72 AND WILL FOREVER DO SO.

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long long ll;
const int INF = 1e9;
int n;

int main() {
  cin >> n;
  vector<int> a(n + 1);
  vector<int> r(n + 1), l(n + 1);

  rep(i, n) cin >> a[i];
  l[0] = a[0];
  r[n - 1] = a[n - 1];
  for (int i = 0; i < n; ++i) l[i + 1] = max(l[i], a[i + 1]);
  for (int i = n - 1; i >= 0; --i) r[i] = max(r[i + 1], a[i]);

  cout << r[1] << endl;
  for (int i = 1; i < n - 1; ++i) cout << max(l[i - 1], r[i + 1]) << endl;
  cout << l[n - 2] << endl;
  return 0;
}


Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(), x.end()

int main() {
  ll n;
  cin >> n;
  vector<pair<ll, ll>> a(n + 1);
  for (ll i = 1; i <= n; i++) {
    ll tmp;
    cin >> tmp;
    a[i] = make_pair(tmp, i);
  }
  sort(all(a));
  for (ll i = 1; i <= n; i++) {
    cout << a[i].second << " ";
  }
  cout << endl;
}

Measured memory_bytes: 2432
s = list(input())
j= 2
count = 0
if not s[0] == 'A':
    print('WA')
    exit()

for i in s[2:-1]:
    if i == 'C':
        count += 1
        tmp = j
    j += 1
if not count == 1:
    print('WA')
    exit()

del s[0]
del s[tmp-1]
s = ''.join(s)

if s.islower():
    print('AC')
    exit()

print('WA')

Measured memory_bytes: 3064
#include <stdio.h>

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

Measured memory_bytes: 1032
import java.util.Scanner;

public class Main{
 public static void main(String[] args) {
   Scanner kbd =new Scanner(System.in);
   int n=kbd.nextInt();
   String c=kbd.next();
   String r="W";
   int num=0;
   int a=0;
   for(int i=0;i<n;i++){
   if(c.charAt(i)==r.charAt(0)){
     num++;
   }
 }
 for(int i=0;i<n-num;i++){
 if(c.charAt(i)==r.charAt(0)){
   a++;
 }
}
 System.out.println(a);
}
}


Measured memory_bytes: 41076
#include <stdio.h>
int main()
{
int W,H,x,y,r;
scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
if ((0 <= x-r)&&(x+r <= W)&&(0 <= y-r)&&(y+r <= H))
printf("Yes\n");

else
printf("No\n");

return 0;

}
 

Measured memory_bytes: 584
sx, sy, tx, ty = (int(i) for i in input().split())  
dx = tx - sx
dy = ty - sy
st = "U"*dy + "R"*dx + "D"*dy + "L"*(dx+1) + "U"*(dy+1) + "R"*(dx+1) + "DR" + "D"*(dy+1) + "L"*(dx+1) + "U"
print(st)

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#define INF 2147483647

long long N, a, b, res, mn = INF;

int main () {
    scanf("%lld", &N);
    for (int i = 1;i <= N; ++i) {
	scanf("%lld%lld", &a, &b);
	res += a;
	if (a > b) mn = std :: min(mn, b);
    }
    if (mn == INF) printf("0\n");
    else printf("%lld\n", res - mn);
    return 0;
}


Measured memory_bytes: 256
import math
K = int(input())
K +=1
ans = 0
for i in range(1,K):
  ans += math.gcd(i,i)
  for j in range(i+1,K):
    ans += 6 * math.gcd(i,j)
    for k in range(j+1,K):
      ans += 6 * math.gcd(math.gcd(i,j),k)

print(ans)

Measured memory_bytes: 9172
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int ans=0,cnt=0;
	for(int i=0;i<s.size();i++)
	{
	 	if(s[i]=='R') cnt++;
	 	else
		 {
		 	ans=max(ans,cnt);
		 	cnt=0;
		 }
	}
	ans=max(ans,cnt);
	cout<<ans;
	return 0;
}

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

using namespace std;

int main() {
	int n; cin>>n;
	vector<int>v;

	for(int i=0;i<n;i++){
		int h; cin>>h;
		h--;
		v.push_back(h); }

	int now=0,c=0;
	for(int i=0;i<n;i++)
   {
		if(now==1){
			cout<<c<<endl;
			return 0; }
		c++;
		now=v[now];
	}

	cout<<-1<<endl;

	return 0;
}


Measured memory_bytes: 892
########関数部分##############
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
############################

import numpy as np

n = int(input())

x = num2alpha(n).lower()
print (x)

Measured memory_bytes: 27080
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int main(){
  string s;cin>>s;
  int i=0;
  int x=s.length();
  //Aの数を保存しながら進めていく
  ll tmp=0,ans=0;
  bool a=false;
  while(i<=x){
    if(i+1>x-1) break;
    if(a and s[i]=='B' and s[i+1]=='C'){
      ans+=tmp;
      i+=2;
    }
    else if(s[i]=='A'){
      tmp++;
      a=true;
      i++;
    }
    else{
      a=false;
      tmp=0;
      i++;
    }

  }
  cout<<ans<<endl;
}


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

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
 
const int INF = 10000000;
const int mod = 1e9 + 7;
const double EPS = 1e-9;


int main(){
	vector<string> v(10);
	v[0] = " ";
	v[1] = "\',.!?";
	v[2] = "abcABC";
	v[3] = "defDEF";
	v[4] = "ghiGHI";
	v[5] = "jklJKL";
	v[6] = "mnoMNO";
	v[7] = "pqrsPQRS";
	v[8] = "tuvTUV";
	v[9] = "wxyzWXYZ";
	string s;
	int a, b;
	bool zeroflag;

	while(cin>>s){
		string ans;
		a = 0; b = 0;
		zeroflag = false;

		a = s[0] - '0';
		if(a == 0) {
			zeroflag = true;
			//cout<<"OK"<<endl;
		}
		for(int i = 1; i < s.size(); i++){
			if(s[i] == '0'){
				if(zeroflag) ans += v[0];
				else {
					zeroflag = true;
					ans += v[a][b];
					//cout<<" a = "<<a<<" b = "<<b<<" "<<ans<<endl;
					a = b = 0;
				}
			}
			else{
				if(zeroflag) a = s[i] - '0';
				else{
					if(s[i] == (char)('0' + a)){
						b = ( b + 1) % v[a].size();
					}
					else{
						ans += v[a][b];
						a = s[i] - '0';
						b = 0;
					}
				}
				zeroflag = false;
			}
		}
		if((a == 0 && zeroflag) || a > 0) ans += v[a][b];
		cout<<ans<<endl;
	}
}	

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int main() {
    int n, r, l; cin >> n >> r >> l;vector<int> d(r), t(r), x(r);
    for(int i = 0; i < r; ++i) { cin >> d[i] >> t[i] >> x[i];d[i]--;}
    vector<int> score(n), ans(n);priority_queue<pii> que;
    for(int i = 0; i < n; ++i) que.emplace(0, -i);
    int pre_t = 0;
    for(int i = 0; i < r; ++i) {
        while(score[-que.top().second] != que.top().first) que.pop();
        ans[-que.top().second] += t[i] - pre_t;
        score[d[i]] += x[i];que.emplace(score[d[i]], -d[i]);
        pre_t = t[i];
    }
    while(score[-que.top().second] != que.top().first) que.pop();
    ans[-que.top().second] += l - pre_t;
    cout << (max_element(begin(ans), end(ans)) - begin(ans) + 1) << endl;
}


Measured memory_bytes: 19508
#include <iostream>

using namespace std;

int main(){
  int n,i;
  long long T,ans=0;
  cin >> n >> T;
  long long t,p=0;
  cin >> t;
  ans=T;
  for(i=1;i<n;i++){
    p = t;
    cin >> t;
    if(t-p>T)ans+=T;
    else ans+=-p+t;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

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

  ll A, B, C, K;
  cin >> A >> B >> C >> K;
  ll answer {};
  if (K > A+B) {
    answer += (-1)*(K-(A+B));
  }
  answer += (min(K, A));
  cout << answer << '\n';
}


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

const ll p = 1e9+7;
ll a, b;
ll binom[4005][2005];
ll ans = 0;

ll c(int x, int y) {
	if (y > x)
		return 0;
	if (x < 0)
		return 0;
	return binom[x][y];
}

int main() {
	cin >> a >> b;
	for (int i = 0; i < 4005; ++i)
		for (int j = 0; j < 2005; ++j) {
			if (j > i)
				continue;
			if (j == 0)
				binom[i][j] = 1;
			else
				binom[i][j] = (binom[i-1][j-1] + binom[i-1][j])%p;
		}

	//case 1: l == 0
	ans = a+1;
	for (int l = 1; l < 2005; ++l)
		for (int n = 0; n < 2005; ++n) {
			ans = (ans + c(b-1, l)*c(l-1, n)%p*c(a-n-l+2, 2)%p)%p;
		}

	cout << ans << endl;
}

Measured memory_bytes: 61568
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <climits>
using namespace std;

#define REP(i,a,n) for(i=a; i<n; i++)
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define foreach(it,x) for(typeof(x.begin()) it=x.begin(); it!=x.end(); it++)

const int dx[] = {0,1,1,0,-1,-1};
const int dy[] = {-1,-1,0,1,1,0};
int N,K, goalX,goalY;
int res;
vector<pair<int,int> > snake_init;
map<vector<pair<int,int> >, int> dp;
set<vector<pair<int,int> > > used;
set<pair<int,int> > stone;

// {{{ input() //
void input(){
    int i,j,k;

    rep(i,N){
        int x,y; cin >> x >> y;
        snake_init.push_back(make_pair(x,y));
    }
    // stone
    cin >> K;
    rep(i,K){
        int u,v; cin >> u >> v;
        stone.insert(make_pair(u,v));
    }
    cin >> goalX >> goalY;
}
// }}} //


bool ccc(int idx, const vector<pair<int,int> >& buf){
    int i,j,k;
    int res = 0;

    if( stone.count(buf[idx]) ) return false;
    if( idx == 0 || idx == buf.size()-1 ) res = 1;

    rep(i,idx) if( buf[i] == buf[idx] ) return false;

    rep(k,6){
        int tx = buf[idx].first + dx[k];
        int ty = buf[idx].second + dy[k];
        if( idx != 0 ){
            if( buf[idx-1].first == tx && buf[idx-1].second == ty ) res++;
        }
        if( idx != N-1 ){
            if( buf[idx+1].first == tx && buf[idx+1].second == ty ) res++;
        }
        rep(i,idx-1){
            if( buf[i].first == tx && buf[i].second == ty ) return false;
        }
    }
    return res == 2;
}


// {{{ dfs //

void dfs(int idx, bool f, int cost, queue<vector<pair<int,int> > >& q, vector<pair<int,int> >& buf){
    int i,j,k;

    if( idx > 0 && ( 20 < cost + 2*max(abs(buf[0].first-goalX), abs(buf[0].second-goalY))-1 ) ) return ;

    if( idx == N ){
        if( dp.count(buf) == 0 ){
            dp[buf] = cost + 1;
            q.push(buf);
            if( buf[0].first == goalX && buf[0].second == goalY ){
                res = cost + 1;
            }
        }
        return;
    }

    if( ccc(idx, buf) ) dfs(idx+1, true, cost, q, buf);

    if( idx == 0 || f ){
        rep(k,6){
            buf[idx].first += dx[k]; buf[idx].second += dy[k];
            if( ccc(idx, buf) ) dfs(idx+1, false, cost, q, buf);
            buf[idx].first -= dx[k]; buf[idx].second -= dy[k];
            if( res != INT_MAX ) return;
        }
    }
}

// }}} //



void bfs(){
    int i,j,u,v,k;

    queue<vector<pair<int,int> > > q;
    q.push(snake_init);
    dp[snake_init] = 0;

    while( !q.empty() ){
        vector<pair<int,int> >& tmpv = q.front();
        int cost = dp[tmpv];

        if( cost > 20 || res != INT_MAX ) break;

        if( used.count(tmpv) ) continue;
        used.insert(tmpv);

        dfs(0,true,cost,q,tmpv);
        q.pop();
    }
}




int main(){

    while( cin >> N, N ){
        // init
        res = INT_MAX;
        snake_init.clear();
        stone.clear();
        used.clear();
        dp.clear();

        input();
        
        bfs();
        cout << res << endl;
    }

    return 0;
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int A, B; cin >> A >> B;
    cout << A*B - (A+B) + 1 << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 256
import sys
def main():
    N,K=tuple(map(int,sys.stdin.readline().split()))
    a=tuple(map(int,sys.stdin.readline().split()))
    dp=[False for _ in range(K+1)]
    for i in range(K+1):
        for x in a:
            if i-x>=0:dp[i]=dp[i] or (not dp[i-x])
    print('First') if dp[K] is True else print('Second')
if __name__=='__main__':main()

Measured memory_bytes: 79020
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
//  πを定義
const double PI = acos(-1);
 
int main() {
  int a, b, h, m;
  cin >> a >> b >> h >> m;
//   短針
  double th = double(h*60+m)/720 * 2*PI;
//   長針
  double tm = double(m)/60 * 2*PI;
//   短針の角度
  double xh = a*cos(th), yh = a*sin(th);
//   長針の角度
  double xm = b*cos(tm), ym = b*sin(tm);
//   座標の差
  double dx = xh-xm, dy = yh-ym;
//   平方根
  double ans = sqrt(dx*dx + dy*dy);
//   10桁ぐらいまで出す
  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 4024
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))


Measured memory_bytes: 64856
//103B
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
int main(void){
    int i=0;
    string s, t, tmps;
    cin>> s >> t;
    while(i <=s.size()){
        tmps = s.back();
        tmps += s.substr(0, s.size()-1);
        if (tmps==t){
            cout << "Yes";
            return 0;
        }
        s = tmps;
        i++;
    }
    cout << "No";
}

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

int main(){
    int H, W;
    cin >> H >> W;
    int a[H][W];
    rep(i, H){
        rep(j,W){
            cin >> a[i][j];
        }
    }
    int y[H*W], x[H*W], Y[H*W], X[H*W];
    int N = 0;
    rep(i, H){
        if(i%2 == 0){
            rep(j, W-1){
                if(a[i][j]%2 != 0){
                    a[i][j]--;
                    a[i][j+1]++;
                    y[N] = i+1;
                    x[N] = j+1;
                    Y[N] = i+1;
                    X[N] = j+2;
                    N++;
                }
            }
            if(i != H-1){
                if(a[i][W-1]%2 != 0){
                    a[i][W-1]--;
                    a[i+1][W-1]++;
                    y[N] = i+1;
                    x[N] = W;
                    Y[N] = i+2;
                    X[N] = W;
                    N++;
                }
            }
        }
        else{
            for(int j = W-1; j > 0; j--){
                if(a[i][j]%2 != 0){
                    a[i][j]--;
                    a[i][j-1]++;
                    y[N] = i+1;
                    x[N] = j+1;
                    Y[N] = i+1;
                    X[N] = j;
                    N++;
                }
            }
            if(i != H-1){
                if(a[i][0]%2 != 0){
                    a[i][0]--;
                    a[i+1][0]++;
                    y[N] = i+1;
                    x[N] = 1;
                    Y[N] = i+2;
                    X[N] = 1;
                    N++;
                }
            }
        }
    }
    cout << N << endl;
    rep(i, N){
        cout << y[i] << ' ' << x[i] << ' ' << Y[i] << ' ' << X[i] << endl;
    }
}

Measured memory_bytes: 4992
#include<iostream>
#include<stack>
#include<vector>

using namespace std;

#define MAX 100000
#define NIL -1

int n;
int color[MAX];
vector<int> G[MAX];


void dfs(int u, int id){
  
  stack<int> S;
  S.push(u);
  color[u] = id;

  int present;
  while( !S.empty() ){
    present = S.top();
    S.pop();

    for(int i=0;i<G[present].size();i++){
      int v = G[present][i];
      if( color[v] == NIL ){
        color[v] = id;
        S.push(v);
      }    
    }  
  }
}

void assignColor(){
 
  for(int i=0;i<n;i++){
    color[i] = NIL;
  } 

  int id = 0;
  for(int u=0;u<n;u++){
    if(color[u] == NIL){
      dfs(u,id);
      id = id + 1;
    }
  }
}

int main(void){

  int m;
  cin >> n >>  m;

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

  assignColor();

  int q;
  cin >> q;

  int s,t;
  for(int i=0;i<q;i++){
    cin >> s >> t;
    if( color[s] == color[t] ){
      cout << "yes" << endl;
    }else{
      cout << "no"<< endl;;
    } 
  }

  return 0;
}



Measured memory_bytes: 9028
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <complex>

int main(){
  
  long long int N, K;
  scanf("%lld%lld", &N, &K);

  long long int digits = 0;
  long long int tmp = 1;
  while(tmp <= N){
    tmp *= K;
    digits++;
  }

  std::cerr << "Answer:" << std::endl;
  std::cout << digits << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// g++ Main.cpp -std=gnu++1y -O2 -I/opt/boost/gcc/include -o main && ./main
// g++ Main.cpp -std=gnu++1y -O2 -I/opt/boost/gcc/include -o main && ./main

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vll = vector<vl>;
using vii = vector<vi>;
using pii = pair<int, int>;

using vc = vector<char>;
using vcc = vector<vc>;
using vb = vector<bool>;
using vbb = vector<vb>;
using pll = pair<ll, ll>;
using vd = vector<double>;
using vdd = vector<vd>;

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


const int MOD = 1e9 + 7;

// n は 2以上の素数表を返す
vb Primes(int n){
  vector<bool> res(n + 1, true);
  res.at(0) = false; res.at(1) = false;
  for(int i = 2; i <= sqrt(n); i++){
    if(res.at(i)){
      for(int j = 2 * i; j <= n; j += i){
        res.at(j) = false;
      }
    }
  }
  return res;
}
// ===================================================

int main(){
  int n; cin >> n;
  vi A(n); REP(i, n) cin >> A.at(i);
  deque<int> B;
  int tmp;
  if((n & 1) == 0){
    REP(i, n){
      tmp = A.at(i);
      if((i & 1) == 0) B.push_back(tmp);
      else B.push_front(tmp);
    }
  }
  else{
    REP(i, n){
      tmp = A.at(i);
      if((i & 1) == 0) B.push_front(tmp);
      else B.push_back(tmp);
    }
  }
  cout << B.front(); B.pop_front();
  REP(i, n - 1){
    cout << " " << B.front();
    B.pop_front();
  }
  cout << "\n";
  return 0;
}

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

void solve(long long X, long long t)
{
    int ans = max((long long)0,X-t);
    cout << ans << endl;
}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end() 
using namespace std;

typedef long long ll;

inline char tc(){
  static char fl[100],*A=fl,*B=fl;
  return A==B&&(B=(A=fl)+fread(fl,1,100,stdin),A==B)?EOF:*A++;  
}

inline int read(){
  int a=0;static char c;
  while((c=tc())<48||c>57);
  while(c>=48&&c<=57)a=a*10+c-48,c=tc();
  return a;
}

const int N = 1e5 + 5;

vector<int> cnt[4];
int res[N];

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   n = read();
   for(int i=0; i<n; ++i) {
       int x = read();
       cnt[x%4].push_back(x);
   }
   int p = n-1;
   for(int i=n-1; i>=0; --i) {
       if(cnt[2].empty()) break;
       res[i] = cnt[2].back();
       cnt[2].pop_back();
       p = i;
   }
   for(int i=p-1; i>=0; i-=2) {
       if(cnt[0].empty()) break;
       res[i] = cnt[0].back();
       cnt[0].pop_back();
   }
   for(int i=0; i<n; ++i) {
       if(res[i] == 0) {
           if(cnt[0].empty()) break;
           res[i] = cnt[0].back();
           cnt[0].pop_back();
       }
   }
   for(int i=0; i<n; ++i) {
       if(res[i] == 0) {
           if(!cnt[1].empty()) {
               res[i] = cnt[1].back();
               cnt[1].pop_back();
           }
           else if(!cnt[3].empty()) {
               res[i] = cnt[3].back();
               cnt[3].pop_back();
           } else {
                puts("No");
             	return 0;
           }
       }
   }
   for(int i=0; i<n-1; ++i) {
        if((res[i] * res[i+1]) % 4 != 0) {
                puts("No");
            return 0;
        }
   }
   puts("Yes");
   return 0;
}



Measured memory_bytes: 1276
n,x,y=map(int,input().split())
ans=[0]*n #個数を数えるのにバケットを用意する
for i in range(1,n+1): #i<jなるすべての頂点の組について最短距離を求める
 for j in range(i+1,n+1):
   dist1=j-i
   dist2=abs(x-i)+abs(y-j)+1
   dist3=abs(y-i)+abs(x-j)+1
   d=min(dist1,dist2,dist3) #最短距離は上式により求められる
   ans[d]+=1 #最短距離がdとなる組の個数を1増やす
for i in range(1,n):
 print(ans[i])

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

namespace AizuOnlineJudge {
    class Program {
        class Pair {
            public string name;
            public int time;

            public Pair(string n, int t) {
                name = n;
                time = t;
            }
        }

        static void Main() {
            var queue = new Queue<Pair>();
            var time = 0;

            var nq = Console.ReadLine().Split().Select(int.Parse).ToArray();
            for (var i = 0; i < nq[0]; ++i) {
                var l = Console.ReadLine().Split();
                queue.Enqueue(new Pair(l[0], int.Parse(l[1])));
            }

            while (queue.Any()) {
                var n = queue.Dequeue();
                var t = Math.Min(n.time, nq[1]);
                time += t;
                n.time -= t;
                if (n.time > 0) {
                    queue.Enqueue(n);
                }
                else {
                    Console.WriteLine(n.name + " " + time);
                }
            }
        }
    }
}



Measured memory_bytes: 27120
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

//ここから書き始める
int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);	
    int N;
    cin >> N;
    VI A(N);
    REP(i,N)
    {
        cin >> A[i];
    }

    int t = 0;
    LL ans = 0;
    LL xorsum = 0;
    LL norsum = 0;

    REP(s,N)
    {
        xorsum -= A[s-1];
        norsum = xorsum;
        while(t < N && ((xorsum ^ A[t])==(norsum + A[t])))
        {
            norsum += A[t];
            xorsum = norsum;
            t++;
        }
        ans += t-s;
    }

    cout << ans << endl;

}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

	public static void main(String args[]) throws NumberFormatException, IOException{
		new Main().mainrun();
	}

    private BufferedReader br;

	private int n;
	private LoopList lp;

	public void mainrun() throws NumberFormatException, IOException {
		br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		lp = new LoopList();

		for(int i = 0;i < n;i++) {
			looprun();
		}

		lp.print();

	}

	private void looprun() throws IOException {
		String[] str = br.readLine().split(" ");
		switch(str[0]) {
		case "insert":
			lp.insert(Integer.parseInt(str[1]));
			break;
		case "delete":
			lp.delete(Integer.parseInt(str[1]));
			break;
		case "deleteFirst":
			lp.deleteFirst();
			break;
		case "deleteLast":
			lp.deleteLast();
			break;
		}
	}

}

class LoopList{

	private Data head,d,n,p;

	public LoopList() {
		head = new Data();

		head.next = head;
		head.prev = head;

		head.num = -1;
	}

	public Data getHead() {
		return head;
	}

	public void insert(int key){
		d = new Data();
		d.num = key;

		Data rd = head.next;

		head.next = d;

		d.prev = head;
		d.next = rd;

		rd.prev = d;
	}

	public void delete(int key){
		d = head.next;

		while(d.num != -1 && d.num != key) {
			d = d.next;
		}

		if(d.num == key) {
			n = d.next;
			p = d.prev;

			n.prev = p;
			p.next = n;

		}
	}

	public void deleteFirst(){
		d = head.next;
		n = d.next;

		n.prev = head;
		head.next = n;
	}

	public void deleteLast(){
		d = head.prev;
		p = d.prev;

		p.next = head;
		head.prev = p;
	}

	public void print() {
		d = head.next;
		int nnum ;

		while(d.num != -1) {
			nnum = d.next.num;
			System.out.print(d.num + (nnum == -1 ? "\n" : " "));
			d = d.next;
		}
	}

	class Data{
		int num;
		Data next,prev;
	}
}


Measured memory_bytes: 196992
package main

import (
    "fmt"
)

func main() {
    var h, w, k int
    ans := 0

    fmt.Scan(&h, &w, &k)
    c := make([]string, h)
    for i := 0; i < h; i++ {
        fmt.Scan(&c[i])
    }

    //赤に塗る行列のパターン
    for y := 0; y < 1<<uint(h); y++ {
        for x :=0; x < 1<<uint(w); x++ {

            //赤く塗られないマス目の黒(#)の数をカウントする
            count := 0
            for q := 0; q < h; q++ {
                for p := 0; p < w; p++ {
                    if (y>>uint(q))&1 == 0 && (x>>uint(p))&1 == 0 {
                        if string(c[q][p]) == "#" {
                            count++
                        }
                    }
                }
            }
            if count == k {
                ans++
            }
        }
    }
    fmt.Println(ans)
}


Measured memory_bytes: 1772
a_li_li = [list(map(int, input().split())) for i in range(3)]
n = int(input())
b = [int(input()) for i in range(n)]

bingo = []

for i, a_li in enumerate(a_li_li):
    for j, a in enumerate(a_li):
        if a in b:
            bingo.append(i + j * 10)

if 0 in bingo and 10 in bingo and 20 in bingo:
    ans = 'Yes'
elif 1 in bingo and 11 in bingo and 21 in bingo:
    ans = 'Yes'
elif 2 in bingo and 12 in bingo and 22 in bingo:
    ans = 'Yes'
elif 0 in bingo and 1 in bingo and 2 in bingo:
    ans = 'Yes'
elif 10 in bingo and 11 in bingo and 12 in bingo:
    ans = 'Yes'
elif 20 in bingo and 21 in bingo and 22 in bingo:
    ans = 'Yes'
elif 0 in bingo and 11 in bingo and 22 in bingo:
    ans = 'Yes'
elif 2 in bingo and 11 in bingo and 20 in bingo:
    ans = 'Yes'
else:
    ans = 'No'

print(ans)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while (!(line = br.readLine()).equals("0")) {
			char[] octs = Integer.toOctalString(Integer.parseInt(line))
					.toCharArray();
			for (int i = 0; i < octs.length; i++) {
				if (octs[i] >= '4')
					octs[i]++;
				if (octs[i] >= '6')
					octs[i]++;
			}
			System.out.println(String.valueOf(octs));
		}
	}
}

Measured memory_bytes: 32020
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define outl(x) cout << x << endl
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+12;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,h,maa = 0,b[100010],cnt = 0,sum = 0;
	cin >> n >> h;
	for(int i = 0;i < n;i++){
		int a;
		cin >> a >> b[i];
		chmax(maa,a);
	}
	sort(b,b + n,greater<int>());
	for(int i = 0;i < n;i++){
		if(b[i] > maa){
			cnt++;
			sum += b[i];
			if(sum >= h){
				cout << cnt << endl;
				return 0;
			}
		}
	}
	cout << cnt + (h - sum + maa - 1) / maa << endl;
	return 0;
}

Measured memory_bytes: 1024
N = int(input())
a = list(map(int,input().split()))
ans = [0 for i in range(N+1)]

for i in range(N,0,-1):
    res = 0
    for j in range(1,N+1):
        if i*j>N:
            break
        else:
            res += ans[i*j]
      
    if res%2 != a[i-1]:
        ans[i] += 1
        
print(sum(ans))
A = []
for i,v in enumerate(ans):
    if v>0:
        A.append(i)
        
        
print(*A)
    






Measured memory_bytes: 17652
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <iomanip>
using namespace std;
using P = pair<int,int>;
typedef long long ll;


#define rep(i,n) for (int i=0; i<(n); i++)
//const int INF =1001001001;
const ll BIG = 1e9+7;
const double PI = 3.141592653589793;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ans = 0;
    rep(i,k){
        ans += p[i];
    }
    int esum = ans;
    rep(i,n-k){
        esum = esum - p[i] + p[i+k];
        ans = max(esum, ans);
    }
    double sans = (double)(ans + k);
    sans /=2.0 ;
    cout << fixed << setprecision(10) << sans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
using namespace std;
long long a[200005];
long long s[200005];
int sl[200005], sr[200005];
long long aabs(long long x) {
    return max(x, -x);
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    long long res = s[n];
    for (int i = 2; i < n - 1; ++i) {
        if (a[i] >= s[i - 1]) {
            sl[i] = i - 1;
        } else {
            int l = 1, r = i - 1, rs = i - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (s[mid] >= s[i] - s[mid]) {
                    rs = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (aabs(s[i] - s[rs] - s[rs]) > aabs(s[i] - s[rs - 1] - s[rs - 1]) && rs != 1) {
                rs--;
            }
            sl[i] = rs;
        }
        if (a[n] >= s[n - 1] - s[i]) {
            sr[i] = n - 1;
        } else {
            int l = i + 1, r = n - 1, rs = n - 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (s[mid] - s[i] >= s[n] - s[mid]) {
                    rs = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (aabs(s[n] - s[rs] - s[rs] + s[i]) > aabs(s[n] - s[rs - 1] - s[rs - 1] + s[i]) && rs != i + 1) {
                rs--;
            }
            sr[i] = rs;
        }
    }
    for (int i = 2; i <= n - 2; ++i) {
        long long mx = max(s[sl[i]], max(s[i] - s[sl[i]], max(s[sr[i]] - s[i], s[n] - s[sr[i]])));
        long long mn = min(s[sl[i]], min(s[i] - s[sl[i]], min(s[sr[i]] - s[i], s[n] - s[sr[i]])));
        res = min(res, mx - mn);
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;

#define sz(a) static_cast<int>((a).size())
#define f first
#define s second
#define els(v) for (auto &el : (v))


#ifdef KIRYA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) {
    cerr << _s << " = " << _h << "\n";
}

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;

    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;

    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

const int64_t INF = static_cast<int64_t>(1e9) + 7;
const int64_t LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;

void dfs(int u, int p, const vector<int> &sum_start, vector<int> &res, vector<vector<int>> &g) {
    res[u] = sum_start[u];
    if (p != -1) {
        res[u] += res[p];
    }
    for (auto ngb : g[u]) {
        if (ngb == p) {
            continue;
        }
        dfs(ngb, u, sum_start, res, g);
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> sum_start(n, 0);
    for (int i = 0; i < q; ++i) {
        int u, x;
        cin >> u >> x;
        sum_start[--u] += x;
    }
    vector<int> res(n);
    dfs(0, -1, sum_start, res, g);
    els(res) {
        cout << el << ' ';
    }
    cout << endl;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int q = 1;

    for (int i = 0; i < q; ++i) {
        solve();
    }
}


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

int matrixChainMultiplication(int *);

int n;

int main(){
  int i,A[101],l,j,k;

  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&A[i-1]);
    scanf("%d",&A[i]);
  }
  printf("%d\n",matrixChainMultiplication(A));


}
int matrixChainMultiplication(int *A){
  int i,l,j,k,P[101][101],g;
  for(i=1;i<n;i++){
    P[i][i]=0;
  }
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      P[i][j]=9999999;
      for(k=i;k<=j-1;k++){
	g=P[i][k]+P[k+1][j]+A[i-1]*A[k]*A[j];
	if(g<P[i][j])
	  P[i][j]=g;
	  
      }
    }
  }

  return P[1][n];
}
    



Measured memory_bytes: 2752
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
   int n, k; cin >> n >> k;
   vector<ll> A(n); rep(i, n) cin >> A[i];

   vector<string> res; int cnt = 0;
   for(int i=k; i<n; i++){
       ll a = A[k+cnt], b = A[cnt];
       if(a>b)res.push_back("Yes");
       else res.push_back("No");
       cnt++;
   } 
   for(auto re: res)cout << re << ln;
}
    


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

int main(){
    string s;
    int ans=0;
    cin>>s;
    rep(i,s.size()){
        if(s[i]=='*'){
            cout<<ans<<endl;
            break;
        }
        else if(s[i]=='(')ans++;
        else ans--;
    }
}


Measured memory_bytes: 3208
#include<bits/stdc++.h>
using namespace std;
long long MOD=(long long)(1e9+7);
int main()
{string s;
   long long k;
   cin>>s;
   cin>>k;
   long long dp[s.length()+1][2][k];
   memset(dp,0,2*sizeof(long long)*(s.length()+1)*k);
   dp[s.length()][0][0]=1;
   dp[s.length()][1][0]=1;
   for(long long i=s.length()-1;i>=0;i--)
   {
       for(long long j=0;j<2;j++)
       {
           for(long long rem=0;rem<k;rem++)
           {
               if(j)
               {
                   for(long long digit=0;digit<=s[i]-'0';digit++)
                   {
                       if(digit==s[i]-'0')
                       dp[i][j][rem]+=dp[i+1][1][(rem-digit+MOD*k)%k];
                       else
                       {
                           dp[i][j][rem]+=dp[i+1][0][(rem-digit+MOD*k)%k];
                           
                       }
                       dp[i][j][rem]%=MOD;
                       
                   }
            }
            else
            {
                for(long long digit=0;digit<=9;digit++)
                {
                    dp[i][j][rem]+=dp[i+1][j][(rem-digit+MOD*k)%k];
                    dp[i][j][rem]%=MOD;
                }
            }
            
   }
}}
cout<<(dp[0][1][0]+MOD-1)%MOD;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<P,int>
#define vpp vector<PP>
#define fi first
#define se second
#define INF (1<<30)
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    string st;
    cin>>st;
    vi d(4);
    REP(i,st.size()){
        d[i]=stoi(st.substr(i,1));
        cerr<<d[i]<<endl;
    }
    REP(i,1<<3){
        int sum=d[0];
        REP(j,3){
            if(i&(1<<j)){
                sum+=d[j+1];
            }else{
                sum-=d[j+1];
            }
        }
        if(sum==7){
            cout<<d[0];
            REP(j,3){
                if(i&(1<<j)){
                    cout<<"+";
                }else{
                    cout<<"-";
                }
                cout<<d[j+1];
            }
            cout<<"=7";
            cout<<endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256