akhauriyash/Code-Regression huggingface dataset:
import numpy as np

def InputToInt():
    A = input().split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A

if __name__ == '__main__':
    N, D = InputToInt()

    X = np.empty((N, D))
    for i in range(N):
        X[i, :] = InputToInt()

    count = 0
    for i in range(N-1):
        for j in range(i+1, N):
            d = np.linalg.norm(X[i,:]-X[j,:], ord=2)
            if d == int(d):
                count += 1

    print(count)


Measured memory_bytes: 12428
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n){
    Int res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

Int gcd(Int a, Int b) {
    return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
    return a * b / gcd(a, b);
}
// a x + b y = gcd(a, b)
Int extgcd(Int a, Int b, Int &x, Int &y) {
    Int g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

int s[100005];


int main(){
    cin.tie(0);

    string S;
    cin >> S;
    int K;
    cin >> K;

    for (int i = 0; i < S.length(); i++){
        s[i] = S[i] - 'a';
    }
    for (int i = 0; i < S.length(); i++){
        if (s[i] != 0 && 26 - s[i] <= K){
            K -= 26 - s[i];
            s[i] = 0;
        }
    }
    s[S.length()-1] += K%26;

    for (int i = 0; i < S.length(); i++){
        cout << char('a'+s[i]);
    }
    cout << endl;
    return 0;
} 


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

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

int main() {
  ll n, ans = 0, four = 0, two = 0, tf = 0, sf = 0, ft = 0;
  cin >> n;
  map<int, int> mp;

  for (int i = 2; i <= n; ++i) {
    int t = i, j = 2;
    while (j * j <= i && t > 1)
      if (t % j == 0)
        mp[j]++, t /= j;
      else
        j++;

    if (t > 1) mp[t]++;
  }

  for (auto m : mp) {
    if (m.second >= 74) sf++;
    if (m.second >= 24) tf++;
    if (m.second >= 14) ft++;
    if (m.second >= 4) four++;
    if (m.second >= 2) two++;
  }

  ll m4 = sf + tf + ft + four;
  ans += sf;
  ans += tf * (two - 1);
  ans += ft * (four - 1);
  ans += four * (four - 1) * (two - 2) / 2;

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

Measured memory_bytes: 3612
#include<stdio.h>
	int main(){
		int a[20][20],x,y,s,k=0,i,j,max=0;
		for(i=0;i<20;i++)
			for(j=0;j<20;j++)
			a[i][j]=0;
		while(scanf("%d,%d,%d",&x,&y,&s)!=EOF){
			if(s==1){
				a[y+2][x+2]++;
				a[y+3][x+2]++;
				a[y+1][x+2]++;
				a[y+2][x+1]++;
				a[y+2][x+3]++;
			}
			else
			if(s==2){
				a[y+2][x+2]++;
				a[y+3][x+2]++;
				a[y+1][x+2]++;
				a[y+2][x+1]++;
				a[y+2][x+3]++;
				a[y+3][x+3]++;
				a[y+1][x+3]++;
				a[y+3][x+1]++;
				a[y+1][x+1]++;
			}
			else if(s==3){
				a[y+2][x+2]++;
				a[y+3][x+2]++;
				a[y+1][x+2]++;
				a[y+2][x+1]++;
				a[y+2][x+3]++;
				a[y+3][x+3]++;
				a[y+1][x+3]++;
				a[y+3][x+1]++;
				a[y+1][x+1]++;
				a[y+2][x]++;
				a[y+2][x+4]++;
				a[y][x+2]++;
				a[y+4][x+2]++;
			}
		}
			for(i=2;i<12;i++)
			for(j=2;j<12;j++){
				if(a[i][j]==0)
					k++;
				if(a[i][j]>max)
					max=a[i][j];
		}
		printf("%d\n%d\n",k,max);
		return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9,MOD = 1e9+7,ohara = 1e6;
const ll LINF = 1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt=0,ans=0,a,b[ohara],c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos,k;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl,visited[ohara];
struct edge{int to,cost;};
vector<ll> g[ohara];

//-------------------------↓↓↓↓↓↓------------------------

ll dfs(ll parent,ll now){
    ll now_depth=0;
    rep(i,Size(g[now])){
        ll to=g[now][i];
        now_depth=max(dfs(now,to),now_depth);
    }
    if(now_depth==k-1){
        if(parent!=0)ans++;
        return 0;
    }
    else return now_depth+1;
}

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>n>>k;
    rep(i,n){
        cin>>a;
        if(i==0&&a!=1)ans=1;
        if(i==a-1)continue;
        if(i==0)continue;
        b[i]=a-1;
        a--;
        g[a].push_back(i);
    }
    dfs(0,0);
    Cout(ans);
    return 0;
}


Measured memory_bytes: 36224
open Printf
open Scanf

let id x = x

let s = read_line ()

let () =
    let ary = Array.init 26 (fun i -> 0) in
    String.iter (fun c ->
        let idx = int_of_char c - int_of_char 'a' in
        ary.(idx) <- ary.(idx) + 1
    ) s;
    try
        for i = 0 to 25 do
            if ary.(i) = 0 then begin
                printf "%c\n" (char_of_int (i + int_of_char 'a'));
                failwith ""
            end
        done;
        print_endline "None"
    with Failure _ -> ()


Measured memory_bytes: 2432
#include <climits>
#include <cmath>
#include <iostream>

// 1  2  3  4  5
// 2  4  6  8 10

int main(int argc, char *argv[]) {
  long n;
  std::cin >> n;

  long min = LONG_MAX;
  for (int i = 1; i <= sqrt(n); ++i) {
    if (i * (n / i) == n)
      min = std::min(min, (i - 1) + (n / i - 1));
  }
  std::cout << min << std::endl;
}


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

ll lcd(ll a, ll b) {
  if (a < b) {
    swap(a, b);
  }
  if (b == 0) {
    return a;
  } else {
    return lcd(b, a % b);
  }
}
struct PC {
  unsigned int P, C;
};

int main() {
  string S, T;
  cin >> S >> T;
  string alpha = "abcdefghijklmnopqrstuvwxyz";
  vector<int> cnt_s(26, 0), cnt_t(26, 0);
  for (int i = 0; i < S.size(); ++i) {
    int c = 0;
    for (int j = 0; j < 26; ++j) {
      if (S[i] == alpha[j]) {
        ++cnt_s[j];
        ++c;
      }
      if (T[i] == alpha[j]) {
        ++cnt_t[j];
        ++c;
      }
      if (c == 2) {
        break;
      }
    }
  }
  sort(cnt_s.begin(), cnt_s.end());
  sort(cnt_t.begin(), cnt_t.end());
  bool flg = true;
  for (int i = 0; i < cnt_s.size(); ++i) {
    if (cnt_s[i] != cnt_t[i]) {
      flg = false;
      break;
    }
  }
  if (flg) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 776
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define PI 3.141592653589793
#define MOD 1000000007

//qsort用、昇順
int compare_int(const void *a, const void *b)
{
	return *(int*)a-*(int*)b;
}
//qsort(data, 10, sizeof(int), compare_int)

int main(){
	double a, b, h, m;
	scanf("%lf%lf%lf%lf", &a, &b, &h, &m);
	double theta = fabs(11*m-60*h);
	//printf("%f\n", theta);
	double cosx = cos(theta*PI/360);
	//printf("%f\n", cosx);
	//printf("%f, %f, %f\n", a*a, b*b, 2*a*b*cosx);
	double ans = sqrt(a*a - 2*a*b*cosx + b*b);
	printf("%10.10lf\n", ans);
	
	return 0;
}

Measured memory_bytes: 2596
#include<bits/stdc++.h>
using namespace std;
int len[] = {5,7,5,7,7};
int main(){
  int n;
  while(cin >> n , n){
    string str[n+1];
    for(int i=0;i<n;i++){
      cin >> str[i];
    }
    for(int i=0;i<n;i++){
      int sum = 0;
      int idx = 0;
      bool flag = false;
      for(int j=i;j<n;j++){
	sum += str[j].size();
	if(len[idx] == sum){
	  sum = 0;
	  idx++;
	} else if(len[idx] < sum) break;
	if(idx == 5){
	  flag = true;
	  break;
	}
      }
      if(flag){
	cout << i+1 << endl;
	break;
      }
    }
  }
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e10;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)
typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;

vector<ll> sou_count(53, 1);
vector<ll> pate_count(53, 1);


ll rec(ll n, ll x) {
    if(n == 0) {
        return 1;
    }

    // X = 1 のとき: f(N, X) = 0 (一番下のバンだけ)
    if (x == 1) {
        return 0;
    }
    // 1 < X ≤ 1 + ai−1 のとき: f(N, X) = f(N − 1, X − 1)
    if (1 < x && x <= 1 + sou_count[n - 1]) {
        return rec(n - 1, x - 1);
    }
    // . X = 2 + ai−1 のとき: f(N, X) = pi−1 + 1
    if (x == 2 + sou_count[n - 1]) {
        return pate_count[n - 1] + 1;
    }
    // 2 + ai−1 < X ≤ 2 + 2ai−1 のとき: f(N, X) = pi−1 + 1 + f(N − 1, X − 2 − ai−1)
    if (2 + sou_count[n - 1] < x && x <= 2 + 2 * sou_count[n - 1]) {
        return pate_count[n - 1] + 1 + rec(n - 1, x - 2 - sou_count[n - 1]);
    }
    // X = 3 + 2ai−1 のとき: f(N, X) = 2pi−1 + 1
    return 2 * pate_count[n - 1] + 1;
}


int main() {


    for (int i = 0; i < 52; i++) {
        ll pc = (1ll << (i + 2)) - 1;
        ll sum = (1ll << (i + 3)) - 3;

        sou_count[i + 1] = sum;
        pate_count[i + 1] = pc;
    }

    ll n, x;
    cin >> n >> x;

    ll ans = rec(n,x);

    cout << ans << endl;

}



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

using namespace std;

int main() {

    int p, f, aux, fd, ans=0;
    int likes[1000000]={};
    char c='x';

    cin>>p>>f;

    for(int i=0;i<p;i++)
    {
        cin>>aux;

        while(aux--)
        {
            cin>>fd;

            likes[fd]++;
        }
    }

    for(int i=0;i<1000000;i++)
    {
        if(likes[i]==p)
        {
            ans++;
        }
    }

    cout<<ans<<endl;

    return 0;
}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// =================グラフテンプレート==================

// costの部分の型は指定できます
template <typename T>
struct edge {
  int from, to;
  T cost;

  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}

  // 行き先を代入できる
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  // その他便利機能、って感じ
  operator int() const { return to; }
  bool operator<(edge x) { return this->cost < x.cost; }
};

template <typename T>
using Edges = vector<edge<T>>;

template <typename T>
using WeightedGraph = vector<Edges<T>>;

template <typename T>
using Matrix = vector<vector<T>>;

using UnWeightedGraph = vector<vector<int>>;

// ==========================プリム法==========================
// 実質ダイクストラっぽく見えるやつ。頂点より辺の数の方が多い時はこっち。
// とある頂点を選んで、そこから一番近い頂点を選んでいく。重み付きグラフが必要。
template <typename T>
T prim(WeightedGraph<T> &g) {
  using Pi = pair<T, int>;

  T total = 0;
  vector<bool> used(g.size(), false);
  priority_queue<Pi, vector<Pi>, greater<Pi>> que;  // 小さい順に出てくる
  que.emplace(0, 0);
  while (!que.empty()) {
    auto p = que.top();
    que.pop();
    if (used[p.second]) continue;
    used[p.second] = true;
    total += p.first;
    for (auto &e : g[p.second]) {
      que.emplace(e.cost, e.to);
    }
  }
  return total;
}

// ====================================================================

int main() {
  int n, m;
  cin >> n >> m;
  WeightedGraph<ll> g(n);
  for (int i = 0; i < m; i++) {
    int s, t, c;
    cin >> s >> t >> c;
    g[s].push_back(edge<ll>{t, c});
    g[t].push_back(edge<ll>{s, c});  // 無向グラフなら
  }

  cout << prim<ll>(g) << endl;
}



Measured memory_bytes: 12412
#include <iostream>
using namespace std;
int main() {
  int n, m;
  cin >> n;
  cin >> m;
  int dp[n+1];
  for (int i = 0; i < n+1; ++i) {
    dp[i] = 1;
  }
  dp[n+1] = 0;
  for (int i = 0; i < m; ++i) {
    int a;
    cin >> a;
    dp[a] = 0;
  }
  for (int i = n-1; i >= 0; --i) {
    if (dp[i] > 0) {
      dp[i] = (dp[i+1] + dp[i+2]) % 1000000007;
    }
  }
  cout << dp[0] << endl;

  return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>

using namespace std;


#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

int h,w;

int c[52][52];

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


void dfs(int i,int j);



int main(){


	while(1){
		cin >> w >> h;

		if(h==0 && w == 0){
			break;
		}

		cnt=0;

		REP(i,h){
			REP(j,w){


				cin >> c[i][j] ;

			}
		}

		REP(i,h){
			REP(j,w){

				//cnt++??????????????\???????????????????????\???????????????
				if(c[i][j] == 1){
					cnt++;
					dfs(j,i);
				}
			}
		}

		cout << cnt << endl;
	}
	return 0;
}

void dfs(int i,int j){

	if(c[j][i] == 1){

		c[j][i] = 0;
		REP(k,8){
			//w???<=???????????£??????????????????
			if(0 <= i+dx[k] && i+dx[k] < w && 0 <= j+dy[k] && j+dy[k] < h){

				dfs(i+dx[k],j+dy[k]);
			}
		}
	}
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  int Alice = 0, Bob = 0;
  for(int i = 0; i < n; i++){
    if(i % 2 == 0){
      Alice += a[i];
    }
    else{
      Bob += a[i];
    }
  }
  cout << Alice - Bob << endl;
  return 0;
}

Measured memory_bytes: 3636
cnt = 0

def insertionSort(A, n, g):
    global cnt
    for i in range(g,n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v

def shellSort(A, n):
    h = 1
    G = []
    while h <= n:
        G.append(h)
        h = 3*h + 1

    for g in reversed(G):
        insertionSort(A, n, g)

    return G

def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    G = shellSort(A, N)
    
    # output
    print(len(G))
    for g in reversed(G):
        if g == G[0]:
            print(g)
        else:
            print(g, end=" ")
    print(cnt)
    for a in A:
        print(a)

if __name__ == "__main__":
    main()


Measured memory_bytes: 45520
#include<bits/stdc++.h>
using namespace std;
#define Fast   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long


int main()
{
    Fast;
    int a;cin>>a;
    cout<<a+(a*a)+(a*a*a)<<endl;

}


Measured memory_bytes: 3636
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val inputs = readLine()!!.split(" ").map { it.toInt() }

    // 余りが最大になるのは，最小公倍数-1 に対して余りを求める場合
    // このときの余りは それぞれ 割る値 - 1

    println(inputs.map { (it - 1).toLong() }.sum())



}

Measured memory_bytes: 42136
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
#include <functional>

using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define MOD 1000000007LL
#define rep(i,a,n) for (int i=a ; i<n ; i++)
#define per(i,a,n) for (int i=n-1 ; i>=a ; i--)
#define LLINF 100000000000000005LL
#define INF 1e9+1
#define endl '\n'

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string)s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto& x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}\n";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:\n", debug_out(__VA_ARGS__)

using llong = long long;
using VI = vector<int>;
using VLL = vector<long long>;
using PII = pair<int, int>;

//struct cmp {
//	bool operator() (int a, int b)
//	{
//		return a > b;
//	}
//};

int main()
{
    IOS;
    int n;
    cin >> n;
    int sum = 0;
    VI a(n);
    rep(i, 0, n) {
        cin >> a[i];
    }
    rep(i, 0, n) {
        rep(j, i + 1, n) {
            sum += a[i] * a[j];
        }
    }
    cout << sum;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)

const string YES = "Yes";
const string NO = "No";

void solve(long long K, long long X){
    if(K * 500 >= X){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long K;
    scanf("%lld",&K);
    long long X;
    scanf("%lld",&X);
    solve(K, X);
    return 0;
}


Measured memory_bytes: 256
# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H =defaultdict(int)
bom_W =defaultdict(int)
posision =set()
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision.add((h,w))
temp_H =max(bom_H.values())
temp_W =max(bom_W.values())
indx_H = [k for k,v in bom_H.items() if v == temp_H]
indx_W = [k for k,v in bom_W.items() if v == temp_W]
set_max_H = set(indx_H)
set_max_W = set(indx_W)


flag =False
for h in set_max_H:
    for w in set_max_W:
        if (h,w) not in posision:
            flag =True
            break
    if flag==True:
        break

if flag ==True:
    print(temp_H +temp_W )
else:
    print(temp_H +temp_W -1)

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

typedef long long ll;

vector<pair<pair<int, int>, ll> > edg;
pair<pair<ll, ll>, int> pt[100005];
int par[100005];
int n;

int gp(int x) { return par[x]==x?x:par[x]=gp(par[x]); }

ll cst(int a, int b)
{
	return min(abs(pt[a].first.first-pt[b].first.first), abs(pt[a].first.second-pt[b].first.second));
}

ll slv()
{
	for (int i = 0;i < n;i++) par[i] = i;
	ll ans = 0;
	sort(edg.begin(), edg.end(), [](pair<pair<int, int>, ll> a, pair<pair<int, int>, ll> b)->bool {
		return (a.second < b.second);
	});
	for (auto u: edg)
	{
		u.first.first = gp(u.first.first), u.first.second = gp(u.first.second);
		if (u.first.first == u.first.second) continue;
		par[u.first.first] = u.first.second;
		ans += u.second;
	}
	return ans;
}

int main()
{
	scanf("%d", &n);
	for (int i = 0;i < n;i++) scanf("%lld%lld", &pt[i].first.first, &pt[i].first.second);
	sort(pt, pt+n); n = unique(pt, pt+n)-pt;
	for (int i = 0;i < n;i++) pt[i].second = i;
	int ptr = -1;
	for (int i = 1;i < n;i++)
	{
		edg.emplace_back(make_pair(pt[i-1].second, pt[i].second), cst(i-1, i));
		if (pt[i].first.first == pt[i-1].first.first)
		{
			if (ptr != -1) edg.emplace_back(make_pair(pt[ptr].second, pt[i].second), cst(ptr, i));
		} else ptr = i-1;
	}
	reverse(pt, pt+n); ptr = -1;
	for (int i = 1;i < n;i++)
	{
		edg.emplace_back(make_pair(pt[i-1].second, pt[i].second), cst(i-1, i));
		if (pt[i].first.first == pt[i-1].first.first)
		{
			if (ptr != -1) edg.emplace_back(make_pair(pt[ptr].second, pt[i].second), cst(ptr, i));
		} else ptr = i-1;
	}
	sort(pt, pt+n, [](pair<pair<ll, ll>, int> a, pair<pair<ll, ll>, int> b)->bool {
		return (a.first.second!=b.first.second)?(a.first.second<b.first.second):(a.first.first<b.first.first);
	});
	ptr = -1;
	for (int i = 1;i < n;i++)
	{
		edg.emplace_back(make_pair(pt[i-1].second, pt[i].second), cst(i-1, i));
		if (pt[i].first.second == pt[i-1].first.second)
		{
			if (ptr != -1) edg.emplace_back(make_pair(pt[ptr].second, pt[i].second), cst(ptr, i));
		} else ptr = i-1;
	}
	reverse(pt, pt+n); ptr = -1;
	for (int i = 1;i < n;i++)
	{
		edg.emplace_back(make_pair(pt[i-1].second, pt[i].second), cst(i-1, i));
		if (pt[i].first.second == pt[i-1].first.second)
		{
			if (ptr != -1) edg.emplace_back(make_pair(pt[ptr].second, pt[i].second), cst(ptr, i));
		} else ptr = i-1;
	}
	printf("%lld\n", slv());
	return 0;
}


Measured memory_bytes: 20200
package main

import (
        "fmt"
        "math"
)

func main() {
        var n, k, x int
        fmt.Scan(&n)
        fmt.Scan(&k)

        answer := 0
        for i := 0; i < n; i++ {
                fmt.Scan(&x)
                kx := int(math.Abs(float64(k - x)))
                if x < kx {
                        answer = answer + x*2
                } else {
                        answer = answer + kx*2
                }
        }

        fmt.Printf("%d\n", answer)
}


Measured memory_bytes: 512
import sys
readline = sys.stdin.readline

N, M = map(int, input().split())
ab = [tuple(map(int, readline().split())) for _ in range(M)]

class UnionFind:
    def __init__(self, size):
        self.rank = [-1]*(size+1)
        self.number = [1]*(size+1)
        
    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
    
    def union(self, a, b):
        if a == b:
            return
        if self.rank[a] == self.rank[b]:
            self.rank[b] = a
            self.rank[a] -= 1
            self.number[a] += self.number[b]
        elif self.rank[a] < self.rank[b]:
            self.rank[b] = a
            self.number[a] += self.number[b]
        else:
            self.rank[a] = b
            self.number[b] += self.number[a]
            
p = N * (N - 1) // 2
ans = [p]
uf = UnionFind(N)

for a, b in ab[1:][::-1]:
    ar = uf.find(a)
    br = uf.find(b)
    
    if ar != br:
        p -= uf.number[ar] * uf.number[br]
        uf.union(ar, br)
    ans.append(p)

print(*ans[::-1], sep='\n')

Measured memory_bytes: 26068
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const ll mod=1e9+7;
const ll inf = (ll)1e17;
const ld eps = 1e-12;
const ld PI = 3.14159265358979323846;
ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int dp[10][10];


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    ll res=0;
    for(int i=1;i<=n;i++){
        string s=to_string(i);
        int taille=s.size();
        dp[s[0]-'0'][s[taille-1]-'0']++;
    }
    for(int i=0;i<=9;i++){
        for(int j=1;j<=9;j++){
            res+=(dp[i][j]*dp[j][i]);
        }
    }
    cout<<res<<endl;
    return 0;
    }


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl







using ll = long long;


const ll mod = 1e9+7;
const int maxn = 52;

void add(ll& x, ll y) {
    if (x>=mod) x%=mod;
    if (y>=mod) y%=mod;
    x += y;
    if (x>=mod) x%=mod;
}



ll brute(ll n, ll k) {
    vector<int> a(n);
    iota(a.begin(),a.end(),0);
    int count = 0;
    do {
	int res = 0;
	for (int i=0; i<n; i++) {
	    res += abs(i-a[i]);
	}
	if (res==k) {
	    for (int i: a) cout<<i+1<<" ";
	    cout<<endl;
	}
	count += (res==k);
    } while (next_permutation(a.begin(),a.end()));
    return count;
}

int n,oddness;

ll dp[maxn][maxn][maxn*maxn]; // seen 1..i, holding j elems, have oddness k

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

    cin>>n>>oddness;
    //ll bru = brute(n, oddness);
    if (oddness%2) out(0);

    oddness /= 2;

    dp[0][0][0] = 1;

    for (int i=0; i<n; i++) {
	for (int j=0; j<=n; j++) {
	    for (int k=0; k<=n*n; k++) {
		//if (dp[i][j][k]) cout<<i<<","<<j<<","<<k<<": "<<dp[i][j][k]<<endl;
		//use ith elem right here
		add(dp[i+1][j][k+j], dp[i][j][k]);

		//use ith elem, but in a previous hole
		add(dp[i+1][j][k+j], 1ll*j*dp[i][j][k]);

		//hold ith elem
		add(dp[i+1][j+1][k+j+1], dp[i][j][k]);


		//place past elem here, hold us
		if (j>0) {
		    add(dp[i+1][j][k+j], 1ll*j*dp[i][j][k]);
		}

		//place previously held elem here, place us somewhere in the past
		if (j>0) {
		    // j options for us in the past
		    // j options to place here
		    add(dp[i+1][j-1][k+j-1], 1ll*j*j%mod*dp[i][j][k]%mod);
		}
	    }
	}
    }


    ll res = dp[n][0][oddness];
    res %= mod;
    res += mod;
    res %= mod;

    // watch(res);
    // assert(res==bru);

    cout<<res<<endl;    
    return 0;
}


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

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

int main() {
    string s; cin >> s;
    int ans=pow(10, 9);
    rep(i, s.size()-2){
        ans = min(ans, abs(atoi(s.substr(i, 3).c_str()) - 753)); 
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define scii(a, b) scanf("%d %d", &a, &b)
#define sci(a) scanf("%d", &a)
#define pri(a) printf("%d ", a)
#define pril(a) printf("%d\n", a)
#define pb(a) push_back(a)
#define oo 1000000007
#define maxN 100005
using namespace std;
int n, m, par[maxN];
long long ans, sz[maxN];
struct canh{
    int u, v;
};
canh ca[maxN];



int findC(int u) {
    if(u != par[u]) return par[u] = findC(par[u]);
    return u;
}


void uSet(int u, int v) {
    int x = findC(u);
    int y = findC(v);
    if(x != y) {
        ans -= sz[x] * sz[y];
        if(sz[x] > sz[y]) {
            par[y] = x;
            sz[x] += sz[y]; 
        }
        else {
            if(sz[y] == sz[x]) {
                par[x] = y;
                sz[y] += sz[x];
            }
            else {
                par[x] = y;
                sz[y] += sz[x]; 
            }
        }
    }
} 

vector<long long> res;
int main() {
    //freopen("de.inp", "r", stdin);
    //freopen("de.out", "w", stdout);
    scii(n, m);
    ans = (long long)((long long)n*(n-1))/2;
    fto(i, 1, m) {
        scii(ca[i].u, ca[i].v);
    }
    fto(i, 1, n) {
        par[i] = i;
        sz[i] = 1;
    }

    fdto(i, m, 1) {
        res.pb(ans);
        uSet(ca[i].u, ca[i].v);
    }
    fdto(i, (int)res.size()-1, 0) {
        printf("%lld\n", res[i]);
    }
    return 0;
}

Measured memory_bytes: 4212
import sys

input = sys.stdin.readline

n = int(input())

def divisors(n):
    div = []
    i = 1
    while(i * i <= n):
        if n % i == 0:
            div.append(i)
            if i * i != n:
                div.append(n // i)
        i += 1
    return div

def f(a, b):
    al = len(str(a))
    bl = len(str(b))
    
    if al > bl:
        return al
    else:
        return bl

cand = divisors(n)

m =float('inf')

for a in cand:
    b = n // a
    c = f(a, b)
    if  c < m:
        m = c

print(c)    


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

int main() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(q);

    for (int i=0; i<q; i++) {
        cin >> a.at(i);
    }

    vector<int> nn(n), kk(n, k), qq(n, q);

    for (int i=0; i<q; i++) {
        int idx = a.at(i) - 1;
        nn.at(idx) ++;
    }

    for (int i=0; i<n; i++) {
        int ans = kk.at(i) - qq.at(i) + nn.at(i);
        if (ans > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 2176
// prevent memory leaking
#include <iostream>
#include <vector>
#include <memory>

using namespace std;

struct Node{
	int id;
	int depth;

	string state;

  int parent;
	vector<shared_ptr<Node>> children;

	Node():
		id(-1),
		state("root")
	{}

	Node(int id):
		id(id),
		state("root"),
		depth(0)
	{
		parent = -1;
	}

	void print() const{
		cout <<  "node "+ to_string(id) +": parent = "+ to_string(parent)+", depth = "+ to_string(depth) +", "+state+", [";
		if( children.size() != 0){
			for(int i=0;i < children.size()-1;i++){
				cout << to_string(children[i]->id) +", ";
			}
			cout<< to_string(children[children.size()-1]->id)<<"]\n";
		}else{
			cout<<"]\n";
		}
	}

};

shared_ptr<Node> make_node(int id){
	return make_shared<Node>(id);
}

void deep(int pos,shared_ptr<Node> node){
	node->depth = pos;
	if(node->children.size() == 0) return;
	for(auto c:node->children){
		deep(pos+1,c);
	}
}

int main(){

  int n, id, k, c;
  cin>>n;
	vector<shared_ptr<Node>> nodes(n);

  for(int i=0;i<n;i++){
  	cin >> id >> k;
		if(nodes[id] == nullptr){
			nodes[id] = make_node(id);
		}
		if(k == 0){
			nodes[id]->state = "leaf";
		}else{
			nodes[id]->state = "internal node";
  	  for(int j=0;j<k;j++){
				cin >> c;
				if(nodes[c] == nullptr){
					nodes[c] = make_node(c);
				}
				nodes[c]->parent = id;
				nodes[id]->children.push_back( nodes[c] );
			}
		}
  }

	shared_ptr<Node> root;
	for(int i=0;i<n;i++){
		if(nodes[i]->parent == -1){
			root = nodes[i];
			break;
		}
	}
	root->state = "root";
	deep(0,root);

	for(int i = 0; i< n;i++){
		nodes[i]->print();
	}
  return 0;
}

Measured memory_bytes: 19640
#include <bits/stdc++.h>
using namespace std;
int main() {

  for(int i=0; i<9; i++) {
    char s[16];
    int a, b;
    cin >> s >> a >> b;
    printf("%s %d %d\n", s, a+b, a*200 + b*300);
  }
} 

Measured memory_bytes: 1144
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int price = scanner.nextInt();
        boolean isBreak = false;

        for(int i=0; i<=25; i++) {
            for(int j=0; j<15; j++) {
                if(price == 4*i + 7*j) {
                    System.out.println("Yes");
                    isBreak = true;
                    break;
                }
            }
            if(isBreak) {
                break;
            }
        }
        if(!isBreak) {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 35788
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[3*n];
		for(int i=0;i<3*n;i++){
			a[i] = sc.nextLong();
		}
		Arrays.sort(a);
		
		long ans=0;
		for(int i=0;i<n;i++){
			ans += Math.max(a[3*n-2*i-2], a[3*n-2*i-3]);
		}
		System.out.println(ans);
		return;
	}
}

Measured memory_bytes: 97536
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)


int main() {
	int n;
	cin >> n;
	vector<int> p(n);
	rep(i, n) cin >> p[i];
	int ans = 0;
	int m = n + 1;
	rep(i, n) {
		if (m > p[i]) {
			ans++;
		}
		m = min(m, p[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    sort(a.begin(), a.end());
    int ai = a[n - 1];
    int aj = a[0];
    int maxDist = min(aj, ai - aj);
    rep(i, 0, n - 1)
    {
        int dist = min(a[i], ai - a[i]);
        if (chmax(maxDist, dist))
        {
            aj = a[i];
        }
    }
    cout << ai << " " << aj << endl;
}


Measured memory_bytes: 640
import bisect

MOD=10**9+7
N=int(input())

clist=[]
for i in range(N):
  c=int(input())
  clist.append(c)  
#print(clist)

c2list=clist[:1]
for i in range(1,N):
  if clist[i]!=c2list[-1]:
    c2list.append(clist[i])
#print(c2list)
N2=len(c2list)

cdic={}
for i in range(N2):
  c=c2list[i]
  if not c in cdic:
    cdic[c]=[i]
  else:
    cdic[c].append(i)
#print(cdic)

dp=[1]+[0]*(N2-1)
for i in range(1,N2):
  c=c2list[i]
  dp[i]=dp[i-1]

  if len(cdic[c])>0:
    ind=bisect.bisect_left(cdic[c],i)
    if ind>0:
      dp[i]+=dp[cdic[c][ind-1]]
      #print(cdic[c],i,ind-1)
    
#print(dp)
print(dp[-1]%MOD)

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

using namespace std;
typedef long long ll;

int main(){
    char b;
    cin >> b;
    if(b == 'A'){
        cout << 'T' << endl;
    }else if(b == 'C'){
        cout << 'G' << endl;
    }else if(b == 'G'){
        cout << 'C' << endl;
    }else{
        cout << 'A' << endl;
    }
    return 0;
}


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

ll x;

int main() {
    cin>>x;
    ll l=0, r=1e10,m;
    while (l<r){
        m=(l+r)/2;
        if (m*(m+1)/2>=x) r=m;
        else l=m+1;
    }
    cout<<r;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    bitset<(int)1e9>bit;
    int n ; cin>>n;
    for(int i = 0 ; i < n; ++i){
        int x ; cin>>x;
        if(bit[x]){
            cout<<"NO\n";
            return 0;
        }
        bit[x] = 1;
    }
    cout<<"YES\n";

}


Measured memory_bytes: 122368
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int N;
    string S;
    cin >> N >> S;
    int result=0;
    int current = 0;
    for (int i = 0; i < N; ++i)
    {
        if(S[i]=='I'){
            current+=1;
        }else{
            current-=1;
        }
        if(current>result){
            result = current;
        }
    }
    cout << result << endl;
    return 0;
}

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

static const int MAX = 200000;
using namespace std;

struct Card {char suit, value;};

void trace(Card a[], int n){
  for(int i = 0; i < n; i++){
    if(i) cout << " ";
    cout << a[i].suit << a[i].value;
  }
  cout << endl;
}

void sSort(Card a[], int n){
  for(int i=0; i < n; i++){
    int mini = i;
    for(int j=i+1; j<n; j++){
      if(a[mini].value > a[j].value){
        mini = j;
      }
    }
    if(mini != i){
      swap(a[mini], a[i]);
    }
  }
}

void bSort(Card b[], int n){
  for(int i=0; i<n; i++){
    for(int j = n-1; j >= i+1; j--){
      if(b[j-1].value > b[j].value){
        swap(b[j-1], b[j]);
      }
    }
  }
}

bool isStable(Card a[], Card b[],int n){
  for(int i=0; i<n; i++){
    if(a[i].suit != b[i].suit) return false;
  }
  return true;
}


int main(int argc, const char * argv[]) {
  int n;
  Card a[MAX], b[MAX];
  
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i].suit >> a[i].value;
  }
  
  for(int i=0; i<n; i++)
    b[i] = a[i];
  
  sSort(a, n);
  bSort(b, n);
  
  trace(b, n);
  cout << "Stable" << endl;
  trace(a, n);
  if(isStable(a,b,n)){
    cout << "Stable" << endl;
  } else{
    cout << "Not stable" << endl;
  }
  return 0;
}


Measured memory_bytes: 3124
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
string name;
 
bool fin;
 
bool check(string& line,int pos,int len)
{
  len++;
  string pre = name.substr(0,2); 
  for(int i=3;i<=name.size();i++)
    {
      if(pos+len > line.size())
    return false;
      pre += line[pos+len];
      pos += len;
    }
  return pre == name;
}
 
void rec(string& line,int pos,int index,int len)
{
  if(fin)
    return;
 
  if(len == -1)
    {
      for(int i=pos;i<line.size();i++)
    {
      if(line[i] == name[index])
        {
          rec(line,i+1,index+1,i-pos);
        }
    }
      return;
    }
 
  if(check(line,pos-1,len))
    {
      fin = true;
      return;
    }
 
}
 
int main()
{
  int N;
  cin >> N;
  cin >> name;
  int cnt =0 ;
  for(int i=0;i<N;i++)
    {
      string s;
      cin >> s;
      if(s == name)
    {
      cnt++;
      continue;
    }
 
      if(s.length() == 1)
    {
      if(s.find(name) != string::npos)
        {
          cnt++;
        }
    }
      else if(s.length() == 2)
    {
      map<char,int> dex;
      for(int i=0;i<s.length();i++)
        {
          dex[s[i]]++;
        }
      if(dex[name[0]] > 0 && dex[name[1]] > 0)
        cnt++;
    }
      else
    {
      
      fin = false;
      for(int i=0;i<s.length();i++)
        {
          if(s[i] == name[0])
        {
          rec(s,i+1,1,-1);
        }
        }
      if(fin)
          cnt++;
        
 
    }
    }
  cout << cnt << endl;
 
  return 0;
}

Measured memory_bytes: 1220
n=int(input())
p=int(n/1.08)
#print(p)
x=int(p*1.08)
#print("x",x)
flag=0
if x==n:
  flag=1
  print(p)
if flag==0 and x<n:
  if int((p+1)*1.08)==n:
    print(p+1)
    flag=1
if flag==0 and x>n:
  if int((p-1)*1.08)==n:
    print(p-1)
if flag==0:
  print(":(")


Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int calc_ds(int i) {
    int ds=0;
    while(10*i/10) {
        ds += i%10;
        i /= 10;
    }

    return ds;
}

int main() {
    int N, A, B;
    cin >> N >> A >> B;

    int i, ds, sum=0;
    for(i=1; i<=N; i++) {
        ds = calc_ds(i);
        if((ds>=A) && (ds<=B)) {
            sum += i;
        }
    }

    cout << sum << endl;

    return 0;

}

Measured memory_bytes: 256
N = gets.to_i
M = 1E9.to_i + 7
PT = %w(A C G T).repeated_permutation(4).select do |a|
  4.times.any?{|i| s = a.join; s[i - 1], s[i] = s[i], s[i - 1] unless i.zero?; s.include?("AGC")}
end.map(&:join)

def go(n, s)
  return 1 if n == N
  @m ||= Array.new(N + 1){{}}
  @m[n][s] ||= %w(A C G T).inject(0) do |r, c|
    t = s + c
    PT.include?(t) ? r : (r + go(n + 1, t[1, 3])) % M
  end
end

puts go(0, 'TTT')

Measured memory_bytes: 2812
import sys
import os
import math
import string
import collections

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    print(abs(max(A)-min(A)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3952
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

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

	int n, h, w;
	cin >> n >> h >> w;
	cout << (n - h + 1) * (n - w + 1) << endl;
}


Measured memory_bytes: 3192
#include <stdio.h>
#define n 2000
int abs(int a)
{
	return (a > 0) ? (a) : (-a);
}


int main(void)
{
	int N, X, Y, idmax, res;
	int a[n];
	scanf("%d%d%d", &N, &X, &Y);
	for (int i = 0; i < N; i++){
		scanf("%d", &a[i]);
	}
	int x = abs(Y - a[N - 1]);
	int y = x;
	if (N > 1) y = abs(a[N - 2] - a[N - 1]);

	if (x<y) printf("%d\n", y);
	else printf("%d\n", x);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a)      (a).begin(),(a).end()
#define debug_array(a,n) for (ll bccc=(0); bccc<(n); bccc++) cout<<a[bccc]<<" "<<"\n"
#define debug_vector(a) for(ll bccc=(0); bccc<(a.size());bccc++) cout<<a[bccc]<<" "<<"\n"
#define F           first
#define S           second
#define debug_set(s) for(auto p:s) cout<<p<<" "
#define debug_map(m) for(auto p:m) cout<<p.F<<" "<<p.S<<"\n"
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
/* ll t = 0;
ordered_multiset me;
...
me.insert({x, t++});
me.erase(me.lower_bound({x, 0}));
cout << me.order_of_key({x, 0}) << "\n";

///////////   t is insertion time
*/
// #pragma GCC optimize("Ofast")  // works very well
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long double lld;
lld pi=3.14159265358;
ll powr(ll a,ll b)
{
    ll c=1;
    ll kjk;
    for(kjk=0;kjk<b;kjk++)
        c*=a;
    return c;
}
ll hell=1000000007;
//ll hell=998244353   ;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
// to generate random number , use rng() ... eg cout<<rng();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    ll n,i,j,k,p,q,r;
    cin>>n;
    ll ans=0;
    for(i=0;i<=1000LL;i++)
    {
        for(j=0;j<2;j++)
        {
            for(k=0;k<2;k++)
            {
                for(p=0;p<2;p++)
                {
                    for(q=0;q<2;q++)
                    {
                        {
                            for(r=0;r<=1000LL;r++)
                            {
                                if((100*i + 101*j + 102*k +103*p + 104*q + 105 * r)==n)
                                    ans=1;
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<ans;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define Maxn 1000006
using namespace std;
char a[Maxn],b[Maxn],c[Maxn];
int n,ans;

int tot1,tot2,pc[Maxn],pcc[Maxn];
int main()
{
//	freopen("1.txt","r",stdin);
	scanf("%s",a+1);
	n=strlen(a+1);
	for(int i=1;i<=strlen(a+1);i++)
	{
		if(a[i]!='x') 
		{
			b[++tot1]=a[i];
		}
		else
		{
			pc[tot1]++;
		}
	}
	if(tot1==0)
	{
		cout<<0;
		return 0;
	}
	for(int i=1;i<=tot1;i++)
	{
		if(b[i]!=b[tot1-i+1])
		{
			printf("-1\n");
			return 0;
		}
	}
	for(int i=0;i<=tot1;i++)
	{
		pcc[i]=pc[tot1-i];
	}
	for(int i=0;i<=tot1;i++)
	{
		ans+=abs(pc[i]-pcc[i]);
	}
	cout<<(ans/2);
//	for(int i=1;i<=strlen(a+1);i++)
//	{
//		c[i]=c[strlen(a+1)-i+1];
//	}
//	pc=1;pcc=1;
//	while(pc<=n&&pcc<=n)
//	{
//		while(a[pc]!=b[pcc])
//		while(a[pc]!=b[pcc])
//		{
//			
//		}
//	}
} 

Measured memory_bytes: 8704
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int unsigned long long
#define endl "\n"
using namespace std;

int32_t main() {
  ios;
  int t = 1;
  // cin>>t;
  while(t--) {
    int n;
    cin>>n;
    int a[n];
    int s = 0;
    for(int i = 0;i < n;i++) cin>>a[i],s^=a[i];
    for(int i = 0;i < n;i++) {
      cout<<(s^a[i])<<" ";
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 5188
#include <cmath>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>


using namespace std;

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> MAP(N);
  vector<vector<double>> DIST;

  for (int i = 0; i < N; ++i) {
    int x, y;
    cin >> x >> y;
    MAP[i] = {x, y};
  }

  int flac = 1;
  for(int i = 1; i<N+1; ++i) {
    flac *= i;
  }

  for (int i = 0; i < N; i++) {
    vector<double> tmp(N);
    DIST.push_back(tmp);
    for (int j = 0; j < N; j++) {
      DIST[i][j] = sqrt(pow(MAP[i].first - MAP[j].first, 2) +
                        pow(MAP[i].second - MAP[j].second, 2));
    }
  }

  long double acc = 0;
  vector<int> v(N);
  for (size_t i = 0; i < N; ++i )
  {
    v[i] = i;
  }

  do {
    for(int i=1; i<N; ++i) {
      acc += DIST[v[i-1]][v[i]];
    }
  } while (std::next_permutation(v.begin(), v.end()));

  printf("%8.10lf\n", (double)acc / (double)flac );

  return 0;
}


Measured memory_bytes: 256
/*input
999999 999999
*/
#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int fact(int n){
	int ans = 1;
	for(int i=1;i<=n;i++){
		ans *= i;	ans %= MOD;
	}
	return ans;
}

int power(int a,int b,int c = MOD){
	if(b==0)	return 1;
	int x = power(a,b/2,c);
	x=(x*x)%c;
	if(b%2==0)
		return x;
	return (a*x)%c;
}

signed main(){
	int x,y;
	cin >> x >> y;
	int a = 2*y-x,b = 2*x-y;

	if(a<0 || b<0 || a%3 !=0 || b%3 !=0){
		cout << "0\n";	return 0;
	}
	a/=3LL; b/=3LL;

	int ans = fact(a+b)*power(fact(a),MOD-2);	ans %= MOD;
		ans *= power(fact(b),MOD-2);	ans %= MOD;
	cout << ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<ll,pair<ll,ll> > pp;
pp mm[100001];
ll d[100001];

int main(){
    ll n,h;
    ll ans=0;
    cin>>n>>h;
    ll di,hi,ch=h;
    for(int i=0;i<n-1;++i){
        cin>>di>>hi;
        mm[i].first=ch+hi<=h||ch<0 ? hi:h-ch;mm[i].second.first=i;mm[i].second.second=ch;
        d[i]=di;
        ch -= di;
    }
    int l=0;
    for(int i=0;i<n;++i){
        ch=mm[i].second.second;
        if(ch<=0){
            pp t=*max_element(mm+l,mm+i);
            hi=t.first;
            int ch2=t.second.second;
            i=t.second.first;l=i;
            int dv;
            if(-ch/hi+1>(h-ch2)/hi){
                dv=(h-ch2)/hi;
                ans+=dv;
                ch=ch2+hi*dv;
            } 
            else{
                dv=-ch/hi+1;
                ans+=dv;
                ch=min(h,ch2+hi*dv); 
            }             
        }
        hi=mm[i].first;
        mm[i].first=ch+hi>h ? h-ch:hi;
        mm[i].second.second=ch; 
        mm[i+1].second.second= ch-d[i];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6212