akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define printarray(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define rep(n) for (ll i = 0; i < n; i++)
#define repc(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define DEC(i, x, y) for (int i = x; i >= y; i--)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a + n
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b)/gcd(a, b)
#define int long long int
#define ull unsigned long long

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 5;

int fastexpo(int b, int exp){
    if(exp == 0) return 1;
    if(exp == 1) return b;
    int ans = (fastexpo(b,exp/2) % MOD);
    ans *= ans;
    ans %= MOD;
    if(exp % 2 == 1){
        ans *= b;
    }
    ans %= MOD;
    return ans;
}

int fact[MAXN]; 

void sieve() { 
    fact[1] = 1; 
    for (int i=2; i<MAXN; i++) fact[i] = i; 
    for (int i=4; i<MAXN; i+=2) fact[i] = 2; 
    for (int i=3; i*i<MAXN; i++) { 
        if (fact[i] == i) { 
            for (int j=i*i; j<MAXN; j+=i) 
                if (fact[j]==j) fact[j] = i; 
        } 
    } 
} 
  
set<int> query(int x) { 
    set<int> ans; 
    while(x != 1){ 
        ans.insert(fact[x]); 
        x /= fact[x]; 
    } 
    return ans; 
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    int n;
    cin>>n;
    int a[n];
    int gcdval = 0;
    map<int, int> cnt;
    bool pairwise = true;
    for(int i = 0;i<n;i++){
        cin>>a[i];
        if(i == 0) gcdval = a[i];
        else gcdval = gcd(gcdval, a[i]);
        for(auto it: query(a[i])){
            cnt[it]++;
            if(cnt[it] > 1){
                pairwise = false;
            }
        }
    }
    if(pairwise){
        cout<<"pairwise coprime"<<endl;
    } else {
        if(gcdval == 1){
            cout<<"setwise coprime"<<endl;
        } else {
            cout<<"not coprime"<<endl;
        }
    }
    
    return 0;
}





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

int f(int n){
    int res=0;
    while(n>0){
        res += n%10;
        n /= 10;
    }
    return res;
}

int main(void){
    int n;
    cin>>n;
    cout<<(n%f(n)==0?"Yes":"No")<<endl;
    return 0;
}


Measured memory_bytes: 256
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,child,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll mod=(ll)1e9+7;
//}}}

int X[100000];
int D[100000];
int main(){
  int N, M;
  cin >> N >> M;
  rep(i, M) cin >> X[i];
  sort(X, X + M);
  rep(i, M - 1) D[i] = X[i + 1] - X[i];
  sort(D, D + M - 1);
  ll ans = 0;
  rep(i, max(0, M - N)) ans += D[i];
  cout << ans << endl;
  return 0;
}


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

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define ld long double

const int INF = 2e9 + 1;
const ll INFLL = 1e18 + 1;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<ll> cnt(n + 1);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    ll ans = 0;
    for (auto &c : cnt) ans += c * (c - 1) / 2;
    for (auto &c : a) {
        ans -= cnt[c] * (cnt[c] - 1) / 2;
        cnt[c]--;
        ans += cnt[c] * (cnt[c] - 1) / 2;
        cout << ans << "\n";
        ans -= cnt[c] * (cnt[c] - 1) / 2;
        cnt[c]++;
        ans += cnt[c] * (cnt[c] - 1) / 2;
    }
    return 0;
}


Measured memory_bytes: 5576
#include <iostream>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;

ll pri(ll x) {
    ll mx = 1;
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) mx = i;
    }
    return mx;
}

int main() {
    ll n;
    cin >> n;
    ll a = pri(n);
    ll b = n / a;
    cout << a + b - 2;
}

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
        int n = sc.nextInt();
        int x = sc.nextInt();
            if(n == 0 && x == 0) break;
        int s = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i + 1; j <= n; j++) {
                for(int k = j + 1; k <= n; k++) {
                    if(i + j + k == x) s++;
                }
            }
        }
        System.out.println(s);
        }
    }
}


Measured memory_bytes: 26692
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> P;
#define int long long
#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
signed main(signed argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int MOD = 1000000007;
    string s;
    cin>>s;
    if(s[0]=='7'||s[1]=='7'||s[2]=='7')cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 3640
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long a[] = new long[N];
		boolean flag = true;
		for(int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
			if(a[i] % 2 == 1) flag = false;
		}
		
		
		if(flag) {
			System.out.println("second");
		} else {
			System.out.println("first");
		}
	}
}


