akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// xy平面上の点(ベクトル)を表現するには、complex型を利用するとよい
typedef complex<double> P;

// 辺の表現 (座標を2つ pair でもつ)
typedef pair<P, P> L;

// 円の表現 (座標 P と 半径 d で表現する)
typedef pair<P, double> C;

// 成分を取り出すのを簡単にする
#define X real()
#define Y imag()

// 誤差(epsilon)の定義
#define EPS (1e-10)

// 2つの要素が等しいかどうか
#define EQ(a,b) (abs((a) - (b)) < EPS)

// 2つのベクトルが等しいかどうか
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )

// m は n より大きい(以上)かどうか
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)

// m は n より小さい(以下)かどうか
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

// 2つのベクトルの内積を求める
double dot(P a, P b) {
    return (a.X * b.X + a.Y * b.Y);
}

// 2つのベクトルの外積を求める
double cross(P a, P b) {
    return (a.X * b.Y - a.Y * b.X);
}

// 点 a と 点 b を通り、半径が r の円の中心を返す
vector<P> circlesPointsRadius(P a, P b, double r) {
    vector<P> cs;
    P abH = (b-a) * 0.5;
    double d = abs(abH);

    if(d == 0 || d > r) return cs; // 必要なら !LE(d,r) として円1つになる側へ丸める
    double dN = sqrt(r*r - d*d);   // 必要なら max(r*r - d*d, 0) とする
    P n = abH * P(0,1) * (dN / d);
    cs.push_back(a + abH + n);
    if(dN > 0) cs.push_back(a + abH - n);
    return cs;
}

int main() {
    int N;

    while(cin >> N, N) {
        vector<P> ps;
        for(int i=0; i<N; i++) {
            double x, y; cin >> x >> y;
            ps.push_back(P(x, y));
        }

        if(N == 1) cout << 1 << endl;
        else if(N == 2) {
            cout << 1 + (abs(ps[0] - ps[1]) < 2 + EPS) << endl;
        }
        else {
            int ans = 1;
            for(int i=0; i<N; i++) {
                for(int j=i+1; j<N; j++) {
                    // printf("i = %d, j = %d, abs = %f\n", i, j, abs(ps[i] - ps[j]));
                    if(abs(ps[i] - ps[j]) > 2 + EPS) continue;
                    // printf("valid\n");

                    vector<P> centers = circlesPointsRadius(ps[i], ps[j], 1);
                    for(auto c : centers) {
                        int sum = 2;
                        for(int k=0; k<N; k++) {
                            if(i == k || j == k) continue;
                            sum += (abs(c - ps[k]) < 1 + EPS);
                        }
                        ans = max(ans, sum);
                    }
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3212
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
#define absl(v) labs((v))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(cv *a, cv *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(cv *a, cv *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(cv *left, cv *right) {return strcmp((char *)left,(char *)right);}
int downchar(cv *left, cv *right) {return strcmp((char *)right,(char *)left);}
void tmpInit(int *c,ll m) {ll i;rep(i,m) c[i]=i;}
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1){
            res *= a; if(mod>=1) res %= mod;
        }
        a *= a; if(mod>=1) a %= mod;
        n >>= 1;
    }
    return res;
}
void initialize(){
    
}
int main(void){
  initialize();
  ll n,m,i,j,k,result[2]={0};
  int a[LIMIT2]={0};
  char s[LIMIT1];
  
  scanf("%lld",&n);
  rep(i,n) scanf("%d",&a[i]);
  qsort(a,n,sizeof(int),upint);
  result[0] = (ll)a[n-1];
  result[1]=-1;
  rep(i,n-1){
    if(result[1]==-1) result[1]=(ll)a[i];
    else if(labs(result[0]/2.0-(ll)result[1])>labs(result[0]/2.0-(ll)a[i])){
      result[1] = (ll)a[i];
    }
  }
  printf("%lld %lld",result[0],result[1]);
  return 0;
}



Measured memory_bytes: 2556
/**
 * @brief AtCoder Beginner Contest 054<br>
 * C - One-stroke Path
 *
 * dfsパターン
 * @see https://atcoder.jp/contests/abc054/tasks/abc054_c
 */
#include <iostream>
using namespace std;

constexpr int MAX_N = 8;
int N, M;
bool graph[MAX_N + 1][MAX_N + 1];
bool visited[MAX_N + 1];

int dfs(int v) {
  for (int i{1}; i <= N; ++i) {
    if (!visited[i])
      goto CONTINUED;
  }
  return 1;
  CONTINUED:
  int count{};
  for (int i{1}; i <= N; ++i) {
    if (!graph[v][i] || visited[i]) continue;
    visited[i] = true;
    count += dfs(i);
    visited[i] = false;
  }
  return count;
}

int main() {
  scanf("%d%d", &N, &M);
  int a, b;
  for (int i{}; i < M; ++i) {
    scanf("%d%d", &a, &b);
    graph[a][b] = true;
    graph[b][a] = true;
  }

  visited[1] = true;
  printf("%d\n", dfs(1));
  return 0;
}


Measured memory_bytes: 256
let () =
  let (n, k) = Scanf.scanf "%d %d\n" (fun n k -> (n, k)) in
  let a = Array.init n (fun _ -> Scanf.scanf "%d\n" (fun i -> i)) in
  let check p =
    let rec doit i j s =
      if i = n then n
      else if j >= k then i
      else
        let x = s + a.(i) in
        if x > p then doit i (j + 1) 0
        else doit (i + 1) j x
    in
    doit 0 0 0
  in
  let rec bin_search l r =
    if r < l then l
    else
      let m = (l + r) / 2 in
      if check m >= n then bin_search l (m - 1)
      else bin_search (m + 1) r
  in
  Printf.printf "%d\n" (bin_search 0 (100000 * 10000))

Measured memory_bytes: 5332
from collections import Counter
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
def find2(x):
  if x==Tree2[x]:
      return x
  else:
      Tree2[x]=find2(Tree2[x])
      return Tree2[x]
def unite2(x,y):
  s1=find2(x)
  s2=find2(y)
  if s1!=s2:
    Tree2[s2]=s1
N,K,L=map(int,input().split())
Tree=[i for i in range(N)]
Tree2=[i for i in range(N)]
ans=[]
for i in range(K):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite(a,b)
for i in range(L):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite2(a,b)
l=[(find(i),find2(i)) for i in range(N)]
lc=Counter(l)
for i in range(N):
  ans.append(lc[l[i]])
print(" ".join(map(str,ans)))

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

int main(){
  int a,i,array[101];
  string s;
  cin>>a>>s;
  array[0]=0;
  for(i=1;i<a+1;i++){
    if(s.at(i-1)=='D'){
      array[i]=array[i-1]-1;
    }else{
      array[i]=array[i-1]+1;
    }
  }
  sort(array,array+a+1);
  cout<<array[a]<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define tot head[0]
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,c[N],head[N],nex[N<<1],to[N<<1];
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
void dfs(int u,int color)
{
    if(c[u])
    {
        if(c[u]!=color)
        {
            printf("%lld\n",(ll)n*(n-1)/2-m);
            exit(0);
        }
        return;
    }
    c[u]=color;
    for(int i=head[u];i;i=nex[i])
        dfs(to[i],c[u]^1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);
    }
    dfs(1,2);
    ll a=0,b=0;
    for(int i=1;i<=n;i++)
        if(c[i]==2) a++;
    else b++;
    ll ans=a*b*2;
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j;j=nex[j])
            if(c[to[j]]!=c[i])
                ans--;
    }
    printf("%lld\n",ans/2);
}


