akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define neko 500010
#define feko 2000010
#define pb push_back
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-(i)))
#define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v)
using namespace std;
vector<int>vec;
struct node
{int v,nex;}e[neko<<1];	
int n,k,t,p[neko],q[neko],dgr[neko],head[neko],ans[neko],inf=0x3f3f3f3f;
int Min[feko];
int cmin(int x,int y)
{return x<y?x:y;}
int cmax(int x,int y)
{return x>y?x:y;}
void add(int x,int y){e[++t].v=y,e[t].nex=head[x],head[x]=t;}
namespace Seg_Tree
{
	#define mid ((l+r)>>1)
	#define ori tagl,tagr
	#define lson root<<1,l,mid
	#define rson root<<1|1,mid+1,r
	void pushup(int root)
	{Min[root]=cmin(Min[root<<1],Min[root<<1|1]);}
	void update(int root,int l,int r,int tag,int x)
	{
		if(l==r){Min[root]=x;return;}
		if(tag<=mid)update(lson,tag,x);
		else update(rson,tag,x);
		pushup(root);
	}
	int query(int root,int l,int r,int tagl,int tagr)
	{
		if(l>=tagl&&r<=tagr)return Min[root];
		int tmp=inf;
		if(tagl<=mid)tmp=query(lson,ori);
		if(tagr>mid)tmp=cmin(tmp,query(rson,ori));
		return tmp;
	}
}
void topsort()
{
	priority_queue<int,vector<int>,greater<int> >q;int u,num=0;
	f(i,1,n)if(!dgr[i])q.push(i);
	while(!q.empty())
	{
		u=q.top(),q.pop();
		ans[u]=++num;
		travel(i,u,v)if(!(--dgr[v]))q.push(v);
	}
	f(i,1,n)printf("%d\n",ans[i]);
}
int main()
{
	using namespace Seg_Tree;
	int x=0x3f3f3f3f,y=0x3f3f3f3f;
	scanf("%d%d",&n,&k);
	f(i,1,n)scanf("%d",&p[i]),q[p[i]]=i;
	memset(Min,0x3f,sizeof Min);
	rf(i,n,1)
	{
		if(q[i]>1)
		{
			x=query(1,1,n,cmax(1,q[i]-k+1),q[i]-1);
			if(x^inf)add(q[i],q[x]),++dgr[q[x]];
		}
		if(q[i]<n)
		{
			y=query(1,1,n,q[i]+1,cmin(q[i]+k-1,n));
			if(y^inf)add(q[i],q[y]),++dgr[q[y]];
		}
		update(1,1,n,q[i],i);
	}return topsort(),0;
}

Measured memory_bytes: 28928
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NIL -1

struct Node{
    int num;
    struct Node* left;
    struct Node* right;
};

struct Node* root;

void insert(int num, struct Node* n){
    if(root == NULL){
        root = (Node*) malloc(sizeof(struct Node));
        root->num = num;
        root->left = NULL;
        root->right = NULL;
        return;
    }

    if(num < n->num){
        if(n->left == NULL){
            n->left = (Node*) malloc(sizeof(struct Node));
            n->left->num = num;
            n->left->left = NULL;
            n->left->right = NULL;
        }else{
            insert(num, n->left);
        }
    }else{
        if(n->right == NULL){
            n->right = (Node*) malloc(sizeof(struct Node));
            n->right->num = num;
            n->right->left = NULL;
            n->right->right = NULL;
        }else{
            insert(num, n->right);
        }
    }
}

void print_middle(struct Node* n){
    if(n == NULL){
        return;
    }
    print_middle(n->left);
    printf(" %d", n->num);
    print_middle(n->right);
}

void print_before(struct Node* n){
    if(n == NULL){
        return;
    }
    printf(" %d", n->num);
    print_before(n->left);
    print_before(n->right);
}

void init(){
    root = NULL;
}

int main(void){
    init();

    int N;
    scanf("%d", &N);

    for(int i = 0; i < N; i++){
        char comm[100];
        int num;
        scanf("%s", comm);

        if(comm[0] == 'i'){
            scanf("%d", &num);
            insert(num, root);
        }else if(comm[0] == 'p'){
            print_middle(root);
            printf("\n");
            print_before(root);
            printf("\n");
        }
    }
}




Measured memory_bytes: 18308
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
struct edge { ll to, cap, rev; };//ikisaki youryou gyakuhen
#define MAX 200
vector<vector<edge> >G(MAX);//[MAX];
vector<bool>used(MAX);//[MAX];
void add_edge(ll from, ll to, ll cap){
	edge q={to,cap,ll(G[to].size())};
    G[from].push_back(q);
	q={from,0,ll(G[from].size()-1)};
    G[to].push_back(q);
}

