akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
//---------------

const int N=16;
const int inf=1e9;
int n,m;
int g[N][N],f[1<<N][N],cost[1<<N][N],del[1<<N],sum[1<<N];

void upd(int &a,int b) {
	a=min(a,b);
}
int lb(int x) {return x&(-x);} 
int calc(int u) {
	if(u==0) return 0;
	if(sum[u]!=-1) return sum[u];
	int &res=sum[u];
	int y=lb(u);
	return res=del[y]+calc(y^u);
}

int main() {
	while(~scanf("%d%d",&n,&m)) {
		///init
		memset(g,0,sizeof(g));
		memset(cost,0,sizeof(cost));
		rep(i,0,1<<n) rep(j,0,n) f[i][j]=inf;
		///read
		rep(i,0,m) {
			int u,v,c;scanf("%d%d%d",&u,&v,&c);
			--u;--v;
			g[u][v]=g[v][u]=c;
		}
		///solve
		rep(i,0,1<<n) rep(j,0,n) rep(k,0,n) if(i>>k&1) cost[i][j]+=g[j][k];
		f[1][0]=0;
		rep(i,0,1<<n) rep(j,0,n) if(f[i][j]!=inf) {
			memset(sum,-1,sizeof(sum));
			rep(k,0,n) if(!(i>>k&1)) del[1<<k]=cost[i^(1<<j)][k];
			rep(k,0,n) if(!(i>>k&1) &&g[j][k]) upd(f[i|(1<<k)][k],f[i][j]+del[1<<k]);
			int x=((1<<n)-1)^i;
			for(int k=x;k;k=(k-1)&x) upd(f[i|k][j],f[i][j]+calc(k));
		}
		///print
		printf("%d\n",f[(1<<n)-1][n-1]);
	}
	return 0;
}

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

#define ll long long

using namespace std;

const int MAXN = 100010;
const int MAXM = 100010;
const int MAXINT = 2147483647;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int n, m, k;
int ans, tot, cnt;

int a[MAXN];
int head[MAXN];

string s;

inline int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
	while ('0' <= ch && ch <= '9') {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
	return s * f;
}

struct edge {
	int to, next;
}e[MAXN << 1];

void add_edge(int x, int y) {
	e[++tot].to = y;
	e[tot].next = head[x];
	head[x] = tot;
	return;
}

int main(){
	int T;
	ios::sync_with_stdio(false);
	scanf("%d%d%d", &a[1], &a[2], &a[3]);
	sort(a + 1, a + 4);
	if (a[1] == a[2] && a[1] == 5 && a[3] == 7) printf("YES\n");
	else printf("NO\n");
	return 0;
}

/*

*/

//Flakire
//Lord Wang
//yxm9
//akdxl
//WYXak
//MifafaOvO
//AKarry5037
//deakX
//xyx
//Fraggay



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
int main() {
    long n, r0, r1, r, max, min;
    std::cin >> n; // skip
    std::cin >> r0 >> r1;
    max = r1 - r0;
    min = std::min(r0, r1);
    while (std::cin >> r) {
        max = std::max(max, r - min);
        min = std::min(min, r);
    }
    std::cout << max << std::endl;
}



Measured memory_bytes: 3096
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = set([_I() for i in range(M)])

#  if M != 0:
#      # 連続した壊れた段がある場合は0
#      B = [i for i in A]
#      B.remove(B[0])
#      B.append(10**15+100)
#      diffs = [b - a for a, b in zip(A,B)]
#      #  print(diffs)

#      if any(i == 1 for i in diffs):
#          # 隣同士なので0
#          print(0)
#          exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i not in A:
        # i段目が障害のときは0になっているので飛ばす
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[N])


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

int main(){
  int64_t a,b,c,d,z;
  cin >> a>>b>>c>>d;
  
  int64_t x = a*c;
  int64_t y = b*d;
  int64_t h = a*d;
  int64_t k = b*c;
  int64_t max1=max(x,y);
  int64_t max2=max(h,k);
  cout << max(max1,max2) << endl;
  //return 0;
}


Measured memory_bytes: 3628
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
Min = min(a) + min(b)
for i in range(M):
    x, y, c = map(int, input().split())
    Min = min(Min, a[x-1]+b[y-1]-c)
print(Min)

Measured memory_bytes: 18608
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin >> n;
    int a,b;
    cin >> a >> b;
    int in[n];
    int first = 0,second = 0 , third = 0;
    for(int i = 0 ; i < n ; i++)
    {
        cin>>in[i];
        if(in[i]<=a)
            first++;
        else
            if(in[i]>a && in[i]<=b)
                second++;
        else
            third++;
    }
    int answer = min(first,min(second,third));
    cout << answer << "\n";

return 0;}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define endl '\n'
#define pb push_back
#define mod 1000000007
#define mp make_pair
#define pi acos(-1)
#define line cout<<"----------------------------"<<endl
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
using namespace std;
vector<ll >v;
int d;
ll dp[10009][2][105];
ll call(ll ind, bool check,ll sum)
{
    if(ind==-1) return sum==0;
    ll cnt=0;
    ll limit=check? (v[ind]):9;
    ll &ret=dp[ind][check][sum];
    if(ret!=-1 and !check) return ret;
    for(ll i=0;i<=limit;i++)
    {
        bool ck=(i==v[ind])? check:0;
        cnt+=call(ind-1,ck,(sum+i)%d);
        cnt%=mod  ;
    }
    if(!check) ret=cnt; ///is used so that we can call this function without memset for another query
    return cnt;
}
ll  get(string x)
{
    for(int i=x.size()-1;i>=0;i--) v.pb(x[i]-'0');

    return call((int)v.size()-1,1,0);
}
int  main()
{
    memset(dp,-1,sizeof dp);
    string a;
    cin>>a>>d;
    ll ans=get(a)-1;
    ans=(ans+mod)%mod ;
    cout<<ans<<endl;
}