Measured memory_bytes: 50096
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  int A; cin >> A;
  N %= 500;
  cout << (N <= A ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
char str[100005];

int main() {
  scanf("%s", str);
  int len = strlen(str);
  int s = -1, e = -1;
  for (int i = 0; i < len; ++i) {
    if (str[i] == str[i + 1]) {
      s = i + 1;
      e = s + 1;
    } else if (str[i] == str[i + 2]) {
      s = i + 1;
      e = s + 2;
    }
    if (s > 0) break;
  }
  printf("%d %d", s, e);
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<numeric>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int const MAXN = 3000;
int const MAXT = 3000;

int A[MAXN], B[MAXN], ix[MAXN];
int N, T;

int dp[MAXN-1][MAXT];

int main() {
  std::cin >> N >> T;
  for(int i = 0; i < N; ++i) std::cin >> A[i] >> B[i];
  std::iota(ix, ix+N, 0);
  std::sort(ix, ix+N, [&](int l, int r){ return A[l] < A[r]; });
  
  std::fill_n(dp[0], T, B[ix[0]]);
  std::fill_n(dp[0], A[ix[0]], 0);
  for(int i = 1; i < N-1; ++i) {
    // doesn't choose dish ix[i]
    std::copy_n(dp[i-1], T, dp[i]);
    // choose dish i;
    for(int j = A[ix[i]]; j < T; ++j) {
      dp[i][j] = std::max(dp[i][j], dp[i-1][j-A[ix[i]]] + B[ix[i]]);
    }
  }
  int ans = 0;
  for(int i = 0; i < N-1; ++i) {
    int cur = 0;
    for(int j = i+1; j < N; ++j) cur = std::max(cur, B[ix[j]]);
    ans = std::max(ans, cur + dp[i][T-1]);
  }
  fin(ans);
  return 0;
}


Measured memory_bytes: 35456
// https://atcoder.jp/contests/abc106/tasks/abc106_d
#include <bits/stdc++.h>
using namespace std;
using P = pair<double, int>;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

template <class T> struct CumulativeSum2D {
    vector<vector<T>> data;

    CumulativeSum2D(int W, int H) : data(W + 1, vector<T>(H + 1, 0)) {}

    void add(int x, int y, T z) {
        ++x, ++y;
        if (x >= data.size() || y >= data[0].size())
            return;
        data[x][y] += z;
    }

    void build() {
        FOR(i, 1, data.size()) FOR(j, 1, data[i].size()) {
            data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
        }
    }

    T query(int sx, int sy, int gx, int gy) {
        return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    CumulativeSum2D<int> sum(N + 1, N + 1);
    REP(i, M) {
        int l, r;
        cin >> l >> r;
        sum.add(l, r, 1);
    }
    sum.build();
    vector<int> ans;
    REP(i, Q) {
        int p, q;
        cin >> p >> q;
        int t = sum.query(p, p, q + 1, q + 1);
        ans.push_back(t);
    }
    for (auto &x : ans) {
        cout << x << "\n";
    }

    return 0;
}


Measured memory_bytes: 2428
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
ans = 0
for i in range(N):
    A = list(map(int, input().split()))
    t = 0
    for m in range(M):
        t += A[m]*B[m]
    if t + C > 0:
        ans += 1
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n,a[105],b[105],cnt; 
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i] >> b[i];
	for(int i = 1;i <= n;i++)
	{
		if(cnt >= 3) break;
		if(a[i] == b[i]) cnt++;
		if(a[i] != b[i]) cnt = 0;
	}
	if(cnt >= 3) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int N=5211,M=311111;
const double eps=1e-6;
inline bool zero(double x)
{
	return fabs(x)<eps;
}

pair <int,int> P[N][2];
pair <int,int> ip[N];
bool vis[N];

struct Road
{
	int u,v;
}r[M];
int Rind=-1;
int first[N],next[M];
inline void addEdge(int iu,int iv)
{
	Rind++; r[Rind].u=iu; r[Rind].v=iv;
	next[Rind]=first[iu]; first[iu]=Rind;
	Rind++; r[Rind].u=iv; r[Rind].v=iu;
	next[Rind]=first[iv]; first[iv]=Rind;
}

int deg[N];
int num[21];

inline void DFS(int cur,vector<pair<int,int> > &V)
{
	vis[cur]=true; V.push_back(make_pair(deg[cur],cur));
	for(int i=first[cur];i!=-1;i=next[i])
		if(!vis[r[i].v])
			DFS(r[i].v,V);
}	

inline void check(vector<pair<int,int> > &V)
{
	sort(V.begin(),V.end());
	/*
	for(int i=0;i<(int)V.size();i++)
		cout<<i<<' '<<V[i].first<<' '<<V[i].second<<'\n';
		*/
	int s=(int)V.size();
	if(s==2) num[1]++;
	else if(s==4)
		if(V[0].first==2)
			num[0]++;
		else num[7]++;
	else if(s==5)
		if(V[1].first==1)
			num[4]++;
		else num[9]++;
	else
	{
		if(V[4].first==3) 
			num[8]++;
		else if(V[2].first==1)
			num[3]++;
		else if(V[5].first==3)
			num[6]++;
		else
		{
			int p=V[0].second;
			int p1=r[first[p]].v;
			int p2=V[1].second;
			double t=(ip[p1].first-ip[p].first)*(ip[p2].second-ip[p].second)
					-(ip[p2].first-ip[p].first)*(ip[p1].second-ip[p].second);
			if(t<0) num[2]++;
			else num[5]++;
		}
	}
}		

inline double dis(pair<int,int> A,pair<int,int> B)
{
	return sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second));
}

