akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
n,x,y = map(int,input().split())
# 問題 nC2 の中から、最短距離がk になる頂点の組み合わせをそれぞれ求める
# n <= 2*10**3なのでnC2は回る。O(1)に行ける
if x > y: x,y = y,x
#x < y
ans = [0]*n#出力は 0　消す
for i in range(1,n):
    for j in range(i+1,n+1):# i < jとする
        # パターン 1 [x,y]の両方外
        if y <= i or j <= x:
            k = j-i
            ans[k] += 1
        # パターン2 片方が[i,j]の内側
        elif (x<=i and i <= y and y <= j):
            k = min(j-i,i-x+j-y+1)
            ans[k] += 1
        # 片方が内側 i,x,j,y
        elif (i<=x and x <= j and j<=y):
            k = min(j-i,y-j+1+x-i)
            ans[k] += 1
        elif i <=x and y <= j:
            k = x-i+1+j-y
            ans[k] += 1
        else:#両方[x,y]の内側 x,i,j,y
            k = min(j-i,1+i-x+y-j)
            ans[k] += 1
        #print(i,j,k)
for i in range(1,n):
    print(ans[i])




Measured memory_bytes: 48092
{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Data.List
import Data.Bits
import Debug.Trace
import Data.Maybe
import qualified Data.ByteString.Char8 as C

main :: IO ()
main = do
  [a, b, x] <- map fromIntegral <$> readInts
  print $ solve a b x

-- 場合1 (x > a ^ 2 * b / 2)
-- (a^2 * b) - x = a^2 * c / 2
-- c = 2 * (b - (x / a^2))
-- a = c * (sin(theta) / cos(theta))
-- tan(theta) = a / (2 * (b - (x / a^2)))
-- theta = atan(a / c)
-- theta * 180 / pi
-- 場合2 (x <= a ^ 2 * b)
-- x = a * b * d / 2
-- d = 2 * x / a / b
-- b = d * (sin(theta) / cos(theta))
-- tan(theta) = b / (2 * x / a / b) = a * b ^ 2 / x / 2
-- atan (a * b ^ 2 / x / 2) * 180 / pi

solve a b x = if x > a ^ 2 * b / 2
  then 90 - atan (a / (2 * (b - (x / a ^ 2)))) * 180 / pi
  else atan (a * b ^ 2 / x / 2) * 180 / pi

-- 以下ライブラリ

readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

readNInts :: Int -> IO [[Int]]
readNInts = flip replicateM readInts

readIntegers :: IO [Integer]
readIntegers = map (fst . fromJust . C.readInteger) . C.words <$> C.getLine

readNIntegers :: Int -> IO [[Integer]]
readNIntegers = flip replicateM readIntegers

getNLns :: Int -> IO [String]
getNLns = flip replicateM getLine

Measured memory_bytes: 508
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<string.h>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
	unsigned long long n, a, b,sum=0,temp;
	cin >> n >> a >> b;
	temp = n / (a + b);
	sum += temp * a;
	n = n % (a + b);
	if (n > a) sum += a;
	else sum += n;
	cout << sum;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<string>
using namespace std;
int main() {
	int h, n;
	cin >> h >> n;
	int a[100000];
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	if (h <= sum) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 640
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        long h = scan.nextLong();
        long w = scan.nextLong();
        scan.close();
        long men = h * w;

        if(h == 1 || w == 1) System.out.println("1");
        else if(men % 2 == 0) System.out.println(men / 2);
        else System.out.println((men / 2) + 1);
    }
}

Measured memory_bytes: 23380
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sct(tc) scanf("%lld",&tc)
#define scl(n) scanf("%lld",&n)
#define scll(n,m) scanf("%lld%lld",&n,&m)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
int main()
{
	ll n,k,r,len,i;
	scanf("%lld",&n);
	string s="";
	while(n)
	{
	   n--;
	   s+='a'+(n%26);
	   //cout << n%26;
	   n/=26;
	}
   len=s.size();
   for(i=len-1;i>=0;i--)
   printf("%c",s[i]);
   printf("\n");	
}


Measured memory_bytes: 3692
#include <stdio.h>

int main() {

	int x, y, s, i=1, j,k=0;
	int answer[100000] = { 0 };

	while (i) {
		scanf("%d %d %d", &x, &y, &s);
		if (x == 0 && y == 0 && s == 0)
			break;
		for (i = 1; i < s; i++){
			for (j = 1; j <s; j++){
				if (s == i*(100 + x) / 100 + j*(100 + x) / 100) {
					if (answer[k] < i*(100 + y) / 100 + j*(100 + y) / 100) {
						answer[k] = i*(100 + y) / 100 + j*(100 + y) / 100;
					}
				}
			}
		}
		k++;
	}

	for (i = 0; i < k; i++)
		printf("%d\n", answer[i]);
	return 0;
}

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

