akhauriyash/Code-Regression huggingface dataset:
formula = input().split()

ans = []
for f in formula:
    if f == '+':
        a = ans.pop()
        b = ans.pop()
        ans.append(a + b)
    elif f == '-':
        a = ans.pop()
        b = ans.pop()
        ans.append(b - a)
    elif f == '*':
        a = ans.pop()
        b = ans.pop()
        ans.append(b * a)
    else:
        ans.append(int(f))

print(*ans)


Measured memory_bytes: 5592
public class Main {

  private static void solve() {
    int n = ni();
    int[] a = na(n);
    int mod = (int) 1e9 + 7;

    long[] dp = new long[n + 1];
    dp[0] = 1;

    if (a[0] != 0) {
      System.out.println(0);
      return;
    }

    int[] cnt = new int[n + 1];
    cnt[0] = 3;
    long ret = 1;
    for (int i = 0; i < n; i++) {
      ret *= cnt[a[i]];
      ret %= mod;
      cnt[a[i]]--;
      cnt[a[i] + 1]++;
    }

    System.out.println(ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}



Measured memory_bytes: 37484
import java.util.Scanner;

//AtCoder Beginner Contest 134
//A	Dodecagon
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		sc.close();

		System.out.println(3 * r * r);
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

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

int main()
{
    ll N, K;
    cin >> N >> K;

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


    vector<ll> t(N+1, -1);
    vector<ll> used(N, -1);

    t[0] = 0;
    used[0] = 0;

    ll offset = 0;
    ll loop = 0;
    {
        ll c = 0;
        for (int i = 1; i <= N; ++i) {
            c = A[c];
            t[i] = c;

            if (used[c] != -1) {
                offset = used[c];
                loop = i - offset;

                break;
            }

            used[c] = i;
        }
    }

    if (K <= offset) {
        cout << t[K] + 1 << endl;
    } else {
        ll r = (K - offset) % loop;
        cout << t[offset + r] + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 7636
#include <bits/stdc++.h>
#define REP(i,n,N) for(ll i=(n);i<(ll) N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=(int) n;i--)
#define p(s) cout<<(s)<<endl
#define DEBUG(x,y) cout<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl;
#define CK(n,a,b) ((a)<=(n)&&(n)<=(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf=1e9+7;

int ans,a,b,c;
string s;

int main(){
	cin>>s;

	REP(i,0,s.size()-8){
		cout<<s[i];
	}
	p("");
	return 0;
}


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

using namespace std;

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

    int a,b;

    cin>>a>>b;

    int c=2*b;

    if(a>c)
    {
        int x=a-c;
        cout<<x<<endl;
    }
    else
    {
        cout<<"0"<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(ll)(n);++i)
#define _repe3(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define _rrepe2(i,n) for(ll i=(ll)(n);i>=0;i--)
#define _rrepe3(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)
#define rrepe(...) _overload3(__VA_ARGS__,_rrepe3,_rrepe2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
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;}

ll X;
ll K;
ll D;

void solve();

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> X;
    cin >> K;
    cin >> D;
    solve();
}

// -10^{15} <= X <= 10^{15}
// 1 <= K <= 10^{15}
// 1 <= D <= 10^{15}
// 入力は全て整数である

// ll X, ll K, ll D
// K 回の移動後の座標の絶対値としてあり得る値の最小値を出力せよ。
void solve(){
    X=abs(X);
    
    ll mi=min(K,X/D);
    X-=mi*D;
    K-=mi;

    if(K%2){
        cout<<abs(X-D)<<endl;
    }else{
        cout<<X<<endl;
    }
}


Measured memory_bytes: 3624
#include<stdio.h>
#include<algorithm>
#include<functional>
using namespace std;
long long a[100000], b[100000];
int main()
{
	int N;
	long long sa1 = 0, sa2 = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = 0; i < N; i++) {
		scanf("%lld", &b[i]);
	}
	for (int i = 0; i < N; i++) {
		if (a[i] > b[i]) {
			sa1 += a[i] - b[i];
		}
		else {
			sa2 += (b[i] - a[i]) / 2;
		}
	}
	if (sa1 - sa2 > 0) {
		printf("No");
	}
	else {
		printf("Yes");
	}
	return 0;
}

Measured memory_bytes: 256
// C - Write and Erase
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N; cin>>N;
	map<int,int> F;
	rp(i, 0, N){
		int a; scanf("%d",&a);
		F[a]++;
	}
	int ans = 0;
	for(auto f:F) ans += f.second%2? 1:0;
	printf("%d\n", ans);
}

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

