akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int maxn =1e5 + 28;
vector <pair<int, int>> v;
bool mark[maxn];
long long ans, sum;
stack <int> v2;
int type;
int main(){
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		v.push_back({y, x});
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	for(int i = 0; i < k; i++){
		sum += v[i].first;
 		if(!mark[v[i].second]){
			type ++;
			mark[v[i].second] = 1;
		}
		else
			v2.emplace(v[i].first);
	}
	ans = sum + ((long long)type * type);
	for(int i = k; i < n; i++){
		sum += v[i].first;
		if(!mark[v[i].second]){
			type ++;
			mark[v[i].second] = 1;
		}
		else
			v2.emplace(v[i].first);
		if(v2.empty())
			break;
		sum -= v2.top();
		v2.pop();
		ans = max(ans, (sum + ((long long)type * type)));
	}
	cout << ans;
	
}

Measured memory_bytes: 1400
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def in_sec(a, b, c):
    return min(a, b) <= c <= max(a, b)

g = input()
lst = []
for loop in range(g):
    x, y = map(int, raw_input().split())
    lst.append((x, y))
lst += lst[:1]

n = input()
for loop in range(n):
    x, y = map(int, raw_input().split())
    flag = False
    for i in range(g):
        x1, y1 = lst[i]
        x2, y2 = lst[i + 1]
        if (x1 - x) * (y2 - y) == (x2 - x) * (y1 - y) and \
            (x1 - x) * (x2 - x) <= 0 and (y1 - y) * (y2 - y) <= 0:
            print 1
            flag = True
            break
    if flag:
        continue
    cnt = 0
    for i in range(g):
        x1, y1 = [x + 1, y + 10000000]
        x2, y2 = lst[i]
        x3, y3 = lst[i + 1]
        a1, b1, c1 = [y1 - y, x - x1, x * (y1 - y) - y * (x1 - x)]
        a2, b2, c2 = [y3 - y2, x2 - x3, x2 * (y3 - y2) - y2 * (x3 - x2)]
        det = a1 * b2 - b1 * a2
        if in_sec(x2 * det, x3 * det, c1 * b2 - c2 * b1) \
            and in_sec(y2 * det, y3 * det, c2 * a1 - c1 * a2) \
            and y < float(c2 * a1 - c1 * a2) / det:
            cnt += 1
    print (cnt % 2) * 2



Measured memory_bytes: 5088
import java.util.*;

public class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	double[] v = new double[n];
	for (int i=0; i<n; i++) v[i] = sc.nextDouble();
	Arrays.sort(v);
	double newIs = (v[0] + v[1]) / 2;
	for (int i=2; i<n; i++) {
	    newIs = (newIs + v[i]) / 2;
	}
	System.out.print(newIs);
    }
}


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

const int maxn = 2510;
int n, m;
int cnt, ans, head[maxn], incf[maxn], dist[maxn], inq[maxn], pre[maxn];
struct edge { int to, cap, cost, nxt; } e[100000];
char str[55][55];

void add(int from, int to, int cap, int cost) {
    e[cnt] = (edge){to, cap, cost, head[from]}, head[from] = cnt++;
    e[cnt] = (edge){from, 0, -cost, head[to]}, head[to] = cnt++;
}

bool spfa(int s, int t) {
    fill(dist, dist + t + 1, -1e9);
    queue<int> q;
    q.push(s), dist[s] = 0, incf[s] = INT_MAX;
    while (!q.empty()) {
        int v = q.front(); q.pop(), inq[v] = 0;
        for (int i = head[v]; ~i; i = e[i].nxt) {
            if (e[i].cap && dist[e[i].to] < dist[v] + e[i].cost) {
                dist[e[i].to] = dist[v] + e[i].cost, pre[e[i].to] = i;
                incf[e[i].to] = min(incf[v], e[i].cap);
                if (!inq[e[i].to]) q.push(e[i].to), inq[e[i].to] = 1;
            }
        }
    }
    return dist[t] != -1e9;
}

void upd(int s, int t) {
	for (int i = t; i ^ s; i = e[pre[i] ^ 1].to) {
		e[pre[i]].cap -= incf[t], e[pre[i] ^ 1].cap += incf[t];
	}
	ans += dist[t] * incf[t];
}