ll dfs(ll v, ll t, ll f) {
    if(v == t) return f;
    used[v] = 1;
    for(int i = 0 ; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(used[e.to] || e.cap <= 0) continue;
        ll d = dfs(e.to, t, min(f, e.cap));
        if(d > 0){
            e.cap -= d;
            G[e.to][e.rev].cap += d;
            return d;
        }
    }
    return 0;
}
ll ford_fulkerson(ll s, ll t) {//from s to t
    ll flow = 0, f;
    while(1){
		used=vector<bool>(MAX,false);
        f = dfs(s, t, inf);
        if(f == 0) return flow;
        flow += f;
    }
}
int gcd(int a,int b){
	if(a<b)swap(a,b);
	if(b==0)return a;
	return gcd(b,a%b);
}
int main(){
	ll n,m;
	map<string,int>ma;
	ma["Sunday"]=0;
	ma["Monday"]=1;
	ma["Tuesday"]=2;
	ma["Wednesday"]=3;
	ma["Thursday"]=4;
	ma["Friday"]=5;
	ma["Saturday"]=6;
	while(cin>>n>>m,n+m){
		rep(i,MAX)G[i].clear();
		ll s=n+7,t=s+1;
		ll out=0;
		rep(i,n){
			ll c,d;
			cin>>c>>d;
			out+=c;
			add_edge(s,i,c);
			rep(j,d){
				string ss;
				cin>>ss;
				add_edge(i,n+ma[ss],m);
			}
		}
		rep(i,7)add_edge(n+i,t,m);
		if(ford_fulkerson(s,t)==out)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

Measured memory_bytes: 1380
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		int[][] map =new int[3][N];
		int[] cc = new int[N-1];
		int s= 0;

		for(int i=0;i<2;i++) {
			for(int j=0;j<N;j++) {
				map[i][j]=sc.nextInt();
			}
		}
		for(int i=0;i<N-1;i++) {
			cc[i]=sc.nextInt();
		}

		for(int i=0;i<N;i++) {
			s+=map[1][map[0][i]-1];
			if(i>0) {
				int c = map[0][i]-map[0][i-1];
				if(c==1) {
					s+=cc[map[0][i-1]-1];
				}
			}
		}
		System.out.println(s);
	}
}

Measured memory_bytes: 21716
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

char adv(char x, int n) {
  string t = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  int p    = distance(t.begin(), find(all(t), x));
  return t[(p - n + t.size()) % t.size()];
}

void solve() {
  int n;
  while (cin >> n, n) {
    vi k(n);
    rep(i, n) cin >> k[i];
    string s;
    cin >> s;
    rep(i, s.size()) s[i] = adv(s[i], k[i % n]);
    cout << s << endl;
  }
}