int main(){
    char S[5];
    cin >> S[0] >> S[1] >> S[2];
    int c[3];
    for(int i = 0; i < 3; i++)c[i] = 0;

    for(int i = 0; i < 3; i++){
        if(S[i] == 'a')c[0]++;
        else if(S[i] == 'b')c[1]++;
        else if(S[i] == 'c')c[2]++;
    }

    if(c[0] == 1 && c[1] == 1 && c[2] == 1){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
    //
    string str;
  cin >> str;
  if(str.at(0) == str.at(1)) cout << "Bad";
  else if(str.at(1) == str.at(2)) cout << "Bad";
  else if(str.at(2) == str.at(3)) cout << "Bad";
  else cout << "Good";
    //
}


Measured memory_bytes: 3588
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n),n){
        int y;
        scanf("%d",&y);
        int mv;
        double ma=0.0;
        while(n--){
            int b,t,r;
            scanf("%d%d%d",&b,&r,&t);
            double d;
            if(t==1){
                d=(1.0+1.0*y*r/100);
            }
            else{
                d=1.0;
                for(int i=0;i<y;i++)d*=(1.0+1.0*r/100);
            }
            if(ma<d){
                ma=d;
                mv=b;
            }
        }
        printf("%d\n",mv);


    }
    return 0;
}

Measured memory_bytes: 1028
def main():
  
  N = int(input())
  alist = list(map(int, input().split()))

  adj4cou = 0
  adjn4y2 = 0
  for a in alist:
    if a%4 == 0:
      adj4cou += 1
      if adj4cou >= N//2:
        return 'Yes'
    elif a%2 == 0:
      adjn4y2 += 1
  if adjn4y2 >= (N - 2*adj4cou):
    return 'Yes'
  return 'No'

if __name__ == '__main__':
  print(main())

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = 998244353;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
ostream& operator<<(ostream& o,T t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){Int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}

class Combination{
public:
  typedef long long ll;
  ll N;
  ll mod;
  vector<ll> fac;
  vector<ll> finv;
  vector<ll> inv;
  
  
  Combination(ll N = 1e6,ll mod = 1e9 + 7): N(N), mod(mod), fac(N+1), finv(N+1), inv(N+1){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i <= N; i++){
      fac[i] = fac[i-1] * i % mod;
      inv[i] = mod - inv[mod%i] * (mod / i) % mod;
      finv[i] = finv[i-1] * inv[i] % mod;
    }
  }

  function<ll(ll,ll)> get = [&](ll n,ll r){
    if( n < r ) return 0LL;
    if( n < 0 || r < 0) return 0LL;
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod;
  };
};
auto nCr = (new Combination(1e6, mod))->get;


signed main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  
  
  Int n, A,B,K;
  cin>>n>>A>>B>>K;
  Int ans = 0;
  
  for(Int a=0;a <= n; a++){
    Int sumA = A * a;
    Int b = (K - sumA)/B;
    Int sumB = B * b;
    if(a < 0 || b < 0 || sumA + sumB != K) continue;
    ans += nCr(n, a) * nCr(n, b)%mod;
    ans %= mod;
  }

  ans%=mod;
  cout<<ans<<endl;
  
  return 0;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

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

	ll ans = 1LL << 60;
	rep(ab,max(x,y)+1){
		const int ra = max(0LL,x - ab);
		const int rb = max(0LL,y - ab);
		ll cost = 2LL * ab * c;
		cost += 1LL * a * ra;
		cost += 1LL * b * rb;
		chmin(ans,cost);
	}

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

Measured memory_bytes: 256
def readinput():
    n=int(input())
    cards=[]
    nums=set()
    for _ in range(n):
        m,nn=input().split()
        nn=int(nn)
        cards.append((m,nn))
        nums.add(nn)
    return n,cards, nums

def partition(cards,p,r):
    #print('before:',end='');print(cards[p:r+1])
    x=cards[r][1]
    i=p-1
    for j in range(p,r):
        if (cards[j][1] <= x):
            i+=1
            cards[j],cards[i]=cards[i],cards[j]
            #print(cards[p:r+1])
    cards[i+1],cards[r]=cards[r],cards[i+1]
    #print('after:',end='');print(cards[p:r+1])
    return i+1