Measured memory_bytes: 6428
#include <bits/stdc++.h>                        
#define pb push_back                            
#define mp make_pair                            
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)((x).size())
#define endl "\n"
#define jonathan ios_base::sync_with_stdio(0)
#define livingston cin.tie(0)
using namespace std;                            
                                                
void yes() {cout << "YES" << endl;}                                               
void no() {cout << "NO" << endl;}                                                        
                                                
int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};         
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1}; 

const long long INF = 8e18 + 8;
const double EPS = 1e-9;
const long long MOD = 998244353;

void solve() {
    int n; cin >> n;
    vector<int> a(n), l(n), r(n), pos(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() and st.top() > a[i]) st.pop();
        if (st.empty()) l[i] = 0;
        else l[i] = pos[st.top()] + 1;
        st.push(a[i]);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() and st.top() > a[i]) st.pop();
        if (st.empty()) r[i] = n - 1;
        else r[i] = pos[st.top()] - 1;
        st.push(a[i]);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += 1ll * a[i] * (i - l[i] + 1) * (r[i] - i + 1);
    }
    cout << ans << endl;
}

int main() {
    jonathan; 
    livingston;
    bool tests = 0;
    int t = 1;
    if (tests) cin >> t;
    for (int i = 1; i <= t; i++) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 7012
s = input()

freq = {}

for c in s:
    if c in freq:
        freq[c] += 1
    else:
        freq[c] = 1


if (len(freq)) != 2:
    print('No')
    exit(0)

cond = True
for c in freq:
    if freq[c] != 2:
        cond = False
        break

if cond:
    print('Yes')
else:
    print('No')



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

using namespace std;
using namespace __gnu_pbds; 
#define     mod            (int)1e9+7
#define     MOD             998244353
#define     ll              long long
#define     mp              make_pair
#define     F               first
#define     S               second
#define     t()             int test;cin>>test;while(test--)
#define     ii              pair<int,int>
#define     que_max         priority_queue <int>
#define     IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define     endl            "\n"
typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
        //use cerr if u want to display at the bottom
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif






 
int main()
 
{  
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    IOS;
    
  ll int n, m, k;
   cin>>n>>m>>k;

   vector<ll int>  a(n+1), b(m+1);

   std::vector<ll int> dp1(n+1, 0), dp2(m+1,0);

   for(int i=1; i<=n ;i++)cin>>a[i];
    for(int i=1; i<=m ;i++)cin>>b[i];

        for(int i=1; i<=n; i++)
        {
            dp1[i] = dp1[i-1]+a[i];
        }

        for(int i=1; i<=m; i++)
        {
            dp2[i] = dp2[i-1]+b[i];
                }

        ll ans =0, j=m;

        for(int i=0; i<=n; i++)
        {
            if(dp1[i]>k)break;

            while(j>=0 && dp2[j] > k-dp1[i])
                j--;

 

            ans = max(ans, i+j);
        }


   cout<<ans<<endl;
   
}

Measured memory_bytes: 9544
def main():
    N = int(input())
    values = list(map(int, input().split(' ')))
    values.sort(reverse=True)
    div = 1
    answer = 0
    for v in values[:-1]:
        div *= 2
        answer += v / div
    answer += values[-1] / div
    print(answer)


if __name__ == '__main__':
    main()

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

int main(){
	int a[3][3], b, s[3][3] = {};
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	int n;
	cin >> n;
	for(int k = 0; k < n; k++) {
		cin >> b;
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++) {
				if (b == a[i][j])
					s[i][j] = 1;
			}
	}
	int r = 0;
	for(int i = 0; i < 3; i++)
		if(s[i][0] && s[i][1] && s[i][2] || s[0][i] && s[1][i] && s[2][i])
			r = 1;
	if(s[0][0] && s[1][1] && s[2][2] || s[0][2] && s[1][1] && s[2][0])
		r = 1;
	cout << (r ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
import Control.Monad
import qualified Data.IntMap as IM
import Data.Maybe

type Map = IM.IntMap Integer

get :: Int -> Map -> Integer
get key m = fromMaybe 0 $ IM.lookup key m

solve :: [[Int]] -> Map -> Map
solve [] m = m
solve ([a, b]:rs) m = solve rs $ IM.insertWithKey f a 1 $ IM.insertWithKey f b 1 m
  where f _ new old = old + new

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  rows <- replicateM m $ map read . words <$> getLine
  let im = solve rows IM.empty
  mapM_ print $ (`get` im) <$> [1..n]

Measured memory_bytes: 892
// *** creator : cfmasterr *** //
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  const long long inf = (long long) 1e18;
  long long ans = inf;
  long long n;
  cin >> n;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      long long x = n / i;
      ans = min(ans, i + x - 2);
    }
  }
  cout << ans << '\n';
  return 0;
}

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

