akhauriyash/Code-Regression huggingface dataset:
import math
n = int(input())

ans_sum = []
for i in range(1, round(math.sqrt(n) + 2)):
    if n%i == 0:
        ans = set([])
        if i <10 and n//i <10:
            ans.add(i)
            ans.add(n//i)
            ans_sum.append(ans)
            
if len(ans_sum) > 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38524
/*I MAY NOT GET THE SUCCESS IMMEDIATELY BUT I WILL GET IT FOR SURE*/
#include<bits/stdc++.h>
#define opt std::ios_base::sync_with_stdio(false)
#define I int
#define li      int32_t
#define lli     long long
#define ulli unsigned long long

#define pn          printf("\n")
#define nl          cout<<'\n'
#define sf(N)       scanf("%lld",&N)
#define pf(N)       printf("%lld",N)
#define sl          cout<<' '
#define ps          printf(" ")

#define rep(i,a,b)  for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>b;i--)
#define elif        else if
#define mset(a,b)   memset(a,b,sizeof(a))

#define pb      push_back
#define pob     pop_back
#define itr     iterator
#define sz()    size()
#define szof    sizeof
#define lb      lower_bound
#define ub      upper_bound
#define mp      make_pair
#define vlli    vector<lli>
#define plli    pair<lli,lli>
#define vplli   vector<plli >
#define F       first
#define S       second
#define ALL(V)  V.begin(),V.end()
#define Dup erase(unique(V.begin(),V.end()),V.end())

#define Inf     1000000000000000
#define mod     1000000007
using namespace std;

lli Power(lli a,lli b)
{
    lli result=1;

    while(b)
    {
        if(b%2)
        {
            result=(result*a)%mod;
        }

        b=b>>1;
        a=(a*a)%mod;
    }

 return result;
}

int main()
{
    /*#ifndef ONLINE_JUDGE
    freopen("double_squares.txt","r",stdin);
    freopen("double_squares_out.txt","w",stdout);
    #endif // ONLINE_JUDGE*/
    
    lli N,i;
    cin>>N;
    
    vlli V(N);
    lli Sum=0;
    
    rep(i,0,N)
    {
        cin>>V[i];
        Sum+=V[i];
    }
    
    lli x=Sum/N;
    lli y=x+1;
    
    lli Min1=0,Min2=0;
    
    rep(i,0,N)
    {
        Min1+=(V[i]-x)*(V[i]-x);
    }
    
    rep(i,0,N)
    {
        Min2+=(V[i]-y)*(V[i]-y);
    }
    
    cout<<min(Min1,Min2);
    
    
    
    
    
    
    


 return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

int prim(){
  int u,minv,v,sum=0;
  int i,d[MAX],p[MAX],color[MAX];
  for(i=0;i<n;i++){
    d[i]=10000;
    p[i]=-1;
    color[i]=WHITE;
  }
  d[0]=0;
  while(1){
    minv=10000;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && color[i]!=BLACK){
	u=i;
	minv=d[i];
      }
    }
    if(u==-1) break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK && M[u][v]!=10000){
	if(d[v]>M[u][v]){
	  d[v]=M[u][v];
	  p[v]=u;
	  color[v]=GRAY;
	}
      }
    }
  }
  sum=0;
  for(i=0;i<n;i++){
    if(p[i]!=-1) sum+=M[i][p[i]];
  }
  return sum;
}

int main()
{
  int i,j,e;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      M[i][j]=(e==-1)? 10000:e;
    }
  }
  printf("%d\n",prim());
  return 0;
}
  

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

