akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE BangPatterns #-}

module Main
  ( main
  )
where

import           Control.Applicative
import           Control.Monad
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as MV
import           Control.Monad.ST
import           Data.Ord

parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine
readIntegerList = map parseInteger . BS.words <$> BS.getLine

main = do
  n <- readInt
  arr <- readIntList
  let s = sum arr
      lb = s `div` n
      ub = lb + 1
      scoreLb = foldl' (\acc val -> acc + (val - lb) ^ 2) 0 arr
      scoreUb = foldl' (\acc val -> acc + (val - ub) ^ 2) 0 arr
  print $ min scoreLb scoreUb


Measured memory_bytes: 508
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long ll;

ll p[111111], x[111111];

int main(void)
{
	ll n, m, i, a, b, c, ans = 0;

	scanf("%lld %lld" ,&n, &m);
	for (i = 1; i <= m; i++)
	{
		scanf("%lld" ,&p[i]);

		if (i == 1)
			continue;

		x[min(p[i - 1], p[i])]++;
		x[max(p[i - 1], p[i])]--;
	}

	for (i = 1; i < n; i++)
		x[i] += x[i - 1];

	for (i = 1; i < n; i++)
	{
		scanf("%lld %lld %lld" ,&a, &b, &c);

		ll ticket = x[i] * a;
		ll IC_card = c + b * x[i];

		ans += min(ticket, IC_card);
	}

	printf("%lld\n" ,ans);
	return 0;
}


Measured memory_bytes: 4264
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    vi v(5);
    rep(i,5)cin>>v[i];
    SORT(v);
    int ans=inf;
    do{
        int t=0;
        rep(i,5){
            if(t%10!=0)t=(t/10+1)*10;
            t+=v[i];
        }
        ans=min(ans,t);
    }while(next_permutation(all(v)));
    cout<<ans<<endl;
}

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

namespace atcoder
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            string indata1,indata2;
            string[] arraydata1, arraydata2;
            int result=0;
            indata1 = Console.ReadLine();
            indata2 = Console.ReadLine();
            arraydata1 = indata1.Split(' ');
            arraydata2 = indata2.Split(' ');
            List<int> sortdata = new List<int>();
            foreach (var dt in arraydata2)
            {
                sortdata.Add(int.Parse(dt));
            }
            sortdata.Sort();
            for(int i = 0; i < int.Parse(arraydata1[1]); i++)
            {
                result += sortdata[i];
            }
            Console.WriteLine(result);
        }
    }
}

Measured memory_bytes: 28072
#include<bits/stdc++.h>
#define L long long
using namespace std;
int n,m,f[310][310][310];
char s[310];
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k,l;
	scanf("%s%d",s+1,&m);
	n=strlen(s+1);
	for(i=1;i<=n;i++)
	  for(j=0;j<=m;j++)
	    f[i][i][j]=1;
	for(l=1;l<n;l++)
	  for(i=1;i+l<=n;i++)
	    for(k=0;k<=m;k++)
	      {
           j=i+l;
           f[i][j][k]=max(max(f[i+1][j][k],f[i][j-1][k]),(s[i]==s[j]?f[i+1][j-1][k]:(k?f[i+1][j-1][k-1]:-1000000000))+2);
          }
    printf("%d\n",f[1][n][m]);
	return 0;
}


Measured memory_bytes: 114560
import sys
sys.setrecursionlimit(200000)

def dp_func(n,dp,h):
    if n==0:
        return 0
    elif n==1:
        return dp[1]
    
    else:
        if dp[n-1]==-1:
            dp[n-1]=dp_func(n-1,dp,h)

        c1=dp[n-1]+abs(h[n]-h[n-1])

        if dp[n-2]==-1:
            dp[n-2]=dp_func(n-2,dp,h)
            
        c2=dp[n-2]+abs(h[n]-h[n-2])
        
        dp[n]=min(c1,c2)
        return dp[n]

def main():
    #input
    N=int(input())
    h=list(map(int,input().strip().split()))
    # N=10000
    # h=[n**2 for n in range(N)]

    dp=[-1 for n in range(N)]
    dp[0]=0
    dp[1]=abs(h[1]-h[0])

    return dp_func(N-1,dp,h)

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