int hash_search(int len,char *ch)
{
    int nk,kn=0;
    for(int i=0;i<len;i++)
    {
        switch(ch[i])
        {
            case 'A':
            nk=0;
            break;
            case 'C':
            nk=1;
            break;
            case 'G':
            nk=2;
            break;
            case 'T':
            nk=3;
            break;
        }
        kn = kn *4 + nk;
    }
    return kn;
}

void insert(char **word,char *ch,int len)
{
    int nk,kn=hash_search(len,ch);
    //printf("insert ch chk = %s\n",ch);
    //printf("insert kn chk = %d\n",kn);
    word[len-1][kn] = 1;
}

void find(char **word,char *ch,int len)
{
    int nk,kn=hash_search(len,ch);
    //printf("find ch chk = %s\n",ch);
    //printf("find kn chk = %d\n",kn);
    if(word[len-1][kn]==1) printf("yes\n");
    else printf("no\n");
}

int main()
{
    int n,p=1;
    scanf("%d",&n);
    char *word[12],CH[13],order[7];
    for(int i=0;i<12;i++)
    {
        p*=4;
        word[i]=malloc(sizeof(char)*p);
    }
    for(int i = 0;i<n;i++)
    {
        scanf("%s %s",order,CH);
        if(strcmp(order,"insert")==0)
        {
            insert(word,CH,strlen(CH));
        }
        else
        {
            find(word,CH,strlen(CH));
        }
    }
}


Measured memory_bytes: 3120
n,m = map(int,input().split())
from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
if n <= 1 and m <= 1:
  print(0)
elif n <= 1:
  print(cmb(m,2))
elif m<= 2:
  print((cmb(n,2)))
else:
  print(cmb(n,2)+cmb(m,2))

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

const int INF = (1<<29);