def quickSort(cards,p,r):
    if (p<r):
        q=partition(cards,p,r)
        quickSort(cards,p,q-1)
        quickSort(cards,q+1,r)

def getMarks(cards,n):
    marks=[]
    for card in cards:
        if(card[1]==n):
            marks.append(card[0])
    return marks

def isStable(cards0, cards1, nums):
    for n in nums:
        marks0=getMarks(cards0,n)
        marks1=getMarks(cards1,n)
        if(marks0!=marks1):
            return False
    return True

def main(n,cards,nums):
    original = cards.copy()
    quickSort(cards,0,n-1)
    ans=isStable(original, cards, nums)
    if(ans==True):
        print('Stable')
    else:
        print('Not stable')
    for card in cards:
        print(card[0]+' '+str(card[1]))
    return

if __name__=='__main__':
    n,cards,nums=readinput()
    main(n,cards,nums)



Measured memory_bytes: 18820
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    s = list(input())
    t = list(input())

    ns = len(s)
    nt = len(t)

    if nt - ns == 1 and s == t[:-1] and 1 <= ns <= 10:
        last = t[-1]
        abc = list(map(chr, range(ord('a'), ord('z')+1)))
        if last in abc:
            print('Yes')
        else:
            print('No')
    else:
        print('No')


if __name__ == '__main__':
    solve()


Measured memory_bytes: 9132
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace At
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = Read();
            if (n[0] == n[2]) WriteLine("=");
            else if (n[0] > n[2]) WriteLine(">");
            else WriteLine("<");


        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  int k, a, b;
  cin >> k >> a >> b;
  if (a/k == b/k && a%k != 0)
    cout << "NG" << endl;
  else
    cout << "OK" << endl;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string color[]={"black","blue","lime","aqua","red","fuchsia","yellow","white"};
    int colornum[8][3]={{0,0,0},{0,0,255},{0,255,0},{0,255,255},{255,0,0},{255,0,255},{255,255,0},{255,255,255}};
    int value[200]={};
    for(int i=0;i<10;i++)value['0'+i]=i;
    for(int i=0;i<6;i++)value['a'+i]=10+i;
    string str;
    while(cin>>str&&str!="0"){
        int num[3];
        for(int i=0;i<3;i++)num[i]=value[str[1+2*i]]*16+value[str[2+2*i]];
        int ans[8]={};
        for(int i=0;i<8;i++){
            for(int j=0;j<3;j++)ans[i]+=pow(colornum[i][j]-num[j],2);
        }
        int co=0;
        for(int i=1;i<8;i++)if(ans[co]>ans[i])co=i;
        cout<<color[co]<<endl;
    }
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1000000007;



int main() {
    int N,Ssize;
    cin >> N;
    vector<string>S(N);
    long long ans = 0,Aback=0,Bfront=0,AB=0;
    for (size_t i = 0; i < N; i++)
    {
        cin >> S.at(i);
        Ssize=S.at(i).size();
        
        if (S.at(i).at(0) == 'B' && S.at(i).at(Ssize - 1) == 'A')AB++;
        else {
            if (S.at(i).at(Ssize - 1) == 'A')Aback++;
            if (S.at(i).at(0) == 'B')Bfront++;
        }
        for (size_t j = 0; j < Ssize-1; j++)
        {
            if (S.at(i).substr(j, 2) == "AB")ans++;
        }
        //末尾Aのやつと先頭Bのやつをドッキングさせる。
        //先頭Bのやつが文頭に孤立せざるを得ない状況もありうる。
        
    }
    if (Aback+Bfront == 0&&AB>0)AB--;
    
    ans += AB+min(Aback, Bfront);
    cout << max(ans,0LL);
}

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;


