akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#define llint long long

using namespace std;

llint K, A, B;

int main(void)
{
	cin >> K >> A >> B;
	
	llint ans;
	if(A > B){
		ans = (K-B-1) / (A-B) * 2 + 1;
	}
	else{
		if(A >= K) ans = 1;
		else ans = -1;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <complex>

using namespace std;

typedef complex<int> Point;

inline int hash(int x, int y) {
    return x*5001 + y;
}

inline bool exist(const vector<bool> &v, int x, int y) {
    if(x < 0 || 5000 < x || y < 0 || 5000 < y) return false;
    return v[hash(x, y)];
}

int main() {
    while(true) {
        int n;
        cin >> n;
        if(!n) break;
        vector<Point> poles;
        vector<bool> v(5000*5001+5000, false);

        for(int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            v[hash(x, y)] = true;
            poles.push_back(Point(x, y));
        }

        int ans = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                Point diff = poles[j] - poles[i];
                Point p1 = poles[i] + Point(diff.imag(), -diff.real());
                Point p2 = poles[i] + Point(-diff.imag(), diff.real());
                if(exist(v, p1.real(), p1.imag())) {
                    if(exist(v, p1.real()+diff.real(), p1.imag()+diff.imag())) {
                        ans = max(ans, norm(diff));
                    }
                }
                if(exist(v, p2.real(), p2.imag())) {
                    if(exist(v, p2.real()+diff.real(), p2.imag()+diff.imag())) {
                        ans = max(ans, norm(diff));
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4016
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip> 

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define MOD 1000000007
#define PI 3.141592653589793
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

int A,B,H,M;
double h = 0.5, m = 6.0, ans, diff;

void solve(){
    diff = (m - h) * (H*60+M);
    int tmp = diff / 360;
    diff -= 360*tmp;
    diff = min(diff, 360-diff);

    // cout << diff << endl;

    ans = A*A + B*B - 2 * A * B * cos(PI*diff/180);

    cout << setprecision(16) <<  sqrt(ans) << endl;
}

int main(){
    cin >> A >> B >> H >> M;

    solve();
}


Measured memory_bytes: 4192
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;

struct edge {
	int a, b;
	LL len;
	LL rou;
	double cost;
	bool operator<(const edge&o)const {
		return cost < o.cost;
	}
};

LL n, m;
vector<edge>vec;

struct ufind {
	vector<int>par, val;
	ufind(int n) {
		par.resize(n);
		val.resize(n);
		for (int i = 0; i < n; ++i) {
			par[i] = i;
		}
	}
	int getpar(int x) {
		if (par[x] == x)return x;
		return par[x] = getpar(par[x]);
	}
	bool same(int u, int v) {
		return getpar(u) == getpar(v);
	}
	void unite(int u, int v) {
		u = getpar(u);
		v = getpar(v);
		if (u == v)return;
		if (val[u] < val[v]) {
			par[u] = v;
		}
		else if (val[u] > val[v]) {
			par[v] = u;
		}
		else {
			par[u] = v;
			++val[v];
		}
	}
};

int main(void)
{
	cin >> n >> m;
	cout.precision(10);
	if (m == n - 1) {
		cout << 0. << endl;
		return 0;
	}
	for (int i = 0; i < m; ++i) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		vec.push_back({ a,b,c,d });
	}
	double lo = 0, hi = 1e7;
	for (int loopcount = 0; loopcount < 100; ++loopcount) {
		double mid = (lo + hi) / 2;
		double total = 0.;
		for (auto& e : vec) {
			e.cost = e.rou - mid * e.len;
			total += e.cost;
		}
		sort(vec.rbegin(), vec.rend());
		double sum = 0;
		ufind uf(n);
		for (edge&e : vec) {
			if (!uf.same(e.a, e.b)) {
				uf.unite(e.a, e.b);
				sum += e.cost;
			}
		}
		double ans = total - sum;
		if (ans <= 0) {
			hi = mid;
		}
		else {
			lo = mid;
		}
	}
	cout << lo << endl;
	return 0;
}



Measured memory_bytes: 3552
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
		double r;
		double p = Math.PI;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		r = Double.parseDouble(str);

		System.out.printf("%1.6f %1.6f",r*r*p,2*r*p);
	}

}

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

int main(){
  int A,B,C;
  cin >>A>>B;
  
  if(A==1 and B==2){
    C = 3;
  }else if(A==1 and B==3){
    C = 2;
  }else if(A==2 and B==3){
    C = 1;
  }else if(A==2 and B==1){
    C = 3;
  }else if(A==3 and B==1){
    C = 2;
  }else{
    C = 1;
  }
  
  cout<<C<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>
#include <fstream> 
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <math.h>
#include <cmath>
using namespace std;
int main(){
     int ans,N;
     cin >> N;
     ans = N*(N+1)/2;
     cout << ans << endl;     
    }    		 
       

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

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

    vector<int> l(n);
    rep(i,n) cin >> l[i];

    int sum = 0;
    rep(i,n) sum += l[i];

    auto iter = std::max_element(l.begin(), l.end());
    size_t index = std::distance(l.begin(), iter);

    if(0 < sum - 2 * l[index])print("Yes");
    else print("No");
}

Measured memory_bytes: 764
N, M = map(int, input().split())
LR = [(map(int, input().split())) for i in range(M)]

L = 1
R = N
for i in range(M):
    a, b = LR[i]
    L = max(L,a)
    R = min(R,b)
if R-L+1>=0:   
	print(R-L+1)
else:
  	print(0)

Measured memory_bytes: 75864
from collections import defaultdict
S = input()

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
            
    def query(self, i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= i & -i
            
        return ret

d = defaultdict(list)
for i, v in enumerate(S):
    d[v].append(i + 1)

if sum(len(l) % 2 != 0 for l in d.values()) > 1:
    print(-1)
    exit()

N = len(S)
ctr = []
key_map = [-1] * (N + 1)

for k, v in d.items():
    t = len(v)
    if t % 2  == 1:
        key_map[v[t // 2]] = N // 2 + 1

    for j in range(t // 2):
        ctr.append((v[j], v[-j - 1]))
        
ctr.sort()

for i, (l, r) in enumerate(ctr):
    key_map[l] = i + 1
    key_map[r] = N - i

tree = BIT(N)
ans = 0
for i, v in enumerate(key_map[1:]):
    ans += i - tree.query(v)
    tree.update(v, 1)
print(ans)


Measured memory_bytes: 56012
#pragma region Template
#include <bits/stdc++.h>
#ifdef _DEBUG
#include "../../../debug_print.hpp"
#else
#define debug(...)
#endif
#define sort_(a) sort(a.begin(), a.end())
#define rsort(a) sort(a.rbegin(), a.rend())
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; 0 <= i; i--)
#define for_(i, start, end) for (int i = start; i < end; i++)
#define rfor(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using namespace std;
constexpr int INF32       = 1'050'000'000;
constexpr long long INF64 = 4'000'000'000'000'000'000;
constexpr int MOD7        = 1'000'000'007;
constexpr int MOD53       = 998'244'353;
constexpr double PI       = 3.14159265358979323846;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void scan() {}
template <class H, class... T> void scan(H &&head, T &&... args) {
    std::cin >> head;
    scan(std::forward<T>(args)...);
}
template <class T> void scan(std::vector<T> &v) {
    for (auto &&i : v) {
        scan(i);
    }
}
#pragma endregion Template

vector<string> split(const string &s, char remove) {
    istringstream stream(s);
    string field;
    vector<string> ans;
    while (getline(stream, field, remove)) {
        ans.emplace_back(field);
    }
    return ans;
}

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

    string s;
    scan(s);
    ll ans    = 0;
    auto calc = [&](string x) {
        auto vec = split(x, '+');
        debug(x);
        for (auto &&i : vec) {
            ans += stoll(i);
        }
    };
    auto rec = [&](auto f, int now, string form) {
        if (now == s.size()) {
            calc(form);
            return;
        }
        string x = form + string{s[now]};
        string y = form + "+" + string{s[now]};
        f(f, now + 1, x);
        f(f, now + 1, y);
    };
    rec(rec, 1, string{s[0]});
    print(ans);

    return 0;
}

Measured memory_bytes: 256
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　redcoderになるためAtCoderを巡る旅をしてます。

　　　 　 ＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　 ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣/ヽ
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

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

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

    int x, a; cin >> x >> a;
    if(x < a) cout << 0 << endl;
    else cout << 10 << endl;
}


Measured memory_bytes: 892
#include<iostream>
#include<array>
using namespace std;
int main() {
	int n;
	int b[101], c[101];
	cin >> n;
	int i,j,k;
	for (i = 1; i <= n; i++) {
		cin >> b[i];
	}
	int maxa, maxb;

	for (i = n; i >= 1; i--) {
		for (j = i; j >= 1; j--) {
			if (b[j] > j) {
				cout << -1;
				return 0;
			}
			else if (b[j] == j) {
				c[i] = j;
				for (k = j; k < n; k++) {
					b[k] = b[k + 1];
				}
				break;
			}
		}
		/*maxa = 0;
		maxb = -1;
		for (j = 0; j < i; j++) {
			if (b[i] > maxa) {
				maxa = b[i];
				maxb = i;
			}
		}
		if (maxa > i) {
			cout << -1;
			return 0;
		}
		else {
			c[i - 1] = maxa;
			for (j = maxb; j < i - 1; j++) {
				b[j] = b[j + 1];
			}
		}*/
	}
	for (i = 1; i <= n; i++) {
		cout << c[i];
		cout << '\n';
	}
	return 0;
}

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

int main(){
  int left1 , left2 , right1 , right2;
  cin >> left1 >> left2 >> right1 >> right2;
  
  if(left1 + left2 > right1 + right2){
    cout << "Left" << endl;
  }
  else if(left1 + left2 < right1 + right2){
    cout << "Right" << endl;
  }
  else{
    cout << "Balanced" << endl;
  }
}

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

int main() {
  int a,b,c;
  cin >>a>>b;
  
  c=a*b;
  if(c%2==0){
    cout << "Even" << endl;
  }
  else{
    cout << "Odd" << endl;
  }
}

  

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

int n;
set<string> ss;
vector<pair<string, string>> vs;
string s, t;

ll solve(string tt, int cnt) {
	//cout << tt << endl;
	if (tt == t)return cnt;
	if (tt.size() >= t.size() || ss.find(tt) != ss.end())return INF;
	//if (cnt > 3)return INF;
	ss.insert(tt);
	ll res = INF;
	rep(i, n) {
		//cout << "!" << i << " ";
		string nxt = "";
		rep(j, tt.size()) {
			ll num = tt.find(vs[i].first, j);
			if (num != string::npos) {
				nxt += tt.substr(j, num - j);
				j = num + vs[i].first.size() - 1;
				//cout << j << " ";
				nxt += vs[i].second;
			}
			else nxt += tt[j];
		}
		//cout << endl;
		res = min(res, solve(nxt, cnt + 1));
	}
	return res;
}

int main() {
	while (cin >> n&&n) {
		ss.clear();
		vs.clear();
		rep(i, n) {
			string ss, tt;
			cin >> ss >> tt;
			vs.push_back({ ss,tt });
		}
		cin >> s >> t;
		ll ans = solve(s, 0);
		if (ans == INF)cout << -1 << endl;
		else cout << ans << endl;
	}
}


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

int main() {
  int A,B,C,K;
  cin >> A >> B >> C >> K;
  if(A>=K){cout<<K<<endl;}
  else if(A+B>=K){cout<<A<<endl;}
  else {cout<<A-K+A+B<<endl;}
}


Measured memory_bytes: 3624
n = int(input())


def calc(n):
    mx = 1
    while True:
        if n <= mx * (mx + 1) // 2:
            break
        mx += 1
    return mx


ans = []
while n > 0:
    x = calc(n)
    ans.append(x)
    n -= x

print(*ans, sep="\n")


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1'000'000'007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
    ll n, W;    cin >> n >> W;
    vector<ll> v(n), w(n);
    REP(i, n)   cin >> w[i] >> v[i];
    vector<vector<ll>> dp(2, vector<ll>(W+1, 0));

    REP(i, n){
        for(ll j=0; j<=W; j++){
            dp[(i+1)%2][j] = dp[i%2][j];
            if(w[i]<=j)
                dp[(i+1)%2][j] = max(dp[i%2][j-w[i]]+v[i], dp[(i+1)%2][j]);
        }

    }

    cout << dp[n%2][W] << endl;
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

const int N=1e5+5;
const int mod=1e9+7;

int32_t main() {
IOS;
int h,w;
cin>>h>>w;
char arr[300][300];
FOR(i,1,h){
    FOR(j,1,w){
        cin>>arr[i][j];
    }
}
    for (int i = 0; i <=h+1   ; ++i) {
        for (int j = 0; j <=w+1; ++j) {
            if(arr[i][j]<'a')cout<<'#';
            else cout<<arr[i][j];
        }
        cout<<endl;
    }
}

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

int main() {
  string S;
  cin >> S;
  int num = 0;
  for (int i = 0; i < S.size(); i++) {
    if (S[i] == 'x') {
      num++;
    }
  }
  if (num >=8) cout << "NO" << endl;
  else cout << "YES" << endl;
  return 0;
}


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

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, k; cin >> n >> k;
  int tmp = ceil((double)n/2);
  if(k <= tmp) cout << "YES\n";
  else cout << "NO\n";
  return 0;
}

Measured memory_bytes: 256
def main():
  import sys
  from numpy import int32
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  f=floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]].clip(0,n)%n-1))))
main()