int main()
{
	ios::sync_with_stdio(false);
	while(true)
	{
		int n; cin>>n;
		if(!n) break;
		for(int i=0;i<n;i++)
		{
			cin>>P[i][0].first>>P[i][0].second;
			cin>>P[i][1].first>>P[i][1].second;
		}
		map <pair<int,int>,int> M;
		//vector <pair<int,int> edge;
		int Mind=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<2;j++)
				if(M.find(P[i][j])==M.end())
				{
					ip[Mind]=P[i][j];
					M[P[i][j]]=Mind++;
				}
		memset(vis,0,sizeof(vis));
		memset(first,-1,sizeof(first));
		memset(next,-1,sizeof(next));
		memset(deg,0,sizeof(deg));
		Rind=-1;
		for(int i=0;i<n;i++)
			for(int j=0;j<2;j++)
				for(int t=0;t<n;t++)
					if((!vis[t])&&P[i][j]!=P[t][0]&&P[i][j]!=P[t][1]&&zero(dis(P[i][j],P[t][0])+dis(P[i][j],P[t][1])-dis(P[t][0],P[t][1])))
					{
						//cout<<i<<' '<<j<<' '<<t<<'\n';
						vis[t]=true;
						addEdge(M[P[i][j]],M[P[t][0]]);
						addEdge(M[P[i][j]],M[P[t][1]]);
						deg[M[P[i][j]]]+=2;
						deg[M[P[t][0]]]++;
						deg[M[P[t][1]]]++;
					}
					
		for(int i=0;i<n;i++)
			if(!vis[i])
			{
				//cout<<i<<'\n';
				addEdge(M[P[i][0]],M[P[i][1]]);
				deg[M[P[i][0]]]++;
				deg[M[P[i][1]]]++;
			}
			
			/*
		for(int i=0;i<Mind;i++)
			cout<<i<<' '<<ip[i].first<<' '<<ip[i].second<<' '<<deg[i]<<'\n';
		*/
		memset(num,0,sizeof(num));
		memset(vis,0,sizeof(vis));
		for(int i=0;i<Mind;i++)
			if(!vis[i])
			{
				vector <pair<int,int> > V;
				V.clear();
				DFS(i,V);
				check(V);
			}
		for(int i=0;i<9;i++)
			cout<<num[i]<<' ';
		cout<<num[9]<<'\n';
	}
	return 0;
}

Measured memory_bytes: 2684
#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 = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
random_device rnd;
mt19937 mt(rnd());

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;

bool ok;

void dfs(int cur, int c, VI &cols, map<int, vector<int>> &g)
{
    if (cols[cur] != -1 && cols[cur] != c)
    {
        ok = false;
        return;
    }
    if (cols[cur] == c)
    {
        return;
    }
    cols[cur] = c;
    for (auto &&x : g[cur])
    {
        dfs(x, 1 - c, cols, g);
        if (ok == false)
            return;
    }
}

void solve(int n, int m)
{
    ok = true;
    map<int, vector<int>> g;
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    VI cols(n, -1);
    dfs(0, 0, cols, g);
    if (ok == false)
    {
        cout << 0 << endl;
        return;
    }
    int num = 0;
    rep(i, n) num += cols[i];
    if (num > n - num)
    {
        num = n - num;
    }
    VI ans;
    if (num % 2 == 0)
    {
        ans.push_back(num / 2);
    }
    num = n - num;
    if (num % 2 == 0)
    {
        ans.push_back(num / 2);
    }
    if (ans.size() == 2 && ans[0] == ans[1])
        ans.pop_back();
    cout << ans.size() << endl;
    for (auto &&x : ans)
    {
        cout << x << endl;
    }
}

int main()
{
    int n, m;
    while (cin >> n >> m, n)
    {
        solve(n, m);
    }
    return 0;
}


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

namespace ABC_Training
{

    class Program
    {
        static void Main(string[] args)
        {
            var Weather = Console.ReadLine();
            Console.WriteLine(WeatherPrediction.GetNextWeather(Weather));
        }
    }
    public static class WeatherPrediction
    {
        public static string GetNextWeather(string s)
        {
            if (s[0] == 'S')
            {
                return "Cloudy";
            }
            if (s[0] == 'C')
            {
                return "Rainy";
            }
            return "Sunny";
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using tii = tuple<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

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

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}
};
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	vl f(100001); f[1]=1;
	//range(i, 2, f.size()) {
	//	f[i] = f[i - 1] * i;
	//	f[i] %= MOD;
	//}
	int n;
	cin >> n;
	vi a(n), b(n);
	rep(i, n) cin >> a[i] ;
	rep(i, n) cin >> b[i];
	sort(all(a));sort(all(b));
	a.push_back(INF);	b.push_back(INF);
	vi v;
	ll ans = 1;
	//cout << a << endl;
	//cout << b << endl;
	int j = 0, k = 0;
	rep(i, 2 * n) {
		if (a[j] < b[k]) {
			v.push_back(j);
			j++;
		}
		else {
			v.push_back(k);
			k++;
		}
	}
	int mx = 0;
	rep(i, v.size()) {
		mx = max(v[i], mx);
		ans *= max(mx - v[i], 0)+1;
		ans %= MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3312
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000
#define EMAX 500000
#define INFTY 2000000000
typedef struct {
  int pre,next,x;
}Cost;
int n,d[MAX];
Cost E[EMAX];
void jr(int);

void jr(int cou){
  int i,tmp;
  
  for(i=0;i<n;i++){
    d[i]=INFTY;
  }
  d[0]=0;

  tmp=1;
  
  while(tmp!=0){
    tmp = 0;
    for(i = 0;i < cou; i++){
      if(E[i].x + d[E[i].pre] < d[E[i].next]){
	d[E[i].next] = E[i].x + d[E[i].pre];
	tmp = 1;
      }
    }
  }
}

int main()
{
  int i,j,u,k,cou=0;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      E[cou].pre = u;
      scanf("%d%d", &E[cou].next, &E[cou].x);
      cou++;
    }
  }