int main(){
  int t;
  cin >> t;
  while(t--){
    int n,dp[2][3];
    bool f[2][20000];
    string str;
    cin >> n >> str;
    for(int i=0;i<str.size();i++) f[i/(2*n)][i%(2*n)] = (str[i] == 'Y') ? true : false;
    fill(dp[0],dp[2],INF);

    dp[0][0] = 0;
    for(int i=0;i<2*n;i+=2){

      for(int j=0;j<2;j++) if(i > 0 && f[j][i-1]) f[j][i] = true;

      if(!f[0][i] && !f[1][i]){
        for(int j=0;j<3;j++){
          for(int k=0;k<3;k++){
            if(j == k) dp[1][k] = min(dp[1][k],dp[0][j]);
            else if(abs(j-k) == 1) dp[1][k] = min(dp[1][k],dp[0][j]+1);
            else dp[1][k] = min(dp[1][k],dp[0][j]+2);
          }
        }
      } else {
        if(f[0][i] && f[1][i]){
          for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
              if(j == k && (j == 0 || j == 2)) dp[1][k] = min(dp[1][k],dp[0][j]+3);
              else dp[1][k] = min(dp[1][k],dp[0][j]+2);
            }
          }
        } else {
          /*
          for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
              if(abs(j-k) < 2) dp[1][k] = min(dp[1][k],dp[0][j]+1);
              else dp[1][k] = min(dp[1][k],dp[0][j]+2);
            }
            }*/
          for(int j=0;j<3;j++) dp[1][j] = min(dp[1][j],dp[0][1]+1);

          if(f[0][i]){
            for(int j=0;j<3;j++){
              dp[1][j] = (j == 2) ? min(dp[1][j],dp[0][0]+2) : min(dp[1][j],dp[0][0]+1);
              dp[1][j] = (j == 2) ? min(dp[1][j],dp[0][2]+3) : min(dp[1][j],dp[0][2]+2);
            }
          } else {
            for(int j=0;j<3;j++){
              dp[1][j] = (j == 0) ? min(dp[1][j],dp[0][2]+2) : min(dp[1][j],dp[0][2]+1);
              dp[1][j] = (j == 0) ? min(dp[1][j],dp[0][0]+3) : min(dp[1][j],dp[0][0]+2);
            }
          }

        }
      }
      for(int j=0;j<3;j++){
        dp[0][j] = dp[1][j] + 1;
        dp[1][j] = INF;
      }
    }

    int ans = INF, m=2*n-1;
    if(!f[0][m] && !f[1][m]) for(int i=0;i<3;i++) ans = min(ans,dp[0][i]+i);
    else if(f[1][m]){
      ans = min(ans,dp[0][0]+3);
      for(int i=1;i<3;i++) ans = min(ans,dp[0][i]+2);
    } else if(f[0][m]){
      for(int i=0;i<2;i++) ans = min(ans,dp[0][i]+1);
      ans = min(ans,dp[0][2]+2);
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 0
n = int(input())
P = []
for i in range(n):
    s, p = input().split()
    p = int(p)
    P.append((s, p, i+1))

P = sorted(P, key=lambda x: x[1], reverse=True)
P = sorted(P, key=lambda x: x[0])

for i in range(n):
    print(P[i][2])


Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))

int main(){
	int h,w;
	scanf("%d%d",&h,&w);
	printf("%d",w+w-h);
}

Measured memory_bytes: 128
import fractions as math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
T = [int(input()) for _ in range(N)]

print(lcm_list(T))

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

int main() {
	int N;
	cin >> N;
	map<int,int>mp;
	for (int i = 0;i<N;++i) {
		int n;
		cin >> n;
		mp[n]++;
	}
	int ans = 0;
	for (auto p:mp) {
		if(1 == p.second%2) {
			ans++;
		}
	}
	cout << ans <<  endl;
	return 0;
}

Measured memory_bytes: 8208
#include<bits/stdc++.h>
using namespace std;
char a[105],b[105];
int ans;
int main()
{
	int l;
	scanf("%d",&l);
	scanf("%s",a);
	scanf("%s",b);
	for(int k=1;k<=l;k++)
	{
		bool p=true;
		for(int i=0;i<k;i++)
		{
			if(a[l-k+i]!=b[i])p=false;
		}
		if(p)ans=k;
	}
	printf("%d",l+l-ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <random>
#include <utility>
#include <cmath>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする

struct edge{int to,cost;};
vector<int> G[100005];

 
ll n,m,num=1,ans=0;
int i,j;
ll a,b;

int main(){
	cin>>n>>a>>b;
	if(a>b){
		cout<<0;
	}else if(n==1 && a!=b){
		cout<<0;
	}else if(n==1){
		cout<<1;
	}else if(n==2){
		cout<<1;
	}else{
		cout<<(n-2)*(b-a)+1;
	}
	cout<<endl;


	return 0;
}

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}

typedef long long int ll;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =1e9+7;
const ll maxn =5*100001;
ll power(ll x, ll n) {
    ll res = 1;
    for (; n > 0; n >>= 1) {
    if (n & 1) res = (res * x) % mod;
    x = (x * x) % mod;
    }
    return res;
}
pll brute(ll n,ll extra)
{
  ll x=n,y=n;
  ll power_2=extra,power_5=0;
  while(1)
  {
    ll temp=(n/2);
    if(temp==0)
      break;
    power_2+=temp;
    n/=2;
  }
  n=x;
  while(1)
  {
    ll temp=(n/5);
    if(temp==0)
      break;
    power_5+=temp;
    n/=5;
  }
  //trace(power_2,power_5);
  return (mp(power_2,power_5));
}
int main()
{
   
  IOS
  ll n;
  cin>>n;
  if(n<2)
  {
    cout<<0<<endl;
    return 0;
  }
  if(n%2==0)
  {
    cout<<min(brute(n/2,n/2).ff,brute(n/2,n/2).ss)<<endl;
  }
  else
  {
    cout<<min(brute(n+1,0).ff-brute((n+1)/2,(n+1)/2).ff,brute(n+1,0).ss-brute((n+1)/2,(n+1)/2).ss);
  }
  
  
  


  

}
  


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

ll INF = 1LL << 60;
using G = vector<map<int, int>>;

int 
main() {

  int N; cin >> N;
  vector<int> ans;
  int count = 0;
  
  if(N == 0){
    cout << 0 << endl;
    return 0;
  }

  while( N != 0){
    if(N % 2 != 0) ans.push_back(1), N--;
    else ans.push_back(0);
    N /= -2;
    ++count;
  }

  for(int i = count - 1; i >= 0; --i){
    cout << ans[i];
  }
  cout << endl;

}

Measured memory_bytes: 3552
/*
ABHIJEET BISWAS
CSE 4th SEM 
MNNIT ALLAHBAD
https://atcoder.jp/contests/dp/tasks/dp_f
VER : 
*/

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1e18
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pli pair<long long,int>
#define pll pair<long long,long long>
#define MAX 1000009
#define pb push_back
#define mp map<int,int>
#define f first
#define s second
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ld pi=2.0*acos(0.0);
int main() {
	fastIO
	string s,t;
	cin>>s>>t;
	int dp[s.size()+1][t.size()+1];
	for(int i=0;i<=s.size();i++)
	for(int j=0;j<=t.size();j++)
	dp[i][j]=0;
	string str="";
	for(int i=1;i<=s.size();i++)
	for(int j=1;j<=t.size();j++)
	{
		if(s[i-1]==t[j-1])
		{
			dp[i][j]=dp[i-1][j-1]+1;
		}
		else
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
		
	}
	//cout<<dp[s.size()][t.size()]<<endl;
	//backtrack
	int i=s.size(),j=t.size();
	while(i>0 and j>0)
	{
		if(s[i-1]==t[j-1])
		{
			str+=s[i-1];
			i=i-1;
			j=j-1;
		}
		else
		{
			if(dp[i-1][j]>dp[i][j-1])
			{
				i=i-1;
				j=j;
			}
			else
			{
				j=j-1;
			}
		}
	}
	reverse(str.begin(),str.end());
	cout<<str<<endl;
	
	return 0;
}

Measured memory_bytes: 35456
#include <iostream>

void solve() {
    int n;
    std::cin >> n;

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int a;
        std::cin >> a;
        if (i % 2 == 1 && a % 2 == 1) ++ans;
    }

    std::cout << ans << "\n";
}

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

    solve();

    return 0;
}


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

