akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int head[500005];
int f[1000005][22];
int deep[1000005];
struct edge
{
    int next,to;
} e[1000005];
void dfs(int now,int father)//now代表当前访问到的节点，father代表now节点的父亲节点
{
    deep[now]=deep[father]+1;//深度比父亲节点多1
    int i;
    for(i=1; (1<<i)<=deep[now]; i++) //判断条件就是不能跳得比根节点还高吧？
        f[now][i]=f[f[now][i-1]][i-1];
    for(i=head[now]; i; i=e[i].next)
    {
        if(e[i].to==father)
            continue;//双向边，不能往回走！
        f[e[i].to][0]=now;
        //遍历每一个以now为起点的边的终点
        dfs(e[i].to,now);
    }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])
        swap(x,y);//直接让x是最深节点，后面就不用分类讨论了
    int i;
    for(i=19; i>=0; i--) //跳到同一层
    {
        if(deep[f[x][i]]>=deep[y])//当x的深度大于等于y的时候都会往上跳，最后就会跳到和y同等深度的地方
            x=f[x][i];
        if(x==y)
            return y;//有可能x、y的最近公共祖先就是y本身
    }
    for(i=19; i>=0; i--)
    {
        if(f[x][i]!=f[y][i])//跳到他们最近公共祖先的下一层就行了
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    int n,m,k;//k是根节点编号
    cin>>n;
    int num=1,i;
    for(i=0; i<=n-1; i++)
    {
        int k;
        scanf("%d",&k);
        int from=i,to;
        while(k--)
        {
            scanf("%d",&to);
            //链式前向星存树
            e[num].to=to;
            e[num].next=head[from];
            head[from]=num;

            num++;
            //用双向边代替无向边
            e[num].to=from;
            e[num].next=head[to];
            head[to]=num;

            num++;
        }

    }
    dfs(0,0);
    cin>>m;
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        cout<<lca(x,y)<<'\n';
    }
    return 0;
}



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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, ans = 0, p = 0;
    cin >> n;
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        p += v[i];
    }
    p = round(float(p)/float(n));
    for (int i = 0; i < n; i++) {
        ans += (v[i]-p)*(v[i]-p);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++)cin >> a[i];

    bool color[8];
    int max = 0;
    for(int i=0;i<8;i++)color[i] = false;

    for(int i=0;i<n;i++){
        if(a[i]<400)color[0] = true;
        else if(a[i]<800)color[1] = true;
        else if(a[i]<1200)color[2] = true;
        else if(a[i]<1600)color[3] = true;
        else if(a[i]<2000)color[4] = true;
        else if(a[i]<2400)color[5] = true;
        else if(a[i]<2800)color[6] = true;
        else if(a[i]<3200)color[7] = true;
        else max++;
    }

    int ans = 0;
    for(int i=0;i<8;i++){
        if(color[i])ans++;
    }
    if(ans==0)ans++, max--;
    cout << ans << " ";

    int i = 0;
    while(i<max)ans++, i++;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int a[N],b[N],vis1[N],vis2[N],c[N];
int n,f;
int main(){
	scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d",&a[i]);
    	
	}
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	
	}
    reverse(b+1,b+1+n);
    vector<int>p,q;
    int cnt=0,val=0;
    for(int i=1;i<=n;i++){
    	if(a[i]!=b[i])continue;
    	cnt++;
    	val=a[i];
    	p.push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(cnt==0)break;
		if(a[i]==b[i])continue;
		if(a[i]!=val&&b[i]!=val){
			cnt--;
			q.push_back(i);
		}
	}
	if(cnt)printf("No\n");
	else{
		for(int i=0;i<q.size();i++)swap(b[p[i]],b[q[i]]);
		printf("Yes\n");
		for(int i=1;i<=n;i++)
		printf("%d ",b[i]);
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 5852
import java.util.Scanner;

public class Main {
    static final long MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt(), w = sc.nextInt(), k = sc.nextInt();
        long[][] dp = new long[h + 1][w + 2];
        long[][] table = calcTable(w);
        dp[0][1] = 1;
        for (int i = 0; i < h; i++) {
            for (int j = 1; j <= w; j++) {
                dp[i + 1][j] = dp[i][j] * table[j - 1][0] % MOD
                        + dp[i][j - 1] * table[j - 1][1] % MOD
                        + dp[i][j + 1] * table[j - 1][2] % MOD;
                dp[i + 1][j] %= MOD;
            }
        }
//        for (long[] arr : dp) {
//            for (long l : arr) {
//                System.out.print(l + " ");
//            }
//            System.out.println();
//        }
        System.out.println(dp[h][k]);
    }

    private static long[][] calcTable(int w) {
        long[][] arr = new long[w][3];
        int kukan = w-1;
        for (int i = 0; i < w; i++) {
            loop:
            for (int j = 0; j < (1L<<kukan); j++) {
                verify:
                for (int k = 0; k < kukan; k++) {
                    if(k==0) continue verify;
                    if(((j>>k) & 1) == 1 && ((j>>k-1) & 1) == 1) continue loop;
                }

                if(check(i-1,j,kukan,true) && check(i,j,kukan,true)) {
                    arr[i][0]++;
                }
                if(check(i-2,j,kukan,true) && check(i-1,j,kukan,false) && check(i,j,kukan,true)) {
                    arr[i][1]++;
                }
                if(check(i-1,j,kukan ,true) && check(i,j,kukan,false) && check(i+1,j,kukan,true)) {
                    arr[i][2]++;
                }
            }
        }
        return arr;
    }

    private static boolean check(int slide, int num, int kukan, boolean isZero) {
        if(slide < 0 || slide >= kukan) {
            return true;
        }

        return  (num>>slide & 1) == (isZero ? 0 : 1);
    }
}