Measured memory_bytes: 30780
import java.util.*;

class Main{

  public static void main(String args[]){

    Scanner s=new Scanner(System.in);
    String S=s.next();
    String T=s.next();
    String box="";
	for(int i=0;i<S.length();i++) box+=T.charAt(i);
    System.out.println(box.equals(S)?"Yes":"No");
  }  
}

Measured memory_bytes: 39200
#include <bits/stdc++.h>
using namespace std;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define MAX 100000

int A[MAX], n;

int partition(int p, int r) {
    int x, i, j;
    x = A[r];
    i = p - 1;
    for (j = p; j < r; j++) {
        if (A[j] <= x) {
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i + 1], A[r]);
    return i + 1;
}

int main() {
    int i, q;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    q = partition(0, n - 1);
    for (i = 0; i < n; i++) {
        if (i) {
            cout << " ";
        }
        if (i == q) {
            cout << "[";
        }
        cout << A[i];
        if (i == q) {
            cout << "]";
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x) for(int i = 0;i < x;++i)
#define FOR(i,x,y) for(int i = x;i < y;++i)
#define ALL(a) a.begin(),a.end()
using ll = long long;

int v,e,r;
struct edge
{
    int to,cost;
};
vector<edge>graph[114514];

using P = pair<int,int>;
const int INF = 1234567890;
int dist[114514];
void dijkstra()
{
    fill(dist,dist+114514,INF);
    dist[r] = 0;
    priority_queue<P,vector<P>,greater<P>>que;
    que.push({0,r});
    while(!que.empty())
    {
        P p = que.top(); que.pop();
        int ds = p.first;
        int now = p.second;
        if(dist[now] < ds)continue;
        for(auto& ed : graph[now])
        {
            if(dist[ed.to] > dist[now] + ed.cost)
            {
                dist[ed.to] = dist[now] + ed.cost;
                que.push({dist[ed.to],ed.to});
            }
        }
    }
}

int main()
{
    cin >> v >> e >> r;
    REP(i,e)
    {
        int s,t,d;
        cin >> s >> t >> d;
        graph[s].push_back({t,d});
    }
    dijkstra();
    REP(i,v)
    {
        int dd = dist[i];
        if(dd >= INF)
        {
            cout << "INF" << endl;
        }
        else
        {
            cout << dd << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 13480
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct aaa{
	ll x,y,w;
}a[1000010];
ll n,t1,cnt,fa[500010],f[500010],ans;
ll find(ll x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
bool cmp(aaa a,aaa b){
	return a.w<b.w;
}
int main(){
	ll i,x,y,w;
	memset(f,44,sizeof(f));
	scanf("%lld%lld",&n,&t1);
	while(t1--){
		scanf("%lld%lld%lld",&x,&y,&w);
		x++;y++;
		a[++cnt].x=x;a[cnt].y=y;a[cnt].w=w;
		f[x]=min(f[x],w+1);f[y]=min(f[y],w+2);
	}
	for(i=1;i<=n;i++)f[i%n+1]=min(f[i%n+1],f[i]+2),fa[i]=i;
	for(i=1;i<=n;i++)f[i%n+1]=min(f[i%n+1],f[i]+2);
	for(i=1;i<=n;i++)a[++cnt].x=i,a[cnt].y=i%n+1,a[cnt].w=f[i];
	sort(a+1,a+cnt+1,cmp);
	for(i=1;i<=cnt;i++){
		x=find(a[i].x);y=find(a[i].y);
		if(x!=y){
			fa[x]=y;ans+=a[i].w;
		}
	}
	printf("%lld",ans);
}

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

using namespace std;

using ll = long long;
using ull = unsigned long long;

// -2進法を求める
string calcminus2(int n){
	string ret = "";
	while (n != 0) {
		if (n < 0) {
			ret = to_string(abs(n) % 2) + ret;
			n = n / -2 + !!(n % -2);
		}
		else {
			ret = to_string(n % -2) + ret;
			n /= -2;
		}
	}
	return ret;
}

int main(int argc, char const *argv[]) {
	int n;
	std::cin >> n;
	if (n == 0) {
		std::cout << 0 << '\n';
		return 0;
	}
	std::cout << calcminus2(n) << '\n';
	return 0;
}


Measured memory_bytes: 256
alpha='abcdefghijklmnopqrstuvwxyz'
from collections import defaultdict
datas=defaultdict(int)
datat=defaultdict(int)
for s in input():
    datas[s]+=1
for t in input():
    datat[t]+=1
S=''
for k in alpha:
    S+=k*datas[k]
T=''
alpha=alpha[::-1]
for k in alpha:
    T+=k*datat[k]
alpha=alpha[::-1]
if len(S)<len(T) and S==T[:len(S)]:
    print('Yes')
elif S==T:
    print('No')
elif len(S)>len(T) and T==S[:len(T)]:
    print('No')
else:
    for i in range(min(len(S),len(T))):
        if alpha.index(S[i])<alpha.index(T[i]):
            print('Yes')
            break
        elif alpha.index(S[i])>alpha.index(T[i]):
            print('No')
            break

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

vector<ll> bitconversion(ll i, ll n, ll N){
    ll x = 1;
    rep(j,N){
        x *= n;
    }
    vector<ll> vec(N);
    rep(j,N){
        x /= n;
        vec[j] = i / x;
        i -= x * vec[j];
    }
    return vec;
}

int main(){
    ll N;
    cin >> N;
    vector<ll> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    vector<vector<ll> > bit60(N, vector<ll>(60));
    rep(i,N){
        vector<ll> binary = bitconversion(vec[i], 2, 60);
        rep(j,60){
            bit60[i][j] = binary[j];
        }
    }
    ll ans = 0;
    ll num = 1;
    for (int i = 59; i >= 0; i--){
        ll count_0 = 0;
        rep(j,N){
            if (bit60[j][i] == 0) count_0++;
        }
        ans += ((num % 1000000007) * (((N - count_0)* count_0) % 1000000007)) % 1000000007;
        num *= 2;
        ans = ans % 1000000007;
    }
    cout << ans << endl;
}


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

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

   int a,b,c,d = 0,e = 0;

   cin >> a >> b >> c;

   for(int i = 1; i < 100; ++i){
      d += a;
      if(d % b == c){
         cout << "YES" << endl;
         return 0;
      }
   }
   cout << "NO" << endl;

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

int main(void) {
  int a, b, c;
  cin >> a >> b >> c;

  cout << (a + b + c >= 22?"bust":"win")<<endl;
  
  return 0;
}

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

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

int main()
{
    IOS

    int n, m, resp = 0;
    cin >> n >> m;
    n--; m--;
    if ( n <= 0 ) resp += 0;
    else
    {
        resp += ( n * n + n ) / 2;
    }

    if ( m <= 0 ) resp += 0;
    else
    {
        resp += ( m * m + m ) / 2;
    }

    cout << resp;

    return 0;
}


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

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

    int n, a[200001];
    cin >> n;
    unordered_map<llong,llong> M;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ++M[a[i]];
    }

    vector<llong> P2;
    llong k = 2;
    while (1) {
        P2.push_back(k);
        k *= 2;
        if (k > 2 * 1000000000) break;
    }

    sort(a, a + n, greater<int>());
    llong ans = 0;
    for (int i = 0; i < n; ++i) {
        if (M.find(a[i]) == M.end()) continue;
        --M[a[i]];
        if (M[a[i]] <= 0) M.erase(a[i]);
        for (vector<llong>::iterator itr = P2.end() - 1; itr != P2.begin() - 1; --itr) {
            llong target_key = *itr - a[i];
            // cout << *itr << " " << a[i] << endl;
            if (target_key <= 0) break;
            if (M.find(target_key) != M.end()) {
                // cout << "find" << " " << a[i] << " " << target_key << " " << M[target_key] << endl;
                ++ans;
                --M[target_key];
                if (M[target_key] <= 0) M.erase(target_key);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11336
import heapq

n,m=map(int,input().split())
a=list(map(int,input().split()))
aa=list(map(lambda x:x*(-1),a))
heapq.heapify(aa)
for i in range(m):
    max=heapq.heappop(aa)
    heapq.heappush(aa,max//2+max%2)
print(-1*sum(aa))

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

using namespace std;

string s;

int main()
{
    cin >> s;
    int len = s.size();
    bool flag = false;
    
    for (int i = 0; i < len; ++i)
    {
        if (s[i] == 'C')
            flag = true;
        if (flag && s[i] == 'F')
        {
            printf("Yes");
            return 0;
        }
    }
    
    printf("No");
    return 0;
}

Measured memory_bytes: 256
/*Flamenco Sketches*/
#include<bits/stdc++.h>
using namespace std;
 
#define NL '\n'
#define xx first
#define yy second
#define ll long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define sz(x) x.size()
#define all(x) (x).begin(), (x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define async() ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 
//#define FayeValentine 
void dbg(){cerr<<NL;}template<typename H,typename... T> void dbg(H h,T... t){cerr<<' '<<h;dbg(t... );}
#ifdef  FayeValentine
#define debug(...) cerr<<"("<<#__VA_ARGS__<<"):",dbg(__VA_ARGS__)
#else
#define debug(...) 
#endif


void absinthe() {
	ll sum = 0, n; cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int k = 1; k <= n; k++)
				sum += __gcd(i, __gcd(j, k));
	cout << sum << NL; 
}
 
 
int main(){
  //freopen("input.txt", "r", stdin);
  async();
  int __t = 1; //cin >> __t;
  for(int __c = 1; __c <=__t; __c++) {
    //cout << "Case #" << __c << ": "; 
    absinthe();
  }
}  

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

int main() {
  double a, b;
  cin >> a >> b;
  double x = (a+b)/2;
  int y = (a+b)/2;
  if ((x-y) >= 0.5) cout << y+1 << endl;
  else if((x-y) < 0.5) cout << y << endl;
}


Measured memory_bytes: 256
n = int(input())
S,T = set(),set()
a = [int(i) for i in input().split()]
for i in range(n):
    S.add(a[i])
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    T.add(a[i])
print(len(S&T))

"""
5
1 2 3 4 5
3
3 4 1
"""


Measured memory_bytes: 6560
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
  uint64_t n, p;
  while (std::cin >> n >> p) {
    std::vector<uint64_t> num, cnt;
    for (uint64_t i = 2; i * i <= p; ++ i) {
      if (p % i == 0) {
        num.push_back(i);
        int temp = 0;
        while (p % i == 0) {
          p /= i;
          ++ temp;
        }
        cnt.push_back(temp);
      }
    }
    if (p > 1) {
      num.push_back(p);
      cnt.push_back(1);
    }
    uint64_t res = 1;
    for (int i = 0; i < num.size(); ++ i) {
      while (cnt[i] >= n) {
        res *= num[i];
        cnt[i] -= n;
      }
    }
    std::cout << res << std::endl;
  }
  return 0;
}


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

int main()
{
  int n;

   cin>>n;
   int A[n+1][3];

  for(int i=1;i<=n;i++)
  {
    for(int j=0;j<3;j++)
      cin>>A[i][j];
  }
  int dp[n+1][3];
  dp[1][0]=A[1][0];
  dp[1][1]=A[1][1];
  dp[1][2]=A[1][2];

  for(int i=2;i<=n;i++)
  {
    dp[i][0]=max(dp[i-1][1]+A[i][0],dp[i-1][2]+A[i][0]);
    dp[i][1]=max(dp[i-1][2]+A[i][1],dp[i-1][0]+A[i][1]);
    dp[i][2]=max(dp[i-1][0]+A[i][2],dp[i-1][1]+A[i][2]);
  }
  int a=max(dp[n][0],dp[n][1]);
  a=max(a,dp[n][2]);
  cout<<a;
  return 0;

}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int dx[2]={1,0};
int dy[2]={0,1};

int main() {
  int h,w;
  cin>>h>>w;
  //
  bool visited[h][w];
  rep(i,0,h)rep(j,0,w)visited[i][j]=false;
  //
  vector<string> a(h);
  rep(i,0,h) cin>>a[i];
  bool ok=true;
  ////////
  queue<P> root;
  root.push(mp(0,0));
  visited[0][0]=true;
   while(!root.empty()){
    P now=root.front();
    root.pop();
   int x=now.first;
   int y=now.second;
     //if(now==mp(w-1,h-1))break;
    rep(i,0,2){
      int nx=x+dx[i];
      int ny=y+dy[i];
     // cout<<nx<<endl;
      if(nx>=h||ny>=w) continue;
      if(a[nx][ny]=='.') continue;
      if(visited[nx][ny])continue;
      root.push(mp(nx,ny));
      visited[nx][ny]=true;  
      break;
    }  
  }
  rep(i,0,h){
   rep(j,0,w){
      if(!visited[i][j]&&a[i][j]=='#') ok=false; 
   }
  }
 // root.push(mp(h,w));
  
  if(ok){
   cout<<"Possible"<<endl;
  }
  else cout<<"Impossible"<<endl;
}

Measured memory_bytes: 3624
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)


Measured memory_bytes: 132688
#include <stdio.h>
#define N 100000
#define NIL -1
typedef struct nn
{
  int parent,left,right;
}Node;
Node T[N];
void print(int u);
int  a,D[N];
int main()
{
  int key,k,c,l,r,i,j;

  scanf("%d",&a);

  for(i=0;i<a;i++)
    {
      T[i].parent=T[i].left=T[i].right=NIL;
    }
  for(i=0;i<a;i++)
    {
      scanf("%d%d",&key,&k);
      for(j=0;j<k;j++){
	
      scanf("%d",&c);
      if(j==0)
	{
	  T[key].left=c;
	}
      else T[l].right=c;
      l=c;
      T[c].parent=key;
      }
    }


  for(i=0;i<a;i++)
    {
      if(T[i].parent==NIL){
	r=i;
      }
    }
  deep(r,0);
  for(i=0;i<a;i++)
    {
      print(i);
    }
	  



  return 0;
  
}


void print(int u)
{
  int i,c ;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("depth = %d, ",D[u]);
  if(T[u].parent==NIL)printf("root, ");
  else  if(T[u].left==NIL)printf("leaf, ");
  else printf("internal node, ");
  printf("[");

  for(i=0,c=T[u].left;c!=NIL;i++,c=T[c].right)
    {
      if(i)printf(", ");
      printf("%d",c);
    }
      printf("]\n");
    
  
}

int deep(int u,int p)
{
  D[u]=p;
  if(T[u].right!=NIL)deep(T[u].right,p);
  if(T[u].left!=NIL)deep(T[u].left,p+1);

}



Measured memory_bytes: 6400
// O(qlogn)
#include<bits/stdc++.h>
#define pb push_back
#define sf scanf
#define pf printf
using namespace std;

const int N=2e6+9;

void slv()
{
    int n,x,t;
    cin>> n >> x >>t;
    int d=ceil(n*1.0/x);
    cout<<d*t<<endl;
}
int main()
{
    int t;
    t=1;
    for(int cs=1;cs<=t;cs++) {
        //printf("Case %d:\n",cs);
        slv();
    }
    return 0;
}


Measured memory_bytes: 3620
/*"for if God is with them who can be against them."
   it's beter to die struggling than to abandon the effort where there is still
   a chance of accomlishing something more..NEVER GIVE UP.
   */

/* "IF THERE IS NO WAY OUT LOOK AT THE BOTTOM". */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define endl '\n'
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
#define watch(x) cout << (#x) << " is " << (x) << endl
void solve() {
	int h, w, m;
	cin >> h >> w >> m;
	map<int, int>x;
	map<int, int>y;
	vector<pii>p(m);
	map<pii, int>mark;
	for (int i = 0; i < m; i++) {
		cin >> p[i].F >> p[i].S;
		mark[p[i]]++;
		x[p[i].F]++;
		y[p[i].S]++;
	}
	int ans1 = 0, ans2 = 0;
	for (auto v : x) {
		ans1 = max(ans1, v.S);
	}
	for (auto v : y) {
		ans2 = max(ans2, v.S);
	}
	vector<int>r;
	vector<int>c;
	for (auto v : x) {
		if (v.S == ans1) {
			r.PB(v.F);
		}
	}
	for (auto v : y) {
		if (v.S == ans2) {
			c.PB(v.F);
		}
	}
	ll k = 1LL * (r.size()) * (c.size());
	if (k > 300000LL) {
		cout << ans1 + ans2 << endl;
		return;
	}
	for (auto p : r) {
		for (auto q : c) {
			if (mark[ {p, q}] == 0) {
				cout << ans1 + ans2 << endl;
				return;
			}
		}
	}
	cout << ans1 + ans2 - 1 << endl;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	IOS;
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
#ifndef ONLINE_JUDGE
	cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
#endif
	return 0;
	/*TRY AGAIN, NO MATTER HOW MANY TIMES YOU FAILED ALWAYS TRY ONCE MORE*/
}

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

int main(){
  int k,a,b;
  cin>>k;
  cin>>a>>b;
  int v = b/k;
  v=v*k;
  if(v>=a && v<=b){
    cout<<"OK\n";
  }
  else
    cout<<"NG\n";
  return 0;
}

Measured memory_bytes: 3620
n, k = map(int,input().split())
mod = int(1e9+7)


def combination(n, r, mod):
    np1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (np1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


for i in range(1, k+1):
    if n-k+1 < i:
        print(0)
    else:
        c1 = combination(k-1, i-1, mod)
        c2 = combination(n-k+1, i, mod)
        print(c1 * c2 % mod)



Measured memory_bytes: 3316
def func():
  n,m=map(int,input().split())
  o=[input() for _ in range(n)]
  p=[input() for _ in range(m)]
  q=[]
  for i in range(n-m+1):
    for j in range(n-m+1):
      fl=True
      for k in range(m):
        for l in range(m):
          if p[k][l]!=o[i+k][j+l]:
            fl=False
      q.extend([fl])
  return q

a=func()
if sum(a):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//using ll = long long;
using P = pair<int,int>;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

int dp[4][5000 * 5000 + 5];

signed main(){
	int n,d[2][3];
	cin >> n;
	for(int i = 0;i < 2;i++){
		for(int j = 0;j < 3;j++) cin >> d[i][j];
	}
	for(int t = 0;t < 2;t++){
		for(int i = 0;i < 4;i++){
			for(int j = 0;j <= n;j++) dp[i][j] = -INF;
		}
		dp[0][n] = 0;
		for(int i = 0;i < 3;i++){
			for(int j = n;j >= 0;j--){
				chmax(dp[i + 1][j],dp[i][j]);
				if(j - d[t][i] >= 0) chmax(dp[i][j - d[t][i]],dp[i][j] + d[(t + 1) % 2][i] - d[t][i]);
			}
		}
		int ma = 0;
		for(int i = 0;i <= n;i++) chmax(ma,dp[3][i]);
		n += ma;
	}
	cout << n << endl;
}

Measured memory_bytes: 781440
fun main(args: Array<String>) {
    val a = "AKIHABARA"
    val s = StringBuilder(readLine()!!)
    for (i in 0 until a.length) {
        if (a[i] != s.getOrNull(i) && a.getOrNull(i + 1) != s.getOrNull(i)) {
            println("NO")
            return
        } else if (a[i] != s.getOrNull(i) ) {
            s.insert(i, "A")
        }
    }
    if (s.length == a.length) {
        println("YES")
    } else {
        println("NO")
    }
}

Measured memory_bytes: 33844
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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

const long long INF = 1LL << 60;

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

  cout << (n%2 == 0 ? n : 2*n) << endl; 

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);  
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
       ios_base::sync_with_stdio(false);  
       cin.tie(NULL);
       /*
       ll n , cnt = 0;
       cin>>n;
       ll a[n];  
       for (int i = 0; i < n; ++i)
       {
       	 cin>>a[i];
       }
       for (int i = 0; i < n - 2; ++i)
       {
       	 if(a[i] != a[i+2]){
       	 	cnt++;
       	 }
       }  
       cout<<cnt<<endl;  
       return 0;
   }
   _______________________________Main_______________

int n ,k;  
cin>>n>>k;
int i = 0 , j = 0 , l= 0;
int cnt = 0;
for (i = 1; i <= n; i++) 
        { 
            for (j = 1; j <= n; j++) 
            { 
                for (l = 1; l <= n; l++) 
                { 
  
                     
 if ((i + j) % k == 0 && (i + l) % k == 0 && (j + l) % k == 0) 
                        cnt++; 
                 
            } 
        } 
}
cout<<cnt<<endl;
}

*/

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

Measured memory_bytes: 5188
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).size()
#define MAX(list) std::max(list)
#define MIN(list) std::min(list)
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())

using namespace std;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

using ll = long long;
constexpr int mod = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u * v / gcd(u, v);
}

void dfs(ll N, ll n, int& ans) {
    if (n > N)return;

    map<int, int> m;
    ll tmp = n;
    while (tmp > 0) {
        m[tmp % 10]++;
        tmp /= 10;
    }
    if (m[3] > 0 && m[5] > 0 && m[7] > 0)ans++;

    dfs(N, n * 10 + 3, ans);
    dfs(N, n * 10 + 5, ans);
    dfs(N, n * 10 + 7, ans);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);

    ll N;
    cin >> N;

    int ans = 0;
    dfs(N, 3, ans);
    dfs(N, 5, ans);
    dfs(N, 7, ans);

    cout << ans << endl;
    return 0;

}

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

#define M 1048576
#define NIL (-1)
#define L 18

char H[M][L];

int getChar(char ch) {
  if (ch == 'A') return 1;
  else if (ch == 'C') return 2;
  else if (ch == 'G') return 3;
  else if (ch == 'T') return 4;
  return 0;
}

long long getKey(char str[]) {
  long long sum = 0, p = 1, i;
  for(i = 0; i < strlen(str); i++) {
    sum += p * (getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key) {return key % M;}
int h2(int key) {return 1 + (key % (M - 1));}

int find(char str[]) {
  long long key, i, h;
  key = getKey(str);
  for(i = 0; ; i++) {
    h = (h1(key) + i * h2(key)) % M;
    if(strcmp(H[h],str) == 0) return 1;
    else if(strlen(H[h]) == 0) return 0;
  }
  return 0;
}

int insert(char str[]) {
  long long key, i, h;
  key = getKey(str);
  for(i = 0; ; i++) {
    h = (h1(key) + i * h2(key)) % M;
    if(strcmp(H[h], str) == 0) return 1;
    else if(strlen(H[h]) == 0) {
      strcpy(H[h], str);
      return 0;
    }
  }
  return 0;
}

int main(void) {
  int i, n;
  char str[L], com[9];
  for(i = 0; i < M; i++) H[i][0] = '\0';
  scanf("%d", &n);
  for(i = 0; i < n; i++) {
    scanf("%s %s", com, str);
    if(com[0] == 'i') {
      insert(str);
    } else {
      if(find(str)) {
        printf("yes\n");
      } else {
        printf("no\n");
      }
    }
  }
  return 0;
}



Measured memory_bytes: 20156
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	void run(){

		for(; sc.hasNext();){
			String s=sc.next();
			int[] a=new int[10];
			for(int i=0; i<s.length(); i++){
				a[s.charAt(i)-'0']++;
			}
			solve(a);
		}
	}

	void solve(int[] a){
		LinkedList<Integer> list=new LinkedList<Integer>();
		for(int i=1; i<=9; i++){
			a[i]++;
			if(satisfy(a.clone())){
				list.add(i);
			}
			a[i]--;
		}
		for(int i=0; i<list.size(); i++){
			print(list.get(i)+(i==list.size()-1?"\n":" "));
		}
		if(list.size()==0){
			println("0");
		}
	}

	boolean satisfy(int[] a){
		if(!check(a)){
			return false;
		}
		for(int i=1; i<=9; i++){
			a[i]-=2;
			if(rec(a, 0)){
				return true;
			}
			a[i]+=2;
		}
		return false;
	}

	boolean rec(int[] a, int n){
		if(!check(a)){
			return false;
		}
		if(n==4){
			return true;
		}
		for(int i=1; i<=9; i++){
			a[i]-=3;
			if(rec(a, n+1)){
				return true;
			}
			a[i]+=3;
		}
		for(int i=1; i<=7; i++){
			a[i]--;
			a[i+1]--;
			a[i+2]--;
			if(rec(a, n+1)){
				return true;
			}
			a[i]++;
			a[i+1]++;
			a[i+2]++;
		}
		return false;
	}

	boolean check(int[] a){
		for(int e : a){
			if(e<0||e>4){
				return false;
			}
		}
		return true;
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 12000
from itertools import permutations
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

P = list(permutations([i for i in range(2, N + 1)]))
ans = 0
for p in P:
    flag = True
    for j in range(len(p) - 1):
        if j == 0:
            a = 1
            b = p[j]
            if [a, b] not in ab:
                flag = False
        a = min(p[j], p[j + 1])
        b = max(p[j], p[j + 1])
        if [a, b] not in ab:
            flag = False
    if flag:
        ans += 1
print(ans)
    

Measured memory_bytes: 3572
#include <bits/stdtr1c++.h>
#define pb push_back
#define fi first
#define sc second
#define inf	1000000000LL
#define MP make_pair
#define N 300005
#define MOD 1000000007 
#define orta ((a+b)/2)
using namespace std;
typedef long long int lint;
typedef pair<int,int> ii;

ii d[N];
std::vector<ii> v;
int main()
{
	int n,k;
	cin >> n >> k;

	int sum=0;
	int t=1;
	v.pb(MP(2,1));
	int i=3,mx=2;
		
	for ( ; i <=n; ++i)
	{
		if(k>0)
		{
			k-=t;
			t++;
			v.pb(MP(i,1));
			mx=max(mx,i);
			if(k==0) break;
		}
		else break;
	}
	if(k>0)
	{	
		printf("-1\n");
		return 0;
	}
	for (int i = 0; i < -k; ++i)
	{
		v.pb(MP(2,i+3));
	}
	for (int i = mx+1; i <= n; ++i)
	for (int j = 1; j <= i-1; ++j)
		v.pb(MP(i,j));
	cout << v.size() << endl;
	for (int i = 0; i < v.size(); ++i)
	{
		cout << v[i].fi << " " << v[i].sc << endl;
	}
}

Measured memory_bytes: 384
//package abc118_B;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] cnt = new int[m];
		
		for (int i = 0; i < n; i++) {
			int k = sc.nextInt();
			for (int j = 0; j < k; j++) {
				int a = sc.nextInt();
				cnt[a - 1]++;
			}
		}
		
		int ans = 0;
		
		for (int i = 0; i < m; i++) {
			if (cnt[i] == n) ans++;
		}
		
		System.out.println(ans);
	}

}

Measured memory_bytes: 21972
from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))

def f(p):
    ret = 0
    ma = 0
    for i, a in enumerate(A):
        if p[i] == 1:
            if ma == 0:
                pass
            else:
                if ma >= a:
                    ret += ma - a + 1
                    ma += 1
        ma = max(ma, a)
    return ret

ans = 10 ** 20
for comb in combinations(range(N), K):
    p = [1 if i in comb else 0 for i in range(N)]
    #if sum(p) < K: continue
    #print(p)
    ans = min(ans, f(p))

print(ans)



Measured memory_bytes: 43484