int main()
{
    long long n, x;
    long long a = 0, b = 0;
    cin>>n;
    vector<long long>v;
    map<long long, int>mp;
    for(int i=0; i<n; i++)
    {
        cin>>x;
        v.push_back(x);
        mp[x]++;
    }
    x = -1;
    sort(v.rbegin(), v.rend());
    for(int i=0; i<n; i++)
    {
        if(x<0)
        {
            if(mp[v[i]]>=4)
            {
                x = 1;
                a = v[i];
                b = a;
                break;
            }
            else if(mp[v[i]]>=2)
            {
                x = 1;
                a = v[i];
            }
        }
        else
        {
            if(mp[v[i]]>=4)
            {
                b = v[i];
                break;
            }
            else if(a!=v[i]&&mp[v[i]]>=2)
            {
                b = v[i];
                break;
            }
        }
    }
    printf("%lld", a*b);
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/15  Problem: 054_abc_d / Link: https://abc054.contest.atcoder.jp/tasks/abc054_d?lang=en  ----- */
/* ------問題------

イルカは、微量の物質Cを生成したいと考えています。
物質Cを生成するためには、タイプAの物質とタイプBの物質の混合比が Ma:Mb となる溶液を用意する必要があります。
しかし、イルカは薬品を1つも持っていないため、薬局へ薬品を買いに行くことにしました。
薬局では、N 種類の薬品を取り扱っており、各薬品 i の在庫はちょうど1つです。
各薬品 i は、タイプAの物質 ai グラム、タイプBの物質 bi グラム含んでおり、価格 ci 円で売られています。 
イルカは、いくつかの薬品を薬局で買います。買った薬品は全て使わなければなりません。
物質Cを生成するために、必要な最小予算を求めてください。 
薬局で売られている薬品の組み合わせで、物質Cを生成できない場合はそれを報告してください。

-----問題ここまで----- */
/* -----解説等-----

半分全列挙かなと思ったけどマージ検索がわからなかったのでDPでできる。
更新順番は後ろからやると良くて、dp[aの重さ][bの重さ]:=コスト最小
として最後にindexを検索すれば良い。

半分全列挙はできて、map上で検索すれば良い。

----解説ここまで---- */

LL N,A,B;

LL ans = 0LL;

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

	cin >> N>>A>>B;
	VI a(N), b(N), c(N);
	FOR(i, 0, N) {
		cin >> a[i] >> b[i] >> c[i];
	}

	VVI dp(401, VI(401, INF));

	dp[0][0] = 0;
	FOR(i, 0, N) {
		FORR(aa, 400, 0-1) {
			FORR(bb, 400, 0-1) {
				if(aa+a[i]<=400&&bb+b[i]<=400)dp[aa+a[i]][bb+b[i]] = min(dp[aa+a[i]][bb+b[i]], dp[aa][bb] + c[i]);
			}
		}
	}
	ans = INF;
	FOR(i, 1, 401) {
		if (A*i<=400 && B*i<=400) {
			ans = min(ans, (long long )dp[A*i][B*i]);
		}
	}
	if (ans == INF)ans = -1;
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 896
n, m = map(int, input().split())
a = set([int(input()) for i in range(m)])

r = [0]*(n+1)
r[0] = 1
if 1 in a:
  r[1] = 0
else:
  r[1] = 1
for i in range(2, n+1):
  if i in a:
    continue
  r[i] = (r[i-1] + r[i-2])%1000000007

print(r[n])

Measured memory_bytes: 13192
#include <atcoder/maxflow.hpp>
#include <iostream>

#define rep(i, n) for (int i = 0; i < n; ++i)

using ll = long long;
using namespace std;
using namespace atcoder;

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

    vector<string> s(n);
    rep(i, n) cin >> s[i];

    int counter = 0;
    int src, dst;
    vector<vector<int>> id(n, vector<int>(m, 0));


    rep(i, n) rep(j, m) {
        id[i][j] = counter++;
    }
    src = counter++;
    dst = counter++;


    mf_graph<int> graph(counter);

    rep(i, n) rep(j, m) {
        if ((i + j) % 2 == 0) {
            graph.add_edge(src, id[i][j], 1);
        } else {
            graph.add_edge(id[i][j], dst, 1);
        }
    }

    rep(i, n) rep(j, m) {
        if (s[i][j] == '#') continue;

        if (i + 1 < n and s[i + 1][j] != '#') {
            if ((i + j) % 2 == 0) {
                graph.add_edge(id[i][j], id[i + 1][j], 1);
            } else {
                graph.add_edge(id[i + 1][j], id[i][j], 1);
            }
        }

        if (j + 1 < m and s[i][j + 1] != '#') {
            if ((i + j) % 2 == 0) {
                graph.add_edge(id[i][j], id[i][j + 1], 1);
            } else {
                graph.add_edge(id[i][j + 1], id[i][j], 1);
            }
        }
    }

    const int ans = graph.flow(src, dst);
    cout << ans << endl;


    for (auto &edge: graph.edges()) {
        if (edge.cap != edge.flow) continue;
        if (edge.from >= n * m) continue;
        if (edge.to >= n * m) continue;

        const int frow = edge.from / m;
        const int fcol = edge.from % m;

        const int trow = edge.to / m;
        const int tcol = edge.to % m;

        if (fcol == tcol) {
            s[min(frow, trow)][fcol] = 'v';
            s[max(frow, trow)][fcol] = '^';
        } else {
            s[frow][min(fcol, tcol)] = '>';
            s[frow][max(fcol, tcol)] = '<';
        }
    }

    rep(i, n) cout << s[i] << endl;

    return 0;
}

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