void EK(int s, int t) {
    while (spfa(s, t)) upd(s, t);
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str[i] + 1);
    }
    auto id = [&](int x, int y) {
        return (x - 1) * m + y;
    };
    int s = 0, t = n * m + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (str[i][j] == 'o') {
                add(s, id(i, j), 1, 0);
            }
            if (str[i][j] != '#') {
                add(id(i, j), t, 1, 0);
            }
            if (i < n && str[i][j] != '#' && str[i + 1][j] != '#') {
                add(id(i, j), id(i + 1, j), 100, 1);
            }
            if (j < m && str[i][j] != '#' && str[i][j + 1] != '#') {
                add(id(i, j), id(i, j + 1), 100, 1);
            }
        }
    }
    EK(s, t), printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 3964
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    int n,m;cin>>n>>m;
    vector<ll> x(n),y(n),z(n);
    rep(i,n) cin>>x[i]>>y[i]>>z[i];
    ll res= (-1e+18);
    rep(i,8){
        priority_queue<ll> que;
        rep(j,n){
            int b=i;
            ll now=0;
            if(b%2==1)now-=x[j];
            else now+=x[j];
            b/=2;
            if(b%2==1)now-=y[j];
            else now+=y[j];
            b/=2;
            if(b%2==1)now-=z[j];
            else now+=z[j];
            que.push(now);
        }
        ll buf=0;
        rep(j,m){
            buf+=que.top();que.pop();
        }
        //cout<<buf<<endl;
        chmax(res,buf);
    }
    cout<<res<<endl;
}

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

using namespace std;
int main(){

	while(1){
		int num;
		
		cin >> num;
		if(num == 0){
			return 0;
		}
		
		bool lu = false;
		bool ru = false;
		int time = 0;
		bool u = false;
		
		for(int i=0; i<num; ++i){
			string dat;
			cin >> dat;
			
			if( dat == "lu" ){
				lu = true;
			}
			if( dat == "ru" ){
				ru = true;
			}
			if( dat == "ld" ){
				lu = false;
			}
			if( dat == "rd" ){
				ru = false;
			}
			
			if( lu==true && ru==true && u==false ){
				u = true;
				time++;
			}
			if( lu==false && ru==false && u==true ){
				u = false;
				time++;
			}
		}
		cout << time << endl;		
		
	}


}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define ff first
#define ss second
typedef long long ll;
ll power(ll a, ll b){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--){
        string s[4];
        int c[4];c[0]=c[1]=c[2]=c[3]=0;
        s[0]="AC";
        s[1]="WA";
        s[2]="TLE";
        s[3]="RE";
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            string w;
            cin>>w;
            for(int j=0;j<4;j++){
                if(s[j]==w)
                    c[j]++;
            }
        }
        for(int i=0;i<4;i++)
            cout<<s[i]<<" x "<<c[i]<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
#define fine cout<<"fine"<<endl;
#define ll long long int
#define pb push_back
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
const ll inf=(ll)2e18;
const int mod=1e9+7;
bool overflow(ll a,ll b){
    if (a <= (inf+b-1)/b) return false;
    return true;
}
int main(){
FASTIO;
ll x;
cin>>x;
ll ans=0;
ans=(x/500)*1000;
x%=500;
ans+=(x/5)*5;
cout<<ans<<endl;
}


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

rr = [0]*N
gr = [0]*N
br = [0]*N

r = 0
g = 0
b = 0
for i in range(N-1, -1, -1):
    if S[i] == "R":
        r += 1
    if S[i] == "G":
        g += 1
    if S[i] == "B":
        b += 1
    rr[i] = r
    gr[i] = g
    br[i] = b

wa = {"R":rr, "G":gr, "B":br}

res = 0

for i in range(N):
    c1 = S[i]
    for j in range(i+1, N):
        c2 = S[j]
        if c1 == c2:
            continue
        c = (c1, c2)
        if "R" not in c:
            c3 = "R"
        elif "G" not in c:
            c3 = "G"
        else:
            c3 = "B"

        if wa[c3][j] == 0:
            break

        res += wa[c3][j]
        x = i+(j-i)*2
        if x < N:
            if S[x] == c3:
                res -= 1
                pass

print(res)