int main(){
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n - 1));
    for(auto&& i : a){
        for(auto&& j : i){
            cin >> j;
            j--;
        }
    }
    vector<int> nextBattle(n);
    vector<int> day(n);
    auto c = [](tuple<int, int, int> l, tuple<int, int, int> r) { return get<2>(r) < get<2>(l); };
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(c)> q(c);
    for(int i = 0; i < n; i++){
        if(i < a[i][0] && a[a[i][0]][0] == i){
            day[i] = day[a[i][0]] = 1;
            nextBattle[i] = nextBattle[a[i][0]] = 1;
            q.push(make_tuple(i, a[i][0], 1));
        }
    }
    int battlecount = 0;
    while(q.size()){
        auto status = q.top();
        q.pop();
        int x = get<0>(status);
        int y = get<1>(status);
        int d = get<2>(status);
        battlecount++;
        if(battlecount == n * (n - 1) / 2){
            cout << d << "\n";
            return 0;
        }
        if(nextBattle[x] < n - 1 && a[a[x][nextBattle[x]]][nextBattle[a[x][nextBattle[x]]]] == x){
            day[x] = day[a[x][nextBattle[x]]] = max(day[x], day[a[x][nextBattle[x]]]) + 1;
            q.push(make_tuple(x, a[x][nextBattle[x]], day[x]));
            nextBattle[a[x][nextBattle[x]]]++;
            nextBattle[x]++;
        }
        if(nextBattle[y] < n - 1 && a[a[y][nextBattle[y]]][nextBattle[a[y][nextBattle[y]]]] == y){
            day[y] = day[a[y][nextBattle[y]]] = max(day[y], day[a[y][nextBattle[y]]]) + 1;
            q.push(make_tuple(y, a[y][nextBattle[y]], day[y]));
            nextBattle[a[y][nextBattle[y]]]++;
            nextBattle[y]++;
        }
    }
    cout << -1 << "\n";
}

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

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

  int ans = 0, tmp = 1e9;

  for (int i = 0; i < N - 1; i++) {
    int b;
    cin >> b;
    ans += min(tmp, b);
    tmp = b;
  }

  cout << ans + tmp << "\n";
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
  int A, B, C, X, count = 0;
  std::cin >> A >> B >> C >> X;
  
  for(int i = 0; i <= A; i++)
  {
    for(int j = 0; j <= B; j++)
    {
      for(int k = 0; k <= C; k++)
      {
        if((i*500 + j*100 + k*50) == X)
        {
          count++;
        }
      }
    }
  }
  
  std::cout << count;
  return 0;
}

Measured memory_bytes: 3172
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		string[] input = Console.ReadLine().Split(' ');
		string s = input[0];
		string t = input[1];
    char[] ss = s.ToCharArray();
    char[] tt = t.ToCharArray();
    string answer = "";

    for(int i = 0; i < n; i++)
    {
      answer += ss[i];
      answer += tt[i];
    }

		Console.WriteLine(answer);
	}
}

Measured memory_bytes: 11092
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
 	string s,t;
 	cin>>s>>t;
 	if(t.size()!=s.size()+1)
 	{
 		cout<<"No"<<endl;
 		return 0;
 	}
 	t.pop_back();
 	if(s==t)
 	{
 		cout<<"Yes"<<endl;
 		return 0;
 	}
 	cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3640
/*
                IftekharMd.Shishir
                Dept. of Information and Communication Engineering
                University of Rajshahi
                19.04.20

*/
#include<bits/stdc++.h>

#define ll          long long int
#define ull         unsigned long long int
#define f(i,n)      for(i=0;i<n;i++)
#define F(i,n)      for(i=n;i>=0;i--)
#define fa(i,a,b)   for(i=a;i<b;i++)
#define Fa(i,a,b)   for(i=a;i>=b;i--)

#define vec         vector<long long int>
#define que         queue<long long int>    // a.push(x)   a.pop()    a.back()    a.front()
#define sea         set<long long int>
#define sed         set<long long int, greater<long long int> >   // a.insert();
#define pb(x)       push_back(x)
#define pob()       pop_back()
#define sor(a)      sort(a.begin(),a.end())
#define rev(a)      reverse(a.begin(),a.end())
#define ins(a,x)    insert(a.begin(),x)          // push in front
#define points(x)   fixed<<setprecision(x)
#define gcd(x,y)    __gcd(x,y)
#define beshi       LONG_LONG_MAX
#define kom         LONG_LONG_MIN
#define done        return 0

const double PI= 2*acos(0.0);
const long long MOD= 1000000007;

/*----------[ string to integer ]--------------
string str;  int x=0;
stringstream demo(str);
demo >> x;
cout<< x <<endl;
*/