int main(){
    int A,B,C,K;
    int n=0;
    cin >> A >> B >> C >> K;
    if(A<=K){
        n+=A;
             if(K>A+B) n-= K-A-B;
    }
    if(A>K) n+=K;

    cout << n << endl;       
    
}

Measured memory_bytes: 3620
a, b, k = map(int, input().split())

div_a = set()
div_b = set()

for i in range(1, 101):
    if a % i == 0:
        div_a.add(i)
    if b % i == 0:
        div_b.add(i)

ans = sorted(list(div_a & div_b))
print(ans[-k])

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

vector<pair<int,int> > c;
set<int> ma[100010];
int p[100010], belong[100010];

int find(int x) {
	if (belong[x] == x) return x;
	else {
		belong[x] = find(belong[x]);
		return belong[x];
	}
}

int main() {
	ios::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
		c.push_back({i,i});
		belong[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		int x,y;
		cin >> x >> y;
		if (x > y) swap(x,y);
		c.push_back({x,y});
	}
	sort(c.begin(),c.end());
	
	for (int i = 0; i < c.size(); i++) {
		int x = find(c[i].first), y = find(c[i].second);
		belong[y] = x;
	}
	for (int i = 1; i <= n; i++) {
		int x = i;
		while (belong[x] != x) x = belong[x];
		ma[x].insert(i);
	}
	
	int ans = 0;
	for (int i = 1; i <= n; i++) if (ma[i].size() > 0) {
		for (auto it = ma[i].begin(); it != ma[i].end(); it++)
			if (ma[i].find(p[*it]) != ma[i].end()) ans++;
	}
	cout << ans << "\n";
}

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

struct node {
    int value;
    node *left = nullptr, *right = nullptr, *parent = nullptr;
    node(int x) { value = x; }
};

struct binary_search_tree {
    node* root = nullptr;
    int size = 0;
    binary_search_tree() {}
    void insert(int v) {
        size++;
        node* c = nullptr;  //子
        node* p = root;     //親
        while (p != nullptr) {
            c = p;
            if (v < (*p).value) {
                p = (*p).left;
            } else {
                p = (*p).right;
            }
        }
        if (c == nullptr) {
            root = new node(v);
        } else if (v < (*c).value) {
            (*c).left = new node(v);
            (*((*c).left)).parent = c;
        } else {
            (*c).right = new node(v);
            (*((*c).right)).parent = c;
        }
    }
    node* find(int v) {
        node* x = root;
        while (x != nullptr) {
            if (v < (*x).value) {
                x = (*x).left;
            } else if (v > (*x).value) {
                x = (*x).right;
            } else {
                return x;
            }
        }
        return nullptr;
    }
    void print_inorder(node* now) {
        if ((*now).left != nullptr) { print_inorder((*now).left); }
        std::cout << " " << (*now).value;
        if ((*now).right != nullptr) { print_inorder((*now).right); }
    }
    void print_preorder(node* now) {
        std::cout << " " << (*now).value;
        if ((*now).left != nullptr) { print_preorder((*now).left); }
        if ((*now).right != nullptr) { print_preorder((*now).right); }
    }
    void print() {
        print_inorder(root);
        std::cout << std::endl;
        print_preorder(root);
        std::cout << std::endl;
    }
    void del(node* now) {
        if ((*now).left != nullptr) { del((*now).left); }
        if ((*now).right != nullptr) { del((*now).right); }
        delete now;
    }
    ~binary_search_tree() { del(root); }
};