int main(){
  long long N, ans = 0, tmp;
  cin >> N;
  for(long long i = 1; i <= N - 1; i++){
   ans += N / i;
   if (N % i == 0) ans--;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[10000];
    int i,j,k,l,m,n;
    scanf("%s",s);
    l=strlen(s);
    int count = 0;
    for(i=0;i<l;i++)
    {
        if(s[i]=='2')
        count++;
    }
    cout<<count;
}

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

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

    long long t = 0;

    for (long long i = 1; i < n; i++) {
        //cout << i << "/ " << (n / i) << ":" << (n % i) << endl;
        if (n % i == 0) {
            continue;
        }
        if (n / i == n % i) {
            t += i;
            i = max(n / i, i);
        } else if (n / i > n % i) {
            //i = max(n / i, i);
        } else if ((n % i) % (n / i) != 0) {
            i += (n % i) / (n / i);
        } else if ((n % i) % (n / i) == 0) {
            i += (n % i) / (n / i) - 2;
        }
    }
    cout << t << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <cstring>
#include <tuple>
#include <bitset>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i=0; i<n; ++i) {
        vector<int> base(3, 0);
        string event;
        int score = 0, out = 0;
        while (cin >> event) {
            if (event == "HIT") {
                score += base[2];
                base[2] = base[1];
                base[1] = base[0];
                base[0] = 1;
            } else if (event == "OUT") {
                out ++;
                if (3 <= out) break;
            } else if (event == "HOMERUN") {
                score += base[2] + base[1] + base[0] + 1;
                fill(base.begin(), base.end(), 0);
            }
        }
        cout << score << endl;
    }

    return 0;
}

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

int main(){
    int n, m=0;
    int c=1;
    bool b;
    unordered_map<unsigned, unsigned> un_mp;
    cin >> n;
    for(int i=1; i<=n; ++i){
        cin >> m;
        un_mp[i]=m;
    }
    for(int i=n; i>1; --i){
        b=true;
        if(un_mp[i]<un_mp[i-1]){
            continue;
        }else{
            for(int j=(i-1); j>=1; --j){
                if(un_mp[i]<un_mp[j]){
                    b=false;
                    continue;
                }
            }
        }
        if(b==true){
            c+=1;
        }
    }
    cout << c << endl;
}

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

using namespace std;