Measured memory_bytes: 100728
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long A = sc.nextLong();
        long B = sc.nextLong();
      	//System.out.println(N);
      	//System.out.println(A);
        //System.out.println(B);
        long a = N/(A+B);
        long b = N%(A+B);
        //System.out.println(a +""+ b);
        if(b > A){
            System.out.print(A*a+A);
        }else{
            System.out.print(A*a+b);
        }
    }
}

Measured memory_bytes: 23252
#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <limits.h>
#include <utility>

using namespace std;

#define fs first
#define sc second

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

template<class T>
vector<int> argsort(vector<T> v, vector<T> w){
    vector<int> index(v.size());
    iota(index.begin(), index.end(), 0);

    sort(index.begin(), index.end(),
            [&v, &w](const size_t &a, const size_t &b){
        if(v[a] == v[b]){
            return w[a] < w[b];
        }
        else{
            return v[a] < v[b];
        }
    });

    return index;
}

vector<ll> w(1100), s(1100), v(1100);
ll dp[1100][21000];

int main(){
    int N;
    cin >> N;
    vector<ll> su;
    for(int i = 0; i < N; i++){
        cin >> w[i] >> s[i] >> v[i];
        su.push_back(w[i] + s[i]);
    }

    vector<int> index = argsort<ll>(su, w);

    for(int i = 0; i < 1100; i++){
        for(int j = 0; j < 21000; j++){
            dp[i][j] = 0;
        }
    }

    dp[0][w[index[0]]] = v[index[0]];
    for(int i = 1; i < N; i++){
        ll ww = w[index[i]];
        ll vv = v[index[i]];
        ll ss = s[index[i]];

        for(int j = 0; j < 21000; j++){
            if(ss >= j && j + ww < 21000){
                dp[i][j+ww] = max(dp[i][j+ww], dp[i-1][j] + vv);
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }

    ll res = 0;
    for(int j = 0; j < 21000; j++){
        res = max(res, dp[N-1][j]);
    }
    cout << res << endl;


    return 0;
}

Measured memory_bytes: 180736
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<char> arr(n);
    for(int i=0;i<n;i++)
        cin >> arr[i];
    
    int ans =0;
    int i=0,j=n-1;
    while(i<=j){
        if(arr[i]=='W'&&arr[j]=='R'){
            ans++;
            i++;
            j--;
        }else if(arr[i]=='R' &&arr[j]=='W'){
            i++;
            j--;
        }else if(arr[i]=='W'&&arr[j]=='W'){
            j--;
        }else if(arr[i]=='R' && arr[j]=='R')i++;
    }
    cout << ans << "\n";
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	ll n;cin>>n;
	vl a(3*n);
	rep(i,3*n){
		cin>>a[i];
	}
	sort(all(a));
	ll ans=0;
	for(int i=3*n-2;i>n-1;i-=2){
		ans+=a[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 2560
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String n = sc.next();
		if (n.equals("RRR")) {
			System.out.println(3);
		} else if (n.contentEquals("SRR") || n.contentEquals("RRS")) {
			System.out.println(2);
		} else if (n.equals("SSS")) {
			System.out.println(0);
		} else {
			System.out.println(1);
		}
	}
}


Measured memory_bytes: 35640
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//(a+b-1)/b

signed main(){
	int a,b,c,d; cin>>a>>b>>c>>d;
	cout<<min(a,b)+min(c,d)<<endl;
}

Measured memory_bytes: 3580
n,m = gets.split.map!(&:to_i)

stu = []
n.times {stu << gets.split.map!(&:to_i)}

poi = []
m.times {poi << gets.split.map!(&:to_i)}

stu.each do |a,b|
    min = -1
    ans = 0

    poi.each_with_index do |l,i|
        c,d = l
        x = (a - c).abs + (b - d).abs

        if min == -1 || x < min
            min = x
            ans = i + 1
        end
    end

    puts ans
end

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

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

    if ( A > B )
    {
        a = A + A - 1;
        cout << a << endl;
    }
    if ( A < B )
    {
        a = B + B - 1;
        cout << a << endl;
    }
    if ( A == B )
    {
        a = B + B;
        cout << a << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long double A,B,V,W,T;
  double X;
  cin>>A>>V>>B>>W>>T;
  if(W<V){
    X=abs(A-B)/(V-W);
    if(X<=T){
      cout<<"YES"<<endl;
    }
    else{
    cout<<"NO"<<endl;
    }
  }
  else{
    cout<<"NO"<<endl;
  }
}


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

int main(void) {
    int N;
    cin >> N;
    vector<long long> A(N);
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum += A[i];
    }

    long long ans = __LONG_LONG_MAX__;
    long long left_sum = 0;
    for (int i = 0; i < N - 1; i++) {
        left_sum += A[i];
        long long l = left_sum;
        long long r = sum - l;
        ans = min(abs(l - r), ans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4828
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] sa = br.readLine().split(" ");
		int[] x = new int[n];
		int[] x2 = new int[n];
		for (int i = 0; i < n; i++) {
			x[i] = Integer.parseInt(sa[i]);
			x2[i] = x[i];
		}
		br.close();

		Arrays.sort(x2);
		int b1 = x2[n / 2 - 1];
		int b2 = x2[n / 2];
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < n; i++) {
			if (x[i] <= b1) {
				pw.println(b2);
			} else {
				pw.println(b1);
			}
		}
		pw.flush();
	}
}