int main() {
    int n;
    binary_search_tree bst;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        if (s == "insert") {
            int x;
            std::cin >> x;
            bst.insert(x);
        } else if (s == "find") {
            int x;
            std::cin >> x;
            if (bst.find(x) == nullptr) {
                std::cout << "no" << std::endl;
            } else {
                std::cout << "yes" << std::endl;
            }
        } else {
            bst.print();
        }
    }
}


Measured memory_bytes: 21752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;string s;
cin>>n>>s;
int max=0;
int sum=0;
for(int i=0;i<n;i++){
    if(s[i]=='I')sum++;
    else sum--;
    if(sum>=max)max=sum;
}
cout<<max<<endl;
}

Measured memory_bytes: 256
from math import degrees, atan
a, b, x = map(int, input().split())

if a*a*b/2 > x:
    t = (b/2) / (x/a/b)
else:
    johen = 2*x/a/a - b
    t = (b-johen) / a
print(degrees(atan(t)))

Measured memory_bytes: 3060
package main

import (
	"bufio"
	"strconv"
	"os"
	"fmt"
)

const (
	A = 0
	C = 1
	G = 2
	T = 3
	MAX_LENGTH = 12
)

type dict struct {
	content []bool
}

func newDict() *dict {
	content := make([]bool, 2 << (2 * MAX_LENGTH))
	return &dict{content: content}
}

func (d *dict) insert(str string) {
	d.content[hash(str)] = true
}

func (d *dict) find(str string) bool {
	return d.content[hash(str)]
}

func hash(str string) int32 {
	var x int32 = 1
	for i := 0; i < len(str); i++ {
		x = x << 2
		c := rune(str[i])
		switch c {
		case 'A':
			x += A
		case 'C':
			x += C
		case 'G':
			x += G
		case 'T':
			x += T
		}
	}
	return x
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}

	d := newDict()

	for i := 0; i < n; i++ {
		command := nextText(sc)
		switch command {
		case "insert":
			str := nextText(sc)
			d.insert(str)
		case "find":
			str := nextText(sc)
			if d.find(str) {
				fmt.Println("yes")
			} else {
				fmt.Println("no")
			}
		default:
			panic(fmt.Errorf("illegal command: %s\n", command))
		}
	}
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func nextInt(sc *bufio.Scanner) (int, error) {
	return strconv.Atoi(nextText(sc))
}


Measured memory_bytes: 20624
#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 a, b; cin >> a >> b;

  int sum = 0;
  rep(i, b-a) sum += i;

  cout << sum - a << endl;

  return 0;
}


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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s; cin >> s;
  int ans = 0;
  for(auto v: s) if(v=='1') ans++;
  cout << ans << endl;

  return 0;
}


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

public class MainClass
{
	public const long Giri = 1000000007;

	public static void Main(string[] args)
	{
		var p = Input();
		var d = p[0].ToInt();
		var n = p[1].ToInt();
		if(n<100)
			Console.WriteLine(Math.Pow(100, d)*n);
		else
			Console.WriteLine(Math.Pow(100, d)*101);
		
		
	}
	

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}



Measured memory_bytes: 13140
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
int main(){
int i,j,a,k;
string s,c;
cin>>s;
k=s.size();
for(i=0;i<k;i++){
	a=s[i];
	if(a>=65&&a<=67)a+=23;
	else if(a>=68&&a<=91)a-=3;
	c[i]=a;
	cout<<c[i];
}
cout<<endl;
return 0;
}

Measured memory_bytes: 3204
#include<stdio.h>


int main(void){
   int N,M,i;
   double sum=0;
   int count=0;
   int data[100];
   scanf("%d %d",&N,&M);

   for(i=0;i<N;i++){
      scanf("%d",&data[i]);
      sum+=data[i];
   }

   sum=sum/(4*M);
   for(i=0;i<N;i++){
      if(sum<=data[i]){
         count+=1;
      }
   }
      if(M<=count){
         printf("Yes\n");
      }else{
         printf("No\n");
      }
   return 0;
}


Measured memory_bytes: 1616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, n) for(long i = x; i < n; i++)
#define erep(i, x, n) for(long i = x; i <= n; i++)
#define all(a) a.begin(), a.end()
#define eall(a) a.begin()+1, a.end()
#define show(ans)  cout << ans << endl;
const long MOD = 1000000007;

int main(){long N, K;
cin >> N >> K;
vector<pair<long, long>> s;
s.push_back(make_pair(0, 0));
erep(i, 1, N) {
  long a1, b1;
  cin >> a1 >> b1;
  s.push_back(make_pair(a1, b1));
}
sort(eall(s));
erep(i, 0, N-1){
  s[i+1].second += s[i].second;
}
long ans;
erep(i, 0, N-1){
  if(K > s[i].second && K <= s[i+1].second){
    ans = s[i+1].first;
    break;
  }
}
show(ans);

return 0;
}