/*----------[ integer to string ]--------------
string name;  int x=345;
stringstream demo;
demo << x;
name=demo.str();
cout<< name <<endl;
*/
using namespace std;

int main()
{
    double n;
    cin>>n;
    cout<<points(20)<<2*PI*n<<endl;
    done;
}




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

int H, W;
vector<string> grid;
const int nx[4] = {0, 0, 1, -1};
const int ny[4] = {1, -1, 0, 0};
 
int main() {
    cin >> H >> W;
    grid.resize(H);
    for (int i = 0; i < H; i++) cin >> grid[i];
    const int conditx[4] = {-1, -1, W-1, 0};
    const int condity[4] = {H-1, 0, -1, -1};
    int flag = 1;
    for (int x = 0; x < W && flag; x++) {
        for (int y = 0; y < H && flag; y++) {
            if (grid[y][x] == '.') continue;
            int tempflag = 0;
            for (int i = 0; i < 4; i++) {
                if (!tempflag && x != conditx[i] && y != condity[i] && grid[y+ny[i]][x+nx[i]] == '#') tempflag = 1;
            }
            flag = tempflag;
        }
    }
    string ans = flag ? "Yes" : "No";
    cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding: utf-8 -*-
x, k, d = map(int, input().split())
if x < 0:
    x *= -1
t1 = x % d
t2 = t1 - d
n = (x - t1) // d
if k < n:
    print(x - k * d)
else:
    n = k - n
    if n % 2 == 0:
        print(t1)
    else:
        print(-t2)


Measured memory_bytes: 9084
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner stdIn = new Scanner(System.in);
    
    int a = stdIn.nextInt(); 
    
    int b = stdIn.nextInt();
    
    int c = stdIn.nextInt();
    
    if(a+b+c==17){
    System.out.println("YES");
    }else{
    System.out.println("NO");  
    }
  }
}

Measured memory_bytes: 22608
#include<stdio.h>
int i,j,n,v,u,k,time,data[101][101],d[101],f[101];
void visit(int u){
  int v;
  d[u]=time++;

  for(v = 1; v <= n; v++){
    if(data[u][v]&d[v]==0)
      visit(v);
  }
  f[u]=time++;
}

int main(){
  time=1;
  scanf("%d",&n);
  for(i = 1; i <= n; i++){
    for(j = 1; j <= n; j++){
      data[i][j]=0;
      d[j]=0;
      f[j]=0;
    }
  }
  for(i = 0; i < n; i++){
    scanf("%d",&u);
    scanf("%d",&k);
    for(j = 0; j < k; j++){
      scanf("%d",&v);
      data[u][v]=1;
    }
  }
  for(i=1;i<=n;i++){
    if(d[i]==0)visit(i);
  }
  for(i = 1;i <= n;i++){
    printf("%d %d %d\n",i,d[i],f[i]);
  }
  return 0;
}


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

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;

lli p, q, a, n;

int dfs (lli pp, lli qq, lli aa, int nn, int fs) {
    if (p * qq == pp * q) return 1;
    if ((p * qq < pp * q) || nn >= n) return 0;
    int cnt = 0;
    for (lli t = fs; t * aa <= a; t++) {
        cnt += dfs(pp * t + qq, qq * t, aa * t, nn + 1, t);
    }
    return cnt;
}

int main () {
    while (cin >> p >> q >> a >> n, p + q) {
        cout << dfs(0, 1, 1, 0, 1) << endl;
    }
    return 0;
}

Measured memory_bytes: 3072
from collections import defaultdict
d = defaultdict(int)

N = int(input())
S = [input() for n in range(N)]

for s in S:
  d[s] += 1

li = []
ma = 0

for s in d:
  if ma == d[s]:
    li.append(s)
    ma = d[s]
    
  if ma < d[s]:
    li = []
    li.append(s)
    ma = d[s]

li.sort()
for i in li:
  print(i)

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