Measured memory_bytes: 51864
#include <iostream>

using namespace std;

int main()
{
    int n,res,a[100],temp_max_height;
    res = 1;
    cin >> n;
    for (int i = 0 ; i < n ; i ++) cin >> a[i];
    temp_max_height = a[0];
    for (int i = 1 ; i < n ; i ++)
    {
        if (a[i] >= temp_max_height)
        {
            temp_max_height = a[i];
            res++;
        }
    }
    cout << res;

}


Measured memory_bytes: 256
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<map>
#include<deque>
#include<cstdio>
#include<cstdio>
#include<time.h>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define pd(a,n) for(int i=0;i<n;i++)cout<<a[i]<<((i==n-1)?"\n":" ")
#define pdd(a,n,m)for(int i=0;i<m;i++)pd(a,m)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>

int n,k;
int h[111111];
int dp[111111];
const int INF=1111111111;

int main(){
  cin>>n>>k;
  rep(i,n)cin>>h[i];
  rep(i,n)dp[i]=INF;
  dp[0]=0;
  rep(i,n){
    for(int j=1;j<=k;j++)
      dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]));
  }
  cout<<dp[n-1]<<endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a, b,c;
  cin >> a >> b;
  c = a + b;
  
 if ((a + b) % 2 == 0) {
    // ====== 普通に切り捨ての割り算を行う
    cout << (a + b) / 2 << endl;
  } else {
    // ====== あまりがあるなら、繰上げ分として１足す
    cout << (a + b) / 2 + 1 << endl;
  }
}

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

#define FOR(i,a,b)  for(ll i=a;(i)<(b);++(i))
#define RFOR(i,a,b) for(ll i=a;(i)>=(b);--(i))
#define REP(i,n)    FOR(i,0,n)
#define RREP(i,n)   RFOR(i,n,0)
#define ALL(v)      v.begin(), v.end()
#define UNIQ(v)     sort(ALL(v)); v.erase(unique(ALL(v)), v.end())
#define BIT(n)      (1LL<<(n))
#define DEBUG(a)    cerr << #a << " = " << a << endl

const int inf = 1001001001;
const int mod = (int)1e9+7;
//const ll inf = 1e15;
//const ll mod = 1e9+7;

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

const double PI = acos(-1);

