akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  vector<ll> A(N+1);
  map<ll, ll> mp1;
  map<ll, ll> mp2;
  for (ll i = 1; i <= N; i++) {
    cin >> A.at(i);
    ll k = i - A.at(i);
    ll m = i + A.at(i);
    mp1[k]++;
    mp2[m]++;
  }
  ll cnt = 0;
  for (ll i = 1; i <= N; i++) {
    ll k = i - A.at(i);
    ll m = i + A.at(i);
    cnt += mp2[k] + mp1[m];
  }
  cout << cnt / 2 << endl;
  

  return 0;
}



Measured memory_bytes: 50172
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,p[maxn],ct;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        if(p[i]!=i){
            ct++;
        }
    }
    printf(ct<=2?"YES\n":"NO\n");
}
/*
    Good Luck
        -Lci70121
*/


Measured memory_bytes: 256
# 参考にした実装
# https://atcoder.jp/contests/abc086/submissions/2340945
# https://atcoder.jp/contests/abc086/submissions/2789430

# 二次元累積和行列の構築処理
# https://paiza.hatenablog.com/entry/2014/05/28/もし女子大生プログラマに『アルゴリズム』を図

n, k = gets.strip.split.map(&:to_i)
xyc = readlines.map {|line| line.strip.split }
k2 = 2*k

cum = Array.new(k2+1) { [0]*(k2+1) }

xyc.each do |x, y, c|
  # (2k) * (2k) に収めるための修正
  x = x.to_i % k2
  y = y.to_i % k2

  # 全部白にする補正
  y = (y+k)%k2 if c=='W'

  # 累積和行列作成の仕込み
  cum[x+1][y+1] += 1
  # 累積和計算時に一つの正方形計算で済むように補正
  cum[(x+k)%k2 + 1][(y+k)%k2 + 1] += 1
end

(1..k2).each do |i|
  (1..k2).each do |j|
    cum[i][j] += cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1]
  end
end

ans = 0

(1..k).each do |i|
  (1..k).each do |j|
    current = cum[i+k][j+k] - cum[i+k][j] - cum[i][j+k] +  cum[i][j]
    ans = [ans, current, n-current].max
  end
end

p ans

Measured memory_bytes: 71260
#include <iostream>

using namespace std;

int main()
{
    int N, L[16];
    int suml = 0, maxl = 0;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> L[i];
        suml += L[i];
        maxl = max(L[i], maxl);
    }

    cout << ((suml - maxl > maxl) ? "Yes" : "No") << endl;
}

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