int main(void){
	int A , B , a_min , a_max , b_min , b_max;
	cin >> A >> B ;
	b_min=B*10;
	b_max=B*10+9;
	if(A%2==0){
		a_min=25*A/2;
		a_max=(25*A+24)/2;
	}
	else {
		a_min=(25*A+1)/2;
		a_max=(25*A+23)/2;
	}
	
	if((a_min>=b_min)&&(a_min<=b_max)) cout << a_min << endl;
	else if((b_min>=a_min)&&(b_min<=a_max)) cout << b_min << endl;
	else cout << "-1" <<endl;

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e15;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 3;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 0;
    rep(i, 0, n - 1) ans += a[i + 1] - a[i];
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>

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

using namespace std;

const double INF=1e77;

int W,n;
double x[500],y[500];

bool disturb(double r){
	bool vis[500]={};
	int Q[500],head=0,tail=0;
	rep(u,n) if(x[u]<r) {
		vis[u]=true;
		Q[tail++]=u;
	}
	while(head<tail){
		int u=Q[head++];
		if(W-x[u]<r) return true;
		rep(v,n) if(!vis[v] && (x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v])<4*r*r) vis[v]=true, Q[tail++]=v;
	}
	return false;
}

int main(){
	scanf("%d%*d%d",&W,&n);
	rep(i,n) scanf("%lf%lf",x+i,y+i);

	double lo=0,hi=1e9;
	while((hi-lo)>1e-4){
		double mi=(lo+hi)/2;
		if(disturb(mi)) hi=mi; else lo=mi;
	}
	printf("%.9f\n",(lo+hi)/2);

	return 0;
}

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

#define REP(i,n) for(ll i = 0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define LINF 1LL<<62
typedef long long ll;
typedef pair<long, long> pl;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n , x;
    cin >> n >> x;
    vector<ll> a(n);
    REP(i,n){
        cin >> a[i];
    }
    ll ans = LINF;
    vector<ll> mia(n, LINF);
    REP(i,n){
        ll anstmp = 0;
        REP(j,n){
            mia[j] = min(mia[j] , a[(j-i+n)%n]);
            anstmp += mia[j];
        }
        anstmp += i*x;
        ans = min(ans, anstmp);
    }
    cout << ans << '\n';

 
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;
#define int long long


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

    int n; cin >> n;
    vector<string> s(n);
    for(int i = 0;i < n;i ++) cin >> s.at(i);

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

    int a = 1;
    int m = 0;
    for(int i = 1;i < n;i ++){
        if(s.at(i) == s.at(i-1)) a ++;
        else a = 1;
        m = max(a,m);
    }

    a = 1;

    if(m == 1) cout << s.at(0) << endl;
    for(int i = 1;i < n;i ++){
        if(s.at(i) == s.at(i-1)) a ++;
        else a = 1;
        if(a == m) cout << s.at(i) << endl;
    }
}

Measured memory_bytes: 12928
N=int(input())
A=[int(i) for i in input().split(" ")]
B=[int(i) for i in input().split(" ")]

count=0
for i in range(N):
    if A[i]>=B[i]:
        A[i]-=B[i]
        count+=B[i]
    elif A[i]<B[i]:
        if A[i+1]>=B[i]-A[i]:
            A[i+1]-=B[i]-A[i]
            count+=B[i]
        elif A[i+1]<B[i]-A[i]:
            count+=A[i]+A[i+1]
            A[i+1]=0
      
print(count)

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

string latte="HD";

int in(){
    char c;
    cin>>c;
    return find(all(latte),c)-latte.begin();
}

signed main(){
    int a=in();
    int b=in();

    a^=b;
    cout<<latte[a]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int n;
	double s;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		if(i%2==1){
            s+=1;
        }
	}
	printf("%.10lf",s/(double)n);
    return 0;
} 


Measured memory_bytes: 128
a,b,c = gets.split.map(&:to_i)

s = []

if (a < b) && (a < c)
    s.insert(0,a)
    if (b < c)
        s.insert(1,b)
        s.insert(2,c)
    else
        s.insert(1,c)
        s.insert(2,b)
    end
elsif (b < a) && (b < c)
    s.insert(0,b)
    if (a < c)
        s.insert(1,a)
        s.insert(2,c)
    else
        s.insert(1,c)
        s.insert(2,a)
    end
else
    s.insert(0,c)
    if (a < b)
        s.insert(1,a)
        s.insert(2,b)
    else
        s.insert(1,b)
        s.insert(2,a)
    end
end

puts s[0].to_s + ' ' + s[1].to_s + ' ' + s[2].to_s


Measured memory_bytes: 6876
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); cout << '\n';}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr ll INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1);
constexpr ld EPS = 1e-11;