int main() {
    string S;
    cin >> S;
    if (S[0] == S[1] && S[1] == S[2]) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S, T;
  cin >> S >> T;
  ll A, B;
  cin >> A >> B;
  string U;
  cin >> U;
  if (U==S){
    cout << A-1 << " " << B << "\n";
  } else {
    cout << A << " " << B-1 << "\n";
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n;
string s;
vector<int> z;


vector< int > z_algorithm(const string &s) {
  vector< int > prefix(s.size());
  for(int i = 1, j = 0; i < s.size(); i++) {
    if(i + prefix[i - j] < j + prefix[j]) {
      prefix[i] = prefix[i - j];
    } else {
      int k = max(0, j + prefix[j] - i);
      while(i + k < s.size() && s[k] == s[i + k]) ++k;
      prefix[i] = k;
      j = i;
    }
  }
  prefix[0] = (int) s.size();
  return prefix;
}

void solve(){
    cin >> n;
    cin >> s;
    int ans=0;
    rep(i,n){
        z=z_algorithm(s.substr(i,n-i));
        rep(j,n-i){
            //cout << s.substr(i,n-i) << " " << j << " " << z[j] << endl;
            if (z[j]<=j) ans=max(ans,z[j]);
        }
    }

    cout << ans << endl;
}

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

Measured memory_bytes: 384
#include <bits/stdc++.h>
     
    using namespace std;
     
    int main() {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      bool ab = abs(a - b) <= d;
      bool bc = abs(b - c) <= d;
      bool ca = abs(c - a) <= d;
      cout << ((ab && bc) || ca ? "Yes" : "No") << endl;
    }

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
  string X;
  cin >> X;

  stack<int> fidx, sidx;
  int ans = 0;
  for (int i = 0; i < X.size(); i++) {
    if (i != 0 && X[i] == 'T') {
      //cout << sidx.top() << ' ' << fidx.top() << endl;
      if (!sidx.empty() && sidx.top() == fidx.top()) {
        ans++;
        sidx.pop();
        fidx.pop();
      } else {
        fidx.push(i);
      }
    } else {
      if (X[i] == 'S') sidx.push(i);
      fidx.push(i);
    }
  }
  cout << (X.size() - 2*ans) << endl;

  return 0;
}


Measured memory_bytes: 1668
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let mut x = vec![];
    for i in 0..n {
        let a: usize = sc.read();
        x.push((a, i));
    }
    x.sort();

    let mut ans = vec![None; n * n];
    let mut hole_head = 0;
    let mut cur_sum = 0;
    for &(x, i) in x.iter() {
        let lower_count = i + 1;
        if cur_sum + lower_count > x {
            println!("No");
            return;
        }
        cur_sum += lower_count;
        ans[x - 1] = Some(i + 1);
        for _ in 1..lower_count {
            while ans[hole_head].is_some() {
                hole_head += 1;
                if hole_head >= n * n {
                    println!("No");
                    return;
                }
            }
            ans[hole_head] = Some(i + 1);
            hole_head += 1;
        }
    }

    let mut hole_tail = n * n - 1;
    let mut cur_sum = 0;
    for &(x, i) in x.iter().rev() {
        let upper_count = n - (i + 1);
        if cur_sum + upper_count > n * n - x {
            println!("No");
            return;
        }
        cur_sum += upper_count;
        for _ in 0..upper_count {
            while ans[hole_tail].is_some() {
                if hole_tail == 0 {
                    println!("No");
                    return;
                }
                hole_tail -= 1;
            }
            if hole_tail <= x - 1 {
                println!("No");
                return;
            }
            ans[hole_tail] = Some(i + 1);
        }
    }

    println!("Yes");
    for ans in ans.into_iter() {
        print!("{} ", ans.unwrap());
    }
    println!();
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 9340
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;

int n;
long long C;
int a[N];

struct ban
{
    long long b, k;
    ban(){}
    ban(long long b, long long k)
    {
        this->b = b;
        this->k = k;
    }
    long long yat(long long x)
    {
        return b + k * x;
    }
};
long double hat(const ban& a, const ban& b)
{
    return (long double) (b.b - a.b) / (a.k - b.k);
}

vector<ban> v;
vector<long double> h;
void ave(ban t)
{
    while (v.size() >= 2 && hat(t, v[v.size() - 2]) <= h.back())
    {
        v.pop_back();
        h.pop_back();
    }
    if (v.empty())
    {
        v.push_back(t);
        return;
    }
    h.push_back(hat(v.back(), t));
    v.push_back(t);
}

long long byn(long long x)
{
    int l = 0, r = h.size() - 1;
    int ans = -1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (h[m] <= x)
        {
            ans = m;
            l = m + 1;
        }
        else
        {
            r = m - 1;
        }
    }
    ++ans;
    return v[ans].yat(x);
}

long long dp[N];

int main()
{
    scanf("%d%lld", &n, &C);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (i > 1)
        {
            dp[i] = byn(a[i]) + a[i] * 1LL * a[i] + C;
        }
        ave(ban(dp[i] + a[i] * 1LL * a[i], -2 * a[i]));
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 12512
# -*- coding: utf-8 -*-


N = int(input())
As = list(map(int, input().split()))

sum1 = 0
sum2 = sum(As)

min_diff = float('inf')

for a in As[0:len(As)-1]:
    sum1 += a
    sum2 -= a
    #print(abs(sum1 - sum2))
    min_diff = min(min_diff, abs(sum1 - sum2))
print(min_diff)

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

using namespace std;

typedef long long ll;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	ll MOD = 998244353;

	ll n, s;
	cin >> n >> s;

	vector<ll> a(n);
	rep(i, n) cin >> a[i];

	vector<vector<ll>> dp(n+1, vector<ll>(s+1, 0));

	ll ans = 0;
	rep(i, n){
		rep(j, s+1){
			if(j < s) dp[i+1][j] = dp[i][j];
			if(j - a[i] == 0){
				dp[i+1][j] += i+1;
				dp[i+1][j] %= MOD;
			}else if(j - a[i] > 0){
				dp[i+1][j] += dp[i][j - a[i]];
				dp[i+1][j] %= MOD;
			}
		}

		ans += dp[i+1][s] * (n - i) % MOD;
		ans %= MOD;
	}

	cout << ans << endl;
}