  jr(cou);

  for(i=0;i<n;i++){
    printf("%d %d\n",i,d[i]);
  }

  return 0;
}

Measured memory_bytes: 8428
m, d = map(int, input().split())
if d < 22:
  print(0)
  exit()
cnt = 0
for i in range(1, m + 1):
  for j in range(22, d + 1):
    ten = int(str(j)[0])
    one = int(str(j)[1])
    if ten >= 2 and one >= 2 and ten * one == i:
      cnt += 1
print(cnt)

Measured memory_bytes: 9072
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: u64,
        k: u64,
    }
    let mut ans = 0;
    let z = n / k;
    let h = (n + k / 2) / k;
    let ans = z * z * z + if k % 2 == 0 { h * h * h } else { 0 };
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<cstdio>
int main(){
    int n;
    char s[101];
    scanf("%d%s",&n,s);
    int x=0,ans=0;
    for(int i=0;i<n;i++){
        if(s[i]=='I'){
            x++;
            if(x>ans)ans=x;
        }else x--;
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 128
N, Y, Z = map(int, input().split())
As = list(map(int, input().split()))
dpx, dpy = [0]*(N-1), [0]*(N-1)
#dpx[i] = min(dpy[i+1]...dpy[N-2], abs(As[N-1]-As[i]))
#dpy[i] = max(dpx[i+1]...dpx[N-2], abs(As[N-1]-As[i]))
for i in range(N-2, -1, -1):
    mny, mxx = 10**10, 0
    for j in range(i+1, N-1):
        mny = min(mny, dpy[j])
        mxx = max(mxx, dpx[j])
    dpx[i] = min(mny, abs(As[N-1]-As[i]))
    dpy[i] = min(mxx, abs(As[N-1]-As[i]))
dpx.append(abs(As[N-1]-Z))
print(max(dpx))


Measured memory_bytes: 42860
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cassert>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;

class Cake{
private:
  int x,y;
public:
  Cake(){};
  Cake(int xx,int yy){
    x=xx;
    y=yy;
  }
  int size(){
    return x*y;
  }
  pair<Cake,Cake> cut(int n){
    pair<Cake,Cake> res;
    Cake tmp[2];
    if((n%(x+y))<x){
      int len = (n%(x+y));
      tmp[0]=Cake(len,y);
      tmp[1]=Cake(x-len,y);
    }else{
      int len = (n%(x+y))-x;
      tmp[0]=Cake(x,y-len);
      tmp[1]=Cake(x,len);
    }
    if(tmp[0].size()>tmp[1].size()){
      res.first=tmp[1];
      res.second=tmp[0];
    }else{
      res.first=tmp[0];
      res.second=tmp[1];
    }
    return res;
  }
};

bool operator<(Cake a,Cake b){
  return a.size()<b.size();
}


int n;
Cake C;
bool init(){
  n=0;
  C=Cake();
}

bool input(){
  int w,h;
  cin>>n>>w>>h;
  if(n==0&&w==0&&h==0)return false;
  C=Cake(w,h);
}

vector<Cake> solve(){
  vector<Cake> res;
  res.push_back(C);
  for(int i=0;i<n;i++){
    int p,s;
    cin>>p>>s;
    p--;
    vector<Cake> tmp;
    pair<Cake,Cake> cut_cake;
    for(int j=0;j<res.size();j++){
      if(j==p){
        cut_cake=res[j].cut(s);
      }else{
        tmp.push_back(res[j]);
      }
    }
    tmp.push_back(cut_cake.first);
    tmp.push_back(cut_cake.second);
    res.clear();
    res=tmp;
    tmp.clear();
  }
  return res;
}

int main(){
  while(init(),input()){
    vector<Cake> ans=solve();
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
      cout<<ans[i].size();
      if(i!=ans.size()-1){
        cout<<" ";
      }else{
        cout<<endl;
      }
    }
  }
}

Measured memory_bytes: 1200
///spaesk

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define pi acos(-1)
#define int long long int
#define ld long double
#define ar array
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

typedef vector<vector<int> > matrix ;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const int ths = 1LL << 40;
const int NN = 5e3 + 6;

const int maxN = 107;

///
///

void solve()
{

    int a, b, c, k;
    cin>>a>>b>>c>>k;
    while(b <= a and k)
        b *= 2, k --;
    while(c <= b and k)
        c *= 2, k --;

    if(a < b and b < c)
        cout<<"Yes";
    else
        cout<<"No";

    cout<<"\n";
    return ;
}

/*
*/

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

    int t = 1;
    //cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3648
#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
/*
// ????????????????§?????§£?????¨
typedef string::const_iterator State;
class ParseError {};
*/

struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int N;
vi depth;
int maxdepth = 0;
Graph G;
vvi dblpar;

void dfs1(int pos, int d = 0) {
	depth[pos] = d;
	maxdepth = max(maxdepth, d);
	for (auto ch : G[pos]) {
		dfs1(ch.to, d + 1);
	}
}

void dfs2(int pos, int par, int dbl) {
	if (dbl == 0) {
		dblpar[0][pos] = par;
	}
	else {
		dblpar[dbl][pos] = dblpar[dbl - 1][dblpar[dbl - 1][pos]];
	}
	for (auto ch : G[pos]) {
		dfs2(ch.to, pos, dbl);
	}
}

int parent(int pos, int step) {
	int ret = pos;
	int dbl = 0;
	while (step > 0) {
		if ((step & 1) != 0) {
			ret = dblpar[dbl][ret];
		}
		step >>= 1;
		dbl++;
	}
	return ret;
}

int bindigit(int n) {
	int ret = 0;
	while (n > 0) {
		ret++;
		n >>= 1;
	}
	return ret;
}

int main(void) {
	int N;
	cin >> N;
	depth = vi(N);
	G = Graph(N);
	rep(i, N) {
		int num;
		cin >> num;
		rep(j, num) {
			int ch;
			cin >> ch;
			G[i].push_back(Edge{ i,ch,1 });
		}
	}

	dfs1(0);
	int D = bindigit(maxdepth) + 1;
	dblpar = vvi(D, vi(N));
	rep(i, D) {
		dfs2(0, 0, i);
	}
	/*
	rep(i, N) {
		cout << depth[i] << ":";
		rep(j, D) {
			cout << dblpar[j][i] << " ";
		}
		cout << endl;
	}
	*/

	int Q;
	cin >> Q;
	rep(q, Q) {
		int u, v;
		cin >> u >> v;
		if (depth[u] < depth[v]) {
			swap(u, v);
		}
		u = parent(u, depth[u] - depth[v]);
		// u,v???????????±???
		/*
		if (u == v) {
			cout << u << endl;
			continue;
		}
		*/
		int ng = -1, ok = depth[u];
		while (ok - ng > 1) {
			int mid = (ok + ng) / 2;
			if (parent(u, mid) == parent(v, mid)) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		cout << parent(u, ok) << endl;
	}

	return 0;
}

Measured memory_bytes: 20152
#include<iostream>
#include<cmath>
#include<cstdio>

using namespace std;


int main(){
  int x;
  int h,m,s;
  cin >> x;
  h = x/3600;
  x -= 3600*h;
  m = x/60;
  s = x - m*60;
  printf("%d:%d:%d\n",h,m,s);
  return 0;
}


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

typedef long long ll;

using tpl = tuple<int, int, int>;
typedef pair<int,int> pii;

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}


class UnionFindTree{
private:
  // indexの数の親ノード(ある集合の親を見つけたいときはここを直接参照せず、findを使う)
  vector<int> par;
  // indexを根とする木のランク
  vector<int> rank;
  // 集合のサイズ
  vector<int> cnts;
  // 集合の黒の数
  vector<int> bks;
  // 木の最大値
  int treeSize;
public:
  UnionFindTree(int initTreeSize = 1000){
    // 引数で与えられた値を最大格納数とするUnionFindTreeの作成
    treeSize = initTreeSize;
    // init(initTreeSize);
  }
   void init(int sz, vector<int > &v){
    par.clear(),rank.clear(),cnts.clear();bks.clear();
    treeSize=sz;
    for(int i = 0; i < sz; i++){
      par.push_back(i);
      rank.push_back(0);
      cnts.push_back(1);
      bks.push_back(v[i]);
    }
  }
  // 与えられた数が格納されている木のルートを探索
  int find(int x){  
    if(par[x] == x)return x;
    else return par[x] = find(par[x]);
  }
  // 和集合をとる。ただしここでは各集合の親の付け替えは起こらない
  void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      par[x] = y;
      cnts[y]+=cnts[x];
      bks[y] += bks[x];
    }
    else{
      par[y] = x;
      cnts[x]+=cnts[y];
      bks[x] += bks[y];
      if(rank[y] == rank[x])rank[x]++;
    }
  }
  // xの属する集合のサイズ
  int getCnt(int x){
    return cnts[find(x)];
  }
  // xの属する集合の黒の数
  int getBks(int x){
      return bks[find(x)];
  }

  bool same(int x,int y){
    return find(x) == find(y);
  }
    
};