int main() {
  string A = "A";
  string T = "T";
  string C = "C";
  string G = "G";
  string b ;
  cin >> b ;
  if ( b == A ) {
    cout << " T" << endl ;
  }
    if ( b == T ) {
      cout << "A" << endl ;
    }
    if ( b == C ){
     cout << "G" << endl;
    }
  if ( b == G) {
    
  cout << "C" << endl;
}
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main(void)
{   
    int n, k;
    cin >> n >> k;
    vector<int> a(3);
    rep(i, 3) cin >> a[i];
    string t;
    cin >> t;
    vector<int> ctoi(n);
    rep(i, n) {
        if(t[i] == 'r') ctoi[i] = 0;
        if(t[i] == 's') ctoi[i] = 1;
        if(t[i] == 'p') ctoi[i] = 2;
    }

    int sum = 0;
    rep(i, k) {
        vector<int> x;
        for(int j = i; j < n; j += k) {
            x.push_back(ctoi[j]);
        }

        vector<int> dp(3, 0);
        for(int nx : x) {
            vector<int> p = dp;
            p[0] = max(dp[1], dp[2]) + a[0]*(nx == 1);
            p[1] = max(dp[0], dp[2]) + a[1]*(nx == 2);
            p[2] = max(dp[0], dp[1]) + a[2]*(nx == 0);
            dp = p;
        }
        sum += *max_element(dp.begin(), dp.end());
    }

    cout << sum << endl;
    
    return 0;
}

Measured memory_bytes: 1404
#include <stdio.h>
#define TRUE 1
#define FALSE 0

int main(void){
  int a,b,c;
  int tmp;
  int x;
  
  scanf("%d %d %d",&a,&b,&c);
  
  if( c >= a && c >= b){
    tmp = c;
    c = a;
    a = tmp;
  }
  
  if( b >= a && b >= c){
    tmp = b;
    b = a;
    a = tmp;
  }
  
  x = (a-b) + (a-c);
  
  if( x % 2 == 0 ) printf("%d\n",x/2);
  else printf("%d\n",x/2+2);
  
  return 0;
}

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

using namespace std;

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

  int n, m, v, p;
  cin >> n >> m >> v >> p;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int l = -1, r = n - p;
  while (l + 1 < r) {
    int mid = l + r >> 1;
    long long tot = 1ll * (v - mid - p) * m;
    if (a[mid] + m < a[n - p]) {
      l = mid;
      continue;
    }
    for (int i = n - p; i >= mid + 1; --i) {
      tot -= a[mid] + m - a[i];
    }
    if (tot > 0) {
      l = mid;
    } else {
      r = mid;
    }
  }
  cout << n - r;

  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#define N 1000

int main(void){
	int set;
	int i,j,k;
	int a[N];
	int v;
	scanf("%d", &set);
	for(i=0;i<set;i++){
		scanf("%d", &a[i]);
		if(i!=set-1){
			printf("%d ",a[i]);
		}else if(i==set-1){
			printf("%d\n", a[i]);
		}
	}

	for(i=1;i<set;i++){
		v=a[i];
		j=i-1;
		while(j>=0 && a[j]>v){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=v;
		for(k=0;k<set;k++){
			if(k!=set-1){
				printf("%d ",a[k]);
			}else{
				printf("%d\n",a[k]);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1716
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<array>
#include<vector>
#include<set>
#include <utility>
#include <map>
#include<bitset>

using namespace std;



int main(){
  int n,m; cin>>n>>m;
  if (n<10 && m<10 ) cout<<n*m<<endl;
  else cout<<-1<<endl;
}


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

vector<int>g[100001];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		if(g[i].size()%2){
			printf("No\n");
			return 0;
		}
	int o,z=0;
	for(int i=1;i<=n;i++)
		if(g[i].size()>=6){
			printf("Yes\n");
			return 0;
		}
		else if(g[i].size()==4){
			o=i;
			z++;
		}
	if(z>=3){
		printf("Yes\n");
		return 0;
	}
	if(z<=1){
		printf("No\n");
		return 0;
	}
	for(int i=0;i<g[o].size();i++){
		int j=g[o][i],jj=o;
		while(g[j].size()==2){
			int jjj=g[j][0]^g[j][1]^jj;
			jj=j;
			j=jjj;
		}
		if(j==o){
			printf("Yes\n");
			return 0;
		}	
	}
	printf("No\n");
}

Measured memory_bytes: 8592
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()


int main(){
    int k;
    cin>>k;
    int a=0;
    int count=0;
    if(k%2==0 || k%5==0){
        count=-1;
    }else{
        while(1){
            count++;
            a=(a*10+7)%k;
            if(a==0){
                break;
            }
            if(count==k){
                count=-1;
            }
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
	string s;
	cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
ll dp[2][100010];
int main(){
    int n; ll c; cin >> n >> c;
    vector<ll> x(n+2),v(n+2);
    FOR(i,1,n+2) cin >> x[i] >> v[i];
    x[n+1] = c;
    rep(i,2){
        rep(j,n+2){
            dp[i][j] = 0;
        }
    }

    ll cal = 0;
    FOR(i,1,n+1){
        cal += v[i];
        cal -= (x[i] - x[i-1]);
        dp[0][i] = max(cal, dp[0][i-1]);
    }
    cal = 0;
    for(int i = n; i >= 1; i--){
        cal += v[i];
        cal -= (x[i+1] - x[i]);
        dp[1][i] = max(cal, dp[1][i+1]);
    }

    ll ans = 0;
    ll tmp = 0;
    rep(i,n+1){
        tmp = dp[0][i] + dp[1][i+1] - x[i];
        ans = max(ans, tmp);
        tmp = dp[0][i] + dp[1][i+1] - c + x[i+1];
        ans = max(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 3328
#include <stdio.h>
 
int main()
{
    int n = 0, m = 0, l = 0, i, j, k;
    int A[100][100], B[100][100];
    long C[100][100]={0};
    
    scanf("%d %d %d", &n, &m, &l);
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            scanf("%d", &A[i][j]);
        }
    }
    
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < l; j++)
        {
            scanf("%d", &B[i][j]);
        }
    }
    
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < l; j++)
        {
            C[i][j] = 0;
            for(k = 0; k < m; k++)
            {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < l; j++)
        {
            if(j) printf(" ");
            printf("%ld", C[i][j]);
        }
        printf("\n");
    }
    return 0;
 }



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

int main() {
    int s, w;
    cin >> s >> w;
    if (s <= w) {
        cout << "unsafe" << endl;
    } else {
        cout << "safe" << endl;
    }
    return 0;
}

Measured memory_bytes: 3568
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<functional>
#include<cmath>

#define REP(i,n) for(int i=0;i<n;i++)
#define ll long long int

using namespace std;

int to_int(string s) {
  return atoi(s.c_str());
}

int main() {
  int n;
  cin >> n;
  if(n < 4) {
    cout << "No" << endl;
    return 0;
  }
  for(int i = 0; 7*i <= n; i++) {
    if((n-7*i)%4 == 0) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;

}


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

int main(void) {
  int N, K;
  string S;
  cin >> N >> K >> S;

  int happy = 0;
  for (int i = 0; i < N-1; i++)
    if (S[i]=='R' && S[i+1]=='R') happy++;
	  
  for (int i = N-1; i > 0; i--)
    if (S[i]=='L' && S[i-1]=='L') happy++;
  
  cout << min(N-1, happy+K*2) << endl;
  return 0;
}


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

using namespace std;

struct mazepoint {
	int y;
	int x;
};

int main() {

	int h, w;
	cin >> h >> w;
	int sy, sx;
	int gy, gx;

	sy = 1;
	sx = 1;
	gy = h;
	gx = w;
	
	vector<int> mukix{ 1,0,-1,0 };
	vector<int> mukiy{ 0,1,0,-1 };

	//迷路読み込み
	int kurokazu = 0;
	vector<string> maze(h + 2);
	for (int i = 1; i <= h; i++) {
		cin >> maze[i];

		for (int j = 0; j < w; j++) {
			if (maze[i][j] == '#') { kurokazu++; }
		}

		maze[i] = "#" + maze[i] + "#";
	}
	for (int i = 0; i <= w + 1; i++) {
		maze[0].push_back('#');
		maze[h+1].push_back('#');
	}


	//幅優先探索処理
	vector<vector<bool>> seen(h + 2, vector<bool>(w + 2));	//発見したらtrue
	deque<mazepoint> todo;					//行く所のスタック

	todo.push_back({ sy, sx });
	mazepoint s = todo.front();							//今いる場所

	seen[s.y][s.x] = true;
	vector<vector<int>> fukasa(h + 2, vector<int>(w + 2, 0));
	fukasa[sy][sx] = 1;

	while (todo.empty() != true) {				//スタックが空になるまで処理	
		s = todo.front();						//処理番号を指定
		int tugiflg = false;					//次があったらtrueにするフラグ
		for (int i = 0; i < 4; i++) {
			if (s.y + mukiy[i] == gy && s.x + mukix[i] == gx) {
				cout << w*h-kurokazu-fukasa[s.y][s.x]-1 << endl;
				return 0;
			}
			if (maze[s.y + mukiy[i]][s.x + mukix[i]] == '#') { continue; }
			if (seen[s.y + mukiy[i]][s.x + mukix[i]] != true) {
				seen[s.y + mukiy[i]][s.x + mukix[i]] = true;
				todo.push_back({ s.y + mukiy[i],s.x + mukix[i] });
				fukasa[s.y + mukiy[i]][s.x + mukix[i]] = fukasa[s.y][s.x] + 1;
				tugiflg = true;
				//				cout << s.y + mukiy[i] << " " << s.x + mukix[i] << endl;
			}
		}
		todo.pop_front(); //次を全部探したので削除する
	}
	//	}
	cout << -1 << endl;

	return 0;

}

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

typedef double R;
typedef complex<R> P;
typedef vector<P> G;
#define REP(i, n) for(int i=0;i<(int)n;i++)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;i--)
#define X real()
#define Y imag()
const R EPS = 1e-8;
const R INF = 1e8;

inline int sig(const R &x){return abs(x)<EPS ? 0 : x > 0 ? 1 : -1;}
inline R  inp(const P &a, const P &b){return (conj(a)*b).X;}
inline R outp(const P &a, const P &b){return (conj(a)*b).Y;}
inline int ccw(const P &s, const P &t, const P &p){return sig(outp(t-s, p-s));}

inline P crosspoint(const P &p1, const P &p2, const P &q1, const P &q2){
	R A = outp(p2-p1, q2-q1), B = outp(p2-p1, p2-q1);
	if(!sig(A) && !sig(B)) return q1;
	return q1 + B/A * (q2 - q1);
}

R area(const G &g){
	R sum = 0;
	REP(i, g.size()) sum += outp(g[i], g[(i+1)%g.size()]);
	return abs(sum/2);
}

G cut(const G &g, const P &p1, const P &p2){
	G res;
	REP(i, g.size()){
		if(ccw(p1, p2, g[i]) >= 0) res.push_back(g[i]);
		if(ccw(p1, p2, g[i]) * ccw(p1, p2, g[(i+1)%g.size()]) < 0)
			res.push_back(crosspoint(g[i], g[(i+1)%g.size()], p1, p2));
	}
	return res;
}

R calc(const G &g, R a){
	R l = 0, r = INF;
	REP(itr, 100){
		R mid = (l+r)/2;
		if(area(cut(g, P(1, mid), P(0, mid))) < a) l = mid;
		else r = mid;
	}
	return r;
}
int n;
R d, V;
int main(){
	while(cin >> n >> d >> V, n){
		G g;
		REP(i, n){
			R x, y;
			cin >> x >> y;
			g.emplace_back(x, y);
		}
		R ans = 0;
		REP(i, n){
			RREP(i, n) g[i] -= g[0];
			P v = g[1]/abs(g[1]);
			RREP(i, n) g[i] /= v;
			ans = max(ans, calc(g, V/d));
			g.push_back(g[0]); g.erase(g.begin());
		}
		printf("%.11f\n", ans);
	}
	return 0;
}

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

int main() {
  string s;
  set<char> array;
  bool frag;

  cin >> s;

  rep(i,s.size()) array.insert(s[i]);

  rep(i,26){
    frag = true;
    for(auto itr = array.begin(); itr != array.end(); ++itr){
      if(97+i == *itr){
        frag = false;
        break;
      }
    }

    if(frag){
      printf("%c\n",97+i);
      break;
    }
    else if(i==25) printf("None\n");
  }

  return 0;
}


Measured memory_bytes: 512
<?php

fscanf(STDIN, "%d %d", $n, $k);

const MAX = 2005;
const MOD = 1000000007;

$inv2 = []; $inv2[1] = 1;
$finv2 = []; $finv2[0] = 1; $finv2[1] = 1;
function extGcd($a, $b, &$x, &$y) {
    if ($b === 0) {
        $x = 1;
        $y = 0;
        return $a;
    }

    $d = extGcd($b, $a % $b, $y, $x);
    $y -= floor($a / $b) * $x;
    return $d;
}

for ($i = 2; $i < MAX; ++$i) {
    $x;$y;
    extGcd($i, MOD, $x, $y);

    $x = ($x % MOD + MOD) % MOD;

    $inv2[$i] = $x;
}

$fac  = []; $fac[0]  = 1; $fac[1]  = 1;
$inv  = [];               $inv[1]  = 1;
$finv = []; $finv[0] = 1; $finv[1] = 1;

for ($i = 2; $i < MAX; ++$i) {
    $fac[$i] = $i * $fac[$i - 1] % MOD;
    $inv[$i] = MOD - $inv[MOD % $i] * floor(MOD / $i) % MOD;
    $finv[$i] = $finv[$i - 1] * $inv[$i] % MOD;

    $finv2[$i] = $finv2[$i - 1] * $inv2[$i] % MOD;
}

function COM($n, $k) {
    if ($n < $k) return 0;
    if ($n < 0 || $k < 0) return 0;

    global $fac;
    global $finv;
    global $finv2;

    /* echo "n!: " . $fac[$n] . ", k!: " . $finv[$k] . ", (n-k)!: " . $finv[$n - $k], PHP_EOL; */

    return $fac[$n] * ($finv2[$k] * $finv2[$n - $k] % MOD) % MOD;
}

/* for ($i = 0; $i < 10; ++$i) { */
/*     echo "i: $i, fac: " . $fac[$i] . ", finnv: ". $finv[$i] . ", finv2: " . $finv2[$i] . ", fac*finv: " . ($fac[$i] * $finv[$i] % MOD) . ", fac*finv2: " . ($fac[$i] * $finv2[$i] % MOD), PHP_EOL; */
/* } */

// all: n個, blue: k, red: n -k
// 赤玉はn -k 個なので,青玉を置けるスペースはn - k + 1個
$a = $n - $k + 1;

// 青玉がk個なので、区切るのはk - 1通りできる
$b = $k - 1;
for ($i = 1; $i <= $k; ++$i) {
    /* echo "i: $i, a: $a, b: $b", PHP_EOL; */
    /* echo "  aCi: " . COM($a, $i), PHP_EOL; */
    /* echo "  bCi-1: " . COM($b, $i - 1), PHP_EOL; */
    echo COM($a, $i) * COM($b, $i - 1) % MOD, PHP_EOL;
}



Measured memory_bytes: 4604
#include<iostream>
#include<algorithm>
#define SENTINEL 1000000009
#define MAX 100000

using namespace std;
struct {char name; int value;} A[MAX], B[MAX];




void Merge(int left, int mid, int right){
    int n1 = mid-left;
    int n2 = right - mid;
    pair<char, int> L[n1], R[n2];
    for(int i=0;i<=n1-1; i++)L[i]=make_pair(B[left+i].name, B[left+i].value);
    for(int i=0;i<=n2-1; i++)R[i]=make_pair(B[mid+i].name, B[mid+i].value);
    L[n1].second=SENTINEL;
    R[n2].second=SENTINEL;
    int i=0;
    int j=0;
    for(int k=left;k<=right-1;k++){
        if(L[i].second<=R[j].second){
            B[k].name=L[i].first;
            B[k].value=L[i].second;
            i++;
        }
        else {
            B[k].name=R[j].first; 
            B[k].value=R[j].second;
            j++;
            }
    }
}

void MergeSort(int left, int right){
    if (left+1<right){
        int mid=(left+right)/2;
        MergeSort(left, mid);
        MergeSort(mid, right);
        Merge(left,mid,right);
    }
}


int Partition(int p, int r){
    int x=A[r].value;
    int i =p-1;
    pair<char, int> temp;
    for(int j=p; j<=r-1; j++){
        if(A[j].value<=x){
            i++;
            temp=make_pair(A[i].name, A[i].value);
            A[i].name=A[j].name;
            A[i].value=A[j].value;
            A[j].name=temp.first;
            A[j].value=temp.second;
        }
    }
    temp=make_pair(A[i+1].name, A[i+1].value);
    A[i+1].name=A[r].name;
    A[i+1].value=A[r].value;
    A[r].name=temp.first;
    A[r].value=temp.second;
    return i+1;
}

void QuickSort(int p, int r){
    if (p<r){
        int q=Partition(p,r);
        QuickSort(p,q-1);
        QuickSort(q+1,r);
    }
}


int main(){
    int n;
    cin >> n;
    for(int i=0;i<=n-1;i++){
        cin >> A[i].name >> A[i].value;
        B[i].name=A[i].name;
        B[i].value=A[i].value;
    }
    MergeSort(0,n);
    QuickSort(0, n-1);

    for(int i=0; i<=n-1;i++){
        if(A[i].name != B[i].name){
            cout << "Not stable\n";
            break;
        }
        else if((i==n-1)&(A[i].name==B[i].name))cout << "Stable\n";
    }

    for(int i=0;i<=n-1;i++){
        cout << A[i].name << " " << A[i].value << "\n";
    }

}


Measured memory_bytes: 5400
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
struct Edge
{
	int to,next,d;
}w[800005];
int n,P[100005],Q[100005],h[200005],cnt=1,s,t,tot,pre[200005],bel[200005],bel2[200005],cur[200005];
bool vis[200005];
int ans=0;
void add(int x,int y,int d)
{
	w[++cnt]=(Edge){y,h[x],d};
	h[x]=cnt;
	w[++cnt]=(Edge){x,h[y],0};
	h[y]=cnt;
}
bool bfs()
{
	queue<int> q;
	q.push(s);
	memset(pre,0,sizeof(pre));
	pre[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=w[i].next)
		{
			int to=w[i].to;
			if(w[i].d&&!pre[to])
			{
				pre[to]=pre[u]+1;
				if(to==t) return 1;
				q.push(to);
			}
		}
	}
	return 0;
}
int dfs(int x,int p)
{
	if(x==t||!p) return p;
	int r=p;
	for(int &i=cur[x];i;i=w[i].next)
	{
		int to=w[i].to;
		if(r&&w[i].d&&pre[to]==pre[x]+1)
		{
			int p2=dfs(to,min(r,w[i].d));
			if(p2)
			{
				w[i].d-=p2;
				w[i^1].d+=p2;
				r-=p2;
			}
			if(!r) return p;
		}
	}
	if(p==r) pre[x]=0;
	return p-r;
}
int Dinic()
{
	int ans=0;
	while(bfs()) memcpy(cur,h,sizeof(h)),ans+=dfs(s,0x3f3f3f3f);
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&P[i]);
	for(int i=0;i<n;i++) scanf("%d",&Q[i]);
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
		{
			int x=i;
			tot++;
			while(!vis[x])
			{
				vis[x]=1;bel[x]=tot;
				x=P[x];
			}
		}
	}
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
		{
			int x=i;
			tot++;
			while(!vis[x])
			{
				vis[x]=1;bel2[x]=tot;
				x=Q[x];
			}
		}
	}
	int sum=0;
	s=0,t=tot+1;
	for(int i=0;i<n;i++)
	{
		if(P[i]!=i&&Q[i]!=i)
		{
			if(P[i]!=Q[i]) add(bel2[i],bel[i],1);
			else add(bel[i],bel2[i],1),add(bel2[i],bel[i],1);
		}
		else if(P[i]!=i||Q[i]!=i)
		{
			if(P[i]==i) add(bel2[i],t,1);
			else add(s,bel[i],1);
		}
		else sum++;
	}
	int ans=Dinic();
	printf("%d\n",n-ans-sum);
}

Measured memory_bytes: 14656
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner cs = new Scanner(System.in);
		int L = cs.nextInt();
		int A = cs.nextInt();
		int B = cs.nextInt();
		int C = cs.nextInt();
		int D = cs.nextInt();
		int ans, japan, math;
		japan = A / C;
		if(A % C !=0){
			japan = japan + 1;
		}
		math = B / D;
		if(B % D != 0){
			math =math + 1;
		}
		if(japan < math){
			ans = L - math;
		}else{
			ans = L - japan;
		}
		System.out.println(ans);

	}

}

Measured memory_bytes: 26172
N=int(input())

for n in range(N):
    gx,gy=map(int,input().split())
    T=[[0 for i in range(gy+1)] for j in range(gx+1)]
    left=[[0 for i in range(gy+1)] for j in range(gx+1)] 
    upper=[[0 for i in range(gy+1)] for j in range(gx+1)]
    p=int(input())
    
    for i in range(p):
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            upper[x1][max(y1,y2)]=1
        if y1==y2:
            left[max(x1,x2)][y1]=1
    for i in range(gx+1):
        for j in range(gy+1):
            if i==0 and j==0:
                T[i][j]=1
                continue
            if i==0 and j>1 and upper[i][j]==0 and left[i][j]==0:
                T[i][j]=T[i][j-1]
                continue
            if i>=1 and j==0 and upper[i][j]==0 and left[i][j]==0:
                T[i][j]=T[i-1][j]
                continue
            if left[i][j]==1 and upper[i][j]==1:
                T[i][j]=0
            elif left[i][j]==0 and upper[i][j]==1:
                T[i][j]=T[i-1][j]
            elif left[i][j]==1 and upper[i][j]==0:
                T[i][j]=T[i][j-1]
            else:
                T[i][j]=T[i-1][j]+T[i][j-1]
    if T[gx][gy]==0:
        print("Miserable Hokusai!")
    else:
        print(T[gx][gy])


Measured memory_bytes: 5624
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main()
{
    string S, T;
    cin >> S >> T;
    int count = 0;
    for (int i = 0, l = S.size(); i < l; ++i) {
        if (S[i] != T[i]) ++count;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3916
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

vector<pair<double,string> > data;
int main(){
	int n;
	while(1){
		cin >> n;
		if(n==0) break;
		data.clear();
		REP(i,n){
			string l;
			int p,a,b,c,d,e,f,s,m;
			cin >> l >> p  >> a >> b >> c >> d >> e  >> f >> s >> m;
			int timesum = a+b+c+(d+e)*m;
			data.pb(mp(-1*(double)(m*f*s-p)/(double)timesum,l));
		}
		sort(All(data));
		REP(i,data.size()){
			cout << data[i].second << endl;
		}
		cout << '#' << endl;
 	}
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
// Hey! 僕の提出を見てくれてありがとう.
// ロボ子さん可愛いぞ！！！！！君もV沼にはまろう↓
// https://www.youtube.com/channel/UCDqI2jOz0weumE8s7paEk6g
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
//sortを降順にする時は greater<型>()

void solve(long long N, std::string S){
  ll r = 0 , g = 0 , b = 0;
  for (int i = 0; i < N; i++) {
    if(S[i] == 'R')r++;
    else if(S[i] == 'G')g++;
    else b++;
  }ll ans = r*g*b;
  for (int i = 1; i <= N; i++) {
    for (int j = i+1; j <= N; j++) {
      ll k = 2*j - i;
      if(k > N)break;
      set<char> test;
      test.insert(S[i-1]);test.insert(S[j-1]);test.insert(S[k-1]);
      if(test.size() == 3)ans--;
    }
  }
  cout << ans << endl;
}

int main(){
    long long N;
	scanf("%lld",&N);
	std::string S;
	std::cin >> S;
    solve(N, S);
}


Measured memory_bytes: 3708
#include <stdio.h>
#include <stdlib.h>
#define SIZE 200

int main(void) {
	int stack[SIZE];
	int t = 0;
	char elm[15];

	while (scanf("%s", elm) != EOF) {
		if (elm[0] >= '0' && elm[0] <= '9') stack[t++] = atoi(elm);
		else if (elm[0] == '+') {t--; stack[t - 1] += stack[t];}
		else if (elm[0] == '-') {t--; stack[t - 1] -= stack[t];}
		else if (elm[0] == '*') {t--; stack[t - 1] *= stack[t];}
	}

	printf("%d\n",stack[0]);

	return 0;
}

Measured memory_bytes: 1760
import java.util.Scanner;

public class Main {

    public static void main(String args[]) throws Exception {

        Scanner Input = new Scanner(System.in);
        long N = Input.nextLong();
        long M = Input.nextLong();       
        long X = Math.min(N, M/2);
        long Ans=0;Ans+=X;
        M-=X*2;
        Ans+=M/4;
        System.out.println(Ans);
    }
}


Measured memory_bytes: 21076
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

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

int iin() {
    int i;
    scanf("%d", &i);
    return i;
}

long long llin() {
    long long i;
    scanf("%lld", &i);
    return i;
}

double din() {
    double i;
    scanf("%lf", &i);
    return i;
}

char cin() {
    char c;
    scanf("%c", &c);
    return c;
}

void stin(char *s) {
    scanf("%s", s);
}

void iout(int i) {
    printf("%d\n", i);
}

void llout(long long i) {
    printf("%lld\n", i);
}

void dout(double i) {
    printf("%lf\n", i);
}

void cout(char c) {
    printf("%c\n", c);
}

void stout(char *s) {
    printf("%s\n", s);
}

int main() {
    int array[5];
    int i, in, tmp;
    array[0] = iin();
    REP(i,4) {
      in = iin();
      if (array[i] % 10 == 0) {
        array[i + 1] = in;
        continue;
      }
      if (in % 10 == 0) {
        tmp = array[i];
        array[i] = in;
        array[i + 1] = tmp;
        continue;
      }
      if ((array[i] % 10) < (in % 10)) {
        tmp = array[i];
        array[i] = in;
        array[i + 1] = tmp;
      } else {
        array[i + 1] = in;
      }
    }
    int total = 0;
    REP(i,5) {
//      iout(array[i]);
      if (array[i] % 10 == 0 || i == 4) {
        total += array[i];
      } else {
        total += (((array[i] / 10) + 1) * 10);
      }
    }
    iout(total);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<string>
#include <cmath>
#define INF 1111111
using namespace std;
typedef pair<int,int> P;

int main(){
   string s;
    cin >> s;
  long long k;
    cin >> k;
  bool flag= true;
  int inum;
   vector<int> vecS(s.size());
  for(int i=0; i<s.size(); i++){
    vecS.at(i) = s.at(i) - '0';
    if(flag){
     if(vecS.at(i) == 1)
       inum++;
     else
      flag = false;
    }
  }
  //if(log10(vecS.at(i) )
  //int a=0;
  int ans;
  if(k<=inum)
    ans = 1;
  else{
    ans = vecS.at(inum);
  }
  
  cout << ans << endl;
    
  
  
  
}


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


int main()
{
	int N, T;
	int c, t;
	int ans;

	cin >> N >> T;

	ans = 9999;

	for (int ni = 0; ni < N; ni++) {
		cin >> c >> t;
		if (t <= T && c < ans) {
			ans = c;
		}
	}

	if (ans == 9999) {
		cout << "TLE";
	}
	else {
		cout << ans;
	}


	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<atcoder/all>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (ll i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT
#define chmax(x, a)  do { x = max(x, a); } while(0)
#define chmin(x, a)  do { x = min(x, a); } while(0)

using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll,ll> PLL;

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

ll N, M;

ll vid(ll y, ll x) {
  return y * M + x;
}

void solve() {
  cin >> N >> M;
  vector<string> a(N);
  rep(i, N)
    cin >> a[i];

  ll s = N * M + 1, e = N * M + 2;
  mf_graph<ll> g(N*M + 100);
  rep(y, N) rep(x, M) {
    ll ix = vid(y, x);
    if ((x+y) % 2 == 0) {
      if (a[y][x] == '#') continue;
      g.add_edge(s, ix, 1);
      rep(k, 4) {
        ll ny = y + dy[k];
        ll nx = x + dx[k];
        if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
        if (a[ny][nx] == '#') continue;
        g.add_edge(ix, vid(ny, nx), 1);
      }
    } else {
      if (a[y][x] == '#') continue;
      g.add_edge(ix, e, 1);
    }
  }
  cout << g.flow(s, e) << endl;
  for (auto e : g.edges()) {
    if (e.from < 0 || e.from >= N*M) continue;
    if (e.to < 0 || e.to >= N*M) continue;
    if (e.flow != 1) continue;
    ll y = e.from / M;
    ll x = e.from % M;
    ll ny = e.to / M;
    ll nx = e.to % M;
    //printf("%lld (%lld,%lld) -> (%lld, %lld)\n", e.flow, y, x, ny, nx);
    if (ny == y+1) { a[y][x] = 'v'; a[ny][nx] = '^'; }
    if (ny == y-1) { a[y][x] = '^'; a[ny][nx] = 'v'; }
    if (nx == x+1) { a[y][x] = '>'; a[ny][nx] = '<'; }
    if (nx == x-1) { a[y][x] = '<'; a[ny][nx] = '>'; }
  }
  rep(i, N) {
    cout << a[i] << endl;
  }
}

int main() {
  //ll T;
  //cin >> T;
  //rep(_,T)
    solve();
  return 0;
}


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

int main(){
  int n ,m ,cnt=0 ,end=0 ,sai ,now=0 ,mass[1001];
  while( true ){
    cin >> n >> m;
    if( n == 0 && m == 0 ){
      break;
    }
    for( int i=0 ; i<n ; i++ ){
      cin >> mass[i];
    }
    
    for( int i=0 ; i<m ; i++ ){
      cin >> sai;
      if( end == 0 ){
	now += sai;
	now += mass[now];
	cnt++;
      }
      if( now >= n ){
	end = 1;
      }
    }
    cout << cnt << endl;
    cnt = 0; end = 0; now = 0;
  }
}

Measured memory_bytes: 1164
q,h,s,d=map(int,input().split())
#1,2,4,8
n=int(input())*4
a2=min(q*2,h)
a4=min(q*4,h*2,s)
a8=min(q*8,h*4,s*2,d)
a=[0,a2,a4,a8]
ans=0
for i in range(3,0,-1):
    ans+=(n//2**i)*a[i]
    n%=2**i
ans+=n*q
print(ans)


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

#define all(x) (x).begin(),(x).end()
#define fastio ios_base::sync_with_stdio(false)

typedef double db;
typedef long long ll;
typedef unsigned long long ull;

typedef long double ldb;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

int main() {
	fastio;
	int n, m, sum = 0; cin >> n >> m;
	vector < int > v(n);
	for(int i = 0; i < n; ++i) cin >> v[i], sum += v[i];
	int ans = 0;
	for(auto it: v) {
		if((it * 4 * m) >= sum)
			++ans;
		if(ans == m) {
			cout << "Yes\n";
			return 0;
		}
	}
	
	cout << "No\n";
	
	return 0;
}

Measured memory_bytes: 256
int dn(const void*a,const void*b){return*(int*)b-*(int*)a;}
int main(){
  int i,n,a[200009];
  long long ans=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",a+i);
  qsort(a,n,4,dn);
  for(i=1;i<n;i++)ans+=a[i/2];
  printf("%lld",ans);
}

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

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

#define INF 1 << 29
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int n,k,x,y;

int main(){
  cin >>n>>k>>x>>y;
  cout << min(k,n)*x + max(0,n-k)*y <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <cstring>
#include <fstream>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int MAX_N = 12+1;
const double INF = 1e+100;
double dist[10+1][10+1]; // ツ板シツ径 a ツづ個ケツーツキツづ個陳心ツづ板シツ径 b ツづ個ケツーツキツづ個陳心ツづづ個仰猟猟」ツ。
double d[MAX_N][MAX_N];
double dp[1<<MAX_N][MAX_N];
int n, w;
int a[MAX_N];

// ツケツーツキツ甘板づ個仰猟猟」ツづーツ仰づ淞づゥ
int calc (void )
{
	for (int i = 3; i <= 10; i++ )
		for (int j = 3; j <= 10; j++ )
			dist[i][j] = 2.0*sqrt ((double)i*j );
}

// ツ経ツ路ツづ個静堋堕アツづーツ仰づ淞づゥ
void make (void )
{
	// ツ渉可甘コツ可サ
	rep (i, n+1 )
		rep (j, n+1 )
				d[i][j] = INF;

	rep (i, n )
		rep (j, n )
			d[i][j] = dist[a[i]][a[j]];

	rep (i, n ){
		d[n][i] = a[i]; d[i][n] = a[i];
	} // end rep
	n++;
}

// bitDP
double solve (){

	// ツ渉可甘コツ可サ
	rep (S, 1<<n ){
		fill (dp[S], dp[S]+n, INF );
	} // end rep

	dp[(1<<n)-1][0] = 0;
	for (int S = (1 << n ) - 2; S >= 0; S-- )
		rep (v, n ) rep (u, n )
			if (!(S >> u & 1 ) )
				dp[S][v] = min (dp[S][v], dp[S | 1 << u][u] + d[v][u] );

	return dp[0][0];
}

int main()
{
	calc ();
	string str = "";

	while (getline (cin, str ) ){
		vector <int> cake; 
		stringstream ss (str );
		ss >> w;
		int i = 0, m;
		while (ss >> m ){
			 a[i++] = m;
		} // end while
		n = i;
		make ();
		if ((double)w >= solve () ){
			printf ( "OK\n" );
		}else{
			printf ( "NA\n" );
		} // end if
	} // end loop
		
	return 0;
}

Measured memory_bytes: 1740
#include <bits/stdc++.h>
#define dum(x) cout<<#x<<'='<<x<<endl
#define ll long long
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> tree(n);
  for (int i = 0; i < n; i++) {
    cin >> tree.at(i);
  }
  sort(tree.begin(), tree.end());
  int ans = 2000000000;
  for (int i = 0; i < n - k + 1; i++) {
    int min_tree = tree.at(i);
    int max_tree = tree.at(i + k - 1);
    int diff_tree = max_tree - min_tree;
    ans = min(diff_tree, ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

enum Walk
{ PreOrder,  InOrder, PostOrder, };

class Node
{
  public:
    Node(){ MyId = ParentId = Left = Right = -1; }
    int MyId;
    int ParentId;
    int Left;
    int Right;
};

Node* Nodes;
Node *Root;

void Print(Node*p)
{ cout << (" ") << p->MyId; }

void Rec(Node *p, Walk walk)
{

  if(walk == PreOrder)
    Print(p);
   
  if(p->Left >= 0)
    Rec(&Nodes[p->Left], walk); 

  if(walk == InOrder)
    Print(p);

  if(p->Right >= 0)
    Rec(&Nodes[p->Right], walk);

  if(walk == PostOrder)
    Print(p);

  return;
  
}


int main()
{

  int N;
  cin >> N;

  Nodes = new Node[N];

  for(int i = 0; i < N; ++i)
    Nodes[i].MyId = i;

  for(int i = 0; i < N; ++i)
  {
    int Id; cin >> Id;
    int Left; cin >> Left;
    int Right; cin >> Right;

    if(Left >= 0)
    {
      Nodes[Id].Left = Left;
      Nodes[Left].ParentId = Id;
    }
    if(Right >= 0)
    {
      Nodes[Id].Right = Right;
      Nodes[Right].ParentId = Id;
    }
  }

  for(int i = 0; i < N; ++i) 
    if(Nodes[i].ParentId == -1)
      Root = &Nodes[i];

  cout << "Preorder" << endl;
  Rec(Root, PreOrder);
  cout << endl;

  cout << "Inorder" << endl;
  Rec(Root, InOrder);
  cout << endl;

  cout << "Postorder" << endl;
  Rec(Root, PostOrder);
  cout << endl;

  delete [] Nodes;

  return 0;
}




Measured memory_bytes: 3100
# -*- coding: utf-8 -*-

n, k = map(int, input().split())

cnt = 0
for b in range(1, n + 1):
    q, r = divmod(n + 1, b)
    cnt += q * max(0, b - k) + max(0, r - k)

if k == 0:
    cnt -= n

print(cnt)


Measured memory_bytes: 2940
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#define N_MAX 20
using namespace std;
double calculator();
typedef struct data{
  double ll,aa,bb;
} d;
vector<d> V;
int N,M;
double l[N_MAX],a[N_MAX],b[N_MAX],ans;
 
int main(){
  cin>>N>>M;
  for(int i=0;i<N;i++) cin>>l[i]>>a[i]>>b[i];
  ans=0;
  for(int i=0;i<(1<<N);i++){
    if(M==__builtin_popcount(i)){
      V.clear();
      for(int j=0;j<N;j++){
    if(i&(1<<j)){
      d t;
      t.ll=l[j],t.aa=a[j],t.bb=b[j];
      V.push_back(t);
    }
      }
      ans=max(ans,calculator());
    }
  }
  printf("%.20f\n",ans);
  return 0;
}
 
double calculator(){
  double ret=0;
  for(int i=0;i<V.size();i++){
    for(int j=i+1;j<V.size();j++){
      double a=fabs(V[j].ll-V[i].ll);
      double b=fabs(V[j].aa-V[i].aa);
      double c=fabs(V[j].bb-V[i].bb);
      ret+=(a*a+b*b+c*c);
    }
  }
  return ret;
}

Measured memory_bytes: 1268
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int n,i;
    cin>>n;
    ll a[n+1];
    for (i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]-=i;
    }
    sort(a+1,a+n+1);
    ll b=a[n/2+1],ans=0;
    for (i=1;i<=n;i++)
        ans+=abs(a[i]-b);
    cout<<ans<<endl;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }

void compute() {

}

int h,w,c[110][110],n;

struct Data {
  int v, c;
  bool operator < ( const Data &d ) {
    if( v != d.v  ) return v > d.v;
    return c < d.c;
  }
};

int ans[110][110];

int main() {
  cin >> h >> w;
  cin >> n;
  vector<Data> a(n);
  rep(i,n) {
    cin >> a[i].v;
    a[i].c = i + 1;
  }
  sort(ALL(a));
  deque<int> v;
  rep(i,n) {
    rep(j,a[i].v) v.push_back(a[i].c);
  }
  rep(i,h) {
    if( !( i & 1 ) ) {
      rep(j,w) {
	ans[i][j] = v.front();
	v.pop_front();
      }
    } else {
      for(int j=w-1;j>=0;--j) {
	ans[i][j] = v.front();
	v.pop_front();
      }
    }
  }
  rep(i,h) {
    rep(j,w) {
      if( j ) {
	printf(" ");
      }
      cout << ans[i][j];
    } puts("");
  }

  compute();
  return 0;
}


Measured memory_bytes: 512
#![allow(unused_imports)]
#![allow(non_snake_case, unused)]

use std::cmp::*;
use std::collections::*;
use std::ops::*;

// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254 より

macro_rules! eprint {
    ($($t:tt)*) => {{
        use ::std::io::Write;
        let _ = write!(::std::io::stderr(), $($t)*);
    }};
}
macro_rules! eprintln {
    () => { eprintln!(""); };
    ($($t:tt)*) => {{
        use ::std::io::Write;
        let _ = writeln!(::std::io::stderr(), $($t)*);
    }};
}
macro_rules! dbg {
    ($v:expr) => {{
        let val = $v;
        eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
        val
    }}
}

macro_rules! mat {
    ($($e:expr),*) => { Vec::from(vec![$($e),*]) };
    ($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
    ($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
    ($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

macro_rules! ok {
    ($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => {
        $a$([$i])*.$f($($t),*)
    };
    ($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { {
        let t = $e;
        ok!($a$([$i])*.$f($($es),*)$(@$t)*@t)
    } };
}

pub fn readln() -> String {
    let mut line = String::new();
    ::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
    line
}

macro_rules! read {
    ($($t:tt),*; $n:expr) => {{
        let stdin = ::std::io::stdin();
        let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
            let line = line.unwrap();
            let mut it = line.split_whitespace();
            _read!(it; $($t),*)
        }).collect::<Vec<_>>();
        ret
    }};
    ($($t:tt),*) => {{
        let line = readln();
        let mut it = line.split_whitespace();
        _read!(it; $($t),*)
    }};
}

macro_rules! _read {
    ($it:ident; [char]) => {
        _read!($it; String).chars().collect::<Vec<_>>()
    };
    ($it:ident; [u8]) => {
        Vec::from(_read!($it; String).into_bytes())
    };
    ($it:ident; usize1) => {
        $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
    };
    ($it:ident; [usize1]) => {
        $it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
    };
    ($it:ident; [$t:ty]) => {
        $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
    };
    ($it:ident; $t:ty) => {
        $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
    };
    ($it:ident; $($t:tt),+) => {
        ($(_read!($it; $t)),*)
    };
}


pub fn main() {
    let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}

const MOD: i64 = 998244353;
// const MOD: usize = 1_000_000_007;
const INF: i64 = std::i64::MAX/2;

fn solve() {
    let x = read!(i64);
    println!("{}",1-x);
}

fn run() {
    solve();
}


Measured memory_bytes: 2240
def line_input(f, type):
    return f(map(type, input().split(" ")))

c = []
for _ in range(3):
    c.append(line_input(list, int))

def check(in_c):
    for bdx in range(3):
        if (in_c[bdx][0] - a1) == (in_c[bdx][1] - a2) == (in_c[bdx][2] - a3):
            pass
        else:
            return False

    return True


for a1 in range(100 + 1):
    for a2 in range(100 + 1):
        for a3 in range(100 + 1):
            if check(c):
                print("Yes")
                exit(0)
print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
const long long INF = 1LL << 60;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
vector<char> Alphabet = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
vector<char> alphabet = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<ll> A(N);
  rep(i,N) cin >> A[i];
  ll ans = 0;
  rep(i,N-1)
  {
    if(A[i]>A[i+1])
    {
      ans += A[i] - A[i+1];
      A[i+1] = A[i];
    }
  }
  cout << ans << endl;
  return 0;
}


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

ll choose(ll n, ll a) {
    ll x = 1, y = 1;
    rep(i, a) {
        x *= n - i;
        y *= i + 1;
    }
    return x / y;
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<ll> dp(n + 5, -1);
    rep(i, n) cin >> a[i];

    map<int, int> mp;
    rep(i, n){
        if(mp.count(a[i])){
            mp[a[i]]++;
        }else{
            mp[a[i]] = 1;
        }
    }
    rep(i, n){
        if(dp[mp[a[i]]] != -1){
            cout << dp[mp[a[i]]] << endl;
            continue;
        }
        ll ans = 0;
        for(auto m : mp){
            if(m.first == a[i]){
                ans += choose(m.second - 1, 2);
            }else{
                ans += choose(m.second, 2);
            }
            dp[mp[a[i]]] = ans;
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 10624
#include <cstdio>
#include <algorithm>
#include <iostream>

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

using namespace std;

int n;
string c;
int dp[1001][8];

int main(){
    cin >> n >> c;

    rep(i, n + 1){
        rep(j, 8){
            if(i == 0){
                dp[i][j] = j == 1;
            }
            else{
                int p;
                if(c[i - 1] == 'J'){
                    p = 1;
                }
                else if(c[i - 1] == 'O'){
                    p = 2;
                }
                else{
                    p = 4;
                }

                rep(k, 8){
                    if(j & p && j & k){
                        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % 10007;
                    }
                }
            }
        }
    }

    int result = 0;
    rep(i, 8){
        result = (result + dp[n][i]) % 10007;
    }

    printf("%d\n", result);
	return 0;
}

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

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


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true; } return false; }
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true; } return false; }

//INT_MAX	2,147,483,647 = 2*1.0e9

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

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

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

    ll b;
    if(N%2 == 0){
        b = (A[N/2] + A[N/2-1])/2;
    } else{
        b = A[(N-1)/2];
    }
    ll ans = 0;
    for(int i = 0; i < N; i++) ans += abs(b-A[i]);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>

typedef unsigned long ulong;

void getUmasa(std::vector<ulong>& v, int count) {
  using namespace std;
  v.resize(count);
  for (auto p = v.begin() ; p != v.end() ; p++) {
    cin >> *p;
  }
  sort(v.begin(), v.end(), greater<int>());
}

// debug
void print(std::vector<ulong>& v) {
  using namespace std;
  for (auto p = v.begin() ; p != v.end() ; p++) {
    cout << *p << ',';
  }
  cout << '\n';
}

int main() {
  using namespace std;
  ios_base::sync_with_stdio(false);

  int x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;
  
  vector<ulong> as;
  getUmasa(as, a);
  //cout << as[0];
  as.resize(x);
  
  vector<ulong> bs;
  getUmasa(bs, b);
  bs.resize(y);
  
  as.reserve(as.size() + bs.size());
  as.insert(as.end(), bs.begin(), bs.end());
  sort(as.begin(), as.end(), greater<int>());
  
  //print(as);
  
  vector<ulong> cs;
  getUmasa(cs, c);
  
  ulong max = 0;
  for (auto p = as.begin() ; p != as.end() ; p++) {
    max += *p;
  }
  for (int i = x + y - 1, j = 0 ; i>=0 && j < c ; i--, j++) {
    long n = cs[j] - as[i];
    if (n <= 0) break;
    max += n;
  }
  cout << max;
}


Measured memory_bytes: 3184
n, m = map(int, input().split())
problem = [0] * n
ac = 0
penalty = 0
for i in range(m):
    p, s = map(str, input().split())
    if s == "AC":
        temp = problem[int(p) - 1]
        if temp >= 0:
            ac += 1
            penalty += temp
            problem[int(p) - 1] = -1
    else:
        if problem[int(p) - 1] >= 0:
            problem[int(p) - 1] += 1
print(ac, penalty)

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
int m,d;
int main()
{
    scanf("%d%d",&m,&d);
    int res=0;
    for (int d1=2;d1<=9;++d1)
        for (int d2=2;d2<=9;++d2) if (d1*d2<=m&&d1+d2*10<=d)
            ++res;
    printf("%d\n",res);
    return 0;
}


Measured memory_bytes: 256