Measured memory_bytes: 73604
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    string str;
    cin >> str;
    
    vector<int> calc(N, 0);
    for(int i=1; i<N; i++) {
        if(str[i-1]=='A' && str[i]=='C') calc[i]++;calc[i] += calc[i-1];
    }
    
    for(int i=0; i<Q; i++) {
        int l, r;
        cin >> l >> r;
        cout << calc[r-1] - calc[l-1] << endl;
    }

    return 0;
    
}

Measured memory_bytes: 1408
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int main() {
  int r, g, b, n;
  scan(r, g, b, n);
  int ans = 0;
  rep (i, 3001) {
    int nr = r * i;
    if (nr > n) {
      break;
    }
    rep (j, 3001) {
      int nrg = nr + g * j;
      if (nrg > n) {
        break;
      }
      int k = (n - nrg) / b;
      if (nrg + b * k == n) {
        ans += 1;
      }
    }
  }
  print(ans);
  return 0;
}


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


int main()
{
	//freopen("in.txt", "rt", stdin);
	long long x,y;
  	scanf("%lld %lld",&x,&y);
  	if(x%y==0) puts("-1");
  	else{
      long long v=__gcd(x,y);
      printf("%lld",x*((y/v)+1));
    }
	return 0;
}


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

using namespace std;

int main() {
    string x;
    cin >> x;
    bool flag = true;
    for(int i=0; i<x.length(); i++) {
        int count = 0;
        for(int j=0; j<x.length(); j++) {
            if(i==j) {
                continue;
            } else {
                if(x[i] == x[j]) {
                    count++;
                }
            }
        }
        if(count != 1) {
            flag = false;
            break;
        }
    }
    if(flag) {
        cout << "Yes" << endl;
    } else { 
        cout << "No" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#define REP(i, n) for(long long i = 0; i < n; i++)
#define SHOWVEC(v, n) for(int _i = 0; _i < n; _i++) cerr << v[_i] << ' '; cerr << endl;

using namespace std;
typedef long long ll;

int main()
{
  ll N, M;
  cin >> N >> M;
  vector<vector<ll>> v(110000);
  REP(i, N) {
    ll A, B;
    cin >> A >> B;
    v[A].push_back(B);
  }
  priority_queue<ll> pq;
  ll ans = 0;
  for (int i = 0; i <= M; i++) {
    for (int j = 0; j < v[i].size(); j++) {
      pq.push(v[i][j]);
    }
    if (!pq.empty()) {
      ans += pq.top();
      pq.pop();
    }
  }
  cout << ans << endl;
  return 0;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define MAX_N 200000
i64 N;
i64 A[MAX_N];

void solve() {
    i64 k = 1;
    REP(i, N) {
        if (A[i] == k) k++;
    }
    if (k == 1) {
        cout << -1 << endl;
        return;
    }
    cout << N - k + 1 << endl;
}

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];

    solve();

    return 0;
}

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



int main() {
	

	int n;
	string s;
	cin >> n;
	cin >> s;
	
	long long ans;

	long long r, g, b;
	r = 0;
	g = 0;
	b = 0;
	ans = 0;

	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'R')
		{
			r += 1;
		}
		else if (s[i] == 'G')
		{
			g += 1;
		}
		else if (s[i] == 'B')
		{
			b += 1;
		}
	}
	
	ans = r * g * b;

	for (int i = 0; i < n-2; i++)
	{
		for (int j = i+1; j < n-1; j++)
		{
			long long k = 2 * j - i;

			if (k >n-1)
				continue;

			if (s[i] != s[j] && s[i] != s[k] && s[j] != s[k])
			{
				ans -= 1;
			}
		}
	}


	

	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;