Measured memory_bytes: 2420
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i,a,n) for(LL i = (a); i < (LL)(n); ++i)
#define REM(i,a,n) for(LL i = ((n) - 1); i >= (a); --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(0); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const string INFSTR = "\x7f";
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
// all_of
// partial_sum, adjacent_difference

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "Flow_Solver.h"
#include "Tree.h"
#include "Suffix_Array.h"
#include "Geometry.h"
#include "Matrix.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
#endif

int N, K;
int a, b, c;
int main() {
	cin >> N >> K;
	K /= 1000;
	REP(a, 0, N + 1) {
		REP(b, 0, N + 1) {
			int c = (K - a * 10 - b * 5);
			if (c < 0) continue;
			if (a + b + c == N) {
				cout << a << ' ' << b << ' ' << c << endl;
				return 0;
			}
		}
	}
	cout << "-1 -1 -1" << endl;

	return 0;
}


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

int main(){
	int n, x, i, j, k, num;

	while(1){
		//input
		cin >> n >> x;

		//init
		num = 0;
		for(i = 1; i <= n; i++){
			for(j = (i + 1); j <= n; j++){
				for(k = (j + 1); k <= n; k++){
					if((i + j + k) == x){
						//hit
						num++; 
						break;
					}
				}
			}
		}

		//end condition
		if(n == 0 && x == 0){
			break;
		}
		else{
			//output
			cout << num << endl;
		}
	}

	return 0;

}

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

int main() {
  char a,b;
  int result = 1;
  cin >> a >> b;

  if (a == 'D') {
    result *= -1;
  }
  if (b == 'D') {
    result *= -1;
  }
  if (result == 1) {
    cout << 'H' <<endl;
  } else {
    cout << 'D' <<endl;
  }
}

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

using namespace std;
using ll = unsigned long long;
ll mo=1e9+7;
int main() {
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b&& b==c)cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}



Measured memory_bytes: 256
N, M = map(int, input().split())
Lmi, Lma = [], []
for i in range(M):
  mi, ma = map(int, input().split())
  Lmi.append(mi)
  Lma.append(ma)
r = max(min(Lma) - max(Lmi) + 1, 0)
print(r)


Measured memory_bytes: 16816
X = int(input())
num = []
kekka = []
N = 2
if 360 % X == 0:
    print(int(360/X))
else:
    while N != X:
        if X / N != 1:
            if X % N == 0:
                num.append(N)
                X /= N
            else:
                N += 1
    num.append(N)
    Z = 1
    for i in range(len(num)):
        Z *= num[i]
    en = [2,2,2,3,3,5]
    for i in range(len(num)):
        if num[i] in en:
            kekka.append(num[i])
            en.remove(num[i])
        else:
            kekka.append(num[i])
    for i in range(len(en)):
        kekka.append(en[i])
    Y = 1
    for i in range(len(kekka)):
        Y *= kekka[i]
    print(int(Y / Z))

Measured memory_bytes: 9304
import java.util.*;
public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int x = sc.nextInt();
      int min = Integer.MAX_VALUE;
      for(int i = 0; i < n; i++) {
        int num = sc.nextInt();
        min = Math.min(min, num);
        x -= num;
      }
      
      System.out.println(n + x / min);
  }
}

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

template <typename T> void chmin(T&x,const T &y)
{
	if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
	char c;
	while(gc<'-');
	if(c=='-')
	{
		int x=gc-'0';
		while(gc>='0')x=x*10+c-'0';
		return -x;
	}
	int x=c-'0';
	while(gc>='0')x=x*10+c-'0';
	return x;
}
#undef gc

const int N=1e5+5;
int a[N];

int main()
{
#ifdef kcz
	freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
	int n;
	cin>>n;
	rep(i,1,n)a[i]=read();
	sort(a+1,a+n+1);
	int m=n/2-1;
	s64 ans=0;
	rep(i,1,m)ans+=(a[n-i+1]-a[i])*2;
	if(n%2==0)ans+=a[m+2]-a[m+1];
	else 
	{
		++m;
		ans+=max(a[m+1]-a[m],a[m+2]-a[m+1])+a[m+2]-a[m];
	}
	cout<<ans; 
}


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

public class Main {

  public static void main(String[] args) {
  
    new Main().run();
  }

  public void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      Card[] cards = new Card[n];
      char suit;
      int  value;

      for ( int i=0; i<n; i++ ) {
        suit = (char)br.read(); br.skip(1);
        value = Integer.parseInt(br.readLine());
        cards[i] = new Card(suit, value, i);
      }

      quickSortOfCards(cards, 0, n-1);
      dispCardArray(cards);
    }
    catch(IOException e) {
      System.out.println("IOException!");
    }
  }

  public void quickSortOfCards(Card[] card, int p, int r) {

    if( p < r) {
      int q = partitionOfCards(card, p, r);
      quickSortOfCards(card, p, q-1);
      quickSortOfCards(card, q+1, r);
    }
  }

  public int partitionOfCards(Card[] card, int p, int r) {

    int x = card[r].value;
    int i = p-1;
    Card t;

    for(int j=p; j<r; j++) {
      if(card[j].value <= x) {
        t = card[++i]; card[i] = card[j]; card[j] = t;
      }
    }
    t = card[i+1]; card[i+1] = card[r]; card[r] = t;

    return i+1;
  }