Measured memory_bytes: 23636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a).size()
#define de(x) cout<<#x<<" ="<<x<<endl
#define rep(i,a,b) for(int i=(a);i<(b);++i)
//-----------------------------------------
const int N=100005;
const double eps=1e-7;
int main() {
    int a,b,c,d,e,f;
    scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
    int ans1=0,ans2=0;
    double now=-1.0;
    for(int i=0;i<=30;++i) {
        if(i*a*100>f) break;
        for(int j=0;j<=30;++j) {
            if(i*a*100+100*b*j>f) break;
            for(int k=0;k<=1600;++k) {
                if(100*i*a+100*j*b+k*c>f) break;
                for(int h=0;h<=1600;++h) {
                    if(100*i*a+100*j*b+k*c+h*d>f) break;
                    //if((k==0&&h==0)||(i==0&&j==0))continue;
                    int t1=100*i*a+100*j*b;
                    int t2=c*k+d*h;
                    if((i*a+b*j)*e<t2) continue;
                    if(t1+t2==0) continue;
                    double t=100.0*t2/(0.0+t1+t2);
                    if(t>now) {
                        ans1=t1+t2,ans2=t2;
                        now=t;
                    }
                }
            }
        }
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}


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

#define N (1<<17)
#define ll long long
#define M 1000000007
#define INF 1000000007
#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
#define L length() - 1

using namespace std;

unordered_map<int, ll> m;

int main () {
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll ans = 1;
	int n;
	cin>>n;
	for (int i = 0; i < n; i++) {
		int x = i + 1;
		for (int j = 2; j * j <= x; j++) {
			while (x % j == 0) {
				x /= j;
				m[j]++;
			}
		}
		if (x != 1) m[x]++;
	}
	for (auto p : m) {
		ans = (ans * (p.S + 1)) % M;
	}
	cout<<ans<<endl;
}

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

int main(){
    long int n,a,b; // a=0,b=1

    cin >> n >> a >> b;

    // 青計算 n / ( a + b )のぶん
    long int x = 0;
    x += ( n / ( a + b ) ) * a;

    // 青計算 n % ( a + b )のぶん
    if( ( n % ( a + b ) ) <= a ){
        x += n % ( a + b );
    }
    else{
        x += a;
    }

    cout << x << "\n";
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    while(n >= 0) {
      if(n % 4 == 0 || n % 7 == 0) {
        System.out.println("Yes");
        return;
      }
      n -= 11;
    }
    
    System.out.println("No");
  }
}

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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

#define rep(i, n) FOR(i, 0, n)
#define FOR(i, x, n) for (int i = (x); i < (n); ++i)
#define all(v) (v).begin(), (v).end()

using ll = long long;

template<class T> void chmax(T& a, T b){ if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b){ if (a > b) { a = b; } }

int main() {
    int n;
    string s;
    set<string> st;
    cin >> n;
    while (n--) {
        cin >> s;
        st.insert(s);
    }
    cout << st.size() << endl;

    return 0;
}