void mod(long long &a){
    if(a > MOD)a %= MOD;
}

int main(){
    double W, H, w, h;
    cin >> W >> H >> w >> h;
    double ans = (W * H) / 2;
    bool ANS = false;
    if(w == W / 2 && h == H / 2)ANS = true;
    cout << ans << " ";
    if(ANS)cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace _2699
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
                if (x.Max() == 0) break;
                double ret = double.MaxValue;
                for (double i = 0; i < x[0]; i++)
                {
                    ret = Math.Min(ret, Math.Abs(x[1] - Math.Sqrt(i * i + (x[0] - i) * (x[0] - i))));
                }
                Console.WriteLine(ret);
            }
        }
    }
}

Measured memory_bytes: 9592
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
	ll w,h,a,b;
	cin>>w>>h>>a>>b;
	long double ans=(w*h*1.0)/2;
	if(w%2==0 && h%2==0 && w/2==a && h/2==b){
		cout<<fixed<<setprecision(9)<<ans<<" "<<"1"<<"\n";
	}
	else
		cout<<fixed<<setprecision(9)<<ans<<" "<<"0"<<"\n";
	return 0;
}

Measured memory_bytes: 256
#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 long long ll;

int main() {
    int n,k,r,s,p; cin >> n >> k >> r >> s >> p;
    string t; cin >> t;
    ll ans = 0;
    rep(i,n){
        if(i >= k && t[i] == t[i-k]){
            t[i] = 'o';
            continue;
        }else{
            if(t[i] == 'r') ans += p;
            if(t[i] == 's') ans += r;
            if(t[i] == 'p') ans += s;
        }
    }
    cout << ans << endl;
}

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

int main()
{
  double v, y;

  while (cin >> v){
    int floor = 0;
    y = (v * v) / (2 * 9.8);
    for (; (floor * 5) - 5 < y; floor++);
    printf("%d\n", floor);
  }
}

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

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
// #define MOD 998244353 
#define MEM_SIZE 100010
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

 

//SOLVE
void solve(void)
{

  int N;cin>>N;
  vector<int> vec (N,0);
  int MAX = -1*INF;
  int MIN = INF;
  int index_MAX = 0;
  int index_MIN = 0;
  for (int i = 0; i < N; i++)
  {
     cin>>vec[i];
     if(chmax(MAX,vec[i]))
     {
       index_MAX = i;
     }
     if(chmin(MIN,vec[i]))
     {
       index_MIN = i;
     }
  }
  cout<<N +N -1<<endl;
  // DEBUG(MAX,MIN);
  if(abs(MAX) > abs(MIN))
  {
    for (int i = 0; i < N; i++)
    {
      cout<<index_MAX+1<<" "<<i+1<<endl;
    }
    for (int i = 0; i < N-1; i++)
    {
      cout<<i+1<<" "<<i+2<<endl;
    }
  }
  else
  {
    for (int i = 0; i < N; i++)
    {
      cout<<index_MIN+1<<" "<<i+1<<endl;
    }
    for (int i = N-1; i >= 1; i--) 
    {
      cout<<i+1<<" "<<i<<endl;
    }
  }
  

  return;
}

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

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


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

class Program
{
    static void Main()
    {
        var ABCD = ReadLine().Split().Select(long.Parse).ToArray();
        var A = ABCD[0];
        var B = ABCD[1];
        var C = ABCD[2];
        var D = ABCD[3];
        A--;
        var gcd = GCD(C, D);
        var lcm = C / gcd * D;
        var a = A - A / C - A / D + A / lcm;
        var b = B - B / C - B / D + B / lcm;
        WriteLine(b - a);
    }

    static long GCD(long a, long b) => b == 0 ? a : GCD(b, a % b);
}

Measured memory_bytes: 13396
import math
def solve():
    N = int(input())
    rootN = math.sqrt(N)

    min_val = float('inf')
    for a in range(1, math.floor(rootN) + 1):
        if N % a == 0:
            b = N / a
            min_val = min(min_val, a + b - 2)
    
    print(int(min_val))

if __name__ == '__main__':
    solve()


Measured memory_bytes: 38640
n=int(raw_input())
p = list(map(int,raw_input().split()))
sorted_p = sorted(p)

cnt = 0
for i in range(len(p)):
    if p[i] != sorted_p[i]:
        cnt += 1

if cnt == 2 or cnt == 0:
    print("YES")
else: print("NO")