int main(void){
	string s, r;
	cin >> s;
	ll q;
	cin >> q;
	bool flg = false;
	rep(i, q){
		ll t;
		cin >> t;
		if(t == 1) flg = !flg;
		else{
			ll f;
		    char c;
			cin >> f >> c;
			if(f == 1){
				if(flg) s += c;
				else r += c;
			}else{
				if(flg) r += c;
				else s += c;
			}
		}
	}

    reverse(all(r));
    r += s;
	if(flg) reverse(all(r));
	co(r);

	return 0;
}


Measured memory_bytes: 1384
#include<stdio.h>
#include<math.h>

int main(){
	char s[200000];
	scanf("%s", s);
	int count=0;
	int i = 0;
	while (s[i] != '\0') {
		if (s[i] == '?') {
			s[i] = 'D';
		}
		i++;
	}
	printf("%s\n", s);
	return 0;
}


Measured memory_bytes: 1856
N,C=map(int, input().split())
D=[list(map(int, input().split())) for _ in range(C)]
c=[list(map(int, input().split())) for _ in range(N)]

d = [[] for _ in range(3)]

for color in range(1,C+1):
    t = [0]*3
    for i in range(N):
        for j in range(N):
            if c[i][j] != color:
                t[(i+j)%3] += D[c[i][j]-1][color-1]
    for k in range(3):
        d[k].append((color, t[k]))

for k in range(3):
    d[k].sort(key=lambda x:x[1])

ans = 10**9
for i in range(3):
    for j in range(3):
        for k in range(3):
            if len({d[0][i][0], d[1][j][0], d[2][k][0]}) != 3: continue
            ans = min(ans, d[0][i][1] + d[1][j][1] + d[2][k][1])
print(ans)

Measured memory_bytes: 44508
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i=0;i<(n);++i)
#define RANGE(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(n)-1;i>= 0;--i)

#define endl '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.141592653589793238
#define dcout cout<<fixed<<setprecision(20)

const long long dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef long long ll;
#define int long long
#define double long double

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
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;}

typedef pair<int, int> INTP;
typedef vector<int> INTV;
struct edge2 {int to, cost;};
struct edge3 {int from, to, cost;};

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

  int N; double x[8], y[8]; cin >> N;
  INTV vec(N);
  REP(i, N){
    cin >> x[i] >> y[i];
    vec[i] = i;
  }
  double ans = 0.0; int cnt = 0;
  do{
    cnt++;
    REP(i, N-1){
      ans += sqrt(pow(x[vec[i]]-x[vec[i+1]], 2.0) + pow(y[vec[i]]-y[vec[i+1]], 2.0));
    }
  } while(next_permutation(ALL(vec)));
  dcout << ans / cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}


// -100 -10 -3 0 2 9 17
// INF   90  7 3 2 7 8
// x      x          x

// int arr[100010][3];

bool cmp1(vi& a, vi& b) {
  return a[0] < b[0];
}
bool cmp2(vi& a, vi& b) {
  return a[1] > b[1];
}
int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  // ll n;
  // cin >> n;
  ll n, m;
  cin >> n >> m;
  // ll n, m, k;
  // cin >> n >> m >> k;
  if(n >= m) {
    cout << "0\n";
    return 0;
  }
  vector< vector<int> > arr(m, vi(3));
  fi(0, m) {
    cin >> arr[i][0];
  }
  sort(all(arr), cmp1);
  arr[0][1] = INF;
  fi(1, m) {
    arr[i][1] = arr[i][0] - arr[i - 1][0];
  }
  sort(all(arr), cmp2);
  fi(0, n) {
    arr[i][2] = 1;
  }
  // sort(all(arr), cmp1);
  // fi(0, m) {
  //   fj(0, 3) {
  //     cout << arr[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  fi(0, m) {
    if(!arr[i][2])
      ans += arr[i][1];
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	int n,x,y,i,j;
	cin>>n>>x>>y;
	x--;y--;
	int dist[n][n];
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		dist[i][j]=min(abs(i-j),min(abs(i-x)+1+abs(y-j),abs(i-y)+1+abs(x-j)));
	}
	int cnt[n];
	for(i=0;i<n;i++)
	cnt[i]=0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		cnt[dist[i][j]]++;
	}
	for(i=1;i<n;i++)
	cout<<cnt[i]/2<<endl;
	return 0;
}


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