int H, W;
char field[410][410];
UnionFindTree uft(1);

int main(){

    cin >> H >> W;
    vector<int> v;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> field[i][j];
            v.push_back(field[i][j] == '#');
        }
    }
    uft.init(H*W, v);
    
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            for(int k = 0; k < 4; k++){
                const int dy[]= {-1,0,0,1};
                const int dx[]= {0,-1,1,0};
                int ni = dy[k] + i;
                int nj = dx[k] + j;
                if(ni >= 0 && nj >= 0 && ni < H && nj < W){
                    int from = i * W + j;
                    int to = ni * W + nj;
                    if((v[from] == 1) ^ (v[to] == 1)) {
                        uft.unite(from, to);
                    }
                }
            }
        }
    }
    set<int> st;
    for(int i = 0; i < H * W; i++){
        st.insert(uft.find(i));
    }
    ll ans = 0;
    for(int pos : st){
        ll tot = uft.getCnt(pos);
        ll bk = uft.getBks(pos);
        ll wh = tot - bk;
        ans += wh * bk;
    }
    cout << ans << endl;

}


Measured memory_bytes: 10228
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if((10*b+c)%4==0){
      cout << "YES";
    }else{
      cout << "NO";
    }
    return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
p = list(map(int,input().split()))

pp = list(map(lambda x:(x+1)/2,p))