Measured memory_bytes: 69192
function Main(arg) {
  let N = BigInt(arg.trim().split(' ')[0]);
  let X = BigInt(arg.trim().split(' ')[1]);
  let T = BigInt(arg.trim().split(' ')[2]);
  let result = T;
  if(N > X){
    result = N/X*T;
    
    if(N%X != 0){
      result +=T;
    }
  }
  console.log(Number(result));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

string s;
int n;

int main(){
	cin>>n>>s;
	int sum=0;
	for(int i=0;i<n;i++) if(s[i]!='#') sum++;
	int ans=sum;
	for(int i=0;i<n;i++){
		if(s[i]=='.') sum--;
		if(s[i]=='#') sum++;
		ans=min(ans,sum);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 640
n = int(input())
a = list(map(int,input().split()))

cnt = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
        a[i] *= -1
ans = sum(a) - 2 * min(a) if cnt % 2 != 0 else sum(a)
print(ans)

Measured memory_bytes: 14332
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
import math
N = ii()
a = 100
n = 0
while True:
    a = math.floor(a * 1.01)
    n += 1
    if a >= N:
        print(n)
        exit()

Measured memory_bytes: 9220
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define REP(i,n) for(int i = 0;i < n; i++)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e18;

#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>vector<T>
make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}



signed main(){
	IOS();
	int N,M,T;
	cin>>N>>M>>T;
	vector<int>a(N+2);
	a[0]=-M;
	a[N+1]=T+M;
	rep(i,1,N+1)cin>>a[i];
	int ans = 0;
	rep(i,0,N+1){
		ans+=max(0ll,a[i+1]-a[i]-M*2);
	}
	cout<<ans<<endl;
}


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

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

int main(){

    ll n;
    cin >> n;

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

    sort(a.begin(), a.end(), less<ll>());
    sort(b.begin(), b.end(), less<ll>());

    if(n%2==1){
        ll mid = n/2;
        ll ma = a[mid];
        ll mb = b[mid];
        cout << mb - ma + 1<< endl;
    }else{
        ll mid = n/2;
        double ma = (a[mid-1]+a[mid])*0.5;
        double mb = (b[mid-1]+b[mid])*0.5;
        cout << (ll)((mb - ma)/0.5)+1 << endl;
    }
    return 0;
}


Measured memory_bytes: 6416
MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
ans = 0

for k in range(60):
    count1 = 0
    for i in range(N):
        if (A[i]>>k) & 1:
            count1 += 1
    count0 = N-count1
    ans = (ans + count0*count1*2**k) % MOD

print(ans)

Measured memory_bytes: 122808
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

using Data = struct{
    int pos;
    string puzzle;
    int t;
};

constexpr int dx[] = {-1, 1, -4, 4};
const string correct{"01234567"};

int main(){
    map<string, int> min_root{{correct, 0}};
    
    queue<Data> q;
    q.push(Data{0, correct, 0});
    while(!q.empty()){
        Data d = q.front();
        q.pop();

        for(int i = 0; i < 4; ++i){
            int npos = d.pos+dx[i];

            if(npos < 0 || npos > 7 || (d.pos == 3 && npos == 4) || (d.pos == 4 && npos == 3)) continue;

            string npuzzle = d.puzzle;
            swap(npuzzle[d.pos], npuzzle[npos]);

            if(min_root.find(npuzzle) != end(min_root)) continue;

            min_root.emplace(make_pair(npuzzle, d.t+1));
            q.push(Data{npos, npuzzle, d.t+1});
        }
    }

    cin.tie(0);
    ios::sync_with_stdio(false);

    string puzzle(8, ' ');

    while (cin >> puzzle[0] >> puzzle[1] >> puzzle[2] >> puzzle[3] >> puzzle[4] >> puzzle[5] >> puzzle[6] >> puzzle[7]) {
        cout << min_root[puzzle] << endl;
    }
}


Measured memory_bytes: 5392
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;

int GCD(int a,int b){
  if(a<b) swap(a,b);
  if(a%b==0) return b;
  else return GCD(b,a%b);
}

signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int ans=0;
  rep(i,n){
    rep(j,n){
      rep(k,n){
	int a=i+1,b=j+1,c=k+1;
	int g=GCD(a,b);
	g=GCD(g,c);
	ans+=g;
      }
    }
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 3652
package main

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

var (
	N     int
	s     [1000]string
	index map[string]int = make(map[string]int)
	cumT  [1000]int
	X     string
)

func main() {
	readVariables()
	answer := cumT[N] - cumT[index[X]]
	fmt.Println(answer)
}

func readVariables() {
	N = nextInt()
	for i := 0; i < N; i++ {
		s, t := nextStr(), nextInt()
		cumT[i+1] = cumT[i] + t
		index[s] = i + 1
	}
	X = nextStr()
}

/* Template */

var scanner *bufio.Scanner

func init() {
	Max := 1001001
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 0, Max), Max)
	scanner.Split(bufio.ScanWords)
}

//nextInt converts next token from stdin and returns integer value.
//nextInt panics when conversion into an integer fails.
func nextInt() int {
	if !scanner.Scan() {
		panic("No more token.")
	}
	num, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic("nextInt(): cannot convert to int: " + scanner.Text())
	}
	return num
}

func nextStr() string {
	if !scanner.Scan() {
		panic("No more token.")
	}
	return scanner.Text()
}

// MinInt returns minimum argument
func MinInt(x, y int) int {
	if x < y {
		return x
	} else {
		return y
	}
}

//MaxInt returns maximum argument
func MaxInt(x, y int) int {
	if x < y {
		return y
	} else {
		return x
	}
}