Measured memory_bytes: 19180
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll power(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define bit(n,m)(((n)>>(m))&1)//nをm(bit)分右にシフト

//your code here!

int main(void){
    char S[15];
    scanf("%s", S);
    ll N=strlen(S), No[15];
    rep(i, N) No[i] = S[i] - '0';
    ll bitall=power(2, N-1), ans=0;
    rep(i, bitall) {
        ll e=0;
        rep(j, N){
            ans += No[N-1-j] * power(10, e++);
            if(bit(i,j)==0) e = 0;
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
	int N; cin >> N;
	vector<int> A(N);
	rep(i,N){
		cin >> A[i];
	}
	int ans = 0;
	int now = 0;
	int cnt = 0;
	rep(i,N-1){
		if(cnt == 0 && A[i] < A[i+1]){
			now = 0;
			cnt++;
		}
		if(cnt == 0 && A[i] > A[i+1]){
			now = 1;
			cnt++;
		}
		if(cnt == 1){
			if(now == 0 && A[i] > A[i+1]){
				cnt = 0;
				ans++;
			}
			if(now == 1 && A[i] < A[i+1]){
				cnt = 0;
				ans++;
			}
		}
	}
	ans++;
	cout << ans << endl;
}


Measured memory_bytes: 640
// atcoder/abc128/E/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

struct X {
  int idx;
  int begin, end, x;
};
bool operator < (X i, X j) {
  return i.end - i.x > j.end - j.x;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, q;
  while (cin >> n >> q) {
    vector<X> v(n);
    int idx = 0;
    each (i, v) {
      i.idx = idx++;
      cin >> i.begin >> i.end >> i.x;
    }

    vector<int> d(q);
    cin >> d;

    sort(v.begin(), v.end(), [] (auto i, auto j) {
      return i.begin - i.x < j.begin - j.x;
    });
    reverse(v.begin(), v.end());

    priority_queue<X> q;
    priority_queue<pair<int, int>> r;
    set<int> used;
    each (i, d) {
      while (v.size() && v.back().begin <= i + v.back().x) {
        // cout << "push: " << v.back().begin << ' ' << v.back().end << ' ' << v.back().x << endl;
        q.push(v.back());
        r.push({-1 * v.back().x, v.back().idx});
        v.pop_back();
      }
      while (q.size() && !(i + q.top().x < q.top().end)) {
        // cout << "pop: " << q.top().begin << ' ' << q.top().end << ' ' << q.top().x << endl;
        used.insert(q.top().idx);
        q.pop();
      }
      while (r.size() && used.count(r.top().second)) {
        r.pop();
      }
      cout << (r.empty() ? -1 : -1 * r.top().first) << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 19308
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fore(b,c) for(int val0=b;val0<c;val0++)
#define forr(k,c,s) for(int k=c;k<s;k++)
#define pb push_back
#define mmp make_pair
using namespace __gnu_pbds;
using namespace std;
template<typename T>
using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long double ld;
typedef vector<vii> al;
typedef vector<ll> vl;
const int INF = 1e9;
const ll INFL = 1LL<<61;
const ll MN = 100010;
const ll MM = (1<<18)+10;
const ll SQ = (1<<9)|1;
ll wa[MM],va[MM];
//maybe less dumb lol
vii ok[SQ];
void pre(int u) {
	if(u == 0) {
		ok[u].push_back({0,0});
		return;
	}
	vii& su = ok[u>>1];
	ok[u] = su;
	for(int i=0;i<su.size();i++) {
		ii co = su[i];
		ok[u].push_back({co.first+wa[u],co.second+va[u]});
	}
	sort(ok[u].begin(),ok[u].end());
	int rs = -1;
	for(int i=0;i<ok[u].size();i++) {
		rs = max(rs,ok[u][i].second);
		ok[u][i].second = max(ok[u][i].second,rs);
	}
}
ll sqan(int u, int wo) {
	ii se = {wo+1,-1};
	auto it = upper_bound(ok[u].begin(),ok[u].end(),se);
	--it;
	return it->second;
}
ll ds(int u, int wo) {
	if(u == 0) {return 0;}
	if(u < SQ) {
		return sqan(u,wo);
	}
	ll res = ds(u>>1,wo);
	if(wo >= wa[u]) {res = max(res,ds(u>>1,wo-wa[u])+va[u]);}
	return res;
}
int main() {
	ios::sync_with_stdio(0);cout.precision(20);cout.tie(0);cin.tie(0);
	ll n;
	cin >> n;
	for(int i=1;i<=n;i++) {
		cin >> va[i] >> wa[i];
	}
	for(int i=0;i<SQ;i++) {
		pre(i);
	}
	int q;
	cin >> q;
	while(q--) {
		int u,w;
		cin >> u >> w;
		cout << ds(u,w) << '\n';
	}
}



Measured memory_bytes: 8948
import collections
n = int(input())
v = list(map(int, input().split()))
even = [v[2*i] for i in range(n//2)]
odd = [v[2*i+1] for i in range(n//2)]
dEven = collections.Counter(even).most_common()
dOdd = collections.Counter(odd).most_common()
if dEven[0][0] != dOdd[0][0]:
    ans = n - dEven[0][1]  - dOdd[0][1]
else:
    if len(dEven) >=2 and len(dOdd) >= 2:
        ans = n - max(dEven[0][1]+dOdd[1][1], dEven[1][1]+dOdd[0][1])
    elif len(dEven) < len(dOdd):
        ans = n - (dEven[0][1]+dOdd[1][1])
    elif len(dEven) > len(dOdd):
        ans = n - (dEven[1][1]+dOdd[0][1])
    else:
        ans = n//2
print(ans)

Measured memory_bytes: 25932
/*2020/03/16 ABC 051*/

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;  


int main() {
    int k, s, ans=0;
    cin >> k >> s;
    for(int i=0; i<=k; i++) {
        for(int j=0; j<=k; j++) {
            int v = s - i - j;
            if(v <= k && v >= 0 ) {
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


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

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
int n , a[maxn];
int dp[maxn][2];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i];
    }
    int res = 0;
    for(int i = 1 ; i <= n + 1 ; ++i){
        int x = a[i] - a[i - 1] , y = 0;
        if(x < y)swap(x , y);
        int pivot[2] = {max(0 , dp[i - 1][0] + x) , max(0 , min(dp[i - 1][0] + y , dp[i - 1][1] + x))};
        if(pivot[0] > a[i])res++ , dp[i][0] = pivot[1];
        else dp[i][0] = pivot[0] , dp[i][1] = pivot[1];
    }
    cout << res;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int l,r,n,m;
	cin>>n>>m;
	pair<int,int> last;
	cin>>l>>r;
	last=make_pair(l,r);
	for(int i=1;i<m;i++)
	{
		cin>>l>>r;
		int x=last.first,y=last.second;
		if(x>r||y<l)
		{
			cout<<0;
			return 0;
		}
		x=max(x,l);
		y=min(y,r);
		last=make_pair(x,y);
	}
	cout<<last.second-last.first+1;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
using namespace std;
int main(void){
    string C;
    int a, b;
    for(int i = 0; i < 9; i++){
        cin >> C >> a >> b;
        cout << C << " " << a + b << " " << a*200 + b*300 << endl;
    }
}


Measured memory_bytes: 3024
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#define pi 3.14159265358979323846264338
using namespace std;

int main() {
	int n, m;
	while (cin >> n >> m) {
		long long a = n, b = m,keep;
		while (a != b) {
			keep = min(a, b);
			b = max(a, b) - min(a, b);
			a = keep;
		}
		cout << a << " " << n/a*m << endl;
	}
	return 0;
}

Measured memory_bytes: 3056
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n;
// string s;

int main() {
    cin >> n;
    Vi a(n);
    REP(i, n) cin >> a[i];

    Vi dp(n, 2e9);
    RREP(i, n-1, 0) {
        *upper_bound(ALL(dp), a[i]) = a[i];
    }

    std::cout << lower_bound(ALL(dp), 2e9) - dp.begin() << '\n';

    return 0;
}


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

using namespace std;

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define FOR(i,m,n) for(int i=(m) ; i<(n) ; i++)
#define FORR(i,m,n) for(int i=(m) ; i>=(n) ; i--)

#define All(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

int main(){
   int n;
   cin >> n;
   vector<int> a(n);
   rep(i,n)cin >> a[i];
   sort(All(a));
   cout << a[n-1] - a[0] << endl;
   return 0;
}

Measured memory_bytes: 256
/**
    The problem simply asks you to do the following
    Given array a of n integer
    Divide it into two groups such that
    sum of (xor sum of two groups) is maximized
*/

/**
    overall xor sum is constant
    At first, observe that if the bit of xor sum is 1
    Then, no matter how we divide it
    The result is constant
    So we can simply ignore this
    Solve the rest
    The xor sum of two groups are equal since over all xor sum is 0
    So we can find maximum xor among overall subset
    by the knowledge of basis (Linear algebra!)
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n;
using ll = long long;
ll basis[65];
ll a[maxn];
void ins(ll x){
    for(int i = 61;i>= 0 ;i--){
        if(!((x>>i) & 1)) continue;
        if(basis[i] == -1)
            return (void)(basis[i] = x);
        x ^= basis[i];
    }
}
bool odd[65];

int main(){
    memset(basis,-1LL,sizeof(basis));
    scanf("%d",&n);
    ll xorsum = 0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        xorsum ^= a[i];
    }
    ll oddsum = 0;
    for(int i=60;i>=0;i--){
        if((xorsum >> i) & 1){
            odd[i] = true;
            oddsum ^= (1LL << i);
        }
    }
    for(int i=60;i>=0;i--){
        if(!odd[i]) continue;
        for(int j=1;j<=n;j++){
            if((a[j] >> i) &1)
                a[j] ^= (1LL << i);
        }
    }
    for(int i=1;i<=n;i++){
        ins(a[i]);
    }
    ll ans = 0;
    for(int i=60;i>=0;i--){
        if( (ans >>i) & 1)continue;
        if(basis[i] != -1) ans ^= basis[i];
    }
    ans <<= 1;
    printf("%lld\n",ans+oddsum);
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;




int main(){
    int h,w,n;cin >> h >> w >> n;
    int sr,sc;cin >> sr >> sc;
    string s,t;cin >> s >> t;
    int l = 0, r = w + 1;
    for (int i = n-1; i >= 0; i--) {
        if(t[i] == 'L') r = min(r+1,w+1);
        else if(t[i] == 'R') l = max(0,l-1);
        if(s[i] == 'R') r--;
        else if(s[i] == 'L') l++;
        if(r<=l+1){
            puts("NO");
            return 0;
        }
    }
    if(sc <= l || r <= sc){
        puts("NO");
        return 0;
    }
    l = 0, r = h + 1;
    for (int i = n-1; i >= 0; i--) {
        if(t[i] == 'U') r = min(r+1,h+1);
        else if(t[i] == 'D') l = max(0,l-1);
        if(s[i] == 'D') r--;
        else if(s[i] == 'U') l++;
        if(r<=l+1){
            puts("NO");
            return 0;
        }
    }
    if(sr <= l || r <= sr){
        puts("NO");
        return 0;
    }
    puts("YES");
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vdb = vector<db>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007; 

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

int main(){
  ll n;
  cin >> n;
  ll ans = 1;
  while(ans <= n) ans *= 2;
  ans--;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#define llint long long

using namespace std;

llint n;
multiset<llint> S, rem;

int main(void)
{
	cin >> n;
	llint a;
	for(int i = 1; i <= n; i++){
		cin >> a;
		rem.insert(a);
	}
	for(int i = 1; i < 33; i++) S.insert(1LL<<i);
	
	llint ans = 0;
	while(rem.size() >= 2){
		auto p = rem.end();
		p--;
		llint x = *p;
		rem.erase(p);
		
		llint y = *(S.upper_bound(x))-x;
		auto q = rem.lower_bound(y);
		if(q != rem.end() && *q == y){
			ans++;
			rem.erase(q);
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 9600
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);
//aryread!string();
//auto PS = new Tuple!(long,string)[](M);
//x[]=1;でlong[]全要素1に初期化
void main()
{
    auto N = lread();
    auto S = new long[](N);
    foreach (i; 0 .. N)
    {
        auto s = lread();
        S[i] = s;
    }
    // writeln(S);
    if (func(S))
    {
        writeln(0);
        return;
    }
    long sum_S = sum(S);
    // writeln(sum_S);
    // S.sort().writeln();
    S.sort();
    if (sum_S % 10 == 0)
    {
        sum_S -= func2(S);
    }
    writeln(sum_S);

}
//全部10の倍数
bool func(long[] S)
{
    foreach (i; 0 .. (S.length))
    {
        if (S[i] % 10 == 0)
        {
            continue;
        }
        else
        {
            return false;
        }
    }
    return true;
}
//sort(S)の中で一番小さいS[i]%10!=0
long func2(long[] S)
{
    foreach (i; 0 .. (S.length))
    {
        if (S[i] % 10 != 0)
        {
            return S[i];
        }
    }
    return 0;
}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}

void arywrite(T)(T a)
{
    a.map!text.join(' ').writeln;
}


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

vector<int> v;
vector<int> vv;

int main(){
	int n,m;
	cin>>n>>m;
	int mm=m;
	while(m--){
		int tmp;
		cin>>tmp;
		v.push_back(tmp);
	}
	sort(v.begin(),v.end());
	for(int i=0;i<mm-1;i++){
		vv.push_back(abs(v[i+1]-v[i]));
		
	}
	sort(vv.begin(),vv.end());
	long long ans=0;
	for(int i=0;i<mm-n;i++){
		ans+=vv[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1400
#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;

int main(int argc, char const *argv[]) {
	int n; cin>>n;
	vector<ll> a(3*n);
	rep(i,3*n) cin>>a[i];

	priority_queue<ll, vector<ll>, greater<ll>> left;
	priority_queue<ll> right;

	vector<ll> sl(3*n), sr(3*n);
	sl[0]=a[0];
	left.push(a[0]);
	sr[3*n-1]=a[3*n-1];
	right.push(a[3*n-1]);

	for (int i = 1; i < n; ++i) {
		left.push(a[i]);
		sl[i] = sl[i-1]+a[i];
	}
	for (int i = n; i < 3*n; ++i) {
		ll x = left.top();
		sl[i]=sl[i-1];
		if (a[i]>x) {
			sl[i]-=x; sl[i]+=a[i];
			left.pop();
			left.push(a[i]);
		}
	}

	for (int i = 3*n-2; i >= 2*n; --i) {
		right.push(a[i]);
		sr[i] = sr[i+1]+a[i];
	}
	for (int i = 2*n-1; i >= 0; --i) {
		ll x = right.top();
		sr[i]=sr[i+1];
		if (a[i]<x) {
			sr[i]-=x; sr[i]+=a[i];
			right.pop();
			right.push(a[i]);
		}
	}

	ll ans = -LINF;

	
	

	for (int i = n-1; i < 2*n; ++i) {
		ans = max(ans,sl[i]-sr[i+1]);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 9588
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, v[50];
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(v, v + n);
    double val1 = v[0], val2 = v[n-1];
    for(int i = 1; i < n; i++){
        val1 = (val1 + v[i]) / 2;
    }
    for(int i = n-2; i >= 0; i--){
        val2 = (val2 + v[i]) / 2;
    }
    cout << max(val1, val2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define mod 1000000007
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static int buf[20],len; len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10;
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('\n');}
inline void writesp(ll x){write(x); putchar(' ');}
int fa[2*maxn],cnt0[maxn],cnt1[maxn];
int n;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
	n=read();
	for(int i=1;i<=200000;i++)fa[i]=i;
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		fa[find(x)]=find(y+100000);
	}
	// for(int i=1;i<=10;i++)
	// 	printf("%d %d\n",i,find(i));
	for(int i=1;i<=100000;i++)
		++cnt0[find(i)];
	for(int i=100001;i<=200000;i++)
		++cnt1[find(i)];
	ll sum=0;
	for(int i=1;i<=200000;i++)
		sum+=(ll)cnt0[i]*cnt1[i];
	writeln(sum-n);
	return 0;
}

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

typedef long long int ll;

const ll inf = ll(1e18) + 1;

int main() {
  ll n, k;

  cin >> n >> k;
  vector<ll> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  sort(a.begin(), a.end());
  ll l = -inf;
  ll r = inf;

  while(l + 1 < r) {
    ll x = (l + r) / 2;
    ll t = 0;
    for(ll i = 0; i < n; i++) {
      if (a[i] < 0) {
        ll l2 = -1;
        ll r2 = n;
        while (l2 + 1 < r2) {
          ll x2 = (l2 + r2) / 2;
          if (a[i] * a[x2] < x) {
            r2 = x2;
          } else {
            l2 = x2;
          }
        }
        t += n - r2;
      } else {
        ll l2 = -1;
        ll r2 = n;
        while (l2 + 1 < r2) {
          ll x2 = (l2 + r2) / 2;
          if (a[i] * a[x2] < x) {
            l2 = x2;
          } else {
            r2 = x2;
          }
        }
        t += r2;
      }
      if (a[i] * a[i] < x) t -= 1;
    }

    if (t / 2 < k) {
      l = x;
    } else {
      r = x;
    }
  }
  cout << l << endl;

  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
using ll = long long;
using namespace std;
const int INF = 1e9;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    rep(i, H) cin >> s[i];

    vector<vector<int>>
        r(H, vector<int>(W)),
        l(H, vector<int>(W)),
        u(H, vector<int>(W)),
        d(H, vector<int>(W));

    rep(i, H) {
        int now = 0;
        rep(j, W) {
            if (s[i][j] == '#')
                now = 0;
            else
                ++now;
            l[i][j] = now;
        }
    }

    rep(i, H) {
        int now = 0;
        for (int j = W - 1; j >= 0; --j) {
            if (s[i][j] == '#')
                now = 0;
            else
                ++now;
            r[i][j] = now;
        }
    }

    rep(i, W) {
        int now = 0;
        rep(j, H) {
            if (s[j][i] == '#')
                now = 0;
            else
                ++now;
            u[j][i] = now;
        }
    }

    rep(i, W) {
        int now = 0;
        for (int j = H - 1; j >= 0; --j) {
            if (s[j][i] == '#')
                now = 0;
            else
                ++now;
            d[j][i] = now;
        }
    }

    int ans = 0;
    rep(i, H) rep(j, W)
        ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3);

    cout << ans << endl;

    return 0;
}

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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n, a, b; cin >> n >> a >> b;
    ll rep = n / (a + b);
    ll rem = n % (a + b);
    ll ans = rep * a + min(a, rem);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
 
int main(){
    string s;
    getline(cin, s);
    char c;
    for(int i=0;i<s.size();i++){
        c = s[i];
        if('a' <= c && c <= 'z'){
            cout << char(c-32);
        }else if('A' <= c && c <= 'Z'){
            cout << char(c+32);
        }else{
            cout << c;
        }
    }
    cout << endl;
}


Measured memory_bytes: 3220
/**
 *   @author: pr4shan7 (प्रशांत)
 */
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // cout << fixed;
    // cout << setprecision (6);

    int n, m;
    cin >> n >> m;
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        pq.push(temp);
    }

    while (m) {
        int a = pq.top();
        pq.pop();
        pq.push(a >> 1);
        m--;
    }

    long long sum = 0;
    while (!pq.empty()) {
        sum += pq.top();
        pq.pop();
    }

    cout << sum << '\n';
    return 0;
}


Measured memory_bytes: 892
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

// rep(i, 100) { cout << i << endl; } => 0 1 2 ... 99
#define rep(i, n) for(int i = 0, i##_len = (n); i < (int)n; i++)

// std::sort(all(v));
#define all(x) (x).begin(), (x).end()

// long long int
using ll = long long;

// utility to cast return value of size function to int
#define SZ(x) ((int)(x).size())

// VS defines "_DEBUG" macro when debug configuration.
#if _DEBUG
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define dump(x)
#define debug(x)
#endif

// update max
template<class T>bool chmax(T & prov, const T & cur)
{
	if (cur > prov)
	{
		prov = cur;
		return true;
	}
	return false;
}

// update min
template<class T>bool chmin(T & prov, const T & cur)
{
	if (cur < prov)
	{
		prov = cur;
		return true;
	}
	return false;
}

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

	double sum = 0.0f;
	rep(i, N)
	{
		sum += 1.0 / A[i];
	}

	double ans = 1.0 / sum;

	printf("%.6lf\n", ans);

	// cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e17;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define RFOR(i, a, b) for(ll i = (a); i > b; i--)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define RREP(i, n) for(ll i = n-1; i > -1; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back
#define epb emplace_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    const ll mod = 1e9+7;
    
    ll N; cin >> N;
    vl C(N); REP(i, N) cin >> C[i];
    
    vvl places(2*1e5+100);
    REP(i, N) places[C[i]].pb(i);
    
    vl dp(N+1, 0); dp[0] = 1;
    REP(i, N){
        // no operation
        dp[i+1] = dp[i];
        
        // operation
        ll c = C[i];
        ll idx = lower_bound(places[c].begin(), places[c].end(), i) - places[c].begin();
        if(idx > 0){
            ll j = places[c][idx-1];
            if(i - j > 1) dp[i+1] += dp[j+1];
        }
        
        dp[i+1] %= mod;
    }
    cout << dp[N] << endstr;
    return 0;
}


Measured memory_bytes: 14336
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>

using namespace std;

int main()
{
    int n;
    double resu;
    cin>>n;
    if(n%2==0){
        resu = (double)n / 2 / (double)n;
    }
    else{
        resu = (n/2+1)/double(n);
    }
    cout<<resu;
}


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

int main(){
	int a, b;
	cin >> a >> b;
	if((a+b)%2 == 0 ){
		int k = (a + b) / 2;
		cout << k <<endl;
	}else{
		cout << "IMPOSSIBLE" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def ww(a,b):
	return (a+b-1)//b

def main():
	n = int(input())
	a, t = IN()
	for _ in range(n-1):
		ap, tp = IN()
		aa=ww(a,ap)
		ta=ww(t,tp)
		rr=max(aa,ta)
		a,t=ap*rr, tp*rr
	return a+t
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 39280
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define endl '\n'

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,w;
    cin>>n>>w;

    ll weight[n],value[n];
    for(ll j=0;j<n;j++)
    {
        cin>>weight[j]>>value[j];
    }

    ll dp[n+1][w+1];

    for(ll j=0;j<=n;j++)
    {
        for(ll k=0;k<=w;k++)
        {
            if(j==0 || k==0)
            {
                dp[j][k]=0;
            }
            else if(weight[j-1]>k)
            {
                dp[j][k]=dp[j-1][k];
            }
            else{
                dp[j][k]=max(dp[j-1][k-weight[j-1]]+value[j-1],dp[j-1][k]);
            }
            //cout<<dp[j][k]<<" ";
        }
        //cout<<endl;
    }

    cout<<dp[n][w]<<endl;
    return 0;
}


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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int a, b, c, k, ans = 0;

    cin >> a >> b >> c >> k;

    vector<unsigned long long int> ac;

    ac.push_back(a);
    ac.push_back(a + b);
    ac.push_back(a + b + c);

    if (k <= ac[0])
    {
        ans+=k;
    }
    else if (k > ac[0] and k <= ac[1])
    {
        ans+=a;
    }
    else if (k > ac[1] and k <= ac[2])
    {
        ans+=a;
        k-=(b+a);
        ans-=k;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

long shift(const vector<long>& A, long b)
{
  return accumulate(A.begin(), A.end(), 0l, [b](auto v, auto a) {
      return v + labs(a - b);
  });
}

int main()
{
  int N;
  cin >> N;
  vector<long> A(N, 0);
  long sum = 0;
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
    A[i] -= i + 1;
    sum += A[i];
  }

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

  long lower = A[A.size() / 2];
  long upper = A[(A.size() + 1) / 2];
  cout << min(shift(A, upper), shift(A, lower)) << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <deque>
#include <array>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define range(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define all(x) x.begin(), x.end()
#define PI 3.1415926536

using namespace std;

const int MAX_N = 5000;
array<int, MAX_N + 1> bit;
int sets, n;

int sum(int i){
  int ret = 0;
  while(i > 0){
    ret += bit[i];
    i -= i & -i;
  }
  return ret;
}

void add(int i, int x){
  while(i <= n){
    bit[i] += x;
    i += i & -i;
  }
}

void solve(){
  cin >> n;
  if(n == 0) exit(0);
  bit.fill(0);
  for (int i = 1; i <= n; ++i) {
    int t; cin >> t;
    add(i, t);
  }

  int ans = -1e9;
  for (int i = 0; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      ans = max(ans, sum(j) - sum(i));
    }
  }
  cout << ans << endl;
}

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

  for(;;) solve();

  return 0;
}

Measured memory_bytes: 1212
import sys

file_input = sys.stdin

NM = file_input.readline()

import itertools, bisect

while NM != '0 0\n':
    N, M = map(int, NM.split())
    P = [int(file_input.readline()) for i in range(N)]
    P.append(0)
    scores = map(sum, itertools.combinations_with_replacement(P, 2))
    scores = list(set(scores))
    scores.sort()
    ans = []
    for s1 in scores:
        rest = M - s1
        i = bisect.bisect_right(scores, rest)
        if i:
            ans.append(s1 + scores[i - 1])
    print(max(ans))
    NM = file_input.readline()

Measured memory_bytes: 72968
#include<iostream>
#include<string>
using namespace std;
int main(){
	int s,h,m;
	cin>>s;
	h=s/3600;
	s-=s/3600*3600;
	m=s/60;
	s-=s/60*60;
	cout<<h<<":"<<m<<":"<<s<<endl;
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <cctype>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <set>
#include <deque>
#include <map>
#include <bitset>
#include <functional>
#include <cmath>

#define INF 1000000000
using namespace std;

map< long long, long long > prime_factor(long long n) {
  map< long long, long long > ret;
  for(long long i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}


int main() {
    long long n; cin >> n;
    map<long long, long long> m = prime_factor(n);


	long long ans = 0;
	for(auto mm : m){
		//cout << mm.first << " " << mm.second << endl;
		long long k = mm.second; 
		for(long long i = 1;; i++){
			if(i*i + i > 2*k){
				ans += i-1;
				break;
			}
		}
	}

	cout << ans << endl;
}

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

int main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n,k; cin >> n >> k;
  vector<long long> tab(n);
  for(int i = 0; i < n; i++) cin >> tab[i];
  vector<long long> dp(n);

  dp[0] = 0;
  for(int i = 1; i < n; i++){
    dp[i] = (long long)1e18;
    for(int j = i - 1; j >= max(0,i-k); j--){
      //cout << j << " " << " " << abs(tab[i] - tab[j]) << " " << tab[i] << " " << tab[j] <<   endl;
      dp[i] = min(dp[i],dp[j] + abs(tab[i] - tab[j]));
    }
    //cout << endl;
  }

  //for(int i = 0; i < n; i++) cout << dp[i] << " ";
  //return 0;

  cout << dp[n-1];
}


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

using namespace std;
typedef long long ll;
int main() {
  double N; cin >> N;
  vector<double> t(5);
  for (ll j=0; j < 5; ++j) cin >> t[j];
  ll time;
  sort(t.begin(), t.end());
  if (t[0] >= N) {
    time = 5;
  } else {
    time = static_cast<ll>(ceil(N/t[0])) + 4;
  }
  cout << time << endl;
  return 0;
}


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

const long long STATE_MAX = 1<<17;
long long dp[41][STATE_MAX];

int main(){
    long long i, j, k;
    long long N, X, Y, Z;
    cin >> N >> X >> Y >> Z;
    long long MOD = 1e9+7;
    long long state = 1<<(X+Y+Z);
    
    dp[0][0] = 1;
    for(i=0; i<N; i++){
        for(j=0; j<state; j++){
            for(k=1; k<=10; k++){
                long long nb = ((j<<k) + (1<<(k-1))) % state;
                if( nb>>(Z-1)     & 1 == 1 &&
                    nb>>(Y+Z-1)   & 1 == 1 &&
                    nb>>(X+Y+Z-1) & 1 == 1){
                        continue;
                }
                dp[i+1][nb] += dp[i][j];
                dp[i+1][nb] %= MOD;
            }
        }
    }
    long long sum = 1;
    for(i=0; i<N; i++){
        sum *= 10;
        sum %= MOD;
    }
    for(j=0; j<state; j++){
        sum = (sum - dp[N][j] + MOD) % MOD;
    }
    cout << sum << endl;
    return 0;
}

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

using namespace std;

int main() {
  int K;
  string S;
  cin >> K >> S;
  if (K < static_cast<int>(S.size())) {
    S = S.substr(0, K) + "...";
  }
  cout << S << endl;
  return 0;
}


Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define RREP(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

int main(){
    string a,b,c;
    cin >> a >> b >> c;
    if(b.front()==a.back()&&c.front()==b.back()){
        put("YES");
    }else{
        put("NO");
    }
    return 0;
}


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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;

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

    int n;
    float t, a, h[1100];

    cin >> n >> t >> a;
    REP(i, n)
    cin >> h[i];

    float diff = 1e9;
    int res = 0;

    REP(i, n)
    {
        float d = abs(a - (t - h[i] * 0.006));

        diff = min(diff, d);

        if (diff == d)
        {
            res = i + 1;
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<complex>
#include<unordered_map>
#define deg(x) cout<<#x<<"="<<x<<endl;
#define fd(x) for(int i=0;i<x;i++)
#define fdd(a,x) for(int i=a;i<x;i++)
#define fx(x,n) for(int i=n-1;i>=x;i--)
#define mst(x) memset(x,0,sizeof(x));
#define fi first
#define se second
#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ok "ok"
#define HH puts("");
#define ls rt<<1
#define rs rt<<1|1
#define pb(a,b) a.push_back(b);
#define FIN  freopen("1.in","r",stdin);
#define FOUT freopen("1.out","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> pss;
typedef unsigned long long ull;
const ll mod=1e18;
const ll inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);

int a[50]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main(){
    TB
    int n;
    cin>>n;
    cout<<a[n-1]<<'\n';
    return 0;
}


Measured memory_bytes: 256