p_rui = [pp[0]]
for i in range(1,n):
    p_rui.append(p_rui[i-1]+pp[i])



walist=[p_rui[k-1]]
for i in range(0,n-k):
    walist += [p_rui[k+i]-p_rui[i]]

print(max(walist))




Measured memory_bytes: 38740
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

char s[100010];
int ans;
int main(){
	scanf("%s",s);
	int n=strlen(s);
	
	char crr=s[0];
	int cnt=1;
	rep(i,1,n){
		if(s[i]==crr)cnt++;
		else if(cnt){
			cnt--;
			ans+=2;
		}else{
			crr=s[i];
			cnt=1;
		}
	}
	printf("%d",ans);
}

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

int main()
{
  string S;cin>>S;
  int count1,count2,i;long long ans=0;
  for(i=0;i<(int)S.size();)
  {
    count1=0,count2=0;
    while(S[i]=='<'){i++;count1++;}
    while(S[i]=='>'){i++;count2++;}
    for(int j=max(count1,count2);j>-1;j--)ans+=j;
    for(int j=min(count1,count2)-1;j>-1;j--)ans+=j;
  }
  printf("%lld",ans);
}

Measured memory_bytes: 4276
#include <iostream>
#include <algorithm>
#include <cassert>
#include <vector>
#include <sstream>
#include <cmath>
#include <stdio.h>

using namespace std;

//-------------------------------------------------------------------------
// geometric library
//-------------------------------------------------------------------------
// geometric library

namespace geometry {

#define EPS 1E-10 ///< 0とみなすサイズ。適当

	struct point {
		double x;
		double y;

		point& operator += (const point& rhs) { x += rhs.x; y += rhs.y; return *this; }
		point& operator -= (const point& rhs) { x -= rhs.x; y -= rhs.y; return *this; }
		point& operator /= (double factor) { x /= factor; y /= factor; return *this; }
		point& operator *= (double factor) { x *= factor; y *= factor; return *this; }
		bool operator == (const point& rhs) const { return (std::abs(x - rhs.x) < EPS) && (std::abs(y - rhs.y) < EPS); }
		bool operator != (const point& rhs) const { return !(*this == rhs); }
		bool operator <= (const point& rhs) const { return x < rhs.x || (x == rhs.x && y <= rhs.y); }
		bool operator >= (const point& rhs) const { return x > rhs.x || (x == rhs.x && y >= rhs.y); }
		bool operator < (const point& rhs) const { return !(*this >= rhs); }
		bool operator > (const point& rhs) const { return !(*this <= rhs); }
		double arg() const { return atan2(y, x); }
		double norm() const { return sqrt(x * x + y * y); }
	};

	typedef point vec;

	struct circle {
		point center;
		double radius;
	};

	struct line {
		// ax + by + c = 0
		double a;
		double b;
		double c;
	};

	enum rotate_dir {
		rotate_None = 0,
		rotate_CW = 1,
		rotate_CCW = -1
	};

	point operator + (const point& p1, const point& p2)
	{
		point p(p1);
		p += p2;
		return p;
	}

	point operator / (const point& p1, double factor)
	{
		point p(p1);
		p /= factor;
		return p;
	}

	point operator * (const point& p1, double factor)
	{
		point p(p1);
		p *= factor;
		return p;
	}

	point operator * (double factor, const point& p1)
	{
		point p(p1);
		p *= factor;
		return p;
	}

	point operator - (const point& p1, const point& p2)
	{
		point p(p1);
		p -= p2;
		return p;
	}

	std::istream& operator >> (std::istream& is, point& p)
	{
		is >> p.x >> p.y;
		return is;
	}

	double inner_product(const point& p1, const point& p2)
	{
		return p1.x * p2.x + p1.y * p2.y;
	}

} // namespace geometry


//-------------------------------------------------------------------------
// solution

using namespace geometry;

// 直線p1-p2についてpqと対称な点を求める
point get_symmetric_point(const point& p1, const point& p2, const point& pq) {
	vec unit_vec = (p2 - p1) / (p2 - p1).norm();

	// pm: pqからp1-p2に下ろした垂線とp1-p2の交点
	point pm = p1 + (inner_product(pq - p1, p2 - p1) / (p2 - p1).norm()) * unit_vec;

	return pm + (pm - pq);
}

int main(void) {
	point p1, p2, pq;
	string line;

	while (getline(cin, line)) {
		replace(line.begin(), line.end(), ',', ' ');
		istringstream ss(line);
		ss >> p1 >> p2 >> pq;

		point pr = get_symmetric_point(p1, p2, pq);

		printf("%f %f\n", pr.x, pr.y);
	}
	return 0;
}

Measured memory_bytes: 1276
def solve():
    S = input()
    K = int(input())

    N = len(S)

    st = set()

    for left in range(N):
        for right in range(left+1,N+1):
            if right - left > K:
                break
            st.add(S[left:right])
    
    tmp = list(st)
    tmp.sort()
    print(tmp[K-1])

if __name__ == '__main__':
    solve()

Measured memory_bytes: 40304
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;