//AbsInt returns |x| for x
func AbsInt(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

//ModPow calculates integer power with modulo operation
//if modulo <= 1, it powers w/o module operation
//if base < 0, return value might be negative too.
func ModPow(base, exponent, modulo int) (result int) {
	result = 1
	for exponent > 0 {
		if exponent%2 == 1 {
			result *= base
			if modulo > 1 {
				result %= modulo
			}
		}
		base *= base
		if modulo > 1 {
			base %= modulo
		}
		exponent /= 2
	}
	return
}

//Gcd
func Gcd(vals ...int) (result int) {
	if len(vals) == 0 {
		return
	}
	result = vals[0]
	for i := 1; i < len(vals); i++ {
		result = gcd(result, vals[i])
	}
	return
}

func gcd(x, y int) int {
	x, y = AbsInt(x), AbsInt(y)
	for y > 0 {
		x, y = y, x%y
	}
	return x
}

//Lcm
func Lcm(vals ...int) (result int) {
	if len(vals) == 0 {
		return
	}
	result = vals[0]
	for i := 1; i < len(vals); i++ {
		result = lcm(result, vals[i])
	}
	return
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}


Measured memory_bytes: 640
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))

ans_list = []
for i in range(N):
    diff = abs(A - (T - H[i] * 0.006))
    ans_list.append(diff)
        
print(ans_list.index(min(ans_list)) + 1)

Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
import functools


@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


if __name__ == '__main__':
    n = int(input())
    print(fib(n))



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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n;
ll d[100010];

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

  cin>>n;
  rep(i,n)cin>>d[i];
  sort(d,d+n);
  ll m=n/2;
  cout<<d[m]-d[m-1]<<endl;

  return 0;
}


Measured memory_bytes: 1024
#https://atcoder.jp/contests/abc128/submissions/13683823
from operator import itemgetter
n = int(input())

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

b = sorted(a, key=itemgetter(1), reverse=True)
guidebook = sorted(b, key=itemgetter(0))

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


Measured memory_bytes: 3060
MOD = 10**9+7
n = int(input())
c = sorted(list(map(int, input().split())))
ans = 2**(2*n-2) % MOD
a = 0
for i in range(1,n+1):
	a = (a + c[i-1] * (2+n-i)) % MOD
ans = (ans * a) % MOD
print(ans)

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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

#define MAX 500000
#define SENTINEL 2000000000

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

ll L[MAX/2+2], R[MAX/2+2], cnt;

void merge(int a[], int n, int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  rep(i, n1) L[i] = a[left + i];
  rep(i, n2) R[i] = a[mid + i];
  L[n1] = R[n2] = SENTINEL;
  int i = 0, j = 0;

  for(int k = left; k < right; k++) {
    cnt++;
    if(L[i] <= R[j]) a[k] = L[i++];
    else a[k] = R[j++];
  }
}

void mergeSort(int a[], int n, int left, int right) {
  if (left + 1 < right) {
    int mid = (left + right) / 2;
    mergeSort(a, n, left, mid);
    mergeSort(a, n, mid, right);
    merge(a, n, left, mid, right);
  }
}

signed main() {
	ll a[MAX], n;
  cnt = 0;
  cin >> n;
  rep(i, n) cin >> a[i];

  mergeSort(a, n, 0, n);
  rep(i, n) {
    if (i) cout << " ";
    cout << a[i];
  }
  cout << endl;

  cout << cnt << endl;
}


Measured memory_bytes: 10992
/**   Created by: Marcos Portales
          Codeforces User: marcosportales
          Country: Cuba
                         **/
#include<bits/stdc++.h>
using namespace std;
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
#define vi vector<int>
#define sz size
#define rep(i,x,y) for(int i=(x);i<(y);i++)
#define rep2(i,x,y) for(int i=(x);i>(y);i--)
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 1e5+1;
const int mod = 1000000009;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 10000000000000000ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if(!e)return 1;
    if(e&1) return qpow(b,e-1)*b;
    int pwur=qpow(b,e>>1);
    return pwur*pwur;
}

/// My Code -------------------------------------------------