Measured memory_bytes: 2568
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

int n,m,flag,dx[]={1,0,-1,0},dy[]={0,1,0,-1};
char c[100][100];

void paint(int x,int y,char ch){
	c[y][x]='o';
	rep(i,4){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx>=0&&nx<n&&ny>=0&&ny<m){
			if(c[ny][nx]==ch)paint(nx,ny,ch);
			if(c[ny][nx]=='&')flag=1;
		}
	}
}

int main(){
	while(cin>>n>>m&&n){
		flag=0;
		rep(i,m)rep(j,n){
			cin>>c[i][j];
			if(i==0||i==m-1||j==0||j==n-1){
				if(c[i][j]=='.')c[i][j]='o';
				if(c[i][j]=='&')flag=1;
			}
		}
		int t=0;
		while(!flag){
			if(t==1)rep(i,m)rep(j,n)if((i==0||i==m-1||j==0||j==n-1)&&c[i][j]=='#')c[i][j]='o';
			if(t)rep(i,m)rep(j,n)if(c[i][j]=='o')paint(j,i,'#');
			rep(i,m)rep(j,n)if(c[i][j]=='o')paint(j,i,'.');
			if(!flag)t++;
		}
		cout<<t<<endl;
	}
}

Measured memory_bytes: 0
#include <cmath>
#include <cstdio>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stack>
#include <fstream>
#include <queue>
#include <iomanip>
#include <iterator>
#include <map>
#include <unordered_map>
#include <set>
#define fast ios_base::sync_with_stdio(false)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vvi vector<vi >
#define pi pair<ll,ll>
#define vvpi vector<vector<pi > >
#define vpi vector<pi >
#define vppi vector<pair<ll,pi > >
#define vs vector<string>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define fs first
#define se second
#define crz(v,n) v.clear(),v.resize(n+1,0)
#define print(v) for(ll it=0;it<v.size();it++) cout<<v[it]<<" ";cout<<endl
#define printp(v) for(ll it=0;it<v.size();it++) cout<<v[it].first<<" "<<v[it].second<<endl
using namespace std;
int main(){
	ll a,b,n,s;cin>>n>>a>>b;s=min(b-1,n-a);
	if((b-a)%2==0) s=min(s,(b-a)/2);
	else s=min(s,min((b+a-1)/2,(1+2*n-b-a)/2));
	cout<<s<<endl;
}


Measured memory_bytes: 256
import math
n = int(input())
n = math.factorial(n)
i = 2
MOD = 10 ** 9 + 7
ans = 1
while i * i <= n:
    cnt = 1
    while n % i == 0:
        cnt += 1
        n //= i
    ans *= cnt
    i += 1

if n != 1:
    ans *= 2

print(ans % MOD)


Measured memory_bytes: 38896
#include<cstdio>
#include<set>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	set<int> st;
	for(int i = 0; i < n; i++){
		int x;
		scanf("%d", &x);
		st.insert(x);
	}
	int ans;
	if(st.size() % 2){
		ans = st.size();
	}else {
		ans = st.size() - 1;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
    // Write Your Code Below
    ll n, ans;
    ans = 0;
    cin >> n;
    vector<ll> v(2 * n);
    rep(i, 2 * n){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    rep(i, n){
        ans += v[i * 2];
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    // Your code here!
    
    val n: Int       = readLine()!!.toInt()
    val p: List<Int> = readLine()!!.split(" ").map { it.toInt() }
    var count: Int = 0
    for (i in 1..p.size - 2) {

        if ((p[i-1] < p[i] && p[i] < p[i+1]) || p[i-1] > p[i] && p[i] > p[i+1]) {
            ++count
        }
    }
    println(count)
}

Measured memory_bytes: 38088
import numpy as np
n, m = map(int, input().split())

X = [input() for _ in range(n)]
np_x = np.zeros((n, n), dtype=int)
for i in range(n):
  for j in range(n):
    np_x[i, j] = X[i][j] == '.'
Y = [input() for _ in range(m)]
np_y = np.zeros((m, m), dtype=int)
for i in range(m):
  for j in range(m):
    np_y[i, j] = Y[i][j] == '.'

for i in range(n-m+1):
  for j in range(n-m+1):
    if np.all(np_x[i:i+m, j:j+m] == np_y):
      print('Yes')
      exit()
else:
  print('No')

Measured memory_bytes: 20572
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

void main() {
    int n;
    scan(n);
    if (n <= 999) {
        writeln("ABC");
    }
    else {
        writeln("ABD");
    }
}










































void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <time.h>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cassert>

using namespace std;

const int N = 100005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

int n;
long long a[N];
map <long long,int> mp;
long long answ = 0;
int k = 0;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        mp[a[i]]++;
    }
    sort(a+1 , a+n+1);
    for(int i=n;i>=1;i--){
        if(a[i] == a[i+1])continue;
        if(k == 0){
            if(mp[a[i]] >= 4){
                k = 4;
                answ = a[i] * a[i];
                break;
            }
            if(mp[a[i]] >= 2){
                k = 2;
                answ = a[i];
            }
        }
        else{
            if(mp[a[i]] >= 2){
                answ *= a[i];
                k = 4;
                break;
            }
        }
    }
    if(k != 4)
        cout<<0<<endl;
    else
        cout<<answ<<endl;
    return 0;
}