int main() {
  int n;
  cin >> n;
  vector<int> x(n), y(n);  
  rep(i, n) cin >> x[i] >> y[i];

  auto dist = [&](int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return sqrt(dx*dx + dy*dy);
  };

  int cnt = 0;//順列の数を数える（next_permutation()がtrueで有る限りインクリメント(要素数1の順列は1つなのでdo {++cnt} while()を使用)）
  double len = 0;// 経路の長さ全ての総和
  vector<int> p(n);//next_permutationで順列の数を調べるため。
  rep(i, n) p[i] = i;//配列pに昇順で要素を格納しておく。配列要素の順番がそのまま点から点の経路を表す。

  do {
    rep(i, n-1) {
      len += dist(p[i], p[i+1]);
    }
    cnt++;
  } while (next_permutation(p.begin(), p.end()));
  double ans = len/cnt;
  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
typedef long long ll;
#define vint vector<int>
#define vstring vector<string>
#define vll vector<ll>
#define vbool vector<bool>
#define INF 100000000

int main(){
  int n,k;
  cin >> n >> k;
  vint x(n);
  rep(i,n) cin >> x[i];
  int ans = 1000000000;
  rep(i,n-k+1){
    if(abs(x[i]) < abs(x[i+k-1])){
      ans = min(ans,x[i+k-1]-x[i]+abs(x[i]));
    }
    else{
      ans = min(ans,x[i+k-1]-x[i]+abs(x[i+k-1]));
    }
  }
  cout << ans << endl;
}



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

int n, k;

int main(void){
    cin >> n >> k;
    vector<int> x(n);
    for(int i = 0; i < n; i++) cin >> x[i];
    int res = 0;
    for(int i = 0; i < n; i++){
        res+=min(abs(x[i]), abs(k-x[i]));
    }
    res*=2;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> p(N);
    for(int i=0; i<N; i++){
        cin >> p[i];
    }

    int cnt=0;
    for(int i=1; i<N-1; i++){
        if(p[i-1]<p[i] && p[i]<p[i+1]){
            cnt++;
        }else if(p[i-1]>p[i] && p[i]>p[i+1]){
            cnt++;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int n;
	cin >> n;
	int g = n % 10;
	if (g == 2 || g == 4 || g == 5 || g == 7 || g == 9) {
		cout << "hon";
		return 0;
	}
	else if (g == 0 || g == 1 || g == 6 || g == 8) {
		cout << "pon";
		return 0;
	}
	else {
		cout << "bon";
	}
}

Measured memory_bytes: 3624
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

//for
#define REP(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define REPS(i,n) for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREPS(i,n) for(int i=(int)(n);i>0;i--)
#define SREP(i,s,n) for(int i=(int)(s),i##_len=(int)(n);i<i##_len;i++)

//printf
#define PRINTD(d) printf("%d\n",(d))
#define PRINTF(d) printf("%lld\n",(d))

//memset
#define m0(s) memset(s,0,sizeof(s))
#define ml(s) memset(s,63,sizeof(s))
#define fill(s,c) memset(s,c,sizeof(s))

#define INF 1e9
#define NMAX 1e9

typedef long long ll;
int diff[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 },
};

int Min(int a, int b) {
	return (a)<(b) ? (a) : (b);
}
int Max(int a, int b) {
	return (a) > (b) ? (a) : (b);
}
void Swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
ll Sqrt(ll n) {
	ll s = n;
	ll x = s / 2;
	while (x > NMAX) {
		x /= 2;
	}
	while(1) {
		x = (x + s / x) / 2;
		if (x*x <= s)break;
	}
	return x;
}

int main() {
	int a, b, x;
	scanf("%d %d %d", &a, &b, &x);
	if (x >= a&&x <= a + b) {
		puts("YES");
	}
	else {
		puts("NO");
	}

}

Measured memory_bytes: 128
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n = I()
    a = LI()
    for i in range(n-1):
        a[i+1] += a[i]
    a.insert(0,0)
    ans = float("inf")
    for m in range(3,n):
        lu = a[m-1]
        ru = a[n]-a[m-1]
        lm = bisect.bisect_left(a,lu//2)
        rm = bisect.bisect_left(a,ru//2+a[m-1])
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        lm -= 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        rm -= 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
        lm += 1
        k = [a[lm],a[m-1]-a[lm],a[rm]-a[m-1],a[n]-a[rm]]
        if min(k):
            ans = min(ans,max(k)-min(k))
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


Measured memory_bytes: 82692
#include <iostream>

int main() {
  std::string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  int n; 
  std::string s; 
  std::cin >> n >> s;
  char r[s.size()];
  if(n == 0) {
    std::cout << s; 
    return 0;
  }
  for(size_t i = 0; i < s.size(); ++i) 
    for(size_t j = 0; j < 26; ++j)
        if(s[i] == alphabet[j]) {
          if( j+n < 26) r[i] = alphabet[j+n];
          else r[i] = alphabet[j+n-26]; 
          break;
        }
  for(auto it: r) {
    std::cout << it;
  }
  return 0;
}

Measured memory_bytes: 256
/*

*/
#include<iostream>
#include<iomanip>
#include<ios>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)
#define MAX_N 10000

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll MOD = ll(1e9+7);

int main(){
  ll n, a, b;cin>>n>>a>>b;
  a-=b;
  vector<ll> h(n);
  rep(i, n)cin>>h[i];
  ll l=0LL, r=ll(1e9)+1LL;
  while(l+1LL!=r){
    ll m=(l+r)/2;
    ll cnt=0LL;
    rep(i, n){
      ll rest=h[i]-b*m;
      if(rest>0LL){
        cnt+=(rest+a-1LL)/a;
      }
    }
    if(cnt<=m){
      // printf("[%lld, %lld) (mid=%lld): ok\n", l, r, m);
      r=m;
    }else{
      // printf("[%lld, %lld) (mid=%lld): not ok\n", l, r, m);
      l=m;
    }
  }
  cout<<r<<endl;
  // system("read -n 1 -s -p \"Press any key to continue...\"");
}


Measured memory_bytes: 1152
/*COMPETITIVE PROGRAMMING C++ TEMPLATE */

#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <stack>
#include <queue>
#include <climits>
#include <iomanip>

#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << "\n"
#define MOD 998244353

const long double PI = 3.141592653589793236L;

typedef long long int ll;
typedef long double ld;

using namespace std;

const int maxN = 2e5;
vector<int> adj[maxN + 1];
vector<bool> vis(maxN + 1, false);
set<pair<int, int>> S;

int dfs(int v)
{
    vis[v] = true;
    int count = 1;

    for(int x : adj[v])
    {
        if(!vis[x])
        {
            count += dfs(x);
        }
    }

    return count;
}

void solve()
{
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;

        if(S.find({u, v}) == S.end())
        {
            adj[v].push_back(u);
            adj[u].push_back(v);
            S.insert({u, v});
            S.insert({v, u});
        }
    }

    int max_component = 1;

    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            max_component = max(max_component, dfs(i));
        }
    }

    cout << max_component << "\n";

}

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

    int T = 1;
    //cin >> T;

    while (T--)
    {
        solve();
    }

    return 0;
}





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