int main()
{
    int w, h, n;
    cin >> w >> h >> n;

    vector<vector<bool>> rec(w, vector<bool>(h, true));

    for (int i = 0; i < n; i++) {
        int x, y, a;
        cin >> x >> y >> a;
        switch (a) {
            case 1:
                for (int j = 0; j < x; j++) {
                    for (int k = 0; k < h; k++) {
                        rec[j][k] = false;
                    }
                }
                break;

            case 2:
                for (int j = x; j < w; j++) {
                    for (int k = 0; k < h; k++) {
                        rec[j][k] = false;
                    }
                }
                break;

            case 3:
                for (int j = 0; j < y; j++) {
                    for (int k = 0; k < w; k++) {
                        rec[k][j] = false;
                    }
                }
                break;

            case 4:
                for (int j = y; j < h; j++) {
                    for (int k = 0; k < w; k++) {
                        rec[k][j] = false;
                    }
                }
                break;
        }
    }

    int ans = 0;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            if (rec[i][j]) {
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

void swap( int* , int* );

int main(void)
{
	int a, b;
	int i;
	int gcd, lcm;
	
	while( scanf("%d %d", &a, &b ) != EOF )
	{
		gcd = 1;
		lcm = 1;
		if( a > b ) swap( &a , &b );
	
		for( i = 1 ; i <= a ; i++ )
		{
			if( a % i == 0 && b % i == 0 )
			{
				gcd *= i;
				a /= i;
				b /= i;
				i = 1;
			}
		}
		lcm = gcd * a * b;

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

void swap( int *a , int *b )
{
	int t;
	t = *a;
	*a = *b;
	*b = t;
}

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

#define ll long long
#define FASTIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ii pair < ll , ll >
#define all(x) std::begin(x), std::end(x)

ll const MAX = 100005 ;
ll const INF = 1e9 ;
ll const mod = 1000000007 ;


ll dp[MAX] ;
ll a[MAX] ;
ll n ;
int k ;

ll cost ( int ndx )
{
    if ( ndx >= n - 1 )
        return 0 ;

    ll &ret = dp[ndx] ;
    if ( ret != -1 )
        return ret ;

    ret = abs ( a[ndx] - a[ndx+1] ) + cost ( ndx + 1 ) ;
    for ( int i = ndx + 2 ; i <= ndx + k ; i ++ )
    {
        if ( i > n - 1 )
            break ;
        ret = min ( ret , abs ( a[ndx] - a[i] ) + cost ( i ) ) ;
    }
    return ret ;
}


int main ()
{
    //freopen ( "portals.in" , "r" , stdin ) ;
    FASTIO ;

    cin >> n >> k ;
    memset ( dp , -1 , sizeof dp ) ;
    for ( int i = 0 ; i < n ; i ++ )
        cin >> a[i] ;

    cout << cost ( 0 ) ;


}


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

int main() {
	int a, b, c, d;
  	cin >> a >> b >> c >> d;
  	int answer = 0;
  	//int times = 2 * max(a/d,c/b);
  	for (int i=0;i<200;i++) {
    	c -= b;
      	if (c <= 0) {
          answer = 1;
          break;
        }
      	a -= d;
      
      	if (a <= 0) {
          answer = 0;
          break;
        }
    }
  
  	if (answer == 1) cout << "Yes" << endl;
  	else cout << "No" << endl;
  	
}

Measured memory_bytes: 3576
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ll = long long;

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> h(n);
  REP(i,n) cin >> h[i];
  sort(h.begin(),h.end());
  
  int ans = 1000000000;
  REP(i,n-k+1){
    ans = min(ans,h[n-1-i]-h[n-i-k]);
  }
  
  cout << ans << endl;
  
}

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

int d(int num){
    int cnt = 1;
    while(num / 10){
        num /= 10;
        cnt++;
    }
    return cnt;
}

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

    int n, m;
    cin >> n >> m;

    pair <pair<int, int>, int> id[m];

    for (int i = 0; i < m; ++i){
        int p, y;
        cin >> p >> y;
        id[i] = make_pair(make_pair(p, y), i);
    }
    sort(id, id + m);
    
    pair <int, pair<int, int>> res[m];
    int cnt = 1;
    int prev = -1;
    for(int i = 0; i < m; ++i){
        // cout << id[i].first.first << " " << id[i].first.second << " " << id[i].second << endl;

        if(id[i].first.first != prev) cnt = 1;
        res[i] = make_pair(id[i].second, make_pair(id[i].first.first, cnt));
        cnt++;
        prev = id[i].first.first;
    }

    sort(res, res + m);

    for(int i = 0; i < m; ++i){
        //cout << res[i].first << " " << res[i].second.first << " " << res[i].second.second << endl;
    }

    for(int i = 0; i < m; ++i){
        int left = res[i].second.first;
        int right = res[i].second.second;
        int ld = d(left);
        int rd = d(right);
        
        for(int j = 0; j < 6-ld; ++j) cout << 0;
        cout << left;
        for(int j = 0; j < 6-rd; ++j) cout << 0;
        cout << right << endl; 
    }
    return 0;
}

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

using namespace std;

int main(void) {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    int ans = numeric_limits<int>::max();
    for(int i=0; i<=2*max(X, Y); i+=2) {
        ans = min(ans, C*i + A*max(0, X-i/2) + B*max(0, Y-i/2));
    }

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


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

using namespace std;

int main() {
  int n,ans=0;
  cin>>n;
  vector<int>a(n);
  for (int i = 0; i < n; i++)
  {
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for (int i = 0; i < n; i++)
  {
    for (int j = i+1; j < n; j++)
    {
      for (int k = j+1; k < n; k++)
      {
        if (a[i]<a[j]+a[k]){
          ans++;
        }
        else{
          break;
        }
      }
      
    }
    
  }
  cout<<ans<<endl;
  
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define str string
#define ld long double
#define vec vector
#define vll vec<ll>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define kai "\n"
#define yuque priority_queue
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mie min_element
#define mae max_element
#define tos to_string
#define sep setprecision
#define lob lower_bound
#define upb upper_bound
#define nep next_permutation
#define MOD 1000000007ll
using namespace std;
void solve();
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed;
	solve();
}
struct pea{
	ll f,s;
	bool operator<(const pea &c)const{
		return f!=c.f?f<c.f:s<c.s;
	};
};
vec<bool> seen;
pea dfs(const vec<vec<pea>> &c,ll i,ll w){
	seen[i]=true;
	pea ww={w,i};
	rep(j,0,c[i].size()){
		if(!seen[c[i][j].s]){
			pea pp=dfs(c,c[i][j].s,w+c[i][j].f);
			if(ww.f<pp.f)ww=pp;
		}
	}
	return ww;
}
void solve(){
	ll n;cin>>n;
	vec<vec<pea>> c(n);
	seen.resize(n,false);
	rep(i,0,n-1){
		ll s,t,w;cin>>s>>t>>w;
		c[s].pub({w,t});
		c[t].pub({w,s});
	}
	pea k=dfs(c,0,0);
	rep(i,0,n)seen[i]=false;
	cout<<dfs(c,k.s,0).f<<kai;
}


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

#define rep(i, first, to) for(ll i = first; i < to; ++i)

using namespace std;
typedef long long ll;

void solve() {
	int x;
	cin >> x;
	cout << (x < 1200 ? "ABC" : "ARC") << endl;
}

int main() {
	solve();
	return 0;
}

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    int N; cin >> N;
    int two = 0;
    int four = 0;
    int odd = 0;
    REP(i,N){
        int a; cin >> a;
        if(a%2==1) odd++;
        else if(a%4==2) two++;
        else if(a%4==0) four++;
    }
    if(odd<=four || (odd==four+1 && two==0)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) int((v).size())
#define ALL(vec) begin(vec), end(vec)
typedef long long ll;
#define pb push_back
template<typename T> inline bool uax(T &x, T y) {return (y > x) ? x = y, true : false;}
template<typename T> inline bool uin(T &x, T y) {return (y < x) ? x = y, true : false;}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
  stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
string to_string(char c) { return "'" + string(1, c) + "'";}
string to_string(string s) { return '"' + s + '"';}
string to_string(const char* s) { return to_string((string) s);}
template<typename A> string to_string(A);
template<typename A, typename B> string to_string(pair<A, B> p){
  return "(" + to_string(p.first) + ": " + to_string(p.second) + ")";}
template<typename A> string to_string(A v) {bool f = false; string r = "{"; 
  for (auto x: v) {if (f) r += ", "; r += to_string(x); f = true;} return r += "}";}
template<typename A> string to_string(vector<vector<A>> v) {string r; 
  for (auto x: v) r += "\n" + to_string(x); return r;}
int Nerr;
template<typename A> string to_string(A *p) {return to_string(vector<A>(p, p + Nerr));}
void err(istream_iterator<string>) { cerr << endl; }
template<typename T,typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << to_string(a) << "; "; err(++it, args...); }
template<typename T> void kek(T ans) {cout << ans << endl; exit(0);}
int const MOD = 1e9 + 7;
long long const INF = 1e9 + 100 ;
int mod = MOD;
int add(int a, int b){
	if(a + b >= mod)return a+ b - mod;
	return a + b;
}
int mul(int a, int b){
	return 1LL * a * b  % mod;
}
int power(int a, int b){
	if(b < 0)return 0;
	int re = 1;
	while(b){
		if(b&1){
			re = mul(re, a);
		}
		a = mul(a, a);
		b >>= 1;
	}
	return re;
}
int const N = 100000 + 5;
int fact[N], inverse[N];
void FAC(){
 	fact[0] = 1;
	for(int x = 1; x< N; x++){
		fact[x] = mul(fact[x-1], x);
	}
	inverse[N-1] = power(fact[N-1], mod -2);
	for(int x = N-2; x>= 0; x--){
		inverse[x] = mul(x + 1, inverse[x+1]);
	}

 }

int ncr(int a, int b){
	if(a < b)return 0;
	return mul(fact[a], mul(inverse[a-b], inverse[b]));
}


/******************************************************/
struct dealer{
    int l, r, c;
    bool operator < (struct dealer b){
        if(b.l != l)return l < b.l;
        if(b.r != r)return r > b.r;
        return c < b.c;
    }
};
void solve(){
    string s;
    cin >> s;
    int n = s.length();
    if(n & 1){
    	cout << "No";
    	return;
    }
    for(int x  =0; x<n-1; x+=2){
    	if(s[x] == 'h' and s[x+1] == 'i');
    	else{
    		cout << "No";
    	  return;
    	}
    }
    cout << "Yes";

}


/******************************************************/
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int t;
	t = 1;
	// cin >> t;
	while(t--){
		solve();
	}

}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100

int main(){
  int i, j, tmp, num, count = 0, array[N];

  //input data number and actual data
  scanf("%d", &num);
  for (i = 0; i < num; i++)
    scanf("%d", &array[i]);

  //bubble sorting procedure
  for (i = 0; i < num; i++){
    for (j = num-1; j >=i+1; j--){//traverses sub-array
      if (array[j-1] > array[j]){//exhange procedure
	tmp = array[j];
	array[j] = array[j-1];
	array[j-1] = tmp;
	count++;
      }
    }
  }

  //display procedure
  for (i = 0; i < num; i++){
    printf("%d", array[i]);
    if (i < num -1)
      printf(" ");
  }
  
  printf("\n%d\n", count);

  return 0;
}



Measured memory_bytes: 2104
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define per(i,m) for(long long i=m-1; i>=0; i--)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define ROF(i,n,m) for(long long i=m-1; i>=n; i--)
#define SORT(v,n) do{sort(v,v+n);reverse(v,v+n);}while(0)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
typedef pair<ll, ll> LP;

ll POW(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW(x*x,n/2)%MOD;
  return x%MOD*POW(x,n-1)%MOD;
}

ll POW2(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW2(x*x,n/2);
  return x*POW2(x,n-1);
}

ll gcd(ll u, ll v) {
  ll r;
  while (0 != v) {
    r = u % v; u = v; v = r;
  }
  return u;
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll KAI2(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI2(m-1);
}

ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
 
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}
 
ll modinv(ll a) {
    ll x, y;
    extGCD(a, MOD, x, y);
    return mod(x, MOD);
}
 
ll COM(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI(m)%MOD*modinv(KAI(n)%MOD*KAI(m-n)%MOD)%MOD;
}

ll COM2(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI2(m)/KAI2(n)/KAI2(m-n);
}

ll DEC(ll x,ll m,ll n)
{
  return x%POW(m,n+1)/POW(m,n);
}

ll keta(ll x,ll n)
{
  if(x==0)return 0;
  return keta(x/n,n)+1;
}

ll DIV(ll x,ll n)
{
  if(x==0)return 0;
  return x/n+DIV(x/n,n);
}

ll ORD(ll x,ll n)
{
  if(x==0)return INF;
  if(x%n!=0)return 0;
  return 1+ORD(x/n,n);
}

int main()
{
  ll a[20],k;
  rep(i,5)cin >> a[i];
  cin >> k;
  if(a[4]-a[0]<=k)printf("Yay!");
  else printf(":(");
}

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

using ll = long long;


int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

    int n;
    cin >> n;

    int a[n];
    int min_num = (int) 1e9;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int prev_gcd = gcd(a[0], a[1]);
    for (int i = 2; i < n; ++i) {
        prev_gcd = gcd(prev_gcd, a[i]);
    }

    cout << prev_gcd << '\n';
    
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#define N 1000005
using namespace std;
typedef long long ll;

ll n, num, lcm=1, ans, M=1e9+7, a[N], cnt[N];

ll pow(ll p, ll q) {
	ll re = 1;
	for(; q; q>>=1, p=p*p%M) {
		if(q&1) re = re * p % M;
	}
	return re;
}

int main() {
	ll i, j, c;
	cin >> n;
	for(i=0; i<n; i++) {
		cin >> a[i];
		num = a[i];
		for(j=2; j*j<=num; j++) {
			if(num%j == 0) {
				c = 0;
				while(num%j == 0) c++, num /= j;
				cnt[j] = max(c, cnt[j]);
			}
		}
		if(num>1 && cnt[num]==0) cnt[num] = 1;
	}
	for(i=2; i<=1000000; i++) {
		if(cnt[i]) lcm = lcm * pow(i, cnt[i]) % M;
	}
	for(i=0; i<n; i++) {
		ans = (ans + lcm * pow(a[i], M-2)) % M;
	}
	cout << ans;
	return 0;
}

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

using lint = long long;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<vector<T>>;
template <typename T> using VVV = vector<vector<vector<T>>>;
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define repu(i, a, b, s) for(int i = int(a); i < int(b); i += int(s))
#define repd(i, a, b, s) for(int i = int(a); i > int(b); i += int(s))
#define endl "\n"
constexpr lint INF = 2e18;
constexpr lint MOD = 1e9 + 7;

struct Combination {
    const lint MAX, MOD;
    vector<lint> fac, finv, inv;

    Combination(lint n, lint mod = 1e9 + 7) : MAX(n + 1), MOD(mod), fac(MAX), finv(MAX), inv(MAX) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for(lint i = 2; i < MAX; 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;
        }
    };

    lint perm(int n, int k) {
        if(n < k)
            return 0;
        if(n < 0 or k < 0)
            return 0;
        return (fac[n] * finv[n - k]) % MOD;
    }

    lint comb(lint n, lint k) {
        if(n < k)
            return 0;
        if(n < 0 or k < 0)
            return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
};

V<lint> bfs(lint N, lint v0, VV<lint> edge) {

    V<lint> d(N, -1);
    d[v0] = 0;

    deque<lint> q;
    q.emplace_back(v0);

    while(not q.empty()) {
        lint v = q.front();
        q.pop_front();
        for(auto &&nv : edge[v]) {
            if(d[nv] == -1) {
                q.emplace_back(nv);
                d[nv] = d[v] + 1;
            }
        }
    }

    return d;
}

void solve() {
    lint N, K;
    cin >> N >> K;

    VV<lint> edge(N);
    rep(i, N - 1) {
        lint a, b;
        cin >> a >> b;
        a--;
        b--;
        edge[a].emplace_back(b);
        edge[b].emplace_back(a);
    }

    auto d = bfs(N, 0, edge);

    VV<lint> dag(N);
    rep(i, N) {
        for(auto &&j : edge[i]) {
            if(d[i] < d[j]) {
                dag[i].emplace_back(j);
            }
        }
    }

    deque<lint> q;
    q.emplace_back(0);

    lint ans = K;
    auto comb = Combination(1e5);

    while(not q.empty()) {
        lint v = q.front();
        q.pop_front();

        if(d[v] == 0) {
            ans *= comb.perm(K - 1, dag[v].size());
            ans %= MOD;
        } else {
            ans *= comb.perm(K - 2, dag[v].size());
            ans %= MOD;
        }

        for(auto &&nv : dag[v]) {
            q.emplace_back(nv);
        }
    }

    cout << ans << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    solve();
}

Measured memory_bytes: 18256
#include <iostream>

using namespace std;

int main(void){
  int N;
  cin >> N;
  int P[N];
  for(int i=0;i<N;i++)
    cin >> P[i];
  int j,min=10000000,count=0;
  for(j=0;j<N;j++){
    if(P[j]<min)
      min=P[j];
    if(min==P[j])
      count++;
  }
  cout<< count<<endl;




  return 0;
}


Measured memory_bytes: 1024
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
h,w=map(int,input().split())
s=[input() for _ in range(h)]
l=[[0]*w for _ in range(h)]
r=[[0]*w for _ in range(h)]
u=[[0]*w for _ in range(h)]
d=[[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            l[i][j]=r[i][j]=u[i][j]=d[i][j]=0
        else: 
            l[i][j]=l[i][j-1]+1 if j!=0 else 1
            u[i][j]=u[i-1][j]+1 if i!=0 else 1
        if s[h-1-i][w-1-j]=="#":
            r[i][j]=d[i][j]=0
        else:
            r[i][j]=r[i][j-1]+1 if j!=0 else 1
            d[i][j]=d[i-1][j]+1 if i!=0 else 1
ans=0
for i in range(h):
    for j in range(w):
        res=l[i][j]+u[i][j]+r[h-1-i][w-1-j]+d[h-1-i][w-1-j]-3
        #print("##",i,j,"##",res)
        ans=max(res,ans)
print(ans)

Measured memory_bytes: 205148
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

int main(){
    int n,m; cin>>n;
    vector<int> a(n+1),b(n);
    for(int i=0;i<n+1;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];

    ll ans=0;
    for(int i=0;i<n+1;i++){
        if(i){
            m=min(a[i],b[i-1]);
            ans+=m;
            b[i-1]-=m;
            a[i]-=m;
        }
        m=min(a[i],b[i]);
        ans+=m;
        b[i]-=m;
        a[i]-=m;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <cstring>
#include<vector>
#include<climits>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<functional>
#include <numeric>
#include <map>
#include <tuple>
#include <string>
#define FORi(N) for(int i=0;i<N;++i)
#define FORj(N) for(int j=0;j<N;++j)
#define FORk(N) for(int k=0;k<N;++k)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll gcd(ll m,ll n){
  if(n==0)return abs(m);
  return(gcd(n,m%n));
}
void putYN(bool b){
  if(b){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}
void swap(ll &a,ll &b){
  ll tmp=a;
  a=b;
  b=tmp;
}
int main(){
  ll N,K;
  cin>>N>>K;
  vector<ll> V(N),Vs(N);
  FORi(N){
    cin>>V[i];
  }
  /*Vs[0]=V[0];
  FORi(N-1){
    Vs[i+1]=Vs[i]+V[i+1];
  }*/
  ll max_=0;
  FORi(N+1){//左から 0-50こ
    FORj(N-i+1){//右から 0-50こ
      if(i+j>K)break;
      //if(i+j>N)break;
      vector<ll> mi;
      ll sum=0;
      FORk(i){
        sum+=V[k];
        //cout<<V[k]<<endl;
        if(V[k]<0)mi.push_back(V[k]);
      }
      FORk(j){
        sum+=V[N-1-k];
        //cout<<V[N-1-k]<<endl;
        if(V[N-1-k]<0)mi.push_back(V[N-1-k]);
      }
      sort(mi.begin(),mi.end());
      FORk(min((ll)(K-i-j),(ll)mi.size())){
        sum-=mi[k];
      }
      //cout<<sum<<endl<<endl;
      if(max_<sum)max_=sum;
    }
    if(i>K)break;
  }
  cout<<max_<<endl;
  return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
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;
}
 
using namespace std;
//ここから

void solve(){
  int n;
  cin>>n;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  for(int i=n-1;i>=0;i-=2){
    if(i!=n-1)cout<<" ";
    cout<<a[i];
  }
  for(int i=n%2;i<n;i+=2){
    cout<<" ";
    cout<<a[i];
  }
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


Measured memory_bytes: 2944
import sys
from heapq import heappop, heappush

input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

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

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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

// >= 91
ll A, M;
ll getPhi(ll m) {
	ll res = 1;
	for(int i=2; i*i<=m; i++) {
		if(m%i == 0) {
			m /= i; res *= i-1;
			while(m%i == 0) m /= i, res *= i;
		}
	}
	if(m != 1) res *= m-1;
	return res;
}
ll getMul(ll a, ll b, ll m) {
	ll r = 0, p = a;
	while(b) {
		if(b%2) r = (r + p) % m;
		p = (p + p) % m;
		b >>= 1;
	}
	return r;
}
ll getPow(ll a, ll b, ll m) {
	ll r = 1, p = a;
	while(b) {
		if(b%2) r = getMul(r, p, m);
		p = getMul(p, p, m);
		b >>= 1;
	}
	return r;
}
ll ee(ll a, ll b, ll &s, ll &t) {
	if(b == 0) {
		s = 1; t = 0;
		return a;
	}
	ll ss, tt, g = ee(b, a%b, ss, tt);
	ll q = a / b;
	s = tt;
	t = ss - q * tt;
	return g;
}
ll toPlus(ll a, ll m) {
	a %= m; if(a < 0) a += m;
	return a;
}
ll getCRT(ll a, ll c, ll b, ll d) {
	//printf("%lld %lld %lld %lld\n", a, c, b, d);
	ll s, t;
	ll g = ee(c, d, s, t);
	s = toPlus(s, d), t = toPlus(t, c);
	if(g > 1) {
		if(a%g != b%g) return -1;
		return getCRT(a/g, c/g, b/g, d/g) * g + a%g;
	}
	ll av = getMul(getMul(a, d, c*d), t, c*d);
	ll bv = getMul(getMul(b, c, c*d), s, c*d);
	ll k = (av + bv) % (c*d);
	if(k == 0) k = c*d;
	return k;
}
ll getAns(ll a, ll m) {
	ll pm = getPhi(m);
	if(m < 91) {
		for(int i=1; i<=pm*m; i++) if(getPow(a, i, m) == (i % m)) return i;
		return -1;
	}
	ll c, d;
	ll g = ee(pm, m, c, d);
	ll y = getAns(a, g);
	if(y == -1) return -1;
	ll Ay = getPow(a, y, m);
	ll yg = y / g, Ayg = Ay / g;

	//printf("%lld %lld - > %lld [%lld %lld]\n", a, g, y, c, d);
	ll x = getCRT(getPow(a, y, m), m, y, pm);
	if(x == -1) return -1;
	//printf("[%lld %lld] (%lld) %lld %lld\n", a, m, x, getPow(a, x, m), x % m);
	return x;
}
int main() {
	int T; cin >> T;
	for(int tc=1; tc<=T; tc++) {
		scanf("%lld%lld", &A, &M);
		//printf("%lld\n", getAns(A, M));
		ll v = getAns(A, M);
		printf("%lld\n", v);
		//if(v > 0) printf("%lld %lld\n", getPow(A, v, M), v % M);
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        String[] lines = getStdin();
        String str = lines[0];
        int num = Integer.parseInt(str);
        int h;
        int hamari;
        int num1;
        int m;
        int mamari;
        int num2;
        int s;

        h = num / 3600;
        hamari = h * 3600;
        num1 = num - hamari;
        m = num1 / 60;
        mamari = m * 60;
        num2 = num1 - mamari;
        s = num2;

        System.out.println(h + ":" + m + ":" + s);


    }
  private static String[] getStdin() {
    Scanner scanner = new Scanner(System.in);
    ArrayList<String> lines = new ArrayList<>();
    while (scanner.hasNext()) {
      lines.add(scanner.nextLine());
    }
    return lines.toArray(new String[lines.size()]);
  }
  
}



Measured memory_bytes: 26160
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;

int main()
{
	ll n;
	cin>>n;string s="";
	while(n){
		ll temp=n%26;
		if(temp==0){
			s+="z";n/=26;n--;
		}
		else{
			s+=('a'+temp-1);n/=26;
		}
	}
	reverse(s.begin(),s.end());
	cout<<s;
	return 0;	
}

Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  int c=0;
  for(int i=0;i<n-1;i++){
    c+=a[i];
  }
  cout<<c+a[n-1]/2;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	sc.Split(bufio.ScanWords)
	defer out.Flush() // !!!!coution!!!! you must use Fprint(out, ) not Print()
	/* --- code ---*/

	n := nextInt()
	dist, px, py := 0, 0, 0
	flag := true
	for i := 0; i < n; i++ {
		if flag == true {
			t, x, y := nextInt(), nextInt(), nextInt()
			dist = (int(math.Abs(float64(x-px))) + int(math.Abs(float64(y-py))))
			if t < dist {
				flag = false
			}
			if t%2 != dist%2 {
				flag = false
			}
		}
	}
	if flag == true {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

// Genericsがないので筋肉で...
// interfaceでの取扱がようわからんし
func containStr(arr []string, target string) bool {
	for _, v := range arr {
		if v == target {
			return true
		}
	}
	return false
}

func PrintOut(src interface{}, joinner string) {
	switch reflect.TypeOf(src).Kind() {
	case reflect.Slice:
		s := reflect.ValueOf(src)
		for idx := 0; idx < s.Len(); idx++ {
			fmt.Fprintf(out, "%v", s.Index(idx))
			if idx < s.Len()-1 {
				fmt.Fprintf(out, "%s", joinner)
			} else {
				fmt.Fprintln(out)
			}
		}
	default:
		fmt.Fprintln(out, "fuck")
	}
}

// mapからkeysとvaluesを返す感じのやつ
// なんかしらんけどmap[interface{}]interface{}しか受け付けない。なんのためのinterface{}やねん
// なので呼ぶときのmapはmap[int]stringとかじゃダメ
func splitKeyValue(m map[interface{}]interface{}) (keys, values []interface{}) {
	switch reflect.TypeOf(m).Kind() {
	case reflect.Map:
		s := reflect.ValueOf(m)
		for _, v := range s.MapKeys() {
			keys = append(keys, v)
			values = append(values, s.MapIndex(v))
		}
	default:
		fmt.Fprintln(out, "fuck")
	}
	return
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
using namespace std;
int n,m,i,j,l,r,mid,ans,a[200005],b[200005];
bool check(int x)
{
	int i,j;
	fz1(i,n+n-1){
		b[i]=(a[i]>=x);
	}
	i=j=n;
	while(j<n+n){
		i--;j++;
		if(b[i]==b[i+1]) return b[i];
		if(b[j]==b[j-1]) return b[j];
	}
	return b[n]^((n-1)&1);
}
int main()
{
	scanf("%d",&n);
	fz1(i,n+n-1){
		scanf("%d",&a[i]);
	}
	l=1;r=n+n;
	while(l<r){
		mid=(l+r)/2;
		if(check(mid)){
			l=mid+1;
			ans=mid;
		}
		else r=mid;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;
typedef pair<int,int> p;

const int INF = 1e9;

int main() {
    int n; cin >> n; cout << n * n << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] A = new int[N];
    int[] B = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
      B[i] = sc.nextInt();
    }
    long ans = 0;
    for (int i = N-1; i >= 0; i--) {
      long diff = (long)(A[i]+ans)%B[i];
      if (diff > 0) {
        ans += B[i]-diff;
      }
    }
    System.out.println(ans);
  }
}

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

int main() {
  int n;
  int a[110];
  cin >> n;
  for(int i=0;i<n;i++) cin >> a[i];
  
  sort(a, a+n, greater<int>());
  
  int alice=0;
  int bob=0;

  for(int i=0;i<n;i++) {
    if(i%2==0) {
      alice+=a[i]; 
    } else {
      bob+=a[i];
    }
  }
  cout << alice-bob << endl;
  return 0;
}


Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE Unsafe #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE FlexibleContexts #-}

import Data.Bits
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy.Char8 as BSL
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IMS
import Data.IntSet (IntSet)
import qualified Data.IntSet as IS
import qualified Data.Sequence as Seq
import Data.Sequence (Seq)
import qualified Data.Array.IArray as A
import qualified Data.Array.MArray.Safe as A
import qualified Data.Array.MArray as A
import Data.Array (Array)
import Data.Array.Unboxed (UArray)
import Data.Array.IArray (IArray)
import Data.Array.MArray.Safe (MArray)
import Data.Array.IO.Safe (IOArray, IOUArray)
import Data.Array.ST.Safe (STArray, STUArray, runSTArray, runSTUArray)
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
import Control.Monad.ST
-- import Control.Monad.ST.Safe
import Control.Applicative
import Data.Maybe
import Data.Tuple
import Data.Ord
import Control.Monad.State.Strict
import Data.Int
import System.IO
import Data.Function
import Control.Monad.Primitive
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Generic.Mutable as VGM
import Data.STRef

main :: IO ()
main = do
  [l,n] <- map read . words <$> getLine :: IO [Int]
  xs <- VU.unfoldrN n (BSL.readInt . BSL.dropWhile (<'!')) <$> BSL.getContents
  print $ query l n xs

query :: Int -> Int -> VU.Vector Int -> Int
query l n xs = maximum $ map cost [0..n]
  where
    cost :: Int -> Int
    cost 0 = l - xs VU.! 0
    cost right | right == n = xs VU.! (n-1)
    cost right = case compare left right of
      EQ -> max
        (l * n + 2 * sumintv 0 right - 2 * sumintv right n - xs VU.! (right-1))
        (l * (n-1) + 2 * sumintv 0 right - 2 * sumintv right n
         + xs VU.! right)
      LT -> max
        (l * (n-rightmore-1)
          + 2 * sumintv rightmore right - 2 * sumintv right n
          - xs VU.! (right-1))
        (l * (n-rightmore-2)
          + 2 * sumintv (rightmore+1) right - 2 * sumintv right n
          + xs VU.! right)
      GT -> max
        (l * (n-leftmore)
          + 2 * sumintv 0 right - 2 * sumintv right (right*2+1)
          + xs VU.! right)
        (l * (n-leftmore-1)
          + 2 * sumintv 0 right
          - 2 *  sumintv right (right*2)
          - xs VU.! (right-1))
      where
        left = n-right
        leftmore = left - right - 1
        rightmore = right - left - 1
    sumsxs = VU.scanl' (+) 0 xs
    -- sum of [i,j)
    sumintv i j = sumsxs VU.! j - sumsxs VU.! i


Measured memory_bytes: 7036
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;

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

    int Q; cin >> Q;
    priority_queue<int> que1;
    priority_queue<int, vector<int>, greater<int>> que2;
    int q, a, b; cin >> q >> a >> b;
    que1.push(a);
    ll ans = b;
    for (int i = 1; i < Q; i++) {
        cin >> q;
        if (q == 1) {
            cin >> a >> b;
            if (que1.size() == que2.size()) {
                int l = que1.top(); que1.pop();
                int r = que2.top(); que2.pop();
                if (a <= l) {
                    que1.push(a);
                    que1.push(l);
                    que2.push(r);
                    ans += l - a;
                }
                else if (a >= r) {
                    que1.push(l);
                    que1.push(r);
                    que2.push(a);
                    ans += a - r;
                }
                else {
                    que1.push(l);
                    que1.push(a);
                    que2.push(r);
                }
            }
            else {
                int c = que1.top(); que1.pop();
                if (a <= c) {
                    que1.push(a);
                    que2.push(c);
                    ans += c - a;
                }
                else {
                    que1.push(c);
                    que2.push(a);
                    ans += a - c;
                }
            }
            ans += b;
        }
        else
            cout << que1.top() << " " << ans << "\n";
    }
}

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

int main(){

    int a, b, c, x; cin >> a >> b >> c >> x;

    int ans = 0;
    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) ans++;
            }
        }
    }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1020000000

int solve(int w, int h){
  vector<string> vec(h);
  rep(i,h) cin>>vec[i];

  int n = w*h;
  vector<vector<int>> d(n,vector<int>(n, INF));
  rep(i,n) d[i][i] = 0;
  rep(i,h)rep(j,w) if(vec[i][j]!='x'){
    if(j+1<w && vec[i][j+1]!='x') d[i*w+j][i*w+j+1] = d[i*w+j+1][i*w+j] = 1;
    if(i+1<h && vec[i+1][j]!='x') d[i*w+j][(i+1)*w+j] = d[(i+1)*w+j][i*w+j] = 1;
  }

  rep(k,n)rep(i,n)rep(j,n) d[i][j] = min(d[i][k]+d[k][j], d[i][j]);

  int m = 0;
  vector<int> pos;
  rep(i,h)rep(j,w) if(vec[i][j] == '*'){pos.pb(i*w+j); m++;}

  int s;
  rep(i,h)rep(j,w) if(vec[i][j] == 'o') s = i*w+j;

  vector<vector<int>> dp(1<<m, vector<int>(m, INF));
  rep(i,m) dp[1<<i][i] = d[s][pos[i]];
  rep(mask,1<<m) rep(i,m) if(dp[mask][i]<INF){
    rep(j,m) if( !(mask & (1<<j) ) ){
      dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + d[pos[i]][pos[j]]);
    }
  }

  int ans = *min_element(all(dp[(1<<m)-1]));
  if(ans == INF) return -1;
  return ans;
}

int main(){
  int w,h;
  while(cin>>w>>h, w|h){
    cout << solve(w,h) << endl;
  }

  return 0;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	priority_queue<int,vector<int>,greater<int>>q;
	int ans=0;
	for(int i=0;i<n;++i){
		int s; cin>>s;
		ans+=s;
		q.push(s);
	}
	if(ans%10==0){
		while(ans%10==0&&q.size()){
			int m=q.top(); q.pop();
			if(m%10)ans-=m;
		}
	}
	cout<<(ans%10?ans:0)<<"\n"s;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,q=0,w;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			w=__gcd(i,j);
			for(int k=1;k<=n;k++)
			{
				q+=__gcd(w,k);
			}
		}
	}
	cout<<q;
}

Measured memory_bytes: 3624
#include<stdio.h>

int main(void){
    int H,W,i,j;
    while ( scanf("%d %d", &H, &W) ){
        if ( H == 0 && W == 0 ) break;
        for ( i = 0 ; i < H ; i++ ){
            for ( j = 0 ; j < W ; j++ ){
                if ( (i % 2) == (j % 2) ) {
                    printf("#");
                } else {
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}


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

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

	ll ans = 0;
	while (x > 0 && y > 0) {
		if (a + b >= c * 2) ans += c * 2;
		else ans += a + b;
		x--; y--;
	}
	rep(i, 0, x) ans += min(a, c * 2);
	rep(i, 0, y) ans += min(b, c * 2);

	cout << ans << endl;

	return 0;
}

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

for h in range(1,3501):
  for n in range(1,3501):
    if 4*h*n-n*N-h*N <= 0:
      continue
    if N*h*n % (4*h*n-n*N-h*N) == 0:
      w = N*h*n // (4*h*n-n*N-h*N)
      print("{} {} {}".format(h,n,w))
      exit()

Measured memory_bytes: 66828