int a[105][105];

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int a,b,c,x;
    cin>>a>>b>>c>>x;
    int cnt=0;
    rep(i,0,a+1)
        rep(j,0,b+1)
            rep(k,0,c+1)
                if(i*500+j*100+k*50==x)cnt++;

    cout<<cnt<<enl;

    return 0;
}


Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt(); //人数
		int total = 0; //必要なキャンディの個数

		for (int i = 1; i <= N; i++) {
			total += i ;
		}
		System.out.println(total);
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
int main(){
    int x, y; cin >> x >> y;
    int f = 0;
    for(int i = 0 ; i <= x; i ++){
        if(2 * i + 4 * (x - i) == y) f = 1;
    }
    if(f == 1) cout << "Yes";
    else cout << "No";
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int n,k,m[26],a=0;
string s[10001];
priority_queue<int>q;
int main(){
	cin>>n>>k;
	rep(i,n){cin>>s[i];m[s[i][0]-'A']++;}
	rep(i,26)if(m[i])q.push(m[i]);
	while(q.size()>=k){
		rep(i,k){m[i]=q.top();q.pop();}
		rep(i,k)if(m[i]>1)q.push(m[i]-1);
		a++;
	}
	cout<<a<<endl;
	return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

void solveSingleCase(int caseNo)
{
    int A, B, C;
    cin >> A >> B >> C;
    cout << (C >= A && C <= B ? "Yes" : "No") << endl;
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    // cin >> T;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long xoror(long n){
    long ans = 0;
    for(long i=1;i<=n;i*=2){
        if(i==1){
            if((n-1)%4 < 2)ans++;
        }else{
            if(n%(i*2)>=i && n%2==0)ans += i;
        }
    }
    return ans;
}

int main(){
    long a,b;
    cin >> a >> b;
    long ans;
    if(a==0)ans = xoror(b);
    else ans = xoror(a-1) ^ xoror(b);
    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	unsigned long long a,b;
	cin>>a>>b;
	if(a==1||b==1)
	{
		cout<<1;
	}
	else if(a%2==0)
	{
		cout<<a*b/2;
	 } 
	else
    {
	    cout<<(a*b+1)/2;	
	}
	return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;

int main(){
    string S;
    cin >> S;
    bool ans = false;
    for(int i=0;i<3;i++){
        if(S[i]== S[i+1])ans = true;
    }
    if(ans)cout << "Bad" << endl;
    else cout << "Good" << endl;
}

Measured memory_bytes: 256
my $N = <STDIN>;

my $sum =0;
my %del;
for(my $i=$N;$i>0;$i--){
 $count = int($N /$i);
 $del{$i} = ($count*$count*$count);
 #print "i$i count$count del$del{$i}  \n";
}
for(my $i=$N;$i>0;$i--){
 #print "i$i  del$del{$i} \n";
 for(my $j=1;$j<$i;$j++){
    if( ($i%$j == 0) ){ $del{$j}= $del{$j} - $del{$i};}
 }
 $sum = $sum + $i*$del{$i};
 #print "i$i del$del{$i} $sum\n";
}
print "$sum";
exit;


Measured memory_bytes: 4712
w = input();count = 0;word = '';T = []
w = w.lower()
while True:
    t = input()
    if t=='END_OF_TEXT':
        break
    t = t.lower()
    T.append(t)


for i in range(len(T)):
    for j in range(len(T[i])):        
        if 'a'<=T[i][j]<='z':
            word += T[i][j]
        if T[i][j]==' ' or j==len(T[i])-1:
            if word == w:
                count+=1
            word =''
    
print(count)


Measured memory_bytes: 5560
n, m, c = gets.split.map &:to_i
b = gets.split.map &:to_i

a = []

n.times{
	a << (gets.split.map &:to_i)
}

count = 0
a.each{ |al|
	sum = c
	al.each_with_index{ |ae, i|
		sum += ae * b[i]
	}
	
	if sum > 0 then
		count += 1
	end
}

puts count


Measured memory_bytes: 1788
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repr(i,a,b) for(int i=a,i > b;--i)
#define mm(lamb, tttt) memset(lamb, tttt, sizeof lamb)

#define null NULL
#define eps 0.000000001
#define mod 1000000007
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define sz(V) (ll)V.size()
#define _ <<" "<<

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <iterator>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <limits.h>
#include <iomanip>
#include <cctype>
#include <numeric>
#include <complex>

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef pair <double, double> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<int> vii;


int main(){
	int n,z,w;
	cin>>n>>z>>w;
	vi a;
	rep(i,0,n){
		int x;cin>>x; a.pb(x);
	}
	if(n==1) {
		cout<<abs(a[0]-w)<<endl;
		return 0;
	}
	cout<<max(abs(a[n-1]-w),abs(a[n-1]-a[n-2]))<<endl;
 	return 0;
}




Measured memory_bytes: 256
#include <stdio.h>  /*入出力*/
#include <stdlib.h> /*標準ライブラリ*/
#include <string.h> /*文字列*/
#include <math.h>   /*計算*/
#include <assert.h> /*確認*/
#include <ctype.h>  /*文字操作*/
#include <stdbool.h>/*bool型*/
#include <limits.h>/*限界*/

#define rep(i, n) for(int  i = 0; i < (n); i++)
#define max(a,b) ((a>b)?a:b)
#define ABS(a) (((a)>(0))?a:-(a))
#define LL long long
#define MOD 1000000007//10^9+7(素数)

//abc159 C

int main(void)
{
  int N;
  double h;
  scanf("%d", &N);
  h = (double)N / 3;
  printf("%lf\n", h*h*h);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>

bool atgc(char c) {
    return c == 'A' || c == 'T' || c == 'G' || c == 'C';
}

int work(std::istream &in) {
    std::string s;
    in >> s;
    int m = 0;

    for (int i = 0; i < s.length(); ++i) {
        int j = i;
        while (j < s.length() && atgc(s[j])) ++j;
        m = std::max(m, j - i);
        i = j;
    }

    return m;
}

struct testdata {
    const char *input;
    int expected;
};

int test() {
    int ret = 0;

    struct testdata testset[] {
        {"ATCODER", 3},
        {"HATAGAYA", 5},
        {"SHINJUKU", 0}
    };

    const int TESTLEN = sizeof(testset) / sizeof(testset[0]);
    for (int i = 0; i < TESTLEN; ++i) {
        std::stringstream sin(testset[i].input);
        int actual = work(sin);
        if (actual != testset[i].expected) {
            fprintf(stderr, "ERROR: expected: %d, but actual %d\n", testset[i].expected, actual);
            ret = 1;
        }
    }

    return ret;
}

int main(int argc, char *argv[]) {
    if (argc == 2 && strcmp("--test", argv[1]) == 0) {
        exit(test());
    }
    printf("%d\n", work(std::cin));
}


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

signed main() {
    int a,b,c;
    cin >> a >> b >> c;
    if (a == b + c || b == a + c || c == a + b) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define wi(t) int t;cin>>t;while(t--)
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int mpow(int base, int exp); 
void ipgraph(int n, int m);
void dfs(int u, int par);

const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vi g[N];
int a[N];

void solve()
    {
  
 string s,t;
 cin>>s>>t;
 ll int ans=0;
 for(int i=0;i<s.size();i++)
 {
     if(s[i]!=t[i])
     ans++;
 }
  
  cout<<ans<<endl;
  
    }

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

  //  wi(t)
    {
      solve();
    }

    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
    u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}






Measured memory_bytes: 10928
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    using ll = long long;
    
    vector<ll> x(n);
    
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    
    ll ans = 1LL << 60;
    
    for (int i = 0; i + k - 1 < n; i++) {
        ll l = x[i];
        ll r = x[i + k - 1];
        
        if (r <= 0) {
            ans = min(ans, -l);
        } else if(0 <= l) {
            ans = min(ans, r);
        } else {
            ans = min({ans, -l + r - l, r + r - l});   
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 1024
def max_ten(s):
    if flag[s]:
        return memo[s]
    ten = 0
    # 分けない場合の点数
    for ai, ar in enumerate(a[:-1]):
        if (s >> ai) & 1:
            ten += sum(ar[j] for j in range(1 + ai, n) if ((s >> j) & 1))
    # 分ける場合の点数
    bubun = (s - 1) & s
    while bubun > 0:
        kari = max_ten(bubun) + max_ten(bubun ^ s)
        if kari > ten:
            ten = kari
        bubun = (bubun - 1) & s
    flag[s] = 1
    memo[s] = ten
    return ten


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
s = (1 << n) - 1
memo = [0] * (1 << n)
flag = [0] * (1 << n)
print(max_ten(s))


Measured memory_bytes: 73820
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#define __max(a,b) (((a) > (b)) ? (a) : (b))
#define __min(a,b) (((a) < (b)) ? (a) : (b))


int main()
{
	int r;
	std::cin >> r;
	std::cout << (int)pow(r, 2) << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

const int MaxN = 100 + 5, MaxV = 100000 + 5;
const long long INF = 0x7F7F7F7F7F7F7F7F;

template <typename Typ>
inline Typ min(Typ x, Typ y) { return x < y ? x : y; }

int N, M;
int W[MaxN], V[MaxN];
long long Dp[MaxV];

void init() {
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= N; ++i)
    scanf("%d %d", &W[i], &V[i]);
}

void solve() {
  memset(Dp, 0x7F, sizeof Dp);
  Dp[0] = 0;
  for (int i = 1; i <= N; ++i)
    for (int j = 100000; j >= V[i]; --j)
      if (Dp[j - V[i]] != INF)
        Dp[j] = min(Dp[j], Dp[j - V[i]] + W[i]);
  for (int j = 100000; j >= 0; --j)
    if (Dp[j] <= M) {
      printf("%d\n", j);
      break;
    }
}

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

Measured memory_bytes: 896
#include<stdio.h>

int main(){
	int n;
	int x = 0, xmax = 0;
	char S[101];
	scanf("%d", &n);
	scanf("%s", S);
	for(int i = 0; i < n; i++){
		if(S[i] == 'I'){
			x++;
			if(x > xmax){
				xmax = x;
			}
		}
		if(S[i] == 'D'){
			x--;
		}
	}
	printf("%d", xmax);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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

	
	int N;
	cin >> N;
	string S;
	cin >> S;


	int OK = 1;
	rep(i, 4) {
		int A[100001];
		A[0] = i % 2;
		A[1] = i / 2 % 2;

		for (int ii = 1; ii < N - 1; ii++) {
			if (S[ii] == 'o') {
				if (A[ii] % 2) A[ii + 1] = A[ii - 1];
				else A[ii + 1] = A[ii - 1] + 1;
			}
			else {
				if (A[ii] % 2) A[ii + 1] = A[ii - 1] + 1;
				else A[ii + 1] = A[ii - 1];
			}
		}

		rep(i, N) A[i] = A[i] % 2;

		OK = 1;
		if (S[N - 1] == 'o') {
			if (A[N - 1]) {
				if (A[N - 2] != A[0]) OK = 0;
			}
			else {
				if (A[N - 2] == A[0]) OK = 0;
			}
		}
		else {
			if (A[N - 1]) {
				if (A[N - 2] == A[0]) OK = 0;
			}
			else {
				if (A[N - 2] != A[0]) OK = 0;
			}
		}

		if (S[0] == 'o') {
			if (A[0]) {
				if (A[N - 1] != A[1]) OK = 0;
			}
			else {
				if (A[N - 1] == A[1]) OK = 0;
			}
		}
		else {
			if (A[0]) {
				if (A[N - 1] == A[1]) OK = 0;
			}
			else {
				if (A[N - 1] != A[1]) OK = 0;
			}
		}

		if (OK) {
			rep(i, N) {
				if (A[i]) cout << 'S';
				else cout << 'W';
			}
			cout << endl;
			break;
		}
	}

	if (OK == 0) co(-1);
	Would you please return 0;
}

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

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

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF = 1e9;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

vector<vector<int>> G;
vector<int> deg;
int N;
   
bool get_path(int v, vector<int> &vis, vector<int> &path, set<int> &path_set)
{
    vis[v] = true;

    bool left = false;
    for (auto u : G[v]) {
        if (!vis[u] && path_set.count(u) == 0) {
            left = true;

            path.push_back(u);
            path_set.insert(u);
            if (get_path(u, vis, path, path_set)) return true;
            path.pop_back();
            path_set.erase(u);
        }
    }
    if (!left) return true;
    vis[v] = false;

    return false;
}

int main()
{
    ios::sync_with_stdio(false);

    int M;
    cin >> N >> M;

    G.resize(N);
    deg.resize(N);

    rep(i, M) {
        int A, B;
        cin >> A >> B;
        A--, B--;
        deg[A]++, deg[B]++;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    vector<int> ans, vis(N);
    set<int> path_set;
    ans.push_back(0);
    path_set.insert(0);
    get_path(0, vis, ans, path_set);
    reverse(ALL(ans));
    get_path(0, vis, ans, path_set);

    cout << ans.size() << endl;
    rep(i, ans.size()) {
        if (i > 0) cout << " ";
        cout << ans[i] + 1;
    }
    cout << endl;
}


Measured memory_bytes: 22136
gets.to_i.times do
  n, k = gets.split.map(&:to_i)
  homes = gets.split.map(&:to_i)

  if homes.size <= k
    puts 0 
    next
  end

  if k == 1
    puts homes.last - homes.first
    next
  end

  diff = homes.each_cons(2).map do |l, r|
    r - l
  end


  minus = diff.sort.reverse[0..(k-2)].inject(:+)
  puts homes.last - homes.first - minus
end

Measured memory_bytes: 20068
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc_168_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int K = Convert.ToInt32(Console.ReadLine());
            string S = Console.ReadLine();

            int len = S.Length;

            if (len <= K)
            {
                Console.WriteLine(S);
            }
            else
            {
                Console.WriteLine(S.Substring(0, K) + "...");
            }

            Console.Read();
        }
    }
}


Measured memory_bytes: 27512
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void){
	int a,b,c,d,e,f;
	a=b=c=d=e=f=0;
	double x=0.0f;
	double y=0.0f;
	while(scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) != EOF){
		x = (c*e-f*b)/(double)(a*e-b*d);
		y = (c*d-f*a)/(double)(b*d-e*a);
		x = (double)floor((x * 1000 + 0.5))/1000;
		y = (double)floor((y * 1000 + 0.5))/1000;
		printf("%.3f %.3f\n", x, y);
	}
	return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"

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

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UI;

using namespace std;


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

	int n;
	cin >> n;

	string s;
	vector<int> abc('z' - 'a' + 1, INT_MAX);

	REP(i, n)
	{
		cin >> s;

		for (char j = 'a'; j <= 'z'; ++j)
		{
			abc[j - 'a'] = (int)min((int)count(s.begin(), s.end(), j), abc[j - 'a']);
		}
	}

	for (size_t i = 0; i < abc.size(); ++i)
	{
		for (int j = 0; j < abc[i]; ++j)
		{
			cout << (char)('a' + i);
		}
	}

	cout << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define vi vector<int>
#define pb(a) push_back(a)
using namespace std;

typedef long long ll;

typedef pair<ll,int> P1;
typedef pair<int,P1> P2;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

#define MAX_N 100002

map<int,int> dp[MAX_N];
vector<edge> G1[MAX_N],G2[MAX_N],G3[1000002];
int dp1[MAX_N];
priority_queue<P2,vector<P2>,greater<P2>> que;

P1 a[200001]={};

int main() {
	int n;
	cin>>n;
	ll p;
	cin>>p;
	ll t=p-1;
	ll m=2;

	rep(i,n-1){
		cin>>p;
		if(p>m){
			t+=(p-1)/m;
		}
		if(p==m)m++;
	}
	cout<<t<<endl;
	return 0;
}


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

int main() {
  int N; cin >> N;
  int total, max_;
  total = max_ = 0;
  rep(i,N) {
    int L; cin >> L;
    max_ = max(L,max_);
    total += L;
  }
  cout << (max_ < total - max_ ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])

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

int main()
{
	char field[3][3];
	while(true){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				cin >> field[i][j];
				if(field[i][j] == '0')
					return 0;
			}
		}
		bool flag = false;
		for(int i=0;i<3;i++){
			if(field[i][1] == field[i][0] && field[i][1] == field[i][2] && field[i][1] != '+'){
				cout << field[i][1] << endl;
				flag = true;
				break;
			}
			if(field[1][i] == field[0][i] && field[1][i] == field[2][i] && field[1][i] != '+'){
				cout << field[1][i] << endl;
				flag = true;
				break;
			}
		}
		if(flag)
			continue;
		if(((field[1][1] == field[0][0] && field[1][1] == field[2][2]) || (field[1][1] == field[2][0] && field[1][1] == field[0][2])) && field[1][1] != '+'){
			cout << field[1][1] << endl;
			continue;
		}
		cout << "NA" << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
#include <stdlib.h> 
struct Node
{
    int value;
    Node *prev,*next;
};
/*void init()*/
//{
    //node = (Node *)malloc(sizeof(Node));
    //node->prev = node;
    //node->prev = node;
    //return;
/*}*/
void insert(Node *head, int val)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->value = val;
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
} 
Node *listSearch(Node *head, int val)
{
    Node *cur = head->next;
    while(cur!=head && cur->value!=val)
    {
        cur = cur->next;
    }
    return cur;
}
void deleteNode(Node *node, Node *head)
{
    if(node==NULL) return;
    if(node==head) return;
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
    return;
}
void deleteFirst(Node *head)
{
    deleteNode(head->next,head);
    return;
}
void deleteLast(Node *head)
{
    deleteNode(head->prev,head);        
    return;
}


void print(Node *head)
{
    Node *cur = head->next;
    while(cur!=head)
    {

        printf("%d",cur->value);
        cur = cur->next;
        if (cur==head) break;
        printf(" ");
    }
    printf("\n");
    return;
}

int main()
{
    int n;
    char com[20];
    int val;
    Node *node;
    node = (Node *)malloc(sizeof(Node));
    node->prev = node;
    node->next = node;
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s %d",com,&val);
        if (com[0]=='i')
        { 
            insert(node, val); 
        } else if (com[0]=='d')
        { 
            if (strlen(com)>6)
            { 
                if (com[6]=='F')
                { 
                    deleteFirst(node); 
                }else if (com[6]=='L')
                {
                    deleteLast(node);
                }
            } else
            {
                deleteNode(listSearch(node,val),node);
            }
        }
    }
    print(node);
    return 0;
}

Measured memory_bytes: 33812
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int a[51], b[51];
    int c[51], d[51];
    rep(i, N) cin >> a[i] >> b[i];
    rep(i, M) cin >> c[i] >> d[i];
    rep(i, N) {
        int idx = 0;
        rep(j, M) {
            if (abs(a[i] - c[j]) + abs(b[i] - d[j]) < abs(a[i] - c[idx]) + abs(b[i] - d[idx])) {
                idx = j;
            }
        }
        cout << idx + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_set>
# include <unordered_map>
using namespace std;


int n;
long long a[100005];
long long dp[100005][2];



int main(int argc, const char * argv[]) {
#ifdef __APPLE__
    freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    dp[1][0] = a[1];
    dp[1][1] = -a[1];
    for (int i = 2; i <= n; ++i) {
        dp[i][0] = max(dp[i - 1][0] + a[i], dp[i - 1][1] - a[i]);
        dp[i][1] = max(dp[i - 1][0] - a[i], dp[i - 1][1] + a[i]);
    }
    cout << dp[n][0] << '\n';
}



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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  ll l,r;cin>>l>>r;
  ll res=3000;
  for(ll i=l;i<r;i++){
    for(ll j=i+1;j<=r;j++){
      ll t = (i*j) % 2019;
      res=min(res, t);
      if(res==0)break;
    }
    if(res==0)break;
  }
  cout<<res<<endl;

  return 0;
}


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

int main(){
  int n;	cin >> n;
  vector<int>	a(n);
  rep(i,n)	cin >> a[i];
  
  int c=0;
  int max=0;
  bool ok=true;
  rep(i,n){
    if(a[i]==1)	ok=false;
    if(a[i]!=max+1)	continue;
    c++;
    max++;
  }
  if(ok){
    cout << -1;
    return 0;
  }
  cout << n-c;
}

Measured memory_bytes: 3996