Measured memory_bytes: 3192
#include<iostream>
#include<string>
using namespace std;
int main(){
  string PS;
  int n,cnt=0;
  string rings;
  cin >> PS >> n;
  for(int i=0;i<n;i++){
    cin >> rings;
    rings=rings+rings;
    if(rings.find(PS)!=string::npos)cnt++;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 1212
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
int main(){
    int a,b,c;
    while(~scanf("%d %d %d",&a,&b,&c)){
        if(a+c==2*b) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007

char ch[1001][1001];
int dp[1001][1001];

int main()
{
	int h,w;
	cin>>h>>w;
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			cin>>ch[i][j];
		
	for(int i=0;i<=h;i++)
		dp[i][0]=0;
	for(int i=0;i<=w;i++)
		dp[0][i]=0;
	
	
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(ch[i-1][j-1]=='#')
				dp[i][j]=0;
			if(i==1&&j==1)
				dp[i][j]=1;
			else if(ch[i-1][j-1]=='.')
			{
				(dp[i][j]=dp[i][j-1]+dp[i-1][j])%=mod;
			}
		}
	}
	cout<<dp[h][w]%mod;
	
	
}

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
struct state{int x,y,d,dir;}st[5][11001];
char s[110001],t[110001];
int n,m,q,sl[110001][2],sr[110001][2],tl[110001][2],tr[110001][2],ex,ey,sx,sy,ans,cnt[5];
void go(int id,int x,int y,int d,bool ns)
{
	if(ns)
		if(t[y]=='S')
		{
			if(sr[x][0])st[id][cnt[id]++]={sr[x][0],y,d+sr[x][0]-x,ns};
			if(sr[x][1])st[id][cnt[id]++]={sr[x][1],y,d+sr[x][1]-x,ns};
			if(ex>x)
			{
				if(ey==y)ans=min(ans,d+ex-x);
				if(int z=sr[ex-1][ey>y])st[id][cnt[id]++]={z,y,d+z-x,ns};
			}
		}
		else
		{
			if(sl[x][0])st[id][cnt[id]++]={sl[x][0],y,d+x-sl[x][0],ns};
			if(sl[x][1])st[id][cnt[id]++]={sl[x][1],y,d+x-sl[x][1],ns};
			if(ex<x)
			{
				if(ey==y)ans=min(ans,d+x-ex);
				if(int z=sl[ex+1][ey>y])st[id][cnt[id]++]={z,y,d+x-z,ns};
			}
		}
	else if(s[x]=='E')
	{
		if(tr[y][0])st[id][cnt[id]++]={x,tr[y][0],d+tr[y][0]-y,ns};
		if(tr[y][1])st[id][cnt[id]++]={x,tr[y][1],d+tr[y][1]-y,ns};
		if(ey>y)
		{
			if(ex==x)ans=min(ans,d+ey-y);
			if(int z=tr[ey-1][ex>x])st[id][cnt[id]++]={x,z,d+z-y,ns};
		}
	}
	else
	{
		if(tl[y][0])st[id][cnt[id]++]={x,tl[y][0],d+y-tl[y][0],ns};
		if(tl[y][1])st[id][cnt[id]++]={x,tl[y][1],d+y-tl[y][1],ns};
		if(ey<y)
		{
			if(ex==x)ans=min(ans,d+y-ey);
			if(int z=tl[ey+1][ex>x])st[id][cnt[id]++]={x,z,d+y-z,ns};
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>q>>(s+1)>>(t+1);
	for(int i=2;i<=n;i++){sl[i][0]=sl[i-1][0];sl[i][1]=sl[i-1][1];sl[i][s[i-1]=='E']=i-1;}
	for(int i=2;i<=m;i++){tl[i][0]=tl[i-1][0];tl[i][1]=tl[i-1][1];tl[i][t[i-1]=='S']=i-1;}
	for(int i=n-1;i;i--){sr[i][0]=sr[i+1][0];sr[i][1]=sr[i+1][1];sr[i][s[i+1]=='E']=i+1;}
	for(int i=m-1;i;i--){tr[i][0]=tr[i+1][0];tr[i][1]=tr[i+1][1];tr[i][t[i+1]=='S']=i+1;}
	while(q--)
	{
		cin>>sx>>sy>>ex>>ey;
		ans=1<<30;
		memset(cnt,0,sizeof cnt);
		go(0,sx,sy,0,0);
		go(0,sx,sy,0,1);
		for(int i=0;i<4;i++)
			for(int j=0;j<cnt[i];j++)go(i+1,st[i][j].x,st[i][j].y,st[i][j].d,st[i][j].dir^1);
		cout<<(ans==(1<<30)?-1:ans)<<'\n';
	}
}


Measured memory_bytes: 5504
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[100004];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        a[k]=i;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}


Measured memory_bytes: 1152
// c++ -std=c++14 atcoder.cpp
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>

using namespace std;

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

    int n = s.size();
    for (int i = 0; i < (n-1)/2; i++) {
        if (s[i] != s[n-1-i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    for (int i = 0; i <= (n-3)/4; i++) {
        if (s[i] != s[(n-1)/2-1-i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    for (int i = (n+3)/2-1; i < n; i++) {
        if (s[i] != s[n-1-i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    use std::collections::HashMap;
    let mut p_q: HashMap<(i32, i32), usize> = HashMap::new();
    let N: usize = read();
    let mut input: Vec<(i32, i32)> = vec![];
    for _ in 0..N {
        input.push((read(), read()));
    }
    for &(x1, y1) in &input {
        for &(x2, y2) in &input {
            if x1 == x2 && y1 == y2 {
                continue;
            }
            let entry = p_q.entry((x1 - x2, y1 - y2)).or_insert(0);
            *entry += 1;
        }
    }
    let mut ans = 0;
    for (_key, v) in p_q {
        ans = std::cmp::max(v, ans);
    }
    println!("{}", N - ans);
}


Measured memory_bytes: 2244
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)
import Data.Char
import Data.List

main = do
  input <- BC.getLine
  let x = map digitToInt . BC.unpack $ input
  print $ solve x

solve :: [Int] -> Int
solve x
  | length x == 1 = 1
  | mod (length x) 2 == 0 = let n = length x
                                mid = div n 2
                                left = reverse $ take mid x
                                right = drop mid x
                            in (div n 2) + (solve' (head left) left right)
  | otherwise    = let n = length x
                       mid = div n 2
                       left = reverse $ take mid x
                       right = drop (mid+1) x
                   in 1 + (div n 2) + (solve' (x !! mid) left right)

solve' :: Int -> [Int] -> [Int] -> Int
solve' n []     []     = 0
solve' n (l:ls) (r:rs)
  | n == r && l == r = 1 + (solve' n ls rs)
  | otherwise        = 0


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

int main()
{
	int n, r; cin >> n >> r;
	
	int ans;

	if (10 <= n ) {
		ans = r;
	}
	else {
		ans = r + 100 * (10 - n);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
ll gcd(ll a, ll b){
  if(b == 0){
    return a;
  }
  else{
    return gcd(b,(a%b));
  }
}
ll lcm(ll a,ll b){
  return a/gcd(a,b)*b;
}

int main() {
  int n,m;
  cin>>n>>m;
  int vec[m][2];
  for(int i=0;i<m;i++){
    cin>>vec[i][0]>>vec[i][1];
  }
  int g=0;
  for(int i=0;i<1000;i++){
    string p=to_string(i);
    if(p.size()!=n){
      continue;
    }
    for(int j=0;j<m;j++){
      if(p.size()<vec[j][0]){
        g++;
        continue;
      }
      char h=p.at(vec[j][0]-1);
      string f=to_string(vec[j][1]);
      char z=f.at(0);
      if(h!=z){
        g++;
      }
    }
    if(g==0){
      cout<<i<<endl;
      return 0;
    }
    g=0;
  }
  cout<<-1<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
using ull = unsigned long long;
using ll = long long;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;


int main(){
    int N;
    cin >> N;
    vector<int> S(N);
    for(int i = 0; i < N; i++) cin >> S[i];
    int sum = 0;
    for(int i = 0; i < N; i++) sum += S[i];
    sort(all(S));
    if(sum % 10 == 0){
        for(int i = 0; i < N; i++){
            if(S[i] % 10 != 0){
                sum -= S[i];
                cout << sum << endl;
                return 0;
            }
        }
    }else{
        cout << sum << endl;
        return 0;
    }
    puts("0");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
static const int N = 2010;
static const int INFTY = (1<<21);
int n, M[N][N];
int d[N];
map<int, int> mp;
// vector<int> mp(N, 0);

void bfs(int sv, int n, int X, int Y){
    queue<int> q;
    q.push(sv);
    rep(i, N) d[i] = INFTY;
    d[sv] = 0;
    int u;
    while ( !q. empty() ){
        u = q.front();
        q.pop();
        // for (int v = 0; v < N; v++){
        //     if (M[u][v] == 0) continue;
        //     if (d[v] != INFTY) continue;
        //     d[v] = d[u] + 1;
        //     q.push(v);
        // }
        if (u-1 >= 1) {
            if (d[u-1] == INFTY){
                d[u-1] = d[u] + 1;
                q.push(u-1);
            }
        }
        if (u+1 <= n) {
            if (d[u+1] == INFTY){
                d[u+1] = d[u] + 1;
                q.push(u+1);
            }
        }
        if (u == X) {
            if (d[Y] == INFTY){
                d[Y] = d[u] + 1;
                q.push(Y);
            }
        }
        if (u == Y) {
            if (d[X] == INFTY){
                d[X] = d[u] + 1;
                q.push(X);
            }
        }
    }
    
    rep(i, N) mp[d[i]]++;
}

int main(){

    int n, X, Y;
    cin >> n >> X >> Y;

    // rep(i, n){
    //     rep(j, n){
    //         M[i][j] = 0;
    //     }
    // }

    // for(int i = 1; i < n; i++){
    //     M[i-1][i] = 1;
    //     M[i][i-1] = 1;
    // }
    // M[X-1][Y-1] = 1;
    // M[Y-1][X-1] = 1;

    // rep(sv, n) bfs(sv, n, X, Y);
    for(int sv = 1; sv <= n; sv++){
        bfs(sv, n, X, Y);
    }

    for(int i = 1; i < n; i++){
        cout << mp[i] / 2 << endl;
    }
  
    return 0;
}


// #include <bits/stdc++.h>
// #define rep(i,n) for(int i = 0; i < (n); ++i)
// using namespace std;
// typedef long long ll;
// static const int N = 2010;
// static const int INFTY = (1<<21);
// int n, M[N][N];
// int d[N];
// map<int, int> mp;

// void bfs(int s){
//     queue<int> q;
//     q.push(s);
//     rep(i, N) d[i] = INFTY;
//     d[s] = 0;
//     int u;
//     while ( !q. empty() ){
//         u = q.front();
//         q.pop();
//         for (int v = 0; v < N; v++){
//             if (M[u][v] == 0) continue;
//             if (d[v] != INFTY) continue;
//             d[v] = d[u] + 1;
//             q.push(v);
//         }
//     }
    
//     rep(i, N) mp[d[i]]++;
// }

// int main(){

//     int n, X, Y;
//     cin >> n >> X >> Y;

//     int k;

//     rep(i, n){
//         if (i + k <= X - Y + N - 1) mp[k]++;
//         if (i + k < (X + Y) / 2) mp[k] ++;
//         if 
//     }

//     // rep(i, n){
//     //     rep(j, n){
//     //         M[i][j] = 0;
//     //     }
//     // }

//     // for(int i = 1; i < n; i++){
//     //     M[i-1][i] = 1;
//     //     M[i][i-1] = 1;
//     // }
//     // M[X-1][Y-1] = 1;
//     // M[Y-1][X-1] = 1;

//     // rep(i, n) bfs(i);

//     // for(int i = 1; i < n; i++){
//     //     cout << mp[i] / 2 << endl;
//     // }
  
//     return 0;
// }


Measured memory_bytes: 384
function Main(input) {
  input = input.split(" ").map(Number);
  var sum = 0;
  if(input[0]<4){
    sum += (4-input[0])*100000;
  }
  if(input[1]<4){
    sum += (4-input[1])*100000;
  }
  if(sum == 600000){
    sum = 1000000;
  }
  console.log(sum);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n, x; cin >> n >> x;
  vector<long long> a(n); REP(i, n) cin >> a[i];
  long long ans = 0;
  if (a[0] > x) {
    ans += a[0] - x;
    a[0] = x;
  }
  FOR(i, 1, n) {
    if (a[i-1] + a[i] > x) {
      ans += a[i-1] + a[i] - x;
      a[i] = x - a[i-1];
    }
  }
  cout << ans << '\n';
  return 0;
}


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

using namespace std;
int main()
{
    int n,m,i,j,r,k[100],k1[100][100],k2[100],k3[100],sum=0,h=0,sum1=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%d",&k[i]);
        for(j=0;j<k[i];j++)
        {
            scanf("%d",&k1[i][j]);
            k1[i][j]=k1[i][j]-1;
        }
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",&k2[i]);
    }
    for(i=0;i<(1<<n);i++)
    {
        memset(k3,0,sizeof(k3));
        for(j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                k3[j]=1;
            }
        }
        h=0;
        for(j=0;j<m;j++)
        {
            sum=0;
            for(r=0;r<k[j];r++)
            {
                if(k3[k1[j][r]]==1)
                {
                    sum++;
                }
            }
            if(k2[j]==0)
            {
                if(sum%2==1)
                {
                    h=1;
                    break;
                }
            }
            else
            {
                if(sum%2==0)
                {
                    h=1;
                    break;
                }
            }
        }
        if(h==0)
        {
            sum1++;
        }
    }
    printf("%d\n",sum1);
    return 0;
}


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

int a,b,mmh=0;
int main(){
	int i,j;
	scanf("%d%d",&a,&b);
	for (i=0;i<=a;i++)
	for (j=0;j<=a;j++)
	mmh+=i+j<=b&&b-i-j<=a;
	printf("%d\n",mmh);
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	private static final Comparator<int[]> COMPARATOR = new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			int result = -(o1[2] - o2[2]);
			if (result == 0) {
				result = o1[3] - o2[3];
				if (result == 0) {
					result = (o1[0] - o2[0]);
				}
			}
			return result;
		}
	};

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[][] team = new int[300][4];
		int[] count = new int[1000];
		for (int n = in.nextInt(); n > 0; n = in.nextInt()) {
			for (int i = 0; i < n; i++) {
				team[i][0] = in.nextInt();
				team[i][1] = in.nextInt() - 1;
				team[i][2] = in.nextInt();
				team[i][3] = in.nextInt();
			}
			Arrays.sort(team, 0, n, COMPARATOR);
			Arrays.fill(count, 0);
			int selected = 0;
			for (int i = 0; i < n; i++) {
				final int[] t = team[i];
				final int group = t[1];
				if (selected < 10 && count[group] < 3 || selected < 20
						&& count[group] < 2 || selected < 26
						&& count[group] == 0) {
					selected++;
					count[group]++;
					System.out.println(t[0]);
				}
			}
		}
	}
}

Measured memory_bytes: 21060
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

void read();
template<typename First, typename... Rest> void read(First& first, Rest&... rest);
void write();
template<typename First, typename... Rest> void write(First first, Rest... rest);
template<typename T> void write_vec(vector<T>& v, char divider);

int main(){
    int N;
    read(N);
    vector<int> A(N);
    for(int i = 0; i < N; i++){
        read(A[i]);
    }
    vector<pair<int, int>> p(N);
    for(int i = 0; i < N; i++){
        p[i] = make_pair(A[i], i);
    }
    sort(p.begin(), p.end());
    vector<int> ans(N);
    for(int i = 0; i < N; i++){
        ans[i] = p[i].second + 1;
    }
    write_vec(ans, ' ');
    return 0;
}

//配列以外の入力を受け取る
void read(){

}
template<typename First, typename... Rest>
void read(First& first, Rest&... rest){
    cin >> first;
    read(rest...);
}
//
//配列以外を出力する
void write(){

}
template<typename First, typename... Rest>
void write(First first, Rest... rest){
    cout << first << " ";
    write(rest...);
}
//
//配列を区切って出力する
template<typename T>
void write_vec(vector<T>& v, char divider){
    for(size_t i = 0; i < v.size(); i++){
        cout << v[i] << divider;
    }
}
//

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

int main() {
	// your code goes here
	long long n,i,sum=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if(i%5!=0 && i%3!=0)
            sum+=i;
    }
    cout<<sum;
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;

int main(){
	int n,k,q;
	cin >> n >> k >> q;
	int a[q];
	for(int i = 0;i < q;i++){
		cin >> a[i];
	}
	int play[n] = {};
	for(int i = 0;i < q;i++){
		play[a[i]-1]++;
	}
	for(int i = 0;i < n;i++){
		if(q - play[i] < k){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <numeric>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




int main() {
	int r;
	cin >>r;
	
	cout << r*r*3<< endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000001
#define MAXN        400005
#define mod         1000000007
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,x,mx=0,smx=0;
    cin>>n;
    ll a[n];
    map<ll,ll> mp1;
    for(i=0;i<n;i++){
        cin>>a[i];
        mp1[a[i]]++;
        mx=max(mx,a[i]);
    }
    for(i=0;i<n;i++){
        if(a[i]!=mx){
            smx=max(smx,a[i]);
        }
    }
    for(i=0;i<n;i++){
        if(a[i]==mx && mp1[a[i]]==1){
            cout<<smx;
        }
        else{
            cout<<mx;
        }
        cout<<endl;
    }
}


Measured memory_bytes: 10624
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
LL ans,x,pr[100005],sf[100005],co[100005],mul[100005];
int n;
int main()
{
    scanf("%d",&n);
    pr[0]=1,sf[n+1]=1,sf[n+2]=1;
    for(int i=1;i<=n;i++)pr[i]=pr[i-1]*i,pr[i]%=MOD;
    for(int i=n;i>0;i--)sf[i]=sf[i+1]*i,sf[i]%=MOD;
    for(int i=1;i<=n;i++)co[i]=co[i-1]+(pr[i]*sf[i+2]),co[i]%=MOD;
    for(int i=1;i<=(n+1)/2;i++)
    {
        mul[i]+=co[n-i];
        mul[i]+=co[i-1];
        mul[i]%=MOD;
    }
    for(int i=n;i>n/2;i--)mul[i]=mul[n-i+1];
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        ans+=x*pr[n];
        ans%=MOD;
        ans+=x*mul[i];
        ans%=MOD;
    }
    printf("%lld",(ans+MOD*50)%MOD);
}


Measured memory_bytes: 6892
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
using namespace std;
int main() {

	int a, p;
	cin >> a >> p;
	p = p + a * 3;
	cout << (p - (p % 2)) / 2 << endl;
	return 0;

}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    string s;
    while(w > 0){
        if(w % 3 == 0){
            s += '0';
        }
        else if(w % 3 == 1){
            s += '+';
            -- w;
        }
        else{
            s += '-';
            ++ w;
        }
        w /= 3;
    }

    reverse(s.begin(), s.end());
    cout << s << endl;

    return 0;
}

Measured memory_bytes: 3184
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <chrono>
#include <random>
#include <unordered_map>
#include <cassert>
#pragma GCC optimize("O3")
#pragma comment(linker, "STACK:36777216")
using namespace std;
using i64 = int64_t;
constexpr i64 MOD = 1e9 + 7;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
using vi = vector<i64>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ii = pair<i64, i64>;

class Graph {
    int n, max_color;
    vector<int> color;
    bool is_bip = true;
    map<int, int> visited;
    vvi blacks, whites;
    
    void dfs(int v, int c) {
        if (color[v] != -1) {
            if (color[v] != c) is_bip = false;
            return;
        }
        color[v] = c;
        visited.erase(v);
        for (int i: adj[v]) {
            dfs(i, c + 1 - c % 2 * 2);
        }
    }
    
public:
    vvi adj;
    vvi adj_matrix;
    
    Graph(int n) {
        this->n = n;
        adj = vvi(n);
    }
    
    void use_adj_matrix() {
        adj_matrix = vvi(n, vi(n));
    }
    
    void addEdge(int a, int b) {
        assert(0 <= a && a < n);
        assert(0 <= b && b < n);
        if (adj_matrix.size()) {
            adj_matrix[a][b] = 1;
            adj_matrix[b][a] = 1;
        }
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    bool is_bipartite() {
        for (int i = 0; i < n; i++) {
            visited[i] = 1;
        }
        color = vector<int>(n, -1);
        max_color = 0;
        while (visited.size()) {
            int v = (*visited.begin()).first;
            dfs(v, max_color);
            max_color += 2;
        }
        return is_bip;
    }
    
    bool is_connected() {
        color = vector<int>(n, -1);
        dfs(0, 0);
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                return false;
            }
        }
        return true;
    }
    
    vvi get_blacks() {
        blacks = vvi(max_color / 2);
        for (int i = 0; i < n; i++) {
            if (color[i] % 2 == 0) {
                blacks[color[i] / 2].push_back(i);
            }
        }
        return blacks;
    }
    
    vvi get_whites() {
        whites = vvi(max_color / 2);
        for (int i = 0; i < n; i++) {
            if (color[i] % 2 == 1) {
                whites[color[i] / 2].push_back(i);
            }
        }
        return whites;
    }
};


int main() {
    i64 n, m;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g.addEdge(a, b);
    }
    
    g.is_connected();
    if (g.is_bipartite()) {
        vvi blacks = g.get_blacks();
        vvi whites = g.get_whites();
        assert(blacks.size() == 1 && whites.size() == 1);
        cout << i64(blacks.front().size()) * i64(whites.front().size()) - m << endl;
    } else {
        cout << n * (n - 1) / 2 - m << endl;
    }
}


Measured memory_bytes: 11904
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int n,m;
  vector<int> a;
  int ak;
  cin >> n >> m;
  int cnt = 0;
  double sum = 0;
  for(int i=0;i<n;i++){
    cin >> ak;
    a.push_back(ak);
    sum += ak;
  }
  //cout << sum/(4*m) << endl;
  for(int i=0;i<n;i++){
    if(a[i]>=sum/(double)(4*m)){
      
      cnt++;
    }
  }
  if(cnt>=m){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define f(i,s,e) for(ll i=s;i<e;i++)
#define pb(x) push_back(x)
#define mp make_pair
#define mod 1000000007
#define all(x) x.begin(),x.end()
using namespace std;

int main(){
    fast;

    ll wei[101],val[101],sum=0,n,w,ans=INT_MIN;

    cin>>n>>w;

    f(i,0,n)cin>>wei[i]>>val[i];

    f(i,0,n)sum+=val[i];

    ll dp[sum+1];

    for(int i=0;i<=sum;i++)
        dp[i]=1e12;

    dp[0]=0;
    for(ll i=0;i<n;i++){
        for(ll j=sum;j>=0;j--){
            if(j>=val[i]){
                dp[j]=min(dp[j],dp[j-val[i]]+wei[i]);
            }
        }
    }

    for(ll i=0;i<=sum;i++)
        if(dp[i]<=w){
            ans=max(i,ans);
            //cout<<dp[i]<<" "<<i<<endl;
        }
    cout<<ans;
}


Measured memory_bytes: 1024
n = int(input())
l = list(map(int, input().split()))

ans = 1
flg = False
for i in range(n):
    for j in range(i):
        if l[i] >= l[j]:
            flg = True
            continue
        else:
            flg = False
            break
    if flg == True: ans += 1  

print(ans)

Measured memory_bytes: 2940
//“ In order to be irreplaceable, one must always be different”
#include <bits/stdc++.h>
using namespace std;
# define ll long long
#define endl "\n"
# define pi 3.14159265359
#define MOD 1000000007
# define str string
# define vll vector<ll>
# define vstr vector<str>
# define vchar vector<char>
# define pb push_back
# define mll map<ll,ll>
#define mchar map<char, ll>
# define mstr map<str,ll>
# define vp vector< pair<ll,ll> >
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
# define f(x,y) for(int x=0;x<y;x++)
# define r(x,y) for(int x=y;x>=0;x--)
# define loop(x,y,z) for(int x=y;x<z;x++)
ll power(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll logx(ll base, ll num){int cnt=0;while(num!=1){num/=base; ++cnt;}return cnt;}
ll gcd(ll a, ll b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b){
    return (a/gcd(a, b))*b;
}
void print(vll a){
    for(int i=0;i<a.size();i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll x,y;
    cin>>x>>y;
    ll x1=x;
    mll m;
    while(x1>=0){
        ll k=x-x1;
        ll ans=x1*4+k*2;
        m[ans]++;
        x1--;
    }
    if(m.find(y)==m.end()){
        cout<<"No";
    }
    else{
        cout<<"Yes";
    }
    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200025,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int gcd(int x,int y){
	if (!y) return x;
	int r=x%y;
	while (r){
		x=y;y=r;r=x%y;
	}
	return y;
}
int n,a[N],m,h[N];
set<int> ans;
void check(int p){
	for (int i=0;i<p-1;i++) h[i]=0;
	for (int i=0;i<=n;i++){
		int x=i%(p-1);
		h[x]=(h[x]+a[i])%p;
	}
	for (int i=0;i<p-1;i++) if (h[i]) return;
	ans.insert(p);
}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	n=read();m=0;
	for (int i=n;i>=0;i--){
		a[i]=read();
		m=gcd(m,abs(a[i]));
	}
	for (int i=2;i*i<=m;i++)
	if (m%i==0){
		ans.insert(i);
		while(m%i==0) m/=i;
	}
	if (m!=1) ans.insert(m);
	for (int i=2;i<=n;i++)
	if (a[0]%i==0){
		int fl=1;
		 for (int j=2;j*j<=i;j++)
		 if (i%j==0) {fl=0;break;}
		 if (fl) check(i);
	}
	for (auto x : ans) printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 384
/*
(1)for binary shift operator always use 'LL' 1LL<<63

*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set_pair tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define Luv(...) [&] (auto &&u, auto &&v) { return __VA_ARGS__; }
  
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s,t;cin>>s>>t;
	t.pop_back();
	if(s==t)
		cout<<"Yes";
	else cout<<"No";

	return 0;
} 

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7;

int main()
{
	IO_OP;

	int n, ans = 0;
	cin >> n;
	for(int i=1;i<=n;i++)
		if(to_string(i).size()%2)
			ans++;
	cout << ans << endl;
	
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Text;

namespace AtCoder
{
  class Program
  {
    static void Main(string[] args)
    {
      string[] ss = Console.ReadLine().Split(' ');
      int A = int.Parse(ss[0]);
      int B = int.Parse(ss[1]);
      int C = int.Parse(ss[2]);
      int D = int.Parse(ss[3]);
      int low = Math.Max(A, C);
      int high = Math.Min(B, D);
      int l = high - low;

      if(l < 0)
        Console.WriteLine("0");
      else
        Console.WriteLine(l.ToString());
      Console.ReadLine();
    }

  }
}

Measured memory_bytes: 27352
#include <stdio.h>

int main(void) {
	int a,b,c;
	while(scanf("%d%d",&a,&b) != EOF){
		if(a < b){
			c = b;b = a;a = c;
		}
		while(a % b){
			a%=b;c = a;a = b;b = c;
		}
		printf("%d\n",b);
	}
	return 0;
}

Measured memory_bytes: 596
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

using namespace std;

typedef long long ll ;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pair<int,int> > vii;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define mp			make_pair
#define fi			 first
#define se			 second
#define for0(i,n)        for(int i=0;i<n;i++)
#define for1(i,n)        for(int i=1;i<=n;i++)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)    cout<<"Case "<<z<<": "<<x<<"\n"
int gcd(int a, int b){
	while(b){
		int r = a%b;
		a = b;
		b = r;
		}
	return a;
	}
int main()
{
	int i,n,x,ans=0;
	cin>>n;
	vi a(n+5);
	for1(i,n) cin>>a[i];
	vi L(n+5),R(n+5);
	L[0] = 0, R[n+1]=0;
	for(i=1 ; i<=n ; i++) L[i] = gcd(L[i-1],a[i]);
	for(i=n ; i>=1 ; i--) R[i] = gcd(R[i+1],a[i]);
	for1(i,n){
		x = gcd(L[i-1],R[i+1]);
		ans = max(ans,x);
		}
		
	cout<<ans<<nw;
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

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

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

  sort(B, B+N);
  int b = B[N/2];

  long long result = 0;

  for(int i=0; i<N;i++){
    result += abs(A[i] - b - (i+1) );
  }

  cout << result << endl;

  return 0;
}


Measured memory_bytes: 3328
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007

using namespace std;

long long N;

int main(){
	cin >> N;

	vector<long long> cur;
	vector<long long> next;

	for(int i = 0; i < pow(2, N); i++){
		long long tmp;
		cin >> tmp;
		cur.push_back(tmp);
	}

	while(true){
		if(cur.size() == 1){
			cout << cur[0] << endl;
			return 0;
		}
		for(int i = 0; i < cur.size(); i+=2){
			if(cur[i] < cur[i+1]){
				next.push_back(cur[i+1] - cur[i]);
			}else if(cur[i] > cur[i+1]){
				next.push_back(cur[i] - cur[i+1]);
			}else{
				next.push_back(cur[i]);
			}
		}
		swap(next, cur);
		next.clear();
	}





}



Measured memory_bytes: 4336
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
 
int main(){
    vector<int>a(3),b(3);
    cin>>a[0]>>a[1]>>a[2]>>b[0]>>b[1]>>b[2];
    if(a<b)swap(a,b);
    if(make_pair(a[1],a[2])<=make_pair(b[1],b[2]))cout<<a[0]-b[0]<<endl;
    else cout<<a[0]-b[0]+1<<endl;
}

Measured memory_bytes: 3092
#include<stdio.h>
int main(){
int a,b,c,ans=0;
scanf("%d %d %d",&a,&b,&c);
if(a==b&&a!=c) ans=1;

if(a==c&&a!=b) ans=1;

if(b==c&&a!=b) ans=1;

if(ans==0) printf("No");
else printf("Yes");
}

Measured memory_bytes: 128
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]
s = [0] * (n+1)
ans = 0
for i in range(n):
    s[i+1] = s[i] + a[i]
c = Counter(s)
for i in c:
    ans += int(c[i]*(c[i]-1)//2)
print(ans)


Measured memory_bytes: 112976
#include <stdio.h>
#include <stdbool.h>
struct card{char suit, value;} ;
void bubblesort(struct card a[],int n){
    for(int i=0;i<n;i++){
        for(int j=n-1;j>=i;j--){
            if(a[j].value<a[j-1].value){
               struct card t=a[j];a[j]=a[j-1];a[j-1]=t;
            }
        }
    }
}
void selection(struct card a[],int n){
    for(int i=0;i<n;i++){
        int minj=i;
        for(int j=i;j<n;j++){
            if(a[j].value<a[minj].value)
                minj=j;
    }
        struct card t=a[i];a[i]=a[minj];a[minj]=t;
}
}
void print(struct card a[],int n){
    for(int i=0;i<n;i++){
        if(i>0)printf(" ");
        printf("%c%c",a[i].suit,a[i].value);
    }
    printf("\n");
}

bool isstable(struct card c1[],struct card c2[],int n){
    for(int i=0;i<n;i++)
        if(c1[i].suit!=c2[i].suit)
            return false;
    return true;
}

int main(){
    struct card c1[100],c2[100];
    int n;
    int i;
    char copy[100];
   
    scanf("%d\n",&n);
  
    for(i=0;i<n;i++){
        scanf("%s",&copy);
        c1[i].suit=copy[0];
        c1[i].value=copy[1];
       
    }
    for(i=0;i<n;i++)
        c2[i]=c1[i];
    bubblesort(c1,n);
    selection(c2,n);
    
    print(c1,n);
    printf("Stable\n");
    print(c2,n);
    if(isstable(c1,c2,n))
        printf("Stable\n");
    else
        printf("Not stable\n");
  
    }
       
        


Measured memory_bytes: 2108
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!

/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define pii pair<ll,ll>
#define vi(x) vector<x>
#define maxn 100005
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
using namespace __gnu_pbds;

signed main()
{
    fast;
   
    ll n,i,ans=0,sum=0;
    cin>>n;
    ll a[n+2];
    for(i=0;i<n;i++)
    {
    	cin>>a[i];
    	sum = (sum + a[i])%mod;
    }
    for(i=0;i<n;i++)
    {
    	ans = (ans + (a[i] * (sum-a[i] + mod)%mod)%mod)%mod;
    	sum = (sum - a[i]+mod)%mod;
    }
    cout<<ans;
}

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

int main(){
  int N,L;
  string S[101];

  cin>>N>>L;
  for(int i=0;i<N;i++){
    cin>>S[i];
  }
  sort(S,S+N);

  for(int i=0;i<N;i++){
    cout<<S[i];
  }

  cout<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
#define  st first
#define  nd second
void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
 
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"
 
 
#define MOD   1000000007
const int LN =19;
#define int long long
const int  MAXN = 100004;
 
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef cc_hash_table<int, int, hash<int > > ht;
 
int mu[MAXN];
int f[MAXN];
int n , k ; 
void mobius(){
     mu[1] = 1;
	 for (int i = 1; i < MAXN; i++)
		for (int j = 2*i; j < MAXN; j += i)
		{
				mu[j] -= mu[i];
		}
}
 
int modular_pow(int  base, int exponent, int modulus)
{
    int result = 1;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}
int fact[MAXN];
int invf[MAXN]; 

void fun(){
  for(int i=1;i<MAXN;i++){
    for(int j=i;j<MAXN;j+=i){
        f[j]= ((f[j]+((i*mu[j/i])%MOD))%MOD + MOD)%MOD;
    }
  }
 
}
int solve(){
   int ans=0;
   for(int d=1;d<=k;d++){
    ans=(ans+((f[d]* modular_pow(k/d,n ,MOD))%MOD))%MOD;
   }
   return ans;
}
void precal(){
  fact[0] = 1 ; 
  for(int i = 1; i<MAXN ; i++){
      fact[i] = (fact[i-1]*i)%MOD;
      invf[i] = modular_pow(fact[i],MOD-2,MOD);
  }
  mobius();
  fun();
}
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  precal();
  cin >> n >> k ;
  cout<<solve();
}
 
 

Measured memory_bytes: 6764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string s;
int main(){
	s ss;
  	cin >> ss;
  	ll sum=0;
  	for( char x:ss){
    sum+=(x-'0');
    }
  	puts( sum % 9 ? "No" : "Yes" );


  	return 0;
}

Measured memory_bytes: 3680
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

vector<pair<int,int> > primeFactorize(int n) {
  vector<pair<int,int> > ret;//prime,cnt;
  int cnt;
  for(int i=2;i*i<=n;i++) {
    if(n%i==0){
      cnt=0;
      while(n%i==0) {
        cnt++;
        n/=i;
      }
      ret.push_back({i,cnt});
    }
  }
  if(n!=1)ret.push_back({n,1});
  return ret;
}

int main(void){
  int n, i, j, cnt=0, tmp;
  vector<pair<int,int> > p;

  cin >> n;

  for(i=1;i<=n;i+=2){
    p = primeFactorize(i);

    tmp = 1;
    for(j=0;j<p.size();j++){
      tmp *= (p[j].second+1);
    }

    if(tmp==8)cnt++;
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256