Measured memory_bytes: 7296
import java.io.*
import java.util.*
import java.lang.*
import java.lang.Math.*


fun solve() {
    val N = rd.readInt()
    val L = rd.readIntArray().sorted()

    var cnt = 0
    for (i in 0 until N-2) {
        for (j in i+1 until N-1) {
            if (L[i] >= L[j]) continue
            for (k in j+1 until N) {
                if (L[j] >= L[k]) continue

                if (L[i]+L[j]>L[k]) cnt++
            }
        }
    }

    val ans = cnt
    println(ans)
}


//val rd = debug.Reader("abc", "175", "b", "sample-1")
val rd = Reader()


fun main(args: Array<String>) {
    try {
        var exception: Throwable? = null
        val sth = Thread(null, SolveThread(), "solveThread", 128 * 1024 * 1024)
        sth.setUncaughtExceptionHandler { _, e -> exception = e }
        sth.start(); sth.join()
        if (exception != null) throw exception!!
    } catch (e: Exception) { throw e }
}
const val MOD = 1_000_000_007L; const val INF = Int.MAX_VALUE/2; const val LINF = Long.MAX_VALUE/2
data class IntPair(val first: Int, val second: Int); data class LongPair(val first: Long, val second: Long)
val errPrintln: (Any) -> Unit = { msg -> System.err.println(msg) }
fun rAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("EAssert Error: $msg"); throw Error(msg) }
}
fun tAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("TAssert Error: $msg"); Thread.sleep(3000) }
}
class SolveThread : Runnable {
    override fun run() { solve() }
}
class Reader {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val readString: () -> String = { br.readLine() }
    val readInt: () -> Int = { br.readLine().toInt() }
    val readLong: () -> Long = { br.readLine().toLong() }
    val readIntArray: () -> IntArray = { br.readLine().split(' ').map { it.toInt() }.toIntArray() }
    val readLongArray: () -> LongArray = { br.readLine().split(' ').map { it.toLong() }.toLongArray() }
    val readListInt: () -> List<Int> = { br.readLine().split(' ').map { it.toInt() } }
    val readListLong: () -> List<Long> = { br.readLine().split(' ').map { it.toLong() } }
}


Measured memory_bytes: 40636
#include<stdio.h>

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a==b)
        printf("%d\n",a+b);
    else if(a>b)
        printf("%d\n",a+a-1);
    else
        printf("%d\n",b+b-1);
    return 0;
}


Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define vec vector
#define fi first
#define se second
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define cout(a) cout << a << " "
#define vcout(v) rep(i,v.size()) cout(v[i]); cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}
#define bit(x) (1ll<<(x))




void dfs(int me, int parent=-1){


}

int main(){
	ll n, q;
	cin >> n >> q;
	
	vec<vec<ll>> to(n);
	rep(i,n-1){
		ll a, b;
		cin >> a >> b;
		--a; --b;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	vec<ll> ans(n);
	
	rep(i,q){
		ll p, x;
		cin >> p >> x;
		--p;
		ans[p] += x;
	}
	
	function<void(ll,ll)> dfs;
	dfs = [&](ll v, ll par) -> void{
		for(int child : to[v]){
			if(child == par) continue; // 自分の親にはカウンタは足さない
			ans[child] += ans[v]; // 子に自分のカウンタを足す
			dfs(child, v);
		}
	};
	
	dfs(0,-1);
	
	vcout(ans);
	return 0;
}


Measured memory_bytes: 30464