int main(){
	int i,n,x = 1;
	cin >> n;
	int a[n],c[n];
	for(i=0;i<n;i++){
		cin >> a[i];
		if(a[i]%2==0){
			c[i] = 2;
		}else{
			c[i]=1;
		}
	x = x*c[i];
	}
	cout << pow(3,n)-x << endl;
}

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

void Main()
{
	int N; cin >> N;
	vector<int> H(N);
	rep(i,N) cin >> H[i];
	int res = 0;
	rep(i,N) {
		rep(j,i) {
			if (H[j] > H[i]) {
				--res;
				break;
			}
		}
		++res;
	}
	cout << res << endl;
}

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


Measured memory_bytes: 256
from collections import deque

def bfs(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    while que:
        cost, cur_node = que.popleft()
        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist

N,M = map(int, input().split())
AB = []
for i in range(M):
    AB.append(tuple(map(int, input().split())))
    
#N,M = 4,3
#AB = [(1,2),(2,3),(3,4)]

adj_list = [[] for _ in range(N)]
for a,b in AB:
    a -= 1
    b -= 1
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    
dist = bfs(adj_list, N, 0)

if dist[N-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 95932
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const Arr = (input.trim()).split("\n");
const N1 = Number(Arr[0]);
const arr1 = Arr[1].split(" ").map(Number);
const arr2 = Arr[3].split(" ").map(Number);

const binarySearch = (function(arr, N) {
  return (key) => {   
    let mid;
    let left = 0;
    let right = N;
    if (key < arr[0] || arr[N-1] < key) return 0;
    while (left < right) {
      mid = Math.floor((left + right) / 2);
      if (key < arr[mid]) right = mid;
      else if (key > arr[mid]) left = mid + 1;
      else return 1;
    }
    return 0;
  }
})(arr1, N1);

const summing = (a, b) => a + b;
console.log(arr2.map(binarySearch).reduce(summing, 0));



Measured memory_bytes: 34968
#include <bits/stdc++.h> 
using namespace std; 
typedef   long long int ll;
int main() 
{   
     ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    ll a[3];cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    if ((a[0]==a[1]&&a[1]!=a[2])||(a[0]!=a[1]&&a[1]==a[2])) {
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
   
   }


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = 1e9+7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

vector<VI> r;

ll bfs(int sy, int gl) {
	const int inf = 1<<28;
	vector<VI> dd(sz(r),VI(3, inf));
	queue< pii > que;
	que.push(pii(sy,0)); dd[sy][0]=0;
	while(!que.empty()){
		int cy, cz; tie(cy, cz) = que.front();
		que.pop();
		for(auto x: r[cy]){
			int nz = (dd[cy][cz]+1)%3;
			if(dd[x][nz] == inf){
				que.push(pii(x, nz));
				dd[x][nz] = dd[cy][cz] + 1;
			}
		}
	}
	//for(auto xl: dd){for(auto x :xl) printf("%d, ",x); puts("");}
	return dd[gl][0] == inf? -1: dd[gl][0]/3;
}
int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, m, s, t;
	cin >>n >>m;
	
	r.resize(n);
	rep(i, m){
		int u,v;
		cin >>u >>v;
		r[u-1].push_back(v-1);
	}
	cin >>s >>t;
	s--,t--;

	cout << bfs(s, t) <<"\n";
	
	return 0;
}


Measured memory_bytes: 11264