Measured memory_bytes: 17792
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int n, i, x, y, sol;
char s[2005];
int num[2005], viz[2005], d[2005], mx[2005];
vector<int> v[2005];
void dfs(int nod){
    viz[nod] = 1;
    num[nod] = s[nod] - '0';
    mx[nod] = 0;
    int i, vecin, x = 0;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(viz[vecin] == 1){
            continue;
        }
        dfs(vecin);
        d[vecin] += num[vecin];
        mx[vecin] += num[vecin];
        mx[nod] += mx[vecin];
        num[nod] += num[vecin];
        if(d[x] < d[vecin]){
            x = vecin;
        }
    }
    d[nod] = max(0, d[x] - (mx[nod] - mx[x]) );
    if(d[nod] == 0 && mx[nod] % 2 == 1){
        d[nod] = 1;
    }
}
int main(){
    cin>> n;
    cin>> s + 1;
    for(i = 1; i < n; i++){
        cin>> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    sol = 10000000;
    d[0] = -1;
    for(i = 1; i <= n; i++){
        memset(viz, 0, sizeof(viz));
        dfs(i);
        if(d[i] == 0){
            sol = min(sol, mx[i]);
        }
    }
    if(sol == 10000000){
        cout<< -1;
    }
    else{
        cout<< sol / 2;
    }
}


Measured memory_bytes: 512
str = input().split('i')
flag = True

for s in str[0:-1]:
  if(flag):
    if(s != 'h'):
      print('No')
      flag = False

if(flag):
  if(str[len(str)-1] != ''):
    print('No')
    flag = False
if(flag):
  print('Yes')

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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long K){
    vector<i64> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout << a[K - 1] << endl;
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long K;
    scanf("%lld",&K);
    solve(K);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef long long ll;
typedef pair<ll,ll> P;
const int INF=INT_MAX / 3;
const ll LINF=LLONG_MAX / 3LL;
#define CONST 1000000007
#define EPS (1e-8)
#define PB push_back
#define MP make_pair
#define sz(a) ((int)(a).size())
#define reps(i,n,m) for(int i=(n);i<int(m);i++)
#define rep(i,n) reps(i,0,n)
#define SORT(a) sort((a).begin(),(a).end())
ll mod(ll a,ll m){return (a%m+m)%m;}
int dx[9]={0,1,0,-1,1,1,-1,-1,0},dy[9]={1,0,-1,0,1,-1,1,-1,0};
ll n,m;

bool es[10][10];
ll dp[1 << 10][10];

string toB(int x, int r = 8) {
  string s = "";
  while(r-->0) {
    s = ((x % 2 == 0)? "0" : "1") + s;
    x /= 2;
  }
  return s;
}

ll rec(int s, int x) {
  //printf("(%s, %d)\n", toB(s,n).c_str(), x);
  if(!(s & (1<<x))) return 0;
  if(dp[s][x] > 0) return dp[s][x];
  dp[s][x] = 0;
  int nx = s & (~(1 << x));
  rep(i, n) {
    if(!es[x][i]) continue;
    dp[s][x] += rec(nx, i);
  }
  //cout << toB(s, n) <<" "<< x <<" "<< dp[s][x] <<endl;
  return dp[s][x];
}


int main(){
  cin >> n >> m;
  rep(i, m) {
    int a,b;
    cin >> a >> b ;
    es[--a][--b] = true;
    es[b][a] = true;
  }

  dp[1][0] = 1;

  ll ans = 0;
  reps(i, 1,n) {
    ans += rec((1<<n)-1, i);
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long int
#define mp(a, b) make_pair(a, b)
using namespace std;
typedef pair<ll, ll> pairs;
typedef pair<ll, pairs> tpl;
ll dp[101][100001], a[100001], b[100001], n;
ll getans(ll i, ll w)
{
	if (w < 0)
		return INT_MIN;
	if (i == n || w == 0)
		return 0;
	if (dp[i][w] != -1)
		return dp[i][w];
	return dp[i][w] = max(getans(i + 1, w - a[i]) + b[i], getans(i + 1, w));
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll w;
	cin >> n >> w;
	for (ll i = 0; i < n; i++)
		cin >> a[i] >> b[i];
	memset(dp, -1, sizeof(dp));
	cout << getans(0, w);
}

Measured memory_bytes: 82468
#include <stdio.h>

int main(void){
    int n,i,j;
    scanf("%d",&n);
    int day[n-1];
    for(i=0;i<n;i++){
        scanf("%d",&day[i]);
    }
    for(j=0;j<n;j++){
        printf("%d",day[n-(j+1)]);
        if(j != n-1)printf(" ");
    }
printf("\n");
    return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define INF 100000
using namespace std;

int main(){
	//int town[11][11];
	int to,from,cost;
	int n;
	while(1){
		cin>>n;
		if(!n)break;
		int maxsize=0;
		int dt[11][11];
		for(int i=0;i<11;i++){
			for(int j=0;j<11;j++){
				//town[i][j]=INF;
				if(i!=j)dt[i][j]=INF;
				else dt[i][j]=0;
				//out<<"yeah "<<i<<" "<<j<<endl;
			}
		}
		for(int i=0;i<n;i++){
			cin>>to>>from>>cost;
			//cout<<"analize"<<endl;
			dt[to][from]=cost;
			dt[from][to]=cost;
			maxsize=max(maxsize,to);
			maxsize=max(maxsize,from);
		}
		for(int k=0;k<maxsize+1;k++){
			for(int i=0;i<maxsize+1;i++){
				for(int j=0;j<maxsize+1;j++){
					dt[i][j]=min(dt[i][j],dt[i][k]+dt[k][j]);
				}
			}
		}
		int sum[maxsize+1];
		rep(i,maxsize+1){
			sum[i]=0;
			rep(j,maxsize+1){
				sum[i]+=dt[i][j];
			}
			//cout<<sum[i]<<" ";
		}
		//cout<<endl;
		int ans[maxsize+1];
		rep(i,maxsize+1)ans[i]=sum[i];
		sort(sum,sum+maxsize+1);
		//cout<<sum[0]<<endl;
		for(int i=0;i<maxsize+1;i++){
			if(ans[i]==sum[0]){
				cout<<i<<" "<<sum[0];
				break;
			}
		}
		cout<<endl;
		//cout<<"finish"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define N 1000200
using namespace std;
inline int read(){
	int x=0,w=0;char ch=getchar();
	while (!isdigit(ch))w|=ch=='-',ch=getchar();
	while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return w?-x:x;
}
int n,a[N];
signed main(){
	n=read();
	for (int i=1;i<=n;++i)a[i]=read();
	sort(a+1,a+1+n,greater<int>());
	for (int i=1;i<=n;++i)
		if (i+1>a[i+1]){
			int ans=0;
			for (int j=i+1;a[j]==i;++j)ans^=1;
			if (ans||((a[i]-i)&1))puts("First");
			else puts("Second");
			break;
		}
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std; 
int main(){
 ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int n,m,k;
   cin>>n;
   vector<long long int> row(n,0);
   for(int i=0;i<n;i++){
   	cin>>row[i];
   }
   sort(row.begin(),row.end());
   long long int ans=0;
   ans+=row[n-1];
   int g=n-2;
   int i=n-2;
   while(g>0){
   	   ans+=row[i];
   	   g--;
   	   if(g>0){
   	   	ans+=row[i];
		}
		g--;
		i--;
   }
   
   cout<<ans<<"\n";
   return 0;
}

Measured memory_bytes: 4780
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};
using modint = ModInt< int(1e9)+7 >;


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

    modint  ans;
    vector<modint > v(K+1,0);
    REPR(i,K) {
        if (i == 0) break;
        modint  d (K/i);
        v[i] =  d.pow(N);
        auto ni = i * 2;
        while ( ni <= K) {
            v[i] -= v[ni];
            ni += i;
        }
        modint m;
        m =   v[i] * i;
        ans += m;
    }

    cout << ans << endl;

}

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


Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
#define all(a) begin(a),end(a)
#define D1(a) cerr<<#a<<":"<<a<<endl
#define D2(a,b) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<endl
#define D3(a,b,c) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cerr<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl
#define DH(c) do{rep(__i, c.size())cerr<<c[__i]<<(__i==c.size()-1?'\n':' ');}while(0)
#define int ll
signed main()
{
    int N, K; cin >>N>> K;
    vector<int> neg, pos;
    rep(i, N) {
        int a; cin >> a;
        if (a > 0) pos.push_back(a);
        else if (a < 0) neg.push_back(a);
    }
    sort(all(pos));
    sort(all(neg));

    int n_neg = neg.size();
    int n_pos = pos.size();
    int n_zero = N - n_neg - n_pos;

    ll pairs = (ll)N * (N - 1) / 2;
    ll neg_pairs = (ll)n_neg * n_pos;
    ll zero_pairs = (ll)n_zero * (n_zero - 1) / 2 + (ll)n_zero * (N - n_zero);
    ll pos_pairs = (ll)pairs - neg_pairs - zero_pairs;

    ll l = (ll)(-1e18)-1, r = 1e18;
    while (r - l > 1) {
        ll m = l + (r - l) / 2;

        ll cnt = 0;
        if (m < 0) {
            for (auto ne : neg) {
                auto it = lower_bound(all(pos), (m + ne + 1) / ne);
                // if (it == pos.end()) break;
                cnt += distance(it, pos.end());
            }
        } else if (m == 0) {
            cnt = neg_pairs + zero_pairs;
        } else {
            for (auto po : pos) {
                auto it = upper_bound(all(pos), m / po);
                if (it == pos.begin()) break;
                cnt += distance(pos.begin(), it);
                if (po <= *(it-1))
                    cnt -= 1;
            }
            for (auto ne : neg) {
                auto it = lower_bound(all(neg), m / ne);
                cnt += distance(it, neg.end());
                if (ne >= *it)
                    cnt -= 1;
            }
            cnt /= 2;
            cnt += neg_pairs + zero_pairs;
        }
//D4(l, r, m, cnt);

        if (cnt >= K) {
            r = m;
        } else {
            l = m;
        }
    }

    cout << r << endl;
}


Measured memory_bytes: 2420
#include <iostream>
using namespace std;
int main() {
    int a, b, c, d, l, r;
    cin >> a >> b >> c >>d;
    l=a+b; r=c+d;
    if(l>r) cout << "Left" << endl;
    else if(l==r) cout << "Balanced" << endl;
    else if(l<r) cout << "Right" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
main()
{
    long long int x,c=0,i;
    cin>>i;
    for(x=1;x<=i;x++){
        if(x%5==0 || x%3==0) continue;

        else c+=x;
    }
    cout<<c;
}


Measured memory_bytes: 3592
def main():
    R, G, B, N = map(int, input().split())
    ans = 0
    for i in range(N//R+1):
        r = i
        for j in range(((N-R*r)//G)+1):
            g = j
            if N-R*r-G*g >= 0 and (N-R*r-G*g) % B == 0:
                ans += 1
    print(ans)

if __name__=='__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 999999999
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;
bool sosu(int n) {
  if (n <= 1)
    return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0)
      return false;
  return true;
}
int main() {
  int b, ans[4] = {};
  string s;
  char a;
  while (cin >> b >> a >> s) {
    if (s == "A")
      ans[0]++;
    else if (s == "B")
      ans[1]++;
    else if (s == "O")
      ans[3]++;
    else
      ans[2]++;
  }
  rep(i, 4) { cout << ans[i] << endl; }
  return 0;
}

Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int quickpow(int x,int y)
{
	long long res=1,base=x;
	while(y)
	{
		if(y&1)res*=base,res%=mod;
		y>>=1;base*=base,base%=mod;
	}
	return res;
}
int inv(int x){return quickpow(x,mod-2);}
int prod[600002];
int c(int x,int y){return 1ll*prod[x]*inv(prod[x-y])%mod*inv(prod[y])%mod;}
signed main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	prod[0]=1;
	for(int i=1;i<=n*2;i++)
		prod[i]=1ll*prod[i-1]*i%mod;
/*	if(k>=n)
	{
		int ans=0;
		for(int i=1;i<=n;i++)
			ans+=1ll*c(n,i)*c(n-1,i-1)%mod,ans%=mod;
		printf("%d",ans);
		return 0;
	}*/
	int ans=0;
	for(int i=max(n-k,1);i<=n;i++)
		{
			ans+=1ll*c(n,i)*c(n-1,i-1)%mod,ans%=mod;
			
		}
	printf("%d",ans);
	return 0;
}


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

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


int main() {
    int X; cin >> X;
    if(X==3 || X==5 || X==7) cout << "YES" << endl;
    else cout << "NO" << endl;
    
    return 0;
}

Measured memory_bytes: 3540
n = int(input())

a = list(map(int, input().split()))

colors = [0,0,0,0,0,0,0,0,0]

count = 0

def check(x):
	if 1<=x<=399:
		colors[0] += 1
	elif 400<=x<=799:
		colors[1] += 1
	elif 800<=x<=1199:
		colors[2] += 1
	elif 1200<=x<=1599:
		colors[3] += 1
	elif 1600<=x<=1999:
		colors[4] += 1
	elif 2000<=x<=2399:
		colors[5] += 1
	elif 2400<=x<=2799:
		colors[6] += 1
	elif 2800<=x<=3199:
		colors[7] += 1
	else:
		colors[8] += 1

for i in a:
	check(i)

for i in range(8):
	if colors[i] == 0:
		count += 1

color_min = 8 - count
color_max = color_min+colors[8]

if color_min==0:
	color_min = 1

print(color_min,color_max)

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>//random,NULL
#include <string.h>
#include <time.h>
#include <unistd.h>//sleep()
#include <math.h>
#include <stdbool.h>

#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000


long dfs(int index, long left, long *Lv_n, long *Lv_p);


int main(){
  char buf[1024];
  int N;
  long X;

  fgets(buf,sizeof(buf),stdin);
  sscanf(buf, "%d %ld", &N, &X);

  //Lv(n)の層数
  long *Lv_n=(long *)malloc(sizeof(long)*(N+1));
  Lv_n[0]=1;
  srep(i,1,N+1){
    Lv_n[i]=Lv_n[i-1]*2+3;
  }

  //Lv_nのパティの個数
  long *Lv_p=(long *)malloc(sizeof(long)*(N+1));
  Lv_p[0]=1;
  srep(i,1,N+1){
    Lv_p[i]=Lv_p[i-1]*2+1;
  }


  long pathy=dfs(N, X, Lv_n, Lv_p);

  printf("%ld\n", pathy);

  return 0;
}



//左からleft個目までの間にパティがいくつあるか。
long dfs(int index, long left, long *Lv_n, long *Lv_p){
  long res;
  if(left==0){
    //printf("1\n");
    res=0;
  }
  else if(index==0){
    //printf("2\n");
    res=1;
  }
  else{
    long temp=Lv_n[index-1]+2;
    if(left<temp){
      //printf("3\n");
      res=dfs(index-1, left-1, Lv_n, Lv_p);
    }
    else if(left>=temp){
      //printf("4\n");
      res=Lv_p[index-1]+1+dfs(index-1, left-2-Lv_n[index-1], Lv_n, Lv_p);
    }
  }

  return res;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(i,n)         for(int i=0;i<n;i++)
#define Fo(i,k,n)       for(int i=k;i<n;i++) 
#define endl            "\n"
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define vec(x)          vector<x>
#define matrix(x)       vector<vector<x>>
#define mem(a,b)        memset(a, b, sizeof a)
#define vii             vector<pair<int,int>>
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define MOD             998244353
#define deb(x)          cerr <<#x<<" = "<<x<<"\n"
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(v)          v.begin(),v.end()
#define rep(i,a,b)      for (int i = a; i<b; ++i)
#define len(s)          s.length()
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
int power(int a,int b,int m=mod)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}

void angshuGod()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

const int N = 1e5+1;
const double pi = acos(-1);

vi v;
vi dp;

int find(int n){
    if(n<0) return 0;
    if(n==1) return 0;
    if(n==2) return abs(v[1]-v[2]);
    if(n==3) return min(abs(v[1]-v[3]),abs(v[1]-v[2])+abs(v[2]-v[3]));
    if(dp[n] != -1) return dp[n];
    else return dp[n] = min(abs(v[n-1]-v[n])+find(n-1), abs(v[n-2]-v[n])+find(n-2));
}

void solve(){    

    int n;
    cin>>n;

    v.resize(n+1);
    dp.resize(n+1);

    v[0] = 0;
    rep(i,1,n+1) {
        dp[i] = -1;
        cin>>v[i];
    }

    cout<<find(n);
}

 
int32_t main()
{
    angshuGod();

    int t;

    t = 1;
    //cin>>t;

    while(t--){
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 7080
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int A;
  int B;
  int C;
  
  cin >> A >> B >> C;
  
  if ( C>(A-B) ) {
    cout << C-(A-B);
  }
  else {
    cout << 0;
  }
  
}


Measured memory_bytes: 256
// I/O
#include <iostream>
#include <iomanip>

// data structures
#include <set>
#include <queue>
#include <vector>

// manipulations
#include <algorithm>

#define rep(i,n) for(int i=0;i< (n);++i)
#define REP(i,n) for(int i=1;i<=(n);++i)
#define for_lowercase(c) for(int c='a';c<='z';++c)
#define for_uppercase(c) for(int c='A';c<='Z';++c)
#define ALL(a) (a).begin(),(a).end()
using LLI = long long int;
LLI GCD(LLI a,LLI b){ if(a<b) return GCD(b,a); else if(a%b==0) return b; else return GCD(b,a%b); }
LLI LCM(LLI a,LLI b){ return (a/GCD(a,b))*b; }
using VI  = std::vector<LLI>;
using PI  = std::pair<LLI,LLI>;
using VVI = std::vector<VI>;
using VPI = std::vector<PI>;
template<class T> bool is_odd (T x){ return   x%2 ; }
template<class T> bool is_even(T x){ return !(x%2); }
LLI combination(LLI n,LLI k,bool reset=false){
    static VVI C; static LLI n_hashed = -1;
    if(n<0){ std::cerr << "[ERROR] n must be non-negative in combination()" << std::endl; exit(1); }
    if(!(0<=k&&k<=n)){ std::cerr << "[WARNING] k should be in range [0,n] in combination()" << std::endl; return 0; }
    if(n_hashed<n || reset){
        C.resize(n+1);
        for(int i=0;i<=n;++i) C[i].resize(i+1,1); // filled with 1
        for(int i=1;i<=n;++i)for(int j=1;j<i;++j) C[i][j] = C[i-1][j-1] + C[i-1][j];
        n_hashed = n;
    }
    return C[n][k];
}

int main() {
    std::ios::sync_with_stdio(false);
    LLI N,M;
    std::cin >> N;
    std::multiset<LLI> D;
    rep(i,N){
        LLI d;
        std::cin >> d;
        D.insert(d);
    }

    std::cin >> M;
    std::string res = "YES";
    rep(i,M){
        LLI t;
        std::cin >> t;
        auto pos = D.find(t);
        if(pos != D.end()){
            D.erase(pos);
        }else{
            res = "NO";
        }
    }

    std::cout << res << std::endl;
    return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int N,K;
  cin >> N >> K;
vector<int> data(N);
  for(int i=0;i < N;i++){
  cin >> data.at(i);
  }
  if(N%(K-1) == 0){
  if(K == 2){
  cout << N-1;
  }
  else{
  cout << N/(K-1);
  }
  }
  else if(N%(K-1) == 1){
  cout << N/(K-1);
  }
  else{
  cout << N/(K-1)+1;
  }
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a >= 13) {
            System.out.println(b);
            return;
        }
        if (a <= 5) {
            System.out.println(0);
            return;
        }
        System.out.println(b / 2);
    }

}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
#define ll long long
#define inc(a) sort(a.begin(), a.end())
#define dec(a) sort(a.rbegin(), a.rend())
#define loop(n) for(ll i = 0; i<n; i++)
using namespace std;

int main(){
    int n; cin>>n;
    int odds = (n+1)/2;
    double prob = double(odds)/n;
    cout<<prob;
    return 0;
}

Measured memory_bytes: 256
using System;

namespace abc92A
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int A = int.Parse(Console.ReadLine());
            int B = int.Parse(Console.ReadLine());
            int C = int.Parse(Console.ReadLine());
            int D = int.Parse(Console.ReadLine());
            if (A > B)
                A = B;
            if (C > D)
                C = D;
            Console.WriteLine(A + C);
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
 
#define mp make_pair
#define pb push_back
#define ld long double
#define f first
#define s second
const ll N =(1e6) ;
const ll mod = (1e9+7);
 	
 int main(){
 	int dp[100001][3]={};
 	int n; 
 	cin >> n;
 	int a[n] , b[n] , c[n];
 	for (int i = 0; i < n; ++i)
 	{
 		cin >>a[i] >> b[i] >>c[i];
 	}
 
 	 dp[0][0] = a[0];
 	 dp[0][1] = b[0];
 	 dp[0][2] = c[0];
 
 	for (int i = 1; i <n ; ++i)
 	 {
 	 	dp[i][0] = a[i] + max(dp[i-1][1] , dp[i-1][2]);
 	 	dp[i][1] = b[i] + max(dp[i-1][0], dp[i-1][2]);
 	 	dp[i][2] = c[i] + max(dp[i-1][0] ,dp[i-1][1]);
 	 } 
 
 	 cout<<max(dp[n-1][0] , max(dp[n-1][1] , dp[n-1][2]));
 }



Measured memory_bytes: 2560
#include<stdio.h>

int IsPrime(int I) {
	for (int i = 2; i*i <= I; i++) {
		if (I%i == 0)return 0;
	}
	return 1;
}

int main() {
	int N;
	int A[10000];
	int cnt = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
		if (IsPrime(A[i]))cnt++;
	}
	printf("%d\n", cnt);

	return 0;
}


Measured memory_bytes: 2732
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>

using namespace std;


int main()
{
	int A,B,C;
	int ans = 0;
	cin >> A >>B >>C;

	ans = max(C-(A-B),0);

	printf("%d\n", ans);


	return 0;
}



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

def solve():
    """ dp[i+k]を求める方法
    TLE 
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    
    for i in range(0, N-1):
        for k in range(1, K+1):
            if i+k <= N-1:
                dp[i+k]=min(dp[i+k],dp[i]+abs(A[i]-A[i+k]))
            else:
                break
    print(dp[N-1])


def solve2():
    """dp[i]を求める方法
    """
    N,K=list(map(int,input().split()))
    A=list(map(int,input().split()))
    
    INF=float("inf")
    
    dp=[INF]*N
    dp[0]=0
    for i in range(1, N):
        for k in range(1, K+1):
            if i-k >= 0:
                dp[i] = min(dp[i], dp[i-k]+abs(A[i]-A[i-k]))
            else:
                break
    print(dp[N-1])


if __name__ == "__main__":
    solve2()


Measured memory_bytes: 55136
#include<iostream>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<functional>
#include<iterator>
#include<complex>
#include<fstream>
#include<random>
#include<ctype.h>
#include<stdio.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using PII = pair<ll, ll>;
using piii = pair<pii, pii>;
using Pi = pair<int, pii>;
using Graph = vector<vector<int>>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
bool check(int x, int y) {
	if (0 <= x && x<55 && 0 <= y && y<55)return true;
	else return false;
}
const ll INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;

//iの逆元mod inf
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const double PI = 3.14159265358979323846;
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
double Euclidean_distance(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//素因数分解
map<int, int>prime_factor(int n) {
	map<int, int>res;
	for (int i = 2; i*i <= n; ++i) {
		while (n%i == 0) {
			++res[i];
			n /= i;
		}
	}
	if (n != 1)res[n] = 1;
	return res;
}


ll powmod(ll a, ll k, ll mod) {
	ll ap = a, ans = 1;
	while (k) {
		if (k & 1) {
			ans *= ap;
			ans %= mod;
		}
		ap = ap * ap;
		ap %= mod;
		k >>= 1;
	}
	return ans;
}
ll invi(ll a, ll mod) {
	return powmod(a, mod - 2, mod);
}
#define PI 3.14159265358979323846  // 円周率
//逆元Aを足したときのmodで割った余りは
//+=invi(A)
//Yで割ることはY^(10^9+7)-2を掛けることは同値
///////////////////////////////////////
bool is_prime(int n) {
	for (int i = 2; i*i <= n; ++i) {
		if (n%i == 0)return false;
	}
	return n != 1;
}

int main() {
	int n; cin >> n;
	if (n % 1000 == 0) {
		cout << 0 << endl;
	}
	else {
		cout << 1000 - (n % 1000) << endl;
	}
	return 0;
}


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

int main(){
    string x; cin >> x;
    int n; n = x.size();
    int scnt = 0;
    int rans = 0;
    for(int i = 0; i < n; i++){
        if(x[i] == 'S') scnt++;
        if(scnt > 0 && x[i] == 'T'){
            scnt--;
            rans += 2;
        }
    }
    cout << n - rans << endl;
}

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


public class Main {
	public static void main(String[] args){
		InputStreamReader is = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(is);

		int syakkin = 100000;
		int week = 0;

		try {
			week = Integer.parseInt(br.readLine());
		} catch (IOException e) {
			System.out.println("error");
		}
		for(int i=0;i < week ;i++){
			syakkin *= 1.05;
			if(syakkin % 1000 > 0){
				syakkin /= 1000;
				syakkin++;
				syakkin *= 1000;
			}
		}
		System.out.println(syakkin);
	}
}

Measured memory_bytes: 9344
#include<bits/stdc++.h>
using namespace std;
/******** Md-Kamran-Ahmad **********/

#define mid(s,e)        (s+(e-s)/2)
#define rff(a)          freopen((a), "r", stdin);
#define wtf(a)          freopen((a), "w", stdout);
#define YES             cout << "Yes" << endl
#define NO              cout << "No" << endl
#define sin(s)	        getline(cin, s)
#define ll              long long
#define ull             unsigned long long
#define dd              double

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef set<int> si;
typedef map<int,int> mii;
typedef map<long,long> mll;
typedef map<string,int> msi;

const double PI=acos(-1.0);

int re(int n)
{
    ll r=0,x;
    while(n!= 0)
    {
        x=n%10;
        r = 10*r+ x;
        n /= 10;
    }
    return r;
}


int main()
{
    //freopen("A.txt","r",stdin);
    ios_base::sync_with_stdio(0);

    int a;
    cin>>a;
    int k=a/10;
    int kk=a%1000;
    if(k==111 || kk==111)
    {
        YES;
    }
    else if(k==222 || kk==222)
    {
        YES;
    }
   else if(k==333 || kk==333)
    {
        YES;
    }
    else if(k==444 || kk==444)
    {
        YES;
    }
   else  if(k==555 || kk==555)
    {
        YES;
    }
    else if(k==666 || kk==666)
    {
        YES;
    }
    else if(k==777 || kk==777)
    {
        YES;
    }
    else if(k==888 || kk==888)
    {
        YES;
    }
    else if(k==999 || kk==999)
    {
        YES;
    }
    else if(k==000 || kk==00)
    {
        YES;
    }
    else
    {
        NO;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstdio>
#include <queue>
using namespace std;

int cnt = 0;

void merge(vector<int> &v, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  vector<int> l(n1+1);
  vector<int> r(n2+1);
  for(int i=0;i<n1;i++){
    l[i] = v[left + i];
  }
  for(int i=0;i<n2;i++){
    r[i] = v[mid + i];
  }
  l[n1] = 1000000007;
  r[n2] = 1000000007;
  int i=0, j=0;
  for(int k = left;k<right;k++){
    cnt++;
    if(l[i] <= r[j]){
      v[k] = l[i++];
    }else{
      v[k] = r[j++];
    }
  }
}

void mergeSort(vector<int> &v, int left, int right){
  if(left+1 < right){
    int mid = (left + right) / 2;
    mergeSort(v, left, mid);
    mergeSort(v, mid, right);
    merge(v, left, mid, right);
  }
}

int main(void){
  int n;
  cin >> n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin >> v[i];

  mergeSort(v, 0, n);


  for(int i=0;i<n;i++){
    cout << v[i];
    if(i != n-1)
      cout << " ";
  }
  cout << endl;
  cout << cnt << endl;

  return 0;
}

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

int main() {
    int n;
    while (cin >> n, n) {
        vector<long long> v(n);
        for (int i=0; i<n; ++i) {
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        long long sum = 0;
        for (int i=1; i<n; ++i) {
            sum += v[i-1] * (n - i);
        }
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 1288
#include <stdio.h>

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

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

int gcd(int x,int y){
  if(y == 0){
    return x;
  }
  
  if(y > x){
    swap(x,y);
  }
  return gcd(y,x%y);
}

int main(){
  int n,x;
  cin >> n >> x;
  vector<int> cont(n+1);
  
  cont.at(0) = x;
  for(int i = 1 ; i < n+1 ; i++){
    cin >> cont.at(i);
  }
  
  sort(cont.begin() , cont.end());
  
  vector<int> aaa(n);
  for(int i = 0 ; i < n ; i++){
    aaa.at(i) = cont.at(i+1) - cont.at(i);
  }
  
  int ans = aaa.at(0);
  
  for(int i = 1 ; i < n ; i++){
    ans = gcd(ans , aaa.at(i));
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 1024
S = input()
s = S.split()

H1 = int(s[0])
M1 = int(s[1])
H2 = int(s[2])
M2 = int(s[3])
K = int(s[4])

awake_minutes = (H2-H1)*60 + (M2-M1)
study_minutes = awake_minutes - K

print(study_minutes)

Measured memory_bytes: 9212
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <math.h> 

using namespace std;


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

	int n, i, j, k, ans, x, y, xx, yy, t, x0, y0, c;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(n));
	vector<vector<bool>> used(n, vector<bool>(n, false));
	int v[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 };
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) a[i][j] = min(min(i, n - 1 - i), min(j, n - 1 - j));
	}

	ans = 0;
	for (i = 0; i < n * n; i++) {
		cin >> t;
		t--;
		x = t / n; y = t % n;
		ans += a[x][y];

		//cout << t + 1 << "   " << x << " " << y << " = " << a[x][y] << "\n";

		queue<pair<int, int>> q;
		q.push({ x, y });
		x0 = x; y0 = y;
		used[x0][y0] = true;

		while (!q.empty()) {
			x = q.front().first;
			y = q.front().second;
			q.pop();

			if (used[x][y]) c = 0;
			else c = 1;

			for (k = 0; k < 4; k++) {
				xx = x + v[k][0]; yy = y + v[k][1];
				if ((xx >= 0) && (xx < n) && (yy >= 0) && (yy < n) && (a[xx][yy] > c + a[x][y])) {
					a[xx][yy] = c + a[x][y];
					q.push({ xx, yy });
				}
			}
		}	

	}

	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 4220
from collections import Counter

def prime_fact(n):
    P= []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            P.append(i)
            n //= i
    if n != 1:
        P.append(n)
    return P

n = int(input())
cnt = Counter(prime_fact(n))

ans = 0
for c in cnt.values():
  tmp = 1
  while c >= tmp:
    c -= tmp
    ans += 1
    tmp += 1
print(ans)

Measured memory_bytes: 9592
import * as readline from 'readline';

/* ここに処理を書く */
const main = (args: any[]) => {
  const A = args[0],
        B = args[1];
  
  console.log(Math.max(A-2*B, 0));
  return;
}




/* 標準入力処理 */
const stdin = (main: Function) => {
    const args: any[] = [];
    const reader = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });
    reader.on('line', function (line: any) {
        line
            .split(" ")
            .forEach((arg: any) => {
                args.push(isNaN(arg) ? arg : Number(arg));
            });
    });
    reader.on('close', function () {
        main(args);
    });
}
/* 実行 */
stdin(main);


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

/*
#if 0
	手法
	
	縦の道と横の道は、それぞれ2本で片方の辺の長さが定まり、もう片方の辺には影響を与えない。
	そのため、縦の道を2本選ぶのを全てやって、長さiの辺の生成回数x[i]をカウントし、横の道も同様にy[i]とすると、
	x[i]*y[i]が辺の長さiの正方形の数になるため、これを全てのiに対して足せばよい。
	2本道の組み合わせを全て作って各長さを集計して全x[i]を求めるのにO(N^2)、同様に全y[i]を求めるのにO(M^2) N,Mは10^3ちょっとぐらい 
	x[i]*y[i]を足し合わせるのにO(i)かかる iは高々最も遠い道同士の距離なので1500*1000≒10^6
	これらを順次行うのでオーダーは足してO(N^2+M^2+i)、10^6ちょっとぐらいなので解ける

	道路間距離を求めるのに前の距離を利用できたのはよかった。

#endif
*/

int N, M;
int h[1510],w[1510];//問題文に寄せて添え字1スタートなので注意
//入力

const int distantmax=1500*1000;//2本の道の距離のありうる最大値、1500*1000
int x[distantmax + 10] = { 0 };
int y[distantmax + 10] = { 0 };


void solve(){
	for (int i = 0; i < distantmax + 10; i++){
		x[i] = 0;
		y[i] = 0;
	}
	//x[i]とy[i]を求める

	//i番目とj+1番目の道路の間の距離を求める
	for (int i = 1; i <= N; i++){
		int sum = 0;//各iに対し、jを1ずつ増やしてfor文を回すことを利用し、前の計算結果を利用して距離を求めていく
					//これにより、道路間距離を求めるのにforをもう1つ回さないで良くなり、オーダーがN^2
		for (int j = i; j+1 <= N+1; j++){
			sum += h[j];
			x[sum]++;
		}
	}

	for (int i = 1; i <= M; i++){
		int sum = 0;
		for (int j = i; j + 1 <= M+1; j++){
			sum += w[j];
			y[sum]++;
		}
	}

	//x[i]+y[i]を足し合わせて終わり
	//答えの最大値は多めに想定するとできる四角形の数であり、つまり多めに見てN^2*M^2 10^12≒2^40 念のため大きい整数型にしておく
	long long answer = 0;
	for (int i = 1; i <= distantmax; i++){
		answer += x[i] * y[i];
	}
	cout<<answer<<endl;
	return;
}


int main(){
	while (cin >> N >> M && N>0){
		for (int i = 1; i <= N; i++){
			cin >> h[i];
		}
		for (int i = 1; i <= M; i++){
			cin >> w[i];
		}
		solve();
	}

	return 0;
}


Measured memory_bytes: 14804
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define MAXN 100000
int n,d;
int x[11][11];
int check[16001],ans;
int main()
{
	scanf("%d%d",&n,&d);
	int p=1;
	while(p*p<=16000)
	{
		check[p*p]=1;
		p++;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=d;j++)
			scanf("%d",&x[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			int sum=0;
			for(int k=1;k<=d;k++)
			sum+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
			ans+=check[sum];
		}
	printf("%d",ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  int N, K;
  cin >> N >> K;
  double ret = 0;
  for (int i = 1; i <= N; i++)
  {
    double tmp = 1.0 / N;
    int now = i;
    while (now < K)
    {
      now *= 2; // ポイント二倍
      tmp /= 2; // コイン表の確率
    }
    ret += tmp;
  }
  printf("%.12f\n", ret);

  return 0;
}

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

#define int long long 

using namespace std;

void solve()
{
	string s;cin >> s;
	int n=s.size();
	if(s[n-1]=='s'){
		cout << s;
	cout <<"es";
	}
	else
		cout << s << 's' ;
}

int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //int t;cin >> t;while(t--)
    	solve();

    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
 
using namespace std;
 
#define PI 3.14159265358979323846264338327950L
 
vector<long long>A, B;
long long K;
 
 
int main(void) {
 
	long long N, M, tmp, ans = 0, time = 0, total = 0, b_max;
 
 
	cin >> N >> M >> K;
 
	vector<long long> A_sum(N+1,0), B_sum(M+1,0);
 
 
	A_sum.push_back(0);
	for (long long i = 1; i <= N; i++) {
		cin >> tmp;
		A.push_back(tmp);
		A_sum[i] = A_sum[i - 1] + tmp;
	}
 
	B_sum.push_back(0);
	for (long long i = 1; i <= M; i++) {
		cin >> tmp;
		B.push_back(tmp);
		B_sum[i] = B_sum[i - 1] + tmp;
	}
 
	ans = 0;
	long long tmp_m = M ;
	for (long long i = 0; i <= N; i++) {
		for (long long j = tmp_m; j >= 0; j--) {
			if (A_sum[i] + B_sum[j] <= K) {
				if (ans < i + j) {
					ans = i + j;
				}
				tmp_m = j;
				break;
			}
		}
	}
 
	cout << ans << endl;
 
	return 0;
}

Measured memory_bytes: 11536
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int x=sc.nextInt();
			int y=sc.nextInt();
			int s=sc.nextInt();
			if((x==0&&y==0)&&s==0) break;
			int max=0;
			for(int i=0;i<s-1;++i){
				for(int j=0;j<s-1;++j){
					if((((i+1)*(100+x))/100)+(((j+1)*(100+x))/100)==s){
						int num=((i+1)*(100+y))/100+((j+1)*(100+y))/100;
						if(max<num) max=num;
					}
				}
			}
			System.out.println(max);
		}
	}
}


Measured memory_bytes: 29340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;
int a[3][3];
bool aa[3][3];
int main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (c == a[j][k]) aa[j][k] = 1;
            }
        }
    }

    bool f1 = 1, f2 = 1, f = 0;
    for (int i = 0; i < 3; i++) {
        f |= (aa[i][0] && aa[i][1] && aa[i][2]);
        f |= (aa[0][i] && aa[1][i] && aa[2][i]);
        f1 &= aa[i][i];
        f2 &= aa[i][2 - i];
    }
    // for (int i = 0; i < 3; i++) {
    //     for (int j = 0; j < 3; j++) {
    //         cout << aa[i][j];
    //     }
    //     cout << endl;
    // }
    cout << (f||f1||f2 ? "Yes":"No") << endl;
    return 0;
}

Measured memory_bytes: 256