public void dispCardArray(Card[] target) {
  StringBuilder s = new StringBuilder();
  int l=target.length;
  boolean isStable = true;
  String sortState = "Stable";

  s.append(target[0]).append("\n");
  for (int i=1; i<l; i++) {
    s.append(target[i]).append("\n");
    if(isStable && target[i-1].value == target[i].value 
      && target[i-1].storedNo > target[i].storedNo) {
      sortState = "Not stable";
      isStable = false;
    }
  }

  System.out.println(sortState);
  System.out.print(s);
  }
}

class Card {
  char suit;
  int value;
  int storedNo;

  public Card( char suit, int value, int storedNo ) {
    this.suit  = suit;
    this.value = value;
    this.storedNo = storedNo;
  }
  public Card( Card card ) {
    this(card.suit, card.value, card.storedNo);
  }

  @Override
  public String toString() {
    return suit + " " + String.valueOf(value);
  }
}


Measured memory_bytes: 59836
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll hb(ll x){
  if(!x)return 0;
  ll ans=1;
  x>>=1;
  while(x){
    //    printf("%lld\n",x);
    x>>=1,ans<<=1;
  }
  return ans;
}
ll solve(ll a,ll b,ll lim){//printf("%lld %lld %lld\n",a,b,lim);
  if(b>lim)b=lim;
  if(a>b)return 0;
  if(a==b)return 1;
  ll t1=hb(a),t2=hb(b);
  if(t1==t2)return solve(a-t1,b-t1,lim-t1);
  //assert:t1<t2
  ll c=t2-1;//printf("%lld\n",(c-a+1)*2);
  return (c-a+1)+(min(lim-t2,c)-a+1)+solve(0,b-t2,min(a-1,lim-t2));
}
int main(){
  ll a,b;scanf("%lld%lld",&a,&b);
  printf("%lld\n",solve(a,b,(1ll<<62)));
  return 0;
}


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

typedef long long ll;

int main()
{
    ll N;
    cin >> N;
    vector<ll> data(N);
    
    for(ll i = 0; i < N; i++){
        cin >> data.at(i);
    }   
    int count = 0;  
    int answer = 0;  
    for(ll j = 0;j < N-1; j++){
        
        if(data.at(j) >=data.at(j+1)){
            count++;
          
        } else {
            answer = max(answer,count);
           count = 0;
        }
    }
    answer = max(answer,count);
    cout << answer  << endl;

}


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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream&
operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream&
operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream&
operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;

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

    vector<int> A(3); cin >> A;
    sort(all(A));
    int cnt = 0;
    int c =  (A[2] - A[0]) / 2;
    cnt += c;
    A[0] += c * 2;
    c = (A[2] - A[1]) / 2;
    cnt += c;
    A[1] += c * 2;
    sort(all(A));
    if(A[0] == A[1] and A[1] == A[2]) ;
    else if(A[0] == A[1]) cnt++;
    else cnt += 2;
    cout << cnt << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
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; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int n;
    cin >> n;
    n/=200;
    cout << 10-n << endl;
}

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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n+1, 0);
    for (int i=1; i<=n; i++) cin >> a[i];
    vector<int> f(n+1, 1000000000);
    f[1] = 0;
    for (int i=2; i<=n; i++)
    {
        for (int j=max(1, i-k); j<i; j++)
        {
            f[i] = min(f[i], f[j] + abs(a[i] - a[j]));
        }
    }
    cout << f[n];
    return 0;
}


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

int main(){
    int64_t n=0,a=0,b=0;
    cin >> n >> a >> b;
    if(a>b)cout << 0 << endl;
    else{
        if(a==b)cout << 1 << endl;
        else{
            if(n==1)cout << 0 << endl;
            //else if(n==2)cout << 1 << endl;
            else cout << (b-a)*(n-2)+1 << endl;
        }
    }
    return 0;
}

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

int main()
{
   int a,i;
   a=0;
   char sz[4];
   scanf("%s",sz);
   for(i=0;i<4;i++)
   {
       if(sz[i]=='+')
        a++;
       if(sz[i]=='-')
        a--;
   }
   printf("%d\n",a);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)
 
vector<int> Zalgo(const vector<int> &s){
    int N=s.size();
    vector<int> z(N,0);
    z[0]=N;
    int i=1,j=0;
    while(i<N){
        int c = s[i]^s[0]; 
        while(i+j<N && (s[i+j]^s[j])==c)j++;
        z[i]=j;
        if(j==0){i++;continue;}
        int k=1;
        while(i+k<N && z[k]+k < j){
            z[i+k]=z[k];
            k++;
        }
        i+=k;j-=k;
    }
    return z;
}
 
int main(){
    int N; cin >> N;
    vector<int> vec(3*N);
    REP(i,N) {
        int a; cin >> a;
        vec[i+N] = a;
        vec[i+2*N] = a;
    }
    REP(i,N) {
        int b; cin >> b;
        vec[i] = b;
    }
    vector<int> z = Zalgo(vec);
    FOR(i,N,2*N) {
        if(z[i]>=N) cout << i-N << ' ' << (vec[0]^vec[i]) << endl;
    }
    return 0;
}

Measured memory_bytes: 8192