int main() {
  string ans;
  int n;
  cin >> n;
  vector<int> p(n, 0), pp(n, 0);
  rep(i,n){
    cin >> p[i];
    pp[i] = i+1;
  }
  ans = "NO";
  if (p == pp) ans = "YES";
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      swap(p[i],p[j]);
      if (p == pp) ans = "YES";
      swap(p[i],p[j]);
    }
  }

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


Measured memory_bytes: 256
n=int(input())
x=0
while True:
    if (x+1)**5-x**5>10**9:
        x+=1
        break
    x+=1
for i in range(-x,x):
    for j in range(-x,x):
        if i**5-j**5==n:
            print(i,j)
            exit()

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

int main() {
    ll X;
    cin >> X;
    for(int i=-600; i<601; i++) {
        for (int j=-600; j<601; j++) {
            if (pow(i,5)-pow(j,5) == X) {
                cout << i << " " << j << endl;
                exit(0);
            }
        }
    }
}

Measured memory_bytes: 4000
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define MP make_pair
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

#define ALL(a)  (a).begin(),(a).end()

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

	int n = S.length();
	REP(i, n - 1){
		if(S[i] == S[i + 1]){
			cout << "Bad" << endl;
			return 0;
		}
	}

	cout << "Good" << endl;
	return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;

ll C[55][55];
int n,p;
int odd,even;

void init(){
	MS(C);
	for(int i=0; i<=n; i++){
		C[i][0] = 1;
		for(int j=1; j<=i; j++)
			C[i][j] =(C[i-1][j-1]+C[i-1][j]);
	}
}

int main(){
	cin >> n >> p;
	init();
	for(int i=1; i<=n; i++){
		int x = read();
		if(x%2) odd++;
		else even++;
	}
	ll sum1 = 0, sum2 = 0;
	for(int i=0; i<=even; i++){
		sum1 += C[even][i];
	}
	if(p == 0){
		for(int i=0; i<=odd; i+=2){
			sum2 += C[odd][i];
		}
	}else{
		for(int i=1; i<=odd; i+=2){
			sum2 += C[odd][i];
		}
	}
	// cout << sum1 << " " << sum2 << endl;
	ll ans = sum1*sum2;
	
	cout << ans << endl;



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

int main(){
  int N;
  cin>>N;
  VI A(N),B(N);
  rep(i,N) cin>>A[i]>>B[i];
  ll sum=0;
  rep(i,N) sum+=A[i];
  int tmp=1001001001;
  rep(i,N){
    if(A[i]>B[i]) tmp=min(tmp,B[i]);
  }
  int F=1;
  rep(i,N) F*=(A[i]==B[i]);
  cout<<(F?0:sum-tmp)<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int a, b; cin >> a >> b;
	cout << a * b << '\n';
	return 0;
}

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

int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }
    ll sm=0;
    ll sm2=0;
    rep(i,n){
        sm+=a[i];
        sm2+=a[i]*a[i];
    }
    ll ans=sm2;
    int mn2;
    double mn=(double)sm/(double)n;
    if(mn>=0){
        mn+=0.5;
        mn2=mn;
    } else{
        mn*=-1;
        mn+=0.5;
        mn2=mn;
        mn2*=-1;
    }
    ans+=n*mn2*mn2;
    ans-=2*mn2*sm;
    cout << ans << endl;
}

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

int main() {
  int r;
  cin >> r;
  double ans = r * 2 * acos(-1);
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3772
#include<iostream>
using namespace std;
int have[4],sum;
int coin[4]={10,50,100,500};

int main(){
  bool first=true;
  while(cin>>sum,sum){
    if(first!=true)cout << endl;
    first=false;

    int price=0;
    for(int i=0;i<4;i++) cin>>have[i];

    for(int i=0;i<4;i++)price+=have[i]*coin[i];
    price-=sum;

    for(int i=3;i>=0;i--){
      while(price>=coin[i]){
        price-=coin[i];
        have[i]--;
      }
    }

    for(int i=0;i<4;i++){
      if(have[i]>0)
        cout <<  coin[i] << " " << have[i]<< endl; 
    }

  }
  return 0;
}

Measured memory_bytes: 2960