int main(){
  int D,G; cin>>D>>G;
  vector<int>p(D,0);
  vector<int>c(D,0);
  for(int i=0;i<D;i++){
    cin>>p[i]>>c[i];
  }
  int ans=1e9;
  for(int mask=0;mask<(1<<D);mask++){
    int s=0,num=0,rest_max=-1;
    for(int i=0;i<D;i++){
      if(mask>>i&1){
        s+=100*(i+1)*p[i]+c[i];
        num+=p[i];
      }
      else{
        rest_max=i;
      }
    }
    if(s<G){
      int s1=100*(rest_max+1);
      int need=(G-s+s1-1)/s1;
      if(need>=p[rest_max]){
        continue;
      }
      num+=need;
    }
    ans=min(ans,num);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn (int)(1e5)
#define i64 long long
#define pii pair<i64,i64>
#define all(x) x.begin(),x.end()
#define LB(x,v) lower_bound(all(x), v) - x.begin()
#define fread() freopen("in.txt", "r", stdin);
using namespace std;

int solve(string s){
    int i =0, j = s.size()-1, cnt =0;
    while(i<j){
        if(s[i]!=s[j]) cnt++;
        i++; j--;
    }
    return cnt;
}

int main() {
    /*BEFORE SUBMIT, CHECK
    sample i/o format
    statements for debugging are removed/comment out
    global values / stl containers are initialized/cleared for each test (if needed)
    all array size are sufficient
    loop variable or output value doesn't cross min/max limit of input
    // */
    // #ifndef ONLINE_JUDGE
    //     fread();
    // #endif
    
    int n,k;
    string s,t; 
    while(cin>>s){
        printf("%d\n", solve(s));     
    }
    return 0;
}

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

int main(){
  string s,t;
  cin >>s>>t;
  int64_t a;
  a=s.size();
  int64_t ans=0;
  for(int64_t i=0;i<a;i++){
    if(s.at(i)!=t.at(i)){
      ans++;
    }
  }
  cout <<ans<<endl;
  return 0;
}

Measured memory_bytes: 3848
N = int(input())
A = list(map(int,input().split()))

P=[0]*(N+1)
P[N]=A[N]
Q=[0]*(N+1)
Q[N]=A[N]

for i in range(N,0,-1):
    mxp=P[i]+A[i-1]
    mnp=(P[i]//2) + (P[i]%2) +A[i-1]
    mxq=Q[i]+A[i-1]
    mnq=(Q[i]//2) + (Q[i]%2) +A[i-1]
    if mnp>2**i:
        print(-1)
        exit()
    P[i-1]=mnp
    Q[i-1]=min(mxq,2**i)

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

Q[0]=1

for i in range(1,N):
    if Q[i]>2**i:
        Q[i]=2**i
    if Q[i]>(Q[i-1]-A[i-1])*2:
        Q[i]=(Q[i-1]-A[i-1])*2

print(sum(Q))

Measured memory_bytes: 86576
#include <stdio.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)((n>>m)&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

ll dp[100010];
ll f(ll n){
	if(dp[n])return dp[n];
	if(n==0)return 0;
	ll t6=1;
	while(t6*6<=n)t6*=6;
	ll t9=1;
	while(t9*9<=n)t9*=9;
	return dp[n]=min(f(n-t6)+1,f(n-t9)+1);
}
int main(){
	ll n;
	scanf("%lld",&n);
	printf("%lld\n",f(n));
}

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

using namespace std;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    int max=0, max_s=0;

    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        if(A[i] > max){
            max = A[i];
        } else if(A[i] >= max_s){
            max_s = A[i];
        }
    }

    for (int j = 0; j < N; ++j) {
        if(A[j]==max){
            cout << max_s << endl;
        } else {
            cout << max << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2432
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstdlib>
#define INF 100000000
#define _INF -100000000
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;

int main() {
	string S;
	cin >> S;
	bool n = 0, w = 0, s = 0, e = 0;
	Loop(i, S.size()) {
		if (S[i] == 'N') n = 1;
		else if (S[i] == 'W') w = 1;
		else if (S[i] == 'S') s = 1;
		else if (S[i] == 'E') e = 1;
	}
	bool judge = 1;
	if (n != s) judge = 0;
	else if (w != e) judge = 0;
	if (judge) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v)                                                            \
  do {                                                                         \
    x = max(x, v);                                                             \
  } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll n,a,b;
  cin>>n>>a>>b;
  if ((b-a)%2==0) {
    cout << (b-a)/2 << endl;
    return 0;
  }
  ll t1 = (a-1) + (b-1);
  ll t2 = (n-b) + (n-a);
  cout << (min(t1,t2)+1)/2 << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import deque
N = input()
A = [int(input()) for i in range(N)]
coef = [2] * N
coef[0] = 1
coef[-1] = 1
coef1 = [coef[i] if i % 2 == 0 else coef[i] * -1 for i in range(N)]
coef2 = [coef[i] if i % 2 != 0 else coef[i] * -1 for i in range(N)]

A = sorted(A)
coef1 = sorted(coef1)
coef2 = sorted(coef2)
res1 = 0
for i in range(N):
	res1 += A[i] * coef1[i]
res2 = 0
for i in range(N):
	res2 += A[i] * coef2[i]
print max(res1, res2)


Measured memory_bytes: 12520
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    cin>>n;
    map<string,ll> mp;
    rep(i,n){
        cin >> str;
        sort(str.begin(),str.end());
        mp[str]++;
        if(mp[str]>=2) sum+=mp[str]-1;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 11356
use std::io;
use std::str::FromStr;

fn input_int_tuple() -> (u64, u64) {
  let mut line: String = String::new();
  io::stdin().read_line(&mut line);
  let vec: Vec<u64> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
  (vec[0], vec[1])
}

fn gcd(a: u64, b: u64) -> u64 {
  if b == 0 {
    a
  } else {
    gcd(b, a % b)
  }
}

fn divisors(n: u64) -> Vec<u64> {
  let mut divs: Vec<u64> = Vec::new();
  for i in 1..(n as f64).sqrt() as u64 + 1 {
    if n % i == 0 {
      divs.push(i);
      if i != (n / i) {
        divs.push(n/i);
      }
    }
  }
  divs.sort();
  divs
}

fn main() {
  let (a, b) = input_int_tuple();
  let gcd = gcd(a, b);
  let divs = divisors(gcd);
  let mut ret_vec: Vec<u64> = Vec::new();
  for n in divs {
    let mut flag = false;
    for m in &ret_vec {
      if *m == 1 {
        continue;
      }
      if n % *m == 0{
        flag = true;
        break;
      }
    }
    if flag == false {
      ret_vec.push(n);
    }
  }
  println!("{:?}", ret_vec.len());
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++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 irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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; }

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll d(n);
  rep(i,n) cin>>d[i];
  vsort(d);
  ll m=n/2-1;
  ll ans=d[m+1]-d[m];
  cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <map>
#include <set>
 
using namespace std;
 
set<string> dic;
map<string,int> times;
 
int main(){
  int msize = 0;
  string str;
  string a,b;
  while(!cin.eof()){
    string in; cin >> in;
    dic.insert(in);
    times[in]++;
    if(msize < in.size()){
      str = in;
      msize = str.size();
    }
  }
  a = str;
  int mfreq = 0;
  for(set<string>::iterator it = dic.begin(); it != dic.end(); ++it){
    if(mfreq < times[*it]){
      mfreq = times[*it];
      str = *it;
    }
  }
  b = str;
  cout << b << " " << a << endl;
 
  return 0;
}

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

using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n); i > 0; i--)
#define all(n) n.begin(), n.end()
#define print(n) cout << n << endl

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

    int h,w,k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i,h) cin >> s[i];

    int cnt,sum,ans=h+w;
    vector<ll> gr(h);
    bool split=false;
    rep(bit,(1<<h-1)){
        sum = 0;
        rep(i,h) if(bit & (1<<i)) sum++;
        rep(j,w){
            cnt = 0;
            rep(i,h){
                if(s[i][j]=='1'){
                    gr[cnt]++;
                    if(gr[cnt]>k){
                        if(split){
                            j = w-1;
                            sum = ans;
                        }else{
                            j--;
                            sum++;
                            rep(c,h) gr[c] = 0;
                        }
                        cnt = 0;
                        split = true;
                        break;
                    }
                }
                if(bit & (1<<i)) cnt++;
                if(split) split = false;
            }
            if(sum >= ans) break;
        }
        rep(c,h) gr[c] = 0;
        if(sum < ans) ans = sum;
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;

public class Main {
	static int n;
	static int k;
	static String[] a;
	static boolean[] used;
	static Set<String> set;
 	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		while(true){
			n = scanner.nextInt();
			k = scanner.nextInt();
			if(n == 0 && k == 0) break;
			a = new String[n];
			for(int i = 0; i < n; i++){
				a[i] = scanner.next();
			}
			used = new boolean[n];
			for(int i = 0; i < n; i++){
				used[i] = false;
			}
			set = new HashSet<String>();
			dfs("", 0);
			System.out.println(set.size());
		}
		return;
	}
	public static void dfs(String s, int count){
		if(count == k){
			set.add(s);
			return;
		}
		for(int i = 0; i < n; i++){
			if(used[i]) continue;
			used[i] = true;
			dfs(s+a[i], count+1);
			used[i] = false;
		}
	}
}



Measured memory_bytes: 31076
#!/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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    if n % 2:
        print(2 * n)
    else:
        print(n)
    return

#B
def B():
    n = II()
    a = LI()
    a.sort()
    print(a[n-1]-a[0])
    return

#C
def C():
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    B()


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

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

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

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

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

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

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

int N;
int A[111111];
int l[111111];
int r[111111];

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

signed main() {
  cin >> N;
  rep (i, N) {
    cin >> A[i];
  }

  rep (i, N) {
    l[i+1] = gcd(l[i], A[i]);
  }
  // print1(l, l+N+2);

  for (int i = N+1; i >= 1; i--) {
    r[i] = gcd(r[i+1], A[i-1]);
  }
  // print1(r, r+N+2);

  int ans = 0;
  for (int i = 1; i <= N; i++) {
    int t = gcd(l[i-1], r[i+1]);
    chmax(ans, t);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2560
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <utility>
using namespace std;

char in[1<<21];
char const*o;

void init_in() { 
  o = in; 
  in[fread_unlocked(in,1,sizeof(in)-4,stdin)] = 0;
}

int readInt(){ 
  unsigned u = 0, s = 0;
  while(*o && *o <= 32){
    ++o; 
  }
  if (*o == '-'){
    s = ~s, ++o;
  } else if (*o == '+'){
    ++o;
  }
   
   while(*o>='0' && *o<='9'){
    u = (u<<3) + (u << 1) + (*o++ - '0');
  }

  return static_cast<int>((u^s) + !!s) ;
}

struct task{
  int year, id;
};

int main(){
  init_in();
  int n = readInt(); int m = readInt();
  vector<vector<task>> v(101010);
  for (int i = 0; i < m; ++i) {
    int p = readInt(); int y = readInt();
    v[p].push_back({y, i + 1});
  }

  vector<int> ans1(101010), ans2(101010);

  for (int i = 1; i <= n; ++i) {
    if (v[i].empty()) continue;
    sort(v[i].begin(), v[i].end(), [](const task &x, const task &y){
      return x.year < y.year;
    });
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < (int) v[i].size(); ++j) {
      ans1[v[i][j].id] = i;
      ans2[v[i][j].id] = j + 1;
    }
  }

  for (int i = 1; i <= m; ++i) {
    cout << setfill('0') << right << setw(6) << ans1[i] << setfill('0') << right << setw(6) << ans2[i] << '\n';
  }

  return 0;
}


Measured memory_bytes: 9344
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

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

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

signed main() {
    int n, p;
    while (cin >> n >> p) {
	if (!n) break;

	int now = 0;
	vector<int> c(n, 0);

	int q = p;
	while (true) {
	    if (p > 0) {
		c[now]++;
		p--;
	    } else {
		p = c[now];
		c[now] = 0;
	    }
	    if (c[now] == q) break;
	    now++;
	    if (now == n) now = 0;
	}
	cout << now << endl;
    }

    return 0;
}

Measured memory_bytes: 3032
#include<iostream>
using namespace std;
int main()
{
	int a,b;
	while(cin>>a>>b)
	{
		if(a==0&&b==0) break;
		int x=0;
		for(int i=1;i<=a;i++)
		{
			if(i%2==0)
			x=0;
			else
			x=1;
			for(int j=1;j<=b;j++)
			{
					if(x)
					cout<<"#";
					else
					cout<<".";
					x=!x;
			}
			cout<<endl;
		}
		cout<<endl;
		
	}
	return 0;
}


Measured memory_bytes: 3100
#define _USE_MATH_DEFINES // for C++  
#include "bits/stdc++.h"
using LL = long long;
using ULL = unsigned long long;
#define NUM 1000000007

using namespace std;

int main()
{
    string s;
    cin >> s;
    cout << count(s.begin(), s.end(), '1') << endl;
}

Measured memory_bytes: 256
#include<stdio.h> 
int main() {
    int a,b,c,d;
    
    scanf("%d%d%d",&a,&b,&c);
    
    for(a;a<b+1;a++) {
        if(c%a==0)d++;
    }
    
    printf("%d\n",d);
    
    return 0; 
    
} 


Measured memory_bytes: 2104
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		// スペース区切りの整数の入力
		int b = a * a* a;
      System.out.println(b);
	}
}


Measured memory_bytes: 35780
N,Y = map(int,input().split())
for x in range(N+1):
    if x*10000 > Y: break
    for y in range(N+1-x):
        z = N-x-y
        if x*10000 + y*5000 > Y: break
        if x*10000 + y*5000 + z*1000 == Y:
            print(x,y,z)
            exit()
print(-1,-1,-1)


Measured memory_bytes: 41964
#include <bits/stdc++.h>
using ll = long long;
constexpr int MOD = 1000000007;
using namespace std;

int main() {
  int x, y;
  cin >> x >> y;
  
  int ans = 0;
  if (x == 3)
    ans += 100000;
  if (y == 3)
    ans += 100000;
  if (x == 2)
    ans += 200000;
  if (y == 2)
    ans += 200000;
  if (x == 1)
    ans += 300000;
  if (y == 1)
    ans += 300000;
  if (x == 1 && y == 1)
    ans += 400000;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
	static int mod = (int) 1e9 + 7;
	static int DX[] = { -1, 0, 1, 0 }, DY[] = { 0, -1, 0, 1 };
	static final int INF = Integer.MAX_VALUE / 3;
	static final long LINF = Long.MAX_VALUE / 3;

	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		int A = fs.nextInt(), B = fs.nextInt(), m = fs.nextInt();
		int a[] = fs.nextIntArray(A);
		int b[] = fs.nextIntArray(B);
		int ans = INF;
		for(int i=0;i<m;i++) {
			int x = fs.nextInt()-1, y = fs.nextInt()-1 , c = fs.nextInt();
			int sum = a[x] + b[y] - c;
			ans = Math.min(ans, sum);
		}
		
		Arrays.sort(a);
		Arrays.sort(b);
		
		ans = Math.min(ans , a[0] + b[0]);
		System.out.println(ans);
		
	}

	//MOD culculations
	static long plus(long x, long y) {
		long res = (x + y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long sub(long x, long y) {
		long res = (x - y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long mul(long x, long y) {
		long res = (x * y) % mod;
		return res < 0 ? res + mod : res;
	}

	static long div(long x, long y) {
		long res = x * pow(y, mod - 2) % mod;
		return res < 0 ? res + mod : res;
	}

	static long pow(long x, long y) {
		if (y < 0)
			return 0;
		if (y == 0)
			return 1;
		if (y % 2 == 1)
			return (x * pow(x, y - 1)) % mod;
		long root = pow(x, y / 2);
		return root * root % mod;
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

pii pp[MAXN];
int ans[MAXN];

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 0, n) {
		scanf("%d", &pp[i]._1);
		pp[i]._2 = i;
	}
	sort(pp, pp + n);
	REP(i, 0, n) {
		//printf("%d %d\n", pp[i]._1, pp[i]._2);
		if (i < n / 2) {
			//printf("%d %d %d\n", i, pp[i]._2, pp[n / 2]._1);
			ans[pp[i]._2] = pp[n / 2]._1;
		} else {
			ans[pp[i]._2] = pp[n / 2 - 1]._1;
		}
	}
	REP(i, 0, n) {
		printf("%d\n", ans[i]);
	}
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pint;
#define ms(arr) memset(arr,0,sizeof(arr))


int main() {
    int n, d;
    cin >> n >> d;
    cout << ceil(n * 1.0 / (2 * d + 1) * 1.0);
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, end) for (int i = begin; i > end; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

int N;
string s[55];
int t[55];
string X;

int main()
{
    cin >> N;
    bool asleep = false;
    ll ans = 0;
    rep(i, 0, N)
    {
        cin >> s[i] >> t[i];
        if (asleep)
        {
            ans += t[i];
        }
        /*
        if (s[i].size() == X.size())
        {
            bool can = true;
            rep(k, 0, s[i].size())
            {
                if (s[i][k] != X[k])
                {
                    can = false;
                }
            }
            if (can)
            {
                asleep = true;
            }
        }
        */
    }
    cin >> X;

    rep(i, 0, N)
    {
        if (asleep)
        {
            ans += t[i];
        }
        if (s[i] == X)
        {
            asleep = true;
        }
        /*
        if (s[i].size() == X.size())
        {
            bool can = true;
            rep(k, 0, s[i].size())
            {
                if (s[i][k] != X[k])
                {
                    can = false;
                }
            }
            if (can)
            {
                asleep = true;
            }
        }
        */
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++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(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N,K;
  cin>>N>>K;
  ll ans=K;
  rep(i,N-1)
    ans*=K-1;
  cout<<ans<<endl;

}




Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MIN 1E9
#define MAX -10000000
long long int i,j;

int cp(const void*a,const void*b){
    return *(int*)a-*(int*)b;
}

int main(void){
    int sx,sy,tx,ty;
    scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
    for(i=sy;i<ty;i++)printf("U");
    for(i=sx;i<tx;i++)printf("R");
    for(i=ty;i>sy;i--)printf("D");
    for(i=tx;i>sx;i--)printf("L");
    printf("L");
    for(i=sy;i<=ty;i++)printf("U");
    for(i=sx;i<=tx;i++)printf("R");
    printf("DR");
    for(i=ty;i>=sy;i--)printf("D");
    for(i=tx;i>=sx;i--)printf("L");
    puts("U");
 // puts("UURDDLLUUURRDRDDDLLU");
    return 0;
}

Measured memory_bytes: 128
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

res = 0
for n in range(N):
    b = min(A[n], B[n])
    B[n] -= b
    b2 = min(A[n + 1], B[n])
    A[n + 1] -= b2
    res += b + b2

print(res)


Measured memory_bytes: 19116
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define FOR(i, a, b) for (int i = a; i < (b + a); i++)
#define W1 while (1)
#define COUT(x) cout << x << endl
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(x) x.begin(),x.end()
#define P pair<int,int>
#define mod 1000000007
#define PB push_back
#define F first
#define S second

int main() {
  int n;
  ll d, x, y;
  cin >> n >> d;
  d = d * d;
  int ans = 0;
  rep(i, n) {
    cin >> x >> y;
    x = x * x;
    y = y * y;
    if (x + y <= d) ans++;
  }
  COUT(ans);

  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int N;
    float v;
    cin >> N;
    vector<float> vec{};
    for(int i=0;i<N;i++){
        cin >> v;
        vec.push_back(v);
    }
    
    sort(vec.begin(), vec.end());
    
    float a,b;
    
    while(1){
        a = vec[0];
        b = vec[1];
        vec.erase(vec.begin());
        vec.erase(vec.begin());
        vec.push_back((a+b)/2);
        sort(vec.begin(), vec.end());
        if(vec.size() == 1) break;
    }
    
    cout << vec[0] << endl;
}

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

using namespace std;

void b()
{
	int n;
	cin >> n;
	int count = 0;
	for (int i = 1; i <= n; i++) {
		string s = to_string(i);
		if (s.length() % 2 != 0) {
			count++;
		}
	}

	cout << count << endl;
}

int main()
{
	b();

	return 0;
}


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

int main() {
    int w,n;
    scanf("%d %d",&n,&w);
    vector<long long int> dp(w+1);
    for(int item = 0;item < n;++item){
        int u, v;
        scanf("%d %d",&u,&v);
        for(int weight = w - u; weight >= 0; --weight){
            dp[weight + u] = max(dp[weight+u],dp[weight] + v);
        }
    }
    long long int ans = 0;
    for(int i = 0; i <= w;i++) ans = max(ans,dp[i]);
    printf("%lld\n",ans);
}


Measured memory_bytes: 1024
import java.util.*;
import java.io.*;

public class Main {

	public static void main (String[] args) {
	   InputReader in = new InputReader(System.in);
	   int n = in.readInt(); 
	   long d[] = new long[5];
	   int P[]={0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,2};
	   int Q[]={1 ,1 ,1 ,2 ,2 ,3 ,2 ,2 ,3 ,3};
	   int R[]={2 ,3 ,4 ,3 ,4 ,4 ,3 ,4 ,4 ,4};
	   
	   for(int i = 0; i<n; i++) {
		   char s[] = in.readString().toCharArray();
		   if ( s[0]== 'M') d[0]++;
		   if ( s[0]== 'A') d[1]++;
		   if ( s[0]== 'R') d[2]++;
		   if ( s[0]== 'C') d[3]++;
		   if ( s[0]== 'H') d[4]++;
	   }
	   long res = 0; 
	   for(int i = 0; i<10; i++) {
		   int s = P[i];  
		   int t = Q[i]; 
		   int u = R[i]; 
		   res += d[s]*d[t]*d[u]; 
	   }
	   System.out.println(res); 
	}
}

class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public long readLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9') {
				throw new InputMismatchException();
			}
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	
	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}


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

int main() {
  int K, N;
  cin >> K >> N;
  int A[N];
  rep(i,N) cin >> A[i];
  
  int m = A[0] + K - A[N - 1];
  rep(i,N-1) m = max(m, A[i + 1] - A[i]);
  
  cout << K - m << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
T gcd(T a, T b) {
	if (b==0) swap(a,b);
	if (a % b == 0) return b;
	gcd(b, a%b);
}

template<typename U>
U gcd_multi(vector<U> A) {
	int n = A.size();
	if (n == 1) return A[0];
	U G = gcd(A[0], A[1]);
	if (n == 2) return G;
	for (int i = 2; i < n; ++i) G = gcd(G, A[i]);
	return G;
}

int main(int argc, char const *argv[]) {
	int n;
	cin>>n;
	vector<ll> a(n);
	rep(i,n) cin>>a[i];
	vector<ll> l(n+10), r(n+10);
	l[0]=0; r[n+1]=0;

	for (int i = 1; i <= n; ++i) {
		l[i] = gcd(l[i-1],a[i-1]);
	}
	for (int i = n+1; i >= 1; --i) {
		r[i-1] = gcd(r[i],a[i-2]);
	}

	/*
	rep(i,n+2) cout<<l[i]<<" ";
	cout<<endl;
	rep(i,n+2) cout<<r[i]<<" ";
	cout<<endl;
	*/
	ll ans = gcd_multi(a);
	for (int i = 1; i <= n; ++i) {
		ll tmp = gcd(l[i-1], r[i+1]);
		ans = max(ans,tmp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rand() (rand() << 15 | rand())
using namespace std;
typedef long long  ll;
#define EPS 1e-9
#define PI acos(-1.0)
const int N = 1e5 + 4;

vector<pair<int , int>> add[N];
vector<long long> er[N];
long long dp[N];
int main() {
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   int n , m;
   cin >> n >> m;
   for(int i = 0 ; i < m ; ++i){
      int l , r , c;
      cin >> l >> r >> c;
      add[l].push_back({r , c});
   }


   multiset<long long> ms;
   for(int i = 1 ; i <= n ; ++i){
      for(long long c : er[i])
         ms.erase(ms.find(c));
      if(i > 1)dp[i] = (ms.empty() ? -LLONG_MAX / 2 : *ms.begin());
      else dp[i] = 0;
      for(auto p : add[i]){
         ms.insert(dp[i] + p.second);
         er[p.first + 1].push_back(dp[i] + p.second);
      }
   }

   cout << (dp[n] < 0 ? -1 : dp[n]) << "\n";
}

Measured memory_bytes: 11776
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int dat[303030];
bool isok(int med, int num)
{
	int mini = 0, now = 0;
	for (int i = 0; i < num; i++)
	{
		if (i % 2 == 0)now += dat[i];
		else now -= dat[i];
		if (i % 2 == 0 && mini + med <= now)
		{
			if (i == num - 1)return true;
			else mini = min(mini, now - dat[i + 1]);
		}
	}
	return false;
}
int main()
{
	int num;
	scanf("%d", &num);
	int s0 = 0, s1 = 0;
	for (int i = 0; i < num; i++)
	{
		scanf("%d", &dat[i]);
		if (i % 2 == 0)s0 += dat[i];
		else s1 += dat[i];
	}
	if (num % 2 == 0)
	{
		printf("%d %d\n", max(s0, s1), min(s0, s1));
		return 0;
	}
	int beg = 0, end = 1000000000;
	for (;;)
	{
		if (beg == end)break;
		int med = (beg + end + 1) / 2;
		if (isok(med, num))beg = med;
		else end = med - 1;
	}
	printf("%d %d\n", s1 + beg, s0 - beg);
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};
constexpr int INF = 1<<30;

template<class T> class SegmentTree {
    public:
    size_t n;          // 葉の数
    vector<T> data; // データ
    T def;          // 単位元
    function<T(T, T)> update_func;  // 点更新で使う処理
    function<T(T, T)> find_func;    // 区間クエリで使う処理

    SegmentTree(size_t _n, T _def, function<T(T, T)> _update_func, function<T(T, T)> _find_func)
        : def(_def), update_func(_update_func), find_func(_find_func) {
        // 2のべき乗にする
        n = 1;
        while(n < _n) n <<= 1;
        data = vector<T>(2*n-1, _def);
    }

    void update(size_t i, T x){
        i += n-1;
        data[i] = update_func(data[i], x);
        while(i){
            i = (i-1)/2;
            data[i] = find_func(data[2*i+1], data[2*i+2]);
        }
    }

    T _find(size_t s, size_t t, size_t k, size_t kl, size_t kr){
        if(kr <= s || t <= kl) return def;
        if(s <= kl && kr <= t) return data[k];
        size_t kc = (kl+kr)/2;
        T vl = _find(s, t, 2*k+1, kl, kc);
        T vr = _find(s, t, 2*k+2, kc, kr);
        return find_func(vl, vr);
    }
    
    T find(size_t s, size_t t) {
        return _find(s, t, 0, 0, n);
    }
};


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

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<int> a(n+1, INF);
    for(int i=0;i<=n;++i) if(s[i] == '1') a[i] = -1;
    vector<int> min_m(n+1, INF);

    SegmentTree<int> tree(
        n+2, INF, 
        [](int a, int b) { return b; }, 
        [](int a, int b) { return min(a, b); }
    );
    a[n] = 0;
    tree.update(n, 0);
    map<ll, int> value_to_idx;
    value_to_idx[0] = n;
    for(int i=n-1;i>=0;--i) {
        if(a[i] == -1) continue;

        a[i] = tree.find(i+1, min(n, i+m)+1) + 1;
        int j = value_to_idx[a[i]-1];
        if(j != 0 && j-i <= m) min_m[i] = j-i;
        // cerr << a[i] << ":" << min_m[i] << endl;

        tree.update(i, a[i]);
        value_to_idx[a[i]] = i;
    }

    {
        int i = 0;
        vector<int> ans;
        while(i < n) {
            if(min_m[i] == INF) {
                cout << -1 << endl;
                return 0;
            }
            ans.push_back(min_m[i]);
            i = i + min_m[i];
        }
        for(int x: ans) cout << x << " ";
        cout << endl;
    }
}


Measured memory_bytes: 9164