akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=200005;

int n,k;
int dp[N],f[N],g[N],a[N];
char s[N];

int main(){
	scanf("%s",s+1); n=strlen(s+1);
	dp[n+1]=1; f[n+1]=n+2;
	for (int i=1;i<=26;i++) a[i]=n+1;
	for (int i=n;i;i--){
		g[i]=1;
		a[s[i]-'a'+1]=i;
		for (int j=2;j<=26;j++)
			if (dp[a[j]+1]<dp[a[g[i]]+1]) g[i]=j;
		dp[i]=dp[a[g[i]]+1]+1; f[i]=a[g[i]];
	}
	k=1;
	while (k<=n){
		printf("%c",g[k]+'a'-1);
		k=f[k]+1;
	}
	return 0;
} 

Measured memory_bytes: 2816
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define Set(i, v) memset(i, v, sizeof i)

using namespace std;

const int N = 200010;

int n, m;
map<int, int> M;

int main(){
	scanf("%d", &n);
	For(i, 1, n){
		int x;
		scanf("%d", &x);
		++M[x];
	}
	scanf("%d", &m);
	For(i, 1, m){
		int x;
		scanf("%d", &x);
		if(M[x] > 0) --M[x];
		else{
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}

Measured memory_bytes: 9600
//
//  main.cpp
//  TestC
//
//  Created by CHEN SINYU on 2020/02/22.
//  Copyright © 2020 CHEN SINYU. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <math.h>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
using namespace std;
typedef long long ll;
 
vector<pair<int, int>> to[100010];
bool visited[100010];
ll dist[100010];
ll gcd(ll a, ll b)
{
   if (b == 0)
   {
       return a;
   }
    return gcd(b, a%b);
}
void dfs(int now, ll d) {
  visited[now] = true;
  dist[now] = d;
  for (auto p : to[now]) {
    if (visited[p.first]) continue;
    dfs(p.first, d + p.second);
  }
}
vector<int>ans(10005,0);
void f(ll n){
    for (ll x = 1; x*x<n;x++){
        for (ll y = 1; y*y<n;y++){
            for (ll z = 1; z*z<n;z++){
                ll v = (x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(z*x);
                if(v<10005) ans[v]++;
            }
        }
    }
}
int find(ll k) {
    ll tag = 7777777;
    int cnt = 0;
    cout << tag%k << endl;
    while (tag%k) {
        cnt++;
        tag/=10;
        cout << tag << endl;
        
    }
    return cnt;
}
 
int main() {
    int n=0,x=0,t=0;
    cin >> n>> x>> t;
    int c = n/x;
    if(n%x) {
        c++;
        cout << c*t<< endl;
    } else {
        cout << c*t<< endl;
    }
    return 0;
}


Measured memory_bytes: 6024
#include<stdio.h>

int main()
{
	int n;
	scanf("%d",&n);
	char ch;
	int a=0,b=0,c=0,d=0;
	for(int i=1;i<=n*2;i++){

		scanf("%c",&ch);
		if(ch=='W'){
			a=1;
		}
		else if(ch=='G'){
			b=1;
		}
		else if(ch=='P'){
			c=1;
		}
		else if(ch=='Y'){
			d=1;
		}
		

	}
	int e=a+b+c+d;
	//printf("%d\n",e);
	switch (e){
		case 4:
		printf("Four\n");
		break;
		case 3:
		printf("Three\n");
		break;
		case 2:
		printf("Two\n");
		break;
		case 1:
		printf("One\n");
		break;
	}


	return 0;
}

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

int main() {
	string input; cin >> input;
	for (int i=0; i<input.length(); i++) {
		input[i] -= 3;
		if (input[i] < 'A') input[i] += 26;
	}
	cout << input << endl;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
typedef pair <int,int> pii;
int N, M;
vector <pii> bomb;
vector <pii> edge[200005];
int xors[100005];
bool vis[100005];
vector <int> lists;

int dfs(int v){
    vis[v] = true;
    int ans = xors[v];
    for (pii e: edge[v]){
        if (!vis[e.first]){
            int res = dfs(e.first);
            if (res == 1){
                lists.push_back(e.second);
            }
            ans ^= res;
        }
    }
    return ans;
}

bool cmp(pii a, int b){
    return a.first < b;
}

int main() {
    cin >> N >> M;
    int a, b;
    for (int i=0; i<N; i++){
        scanf("%d %d", &a, &b);
        bomb.push_back({a,b});
    }
    sort(bomb.begin(), bomb.end());
    int l, r;
    for (int i=0; i<M; i++){
        scanf("%d %d", &a, &b);
        l = lower_bound(bomb.begin(), bomb.end(), a, cmp) - bomb.begin();
        r = lower_bound(bomb.begin(), bomb.end(), b+1, cmp) - bomb.begin();
        edge[l].push_back({r, i+1});
        edge[r].push_back({l, i+1});
    }
    xors[0] = bomb[0].second;
    for (int i=1; i<N; i++){
        xors[i] = bomb[i-1].second ^ bomb[i].second;
    }
    xors[N] = bomb[N-1].second;
    memset(vis, false, sizeof(vis));
    for (int i=0; i<N; i++){
        if (!vis[i]){
            int res = dfs(i);
            if (res == 1){
                cout << "-1\n";
                return 0;
            }
        }
    }
    cout << lists.size() << endl;
    sort(lists.begin(), lists.end());
    for (int q: lists){
        printf("%d ", q);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 17652
N,Y=map(int,input().split())

for a in range(N+1):
  for b in range(N-a+1):
    c = N - a - b
    if (10000*a + 5000*b + 1000*c) == Y:
      print(a,b,c,sep=' ')
      exit()
    
print(-1,-1,-1,sep=' ') 

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
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; }
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(){
    ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    vector<ll> a(n);
    vector<ll> a_plus, a_minus;
    rep(i,n) {
        cin >> a[i];
        if(a[i] > 0) a_plus.push_back(a[i]);
        if(a[i] <= 0) a_minus.push_back(-a[i]);
    }
    sort(a_plus.rbegin(), a_plus.rend());
    sort(a_minus.rbegin(), a_minus.rend());
    mint ans=1;
    if(n==k) {
        rep(i,n) ans*= a[i];
        cout << ans << endl;
        return 0;
    } else if(a_plus.size() == 0 && k%2 == 1) {
        rep(i,k) ans*=-a_minus[a_minus.size() - i - 1];
    } else {
        int rem = k;
        int plus_idx = 0;
        int minus_idx = 0;
        if(k%2==1) {
            rem--;
            plus_idx++;
            ans*=a_plus[0];
        }
        while(rem>0) {
            if(plus_idx+1 > a_plus.size()) {
                ans*=a_minus[minus_idx];
                ans*=a_minus[minus_idx+1];
                minus_idx+=2;
            } else if(minus_idx+1 > a_minus.size()) {
                ans*=a_plus[plus_idx];
                ans*=a_plus[plus_idx+1];
                plus_idx+=2;
            } else {
                if(a_plus[plus_idx]*a_plus[plus_idx+1] > a_minus[minus_idx]*a_minus[minus_idx+1]) {
                    ans*=a_plus[plus_idx];
                    ans*=a_plus[plus_idx+1];
                    plus_idx+=2;
                } else {
                    ans*=a_minus[minus_idx];
                    ans*=a_minus[minus_idx+1];
                    minus_idx+=2;
                }
            }
            rem-=2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 6944
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include <set>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define PRIME1 99999883
#define PRIME2 99999893
#define EPS 0.00000001
using namespace std;

int main(){

	char buf[51],left,right;
	scanf("%s",buf);

	left = buf[0];

	for(int i = 0; buf[i] != '\0';i++){
		right = buf[i];
	}

	if(left == 'x' && right == 'x')printf("x\n");
	else{
		printf("o\n");
	}

    return 0;
}

Measured memory_bytes: 3156
#include<stdio.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
int countprime(int num);
int main(void){
    int n;
    int i;
    int cnt=0;
    int num;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&num);
        if(countprime(num))
            cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}
int countprime(int num){
    int i;
    if(num==2)
        return TRUE;
    else if(num<2 || num%2==0)
        return FALSE;
    for(i=3;i<=sqrt(num);i+=2)
        if(num%i==0)
            return FALSE;
    return TRUE;
}

Measured memory_bytes: 596
#define _CRT_SECURE_NO_WARNINGS
#pragma _attribute_((optimize("-O2")))
#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <cstdio>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <time.h>
#include <iomanip>
#define Endl endl

//#define Local

using namespace std;

bool chk(long long a, long long b)
{
	if (a < b)
		return 0;
	long long t = a | b;
	if (t == a)
		return 1;
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input1.txt", "r", stdin);
	//freopen("output1.txt", "w", stdout);

	long long n, k;
	cin >> n >> k;
	vector<pair<long long, long long> >all;
	for (int i = 0; i < n; i++)
	{
		long long a, b;
		cin >> a >> b;
		all.push_back({ a,b });
	}
//	sort(all.begin(), all.end());

	long long fd = k;

	queue<int> can;
	int cont = 0;
	while (fd)
	{
		if (fd & 1)
			can.push(cont);
		cont++;
		fd >>= 1;
	}

	long long ma = 0;
	for (int i = 0; i < n; i++)
	{
		if (chk(k, all[i].first))
			ma += all[i].second;
	}
	while (!can.empty())
	{
		int t = can.front();
		can.pop();
		long long s = 0;
		long long tmp = k - (long long)(pow(2, t));
		tmp |= (long long)(pow(2, t) - 1);
		for (int i = 0; i < n; i++)
		{
			if (chk(tmp, all[i].first))
				s += all[i].second;
		}
		ma = max(ma, s);
	}

	cout << ma << endl;

#ifdef Local
	cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
	return 0;
}

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

int main()
{
  int w, a, b;
  cin >> w >> a >> b;
  int ans = max(a, b) - (w + min(a, b));
  if(ans < 0) ans =0;
  cout << ans << endl;
  

  return 0;
}


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

int main(void) {
    int N=0;
    std::cin >> N;

    std::vector<int> X(N);
    for (int i=0; i< N; i++) {
        std::cin >> X[i];
    }

    std::sort(X.begin(), X.end());

    std::vector<long long int> a(100);
    for (int P = 0; P < 101; P++) {
        a[P] = 0;
        for (int v = 0; v < N; v++) {
            a[P] += (X[v] - P) * (X[v] - P);
        }
    }
    std::sort(a.begin(), a.end());
    std::cout << a[0] << std::endl;
}

Measured memory_bytes: 256
mod = 10 ** 9 + 7

S = input()
N = len(S)

ans = 0
cnt = 0
length = N - 1
for s in S:
    if s == '1':
        ans += pow(2, cnt, mod) * pow(3, length, mod)
        ans %= mod
        cnt += 1
    length -= 1
ans += pow(2, cnt, mod)
ans %= mod

print(ans)


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

typedef long long ll;
typedef long double ld;

#define deb(x) cerr << #x << ":" << x << "\n"

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        ll n, i, j, s, e, ans = 0;
        cin >> n;
        vector<vector<ll>> se(10, vector<ll>(10));
        for (i = 0; i < 10; i++)
        {
            for (j = 0; j < 10; j++)
                se[i][j] = 0;
        }
        for (i = 1; i <= n; i++)
        {
            j = i;
            e = j % 10;
            while (j >= 10)
                j /= 10;
            s = j;
            se[s][e]++;
        }
        for (i = 0; i < 10; i++)
        {
            for (j = 0; j < 10; j++)
            {
                ans += (se[i][j] * se[j][i]);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define pi pair<int,int>
#define pd pair<ld,ld>
#define ft first
#define sd second
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define FOR(i,a,b) for(int i=(a); i<=(b);i++)
#define F(i,a,b) FOR(i,(a),(b)-1)
#define REV(i,a,b) for(int i=(a); i>=(b);i--)
#define VI vector<int>
#define VPI vector<pi>
#define VPD vector<pd>
#define PI 3.14159265
#define all(x) (x).begin(), (x).end()
#define sz(a) (int)((a).size())
#define int long long

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
	while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
mt19937 r(chrono::steady_clock::now().time_since_epoch().count());
int rand_range(int a, int b)
{
	assert(a<=b);
	return a+r()%(b-a+1);
}
const long long K = 1000;
const long long KK = K*K;
const long long MIL = KK*K;
const long long INF = MIL*MIL;
const long long MOD = MIL+7;
const long long N = 2e6 + 10, M=10;

void solve(){
    int a, b;
    cin>>a>>b;
    cout<<max(a+b, max(a-b, a*b));
}

int32_t main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	cerr.tie(0);
	cout<<setprecision(9)<<fixed;
	cerr<<setprecision(6)<<fixed;
	int test = 1, f;
    //cin>>test;
	F(_test, 0, test){
        //cout<<"Case #"<<_test + 1<<": ";
		solve();
//		if(_test == 1)
//            return 0;
	}
}
/*
1
WSSWW
*/


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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N;
	cin >> N;
	cout << N / 3 << endl;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FOR(i) for(cin>>i;i>0;i--)
#define elif else if
#define pb push_back
#define ll long long
#define mp make_pair
#define all(x) x.begin(),x.end()
#define re(x) {cout<<x<<endl;return 0;}
//#define x first
//#define y second

using namespace std;
int k,i=1;
int main()
{
	cin>>k;
	while(1)
	{
		rep2(j,1,10)
		{
			queue<vector<int> >a;
			vector<int>tp;tp.pb(j);
			a.push(tp);
			while(!a.empty())
			{
				tp=a.front();
				a.pop();
				if(tp.size()==i)
				{
					if(k==1)
					{
						rep(n,i) cout<<tp[n];
						cout<<endl;
						return 0;
					}
					else k--;
				}
				elif(tp[tp.size()-1]==0)
				{
					tp.pb(0);a.push(tp);
					tp[tp.size()-1]=1;a.push(tp);
				}
				elif(tp[tp.size()-1]==9)
				{
					tp.pb(8);a.push(tp);
					tp[tp.size()-1]=9;a.push(tp);
				}
				else
				{
					tp.pb(tp[tp.size()-1]-1);a.push(tp);
					tp[tp.size()-1]++;a.push(tp);
					tp[tp.size()-1]++;a.push(tp);
				}
			}
		}
		i++;
	}
	return 0;}

Measured memory_bytes: 1456
#include <stdio.h>
#include <stdlib.h>
 
void merge_sort(int x[], int n)
{
	static int y[200001] = {};
	if (n == 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p] < x[q])? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, K, A[200001];
	scanf("%d %d", &N, &K);
	for (i = 1; i <= N; i++) scanf("%d", &(A[i]));
	
	int count[200001] = {}, ans = 0;
	for (i = 1; i <= N; i++) count[A[i]-1]++;
	merge_sort(count, N);
	for (i = 0; i < N - K; i++) ans += count[i];
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
char sh[100001];
bool same[100001];
int n;
void ok()
{
	for(int i=1;i<=n;i++)
	{
		cout<<sh[i];
	}
//	cout<<" "<<sh[n+1]<<sh[n+2];
	cout<<endl;
	exit(0);
}
void check(char a,char b)
{
	sh[1]=a;
	sh[2]=b;
	for(int i=2;i<=n+1;i++)
	{
		if((sh[i]=='S'&&same[i]==1)||sh[i]=='W'&&same[i]==0)
		{
			if(sh[i-1]=='S')
			{
				sh[i+1]='S';
			}
			else
			{
				sh[i+1]='W';
			}
		}
		else
		{
			if(sh[i-1]=='S')
			{
				sh[i+1]='W';
			}
			else
			{
				sh[i+1]='S';
			}
		}
	}
	if(!(sh[n+1]==sh[1]&&sh[n+2]==sh[2]))
	{
		return;
	}
	if(sh[n]=='S'&&same[n]==1&&sh[1]==sh[n-1])
	{
		ok();
	}
	else if(sh[n]=='S'&&same[n]==0&&sh[1]!=sh[n-1])
	{
		ok();
	}
	else if(sh[n]=='W'&&same[n]==1&&sh[1]!=sh[n-1])
	{
		ok();
	}
	else if(sh[n]=='W'&&same[n]==0&&sh[1]==sh[n-1])
	{
		ok();
	}
//	cout<<sh[n+1]<<" "<<sh[1]<<"        "<<sh[n+2]<<" "<<sh[2]<<endl;
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char ch;
		cin>>ch;
		if(ch=='o')
		{
			same[i]=1;
		}
		else
		{
			same[i]=0;
		}
	}
	same[n+1]=same[1];
	same[n+2]=same[2];
	check('S','S');
	check('S','W');
	check('W','S');
	check('W','W');
	cout<<-1<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iterator>
#include <typeinfo>
using namespace std;


// define list


namespace  math{
    const double PI = 3.14;
    const int INF = 1000000007;
    int GCM(int a,int b); //最大公約数
    int LCM(int a,int b); //最小公倍数
    int Pemu(int n,int r); //順列
    int Comb(int n,int m); //組み合わせ
    
    int GCM(int a,int b){
        if(a<b){
            swap(a,b);
        }
        int r = a%b;
        while (r!=0)
        {
            a=b;
            b=r;
            r=a%b;
        }
        return b;
    }

    int LCM(int a,int b){
        return a*(b/GCM(a,b));
    }

    int Pemu(int n,int r){
        int ans = n;
        for(int i=1;i<r;i++){
            ans*=(ans-i);
        }
        return ans;
    }

    int Comb(int n,int m){
        int a=n,b=m;
        for(int i=1;i<m;i++){
            a *= (a-i);
        }
        for(int i=1;i<m;i++){
            b *= (b-i);
        }
        
        return a/b;
    }
}

namespace SubLib{
    #define int long long
    #define double long double
    #define incin(n) int (n); cin >> (n);
    #define incin2(a,b) int a,b; cin >> a >> b; 
    #define rap(n,i) for(int (i) = 0;i<(n);(i)++)
    #define input(n,v) (v) = SubLib::Input((n),(v))
    #define all(v) (v).begin(),(v).end()
    using intv = vector<int>;
    using strv = vector<string>;
    using charv = vector<char>;
    template <class T1>
    using pvec = vector<pair<T1,T1>>;
    template <typename T> vector<T> Input(int n,vector<T> v){
        for(int i=0;i<n;i++){
            cin >> v.at(i);
        }
        return v;
    }
}

using namespace math;
using namespace SubLib;

signed main(){
    incin(n);
    intv p(n);
    int cost = 0;
    rap(n,i){
        cin >> p.at(i);
        cost += p[i];
    }   
    sort(all(p));
    cout<<cost-p[n-1]/2<<endl;
    return 0;
}

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

int main() {
  string s;
  int start, end;
  cin >> s;
  for (int i=0; i<s.size(); i++)
    if (s.at(i) == 'A') {
      start = i;
      break;
    }
  for (int i=s.size()-1; i>=0; i--)
    if (s.at(i) == 'Z') {
      end = i;
      break;
    }
  cout << end - start + 1 << endl;
}

Measured memory_bytes: 640
from collections import Counter
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
pq = []
if n == 1:
    print(1)
    exit()
for i in range(n):
    for j in range(n):
        r = (xy[i][0]-xy[j][0],xy[i][1]-xy[j][1])
        if i!=j:
            pq.append(r)
#print(pq)
ans = Counter(pq).most_common()
print(n-ans[0][1])

Measured memory_bytes: 39664
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#define REP(i, n) for(int i=0; i<(n); i++)
#define FOR(i, a, n) for(int i=(a); i<(n); i++)
using namespace std;

int main(){
    long long int W,H,x,y;
    cin>>W>>H>>x>>y;
    double ans = (double)(W*H)/2.0;
    int n;
    if((double)x==(double)W/2.0 && (double)y==(double)H/2.0) n=1;
    else n=0;
    printf("%.10f %d\n", ans, n);
    return 0;
}

Measured memory_bytes: 256
N,M = map(int, raw_input().split())
a = [0]*M
b = [0]*M
for i in range(M):
  a[i],b[i] = map(int, raw_input().split())
  a[i] -= 1
  b[i] -= 1

A = [[] for _ in range(N)]
B = [[] for _ in range(N)]
for i in range(M):
  A[a[i]] += [i]
  B[b[i]] += [i]

ans = 0
F = [False]*M
T = []
for i in range(N):
  for t in B[i]:
    if not F[t]:
      ans += 1
      for x in T:
        F[x] = True
      T = []
  for t in A[i]:
    T += [t]
print ans


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

#define FOR(i,N) for(int i=0;i<N;i++)
#define ROF(i,N) for(int i=N-1;i>=0;i--)
#define ROF1(i,a,b) for(int i=(b);i>=(a);i--)
#define FOR1(i,a,b) for(int i=(a);i<=(b);i++)
#define FORi(i,a,b,c) for(int i=(a);i<=(b);i+=(c))

#define read freopen("IN.txt","r",stdin)
#define write freopen("OT.txt","w",stdout)
#define fastread {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define mem(a,b)          memset(a,b,sizeof(a))
#define EPS 1e-9
#define PI              acos(-1.0)
#define INF             2e16

#define ll              long long
#define ull             unsigned long long
#define ft              first
#define sd              second
#define bn              begin
#define en              end
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define pll             pair<LL,LL>
#define all(x) x.begin(), x.end()


#define dbg(args...) {cerr<<"-->";debugger::call(#args,args);cerr<<"\n";}
struct debugger {
    static void call(const char* it) {}
    template<typename T, typename ... aT>
    static void call(const char* it, T a, aT... rest) {
        string b;
        for (; *it&&*it != ','; ++it) if (*it != ' ')b += *it;
        cerr << b << "=" << a << " ";
        call(++it, rest...);
    }
};

int main()
{
#ifdef SunWalker
    //read;
   //write;
#endif

     int n,a[100010],last=LONG_MAX,c=-1,mx=0;
     cin>>n;
     FOR(i,n)
     {
          cin>>a[i];
          if(a[i]<=last)c++;
          else c=0;
          last = a[i];
          mx = max(mx,c);
     }

     cout<<mx<<"\n";
return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll n, k;
  cin >> n >> k;
  ll ans = 1;
  while(true) {

    if (pow(k, ans) - 1 >= n) break;
    ans++;

  }
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 256
n, m = gets.strip.split.map(&:to_i)
tab = gets.strip.split.map(&:to_i)
pos = false
for i in 0...(n - 1) do
    if tab[i] + tab[i + 1] >= m
        puts("Possible")
        pos = true
        for j in 0...i do
            puts j + 1
        end
        j = n - 2
        while j >= i do
            puts j + 1
            j -= 1
        end
        break
    end

end
if !pos
    puts ("Impossible")
end


Measured memory_bytes: 12812
from collections import deque

H,W=map(int,input().split())
field=[]
dist=[[-1]*W for _ in range(H)]
que=deque()

for i in range(H):
    tmp=list(input())
    for j in range(W):
        if tmp[j]=="#":
            dist[i][j]=0
            que.append([i,j])
    field.append(tmp)

DX=[1,0,-1,0]
DY=[0,1,0,-1]
ans=0
while que:
    y,x=map(int,que.popleft())
    ans=dist[y][x]
    for dx,dy in zip(DX,DY):
        nx=x+dx
        ny=y+dy
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

print(ans)


Measured memory_bytes: 210944
def f_a():
    s = input()
    c, l, ans = 0, [], 0
    for i in range(1, len(s)):
        c += 1
        if s[i-1]!=s[i]:
            l.append(c); c = 0
    l.append(c+1)

    if s[-1]=="<":
        ans += sum(range(l[-1]+1))
        l.pop()

    while len(l)>1:
        a, b = l[-1], l[-2]
        ans += sum(range(a)) + sum(range(b))
        ans += max(a, b)
        l.pop(); l.pop()

    if len(l)>0:
        ans += sum(range(l[-1]+1))

    print(ans)


if __name__ == "__main__":
    f_a()


Measured memory_bytes: 6300
#include<iostream>
#include<queue>
using namespace std;
int n,a[1<<17],p[1<<17],c[1<<17];
int d[1<<17];
int dfs(int u)
{
	c[u]=1;
	if(a[u]==0)
	{
		c[u]=2;
		return p[u]=u;
	}
	else
	{
		int v=u+a[u];
		if(c[v]==2)
		{
			c[u]=2;
			return p[u]=p[v];
		}
		else if(c[v]==1)
		{
			c[u]=2;
			return p[u]=-1;
		}
		else
		{
			p[u]=dfs(v);
			c[u]=2;
			return p[u];
		}
	}
}
main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		if(!p[i])
		{
			dfs(i);
		}
		d[i]=1e9;
	}
	priority_queue<pair<int,int> >P;
	P.push({0,1});
	d[1]=0;
	while(!P.empty())
	{
		int c=-P.top().first,u=P.top().second;
		P.pop();
		for(int i=1;i<=6;i++)
		{
			if(u+i>n||p[u+i]<0)continue;
			int ne=c+1;
			int v=p[u+i];
			if(d[v]>ne)
			{
				d[v]=ne;
				P.push({-ne,v});
			}
		}
	}
	cout<<d[n]<<endl;
}



Measured memory_bytes: 5876
#include <stdio.h>

void
calc_line_params(double x1, double y1, double x2, double y2, double *ap, double *bp, double *cp)
{
    *ap = y1 - y2;
    *bp = x2 - x1;
    *cp = y1*x2 - y2*x1;
}

/*
 * Determinant for maxrix:
 *   |a  b|
 *   |d  e|
 */
double
det_for(double a, double b, double d, double e)
{
    return a*e - b*d;
}

void
calc_cross_point(double a, double b, double c, double d, double e, double f, double *cxp, double *cyp)
{
    double det = det_for(a, b, d, e);
    *cxp = (c*e - b*f) / det;
    *cyp = (a*f - c*d) / det;
}

int
judge_cross_point_is_valid(double x1, double y1, double x2, double y2, double x3, double y3, double xp, double yp)
{
        double a, b, c, d, e, f, cx, cy;

        calc_line_params(x1, y1, x2, y2, &a, &b, &c);
        calc_line_params(x3, y3, xp, yp, &d, &e, &f);

        if (!det_for(a, b, d, e)) return 0;
        calc_cross_point(a, b, c, d, e, f, &cx, &cy);

        if ((x1 < cx) && (x2 < cx)) return 0;
        if ((cx < x1) && (cx < x2)) return 0;
        if ((y1 < cy) && (y2 < cy)) return 0;
        if ((cy < y1) && (cy < y2)) return 0;
        return 1;
}

int
main(int argc, char *argv[])
{
    double x1, y1, x2, y2, x3, y3, xp, yp;

    while (EOF != scanf("%lf %lf %lf %lf %lf %lf %lf %lf\n", &x1, &y1, &x2, &y2, &x3, &y3, &xp, &yp)) {
        if (judge_cross_point_is_valid(x1, y1, x2, y2, x3, y3, xp, yp)
            && judge_cross_point_is_valid(x2, y2, x3, y3, x1, y1, xp, yp)
            && judge_cross_point_is_valid(x3, y3, x1, y1, x2, y2, xp, yp)
            ) {
            puts("YES");
            continue;
        }
        puts("NO");
    }

    return 0;
}

Measured memory_bytes: 616
#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5;
struct food {
	int a, b;
	bool operator<(const food &rhs) const { return a + b < rhs.a + rhs.b; }
} f[N];
int n;
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fw (i, 0, n) cin >> f[i].a >> f[i].b;
	sort(f, f + n);
	reverse(f, f + n);
	int guy1 = 0, guy2 = 0;
	fw (i, 0, n) {
		if (!(i & 1)) guy1 += f[i].a;
		else guy2 += f[i].b;
	}
	cout << guy1 - guy2;
	return 0;
}


Measured memory_bytes: 1792
def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

    dp = [0] * (N+1)
    dp[0] = 1

    ai = 0
    for i in range(N):
        if ai < M and A[ai] == i+1:
            dp[i+1] = 0
            ai += 1
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    # print(dp)
    return dp[N]


if __name__ == "__main__":
    M = 0

    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]

    ans = typical_stairs(N, M, A)
    print(ans)


Measured memory_bytes: 7844
#include <bits/stdc++.h>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 
int main()
{
  string S;
  cin >> S;

  int n = 0,s = 0,w = 0,e = 0;
  REP(i,S.size()){
    if(S.at(i) == 'N'){
      n++;
    }
  }
  REP(i,S.size()){
    if(S.at(i) == 'S'){
      s++;
    }
  }
  REP(i,S.size()){
    if(S.at(i) == 'W'){
      w++;
    }
  }
  REP(i,S.size()){
    if(S.at(i) == 'E'){
      e++;
    }
  }

  if((n!=0&&s==0)||(n==0&&s!=0)){
    cout << "No" << endl;
  }else if((e!=0&&w==0)||(e==0&&w!=0)){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

A.sort()
res = 0
ans = 0
for i in range(N):
    res += A[i][1]
    if M-res == 0:
        ans += A[i][0]*A[i][1]
        print(ans)
        break
    elif M-res > 0:
        ans += A[i][0]*A[i][1]
    else:
        res -= A[i][1]
        ans += A[i][0]*(M-res)
        print(ans)
        break

Measured memory_bytes: 27760
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define sz(x) int(x.size())

typedef long long ll;

using namespace std;

static const int MAX = 100001;

int main(int argc, const char * argv[]) {
    // input from txt
    
    /////////
    //write//
    /////////
    
    ll l, r;
    cin >> l >> r;
    if(r-l>2019){
        cout << 0 <<endl;
        return 0;
    }
    
    ll mi = 2019;
    
    for(ll i = l; i<=r-1; i++){
        for(ll j = i+1; j<=r; j++){
            mi = min((i*j)%2019, mi);
        }
    }
    
    cout << mi << endl;
    
    return 0;
}




Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int temp;
    int count =0;
    for(int i=0;i<n;i++){
        scanf("%d",&temp);
        if(temp>=k){
            count++;
        }
    }
    printf("%d",count);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;int s[200001];
int main(){
	
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&s[i]);
	}
	sort(s,s+n);
	for(int i=0;i<n-1;i++){
		if(s[i]==s[i+1]){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	return 0; 
	
} 

Measured memory_bytes: 1024
N = int(input())
c = 'R' + input() + 'W'

left = 0
right = N + 1
count = 0

while left <= right:
    if c[left] == 'W' and c[right] == 'R':
        count += 1
        left += 1
        right -= 1
    if c[left] == 'R':
        left += 1
    if c[right] == 'W':
        right -= 1

print(count)

Measured memory_bytes: 70456
n, k = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
ans = 0
z = list(zip(a, b))
for x, y in z:
    if (k | x) == k:
        ans += y
for i in range(30):
    if (k >> i) & 1:
        res = 0
        t = ((k >> (i + 1)) << (i + 1)) + (1 << i) - 1
        for x, y in z:
            if (t | x) == t:
                res += y
        ans = max(ans, res)
print(ans)


Measured memory_bytes: 56464
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int h, w;
    while(cin >> h >> w, h){
        map<int, int> a, b;
        for (int i = 0; i < h; ++i) {
            int x; cin >> x;
            a[x]++;
        }
        for (int i = 0; i < w; ++i) {
            int x; cin >> x;
            b[x]++;
        }
        for (auto &&j : b) {
            a[j.first] = max(j.second, a[j.first]);
        }
        int ans = 0;
        for (auto &&i : a) {
            ans += i.first*i.second;
        }
        cout << ans << "\n";
    }
    return 0;
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>
#include <utility>
#include <sstream>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) x.begin(),x.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

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

    if(s.at(0) == s.at(1) and s.at(0) == s.at(2))
        cout << "Yes" << endl;
    else if(s.at(1) == s.at(2) and s.at(1) == s.at(3))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
        

}

Measured memory_bytes: 3604
n = int(input())
A = [int(x) for x in input().split()]
sum_start_plus = 0
sum_start_minus = 0
ans_start_plus = 0
ans_start_minus = 0
flag_start_plus = True
flag_start_minus = True

# プラス始まりの場合を計算する
for a in A:
    sum_start_plus += a
    if flag_start_plus:
        flag_start_plus = False
        if sum_start_plus > 0:
            continue
        else:
            ans_start_plus += abs(1 - sum_start_plus)
            sum_start_plus = 1
    else:
        flag_start_plus = True
        if sum_start_plus < 0:
            continue
        else:
            ans_start_plus += abs(-1 - sum_start_plus)
            sum_start_plus = -1

# マイナス始まりの場合を計算する
for a in A:
    sum_start_minus += a
    if flag_start_minus:
        flag_start_minus = False
        if sum_start_minus < 0:
            continue
        else:
            ans_start_minus += abs(-1 - sum_start_minus)
            sum_start_minus = -1
    else:
        flag_start_minus = True
        if sum_start_minus > 0:
            continue
        else:
            ans_start_minus += abs(1 - sum_start_minus)
            sum_start_minus = 1

print(min(ans_start_plus, ans_start_minus))

Measured memory_bytes: 63856
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n,a,b,c=LI()
l=[I() for _ in range(n)]

def dfs(cnt,aa,bb,cc):
  if cnt==n:
    if aa==0 or bb==0 or cc==0:
      return inf
    return abs(aa-a)+abs(bb-b)+abs(cc-c)-30

  aaa=dfs(cnt+1,aa+l[cnt],bb,cc)+10
  bbb=dfs(cnt+1,aa,bb+l[cnt],cc)+10
  ccc=dfs(cnt+1,aa,bb,cc+l[cnt])+10
  ddd=dfs(cnt+1,aa,bb,cc)
  return min(aaa,bbb,ccc,ddd)

print(dfs(0,0,0,0))


Measured memory_bytes: 10712
def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


X = int(input())
i = X
while True:
    if is_prime(i):
        print(i)
        break
    else:
        i += 1


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define pb push_back
#define int long long int
#define f(i,a,b) for (int i= a; i <b; ++i)
using namespace std;

vector<int> v[100005];
int mod=1000000007;
int dp[100005][2];
int solve(int src,int c,int p)
{

    if(dp[src][c]!=-1)
        return dp[src][c];
    int ans=0;
    int w1=1;
    for(int i=0;i<v[src].size();i++)
    {
        if(v[src][i]!=p)
            w1=(w1*solve(v[src][i],0,src))%mod;
    }
     ans+=w1;
     if(c==0)
     {
         int w2=1;
         for(int i=0;i<v[src].size();i++)
        {
          if(v[src][i]!=p)
            w2=(w2*solve(v[src][i],1,src))%mod;
        }
        ans=(ans+w2)%mod;
     }
     return dp[src][c]=ans;
}
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(dp,-1,sizeof dp);
    int n,x,y;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    cout<<solve(1,0,-1);
}



Measured memory_bytes: 14208
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;

    cin >> n;

    vector<pair<int, int> > r;
    vector<pair<int, int> > b;

    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        r.push_back(make_pair(x, y));
    }
    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        b.push_back(make_pair(x, y));
    }

    
    int count = 0;

    //sort(r.begin(), r.end());
    sort(b.begin(), b.end());
    for(int j = 0; j < b.size(); j++){
        int max_y = -1;
        int index;
        for(int i = 0; i < r.size(); i++){
            if(b[j].first > r[i].first and b[j].second > r[i].second){
                if(max_y < r[i].second){
                    max_y = r[i].second;
                    index = i;
                }
            }
        }
        if(max_y != -1){
            r.erase(r.begin()+index);
            count++;
        }
    }

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

    return 0;

}

Measured memory_bytes: 256
import java.util.*;
import java.text.DecimalFormat;
// warm-up
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), no = N, i = 0;
		double min = Double.MAX_VALUE, s = 0, t = 0;
		double[] a = new double[N];
		while (N-->0) {
			double b = sc.nextDouble();
			a[i++] = b; s+=b;
		}
		N = no;
		for (i=N-1; i>0; i--) {
			t+=a[i];
			if (Math.abs(s-(2*t))<min) min = Math.abs(s-(2*t));
		}
		System.out.println(new DecimalFormat("#").format(min));
		sc.close();		
	}

	public static void main(String args[]) {
		solve();
	}

}

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

using namespace std;

long long DP[100010];

int main()
{
   int n;
   int x,y,k;
   cin >> n >> k;
   for (int a=1;a<=n;a++)
   {
       cin >> x >> y;
       for (int i=100000;i>=x;i--)
       {
           DP[i]=max(DP[i],DP[i-x]+y);
       }
   }
  
   cout << DP[k];

}



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

using namespace std;

int main(void) {
	int r, D, x2000;
	cin >> r >> D >> x2000;
	int x = x2000;
	for(int i = 0; i < 10; ++i) {
		x = r * x - D;
		cout << x << '\n';
	}
	return 0;
}



Measured memory_bytes: 384
def show_ary(n,a)
	(n-1).times do |i|
		print a[i]
		print " "
	end
	print a[n-1]
	print "\n"
end

num = gets.to_i
num -= 1
a = gets.split(" ").map{|item| item.to_i}
show_ary(num+1,a)
num.times do |i|
	v = a[i+1]
	j = i
	if a[j] > v
		while j >= 0 && a[j] > v do
			a[j+1] = a[j]
			j -= 1
			a[j+1] = v
		end
		show_ary(num+1,a)
	elsif
		show_ary(num+1,a)
	end
end



Measured memory_bytes: 6876
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll i, temp,t, n,j, a[200600], ans, sum;
bool cond;
map<ll,ll>C;
map<ll,pair<ll,ll> >Ans;
vector<int>V;
bool vis[200010];
string s;
int main()
{
    //I am Monim, a tiny creature of Allah
    cin >> n;
    for(i=0;i<n;i++)
    {
        cin >> temp;
        a[i] = temp;
        if(!vis[temp])
        {
            V.push_back(temp);
            vis[temp] =  true;
        }
        C[temp]++;
    }
    sum = 0;
    for(i=0;i<V.size();i++)
    {
        sum += (C[V[i]]*(C[V[i]]-1))/2;
    }
    for(i=0;i<n;i++)
    {
        cout << sum - (C[a[i]]*(C[a[i]]-1))/2 + ((C[a[i]]-1)*(C[a[i]]-2))/2 << endl;
    }
    return 0;
}


Measured memory_bytes: 13252
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int N, D;
    cin >> N >> D;
    int x = 2 * D + 1;
    int ans = (N + x - 1) / x;
    cout << ans << '\n';
    return 0;
}

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

vector<ll> to[100010];
ll cn,n;
vector<bool> seen(8,0);

void dfs(ll v,ll dep=1){
    if(dep==n){
        cn++;
        return;
    }
    seen.at(v)=1;
    for(auto nv:to[v]){
        if(seen.at(nv)==0)dfs(nv,dep+1);
    }
    seen.at(v)=0;
}

int main(){
    ll m;cin>>n>>m;
    rep(i,0,m){
        ll a,b;cin>>a>>b;
        a--;b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    dfs(0);
    cout<<cn<<endl;
}







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

typedef long long ll;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> A(N, vector<ll>(N));
    rep(i, N) {
        rep(j, N) {
            cin >> A[i][j];
        }
    }
    mcf_graph<ll, ll> graph(N * N + N * 2 + 3);
    rep(i, N) {
        graph.add_edge(N * N + N * 2, N * N + i, K, 0);
        graph.add_edge(N * N + i, N * N + N * 2 + 2, K * N, 1e9);
        graph.add_edge(N * N + N + i, N * N + N * 2 + 1, K, 0);
        graph.add_edge(N * N + N * 2 + 2, N * N + N + i, K * N, 0);
        rep(j, N) {
            graph.add_edge(N * N + i, i * N + j, 1, 1e9 - A[i][j]);
            graph.add_edge(i * N + j, N * N + N + j, 1, 0);
        }
    }
    graph.flow(N * N + N * 2, N * N + N * 2 + 1, N * K);
    auto edges = graph.edges();
    vector<string> ans2(N, "");
    rep(i, N) {
        rep(j, N) {
            ans2[i].push_back('.');
        }
    }
    ll ans = 0;
    for (auto e : edges) {
        if (e.to >= N * N) continue;
        if (e.flow == 0) continue;
        int i0 = e.to / N, j0 = e.to % N;
        ans += A[i0][j0];
        ans2[i0][j0] = 'X';
    }
    cout << ans << "\n";
    rep(i, N) {
        cout << ans2[i] << "\n";
    }
}

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

int mod = 1'000'000'007;
map<pair<long long, long long>, long long> mp;

long long solve(long long s, long long x){
    if (mp[{s, x}] != 0) return mp[{s, x}];
    if (s < 0 || x < 0) return 0;
    if (s == 0 && x == 0) return 1;
    if (s == 1 && x == 1) return 2;
    long long tmp = solve(s / 2, x / 2);
    if (x >= 2) tmp += solve(s / 2, (x - 2) / 2);
    if (s >= 1 && x >= 1) tmp += solve((s - 1) / 2, (x - 1) / 2);
    tmp %= mod;
    mp[{s, x}] = tmp;
    return tmp;
}

int main(){
    long long n;
    cin >> n;
    cout << solve(n, n) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}

int main(){
	int X;read(X);
	int ans=(X/500)*1000;X%=500;
	ans+=(X/5)*5;write(ans);
	return 0;
}


Measured memory_bytes: 256
//Om Sree Sai Ram
#include "bits/stdc++.h"
using namespace std;

void min_self(long long &a,long long b)
{
  a = min(a,b);
}
const long long nax = 1e18+5;
int main() 
{


int n;
cin>>n;
vector<long long> ar(n);
for(int i=0;i<n;i++)
{
  cin>>ar[i];
}   

vector<vector<long long>> dp(n,vector<long long>(n,nax));
//dp[i][j] represents the answer for index i to j. 
vector<long long> sum(n+1);
for(int i=1;i<=n;i++)
  {
    sum[i]+=sum[i-1]+ar[i-1];
  }
for(int len=1;len<=n;len++)
{
  for(int i=0;i<n;i++)
  {
    int l = i;
    int r = i+len-1;
    if(r>=n)
    {
      continue;
    }
    if(l==r)
    {
      dp[l][r] = 0;
      continue;
    }
    long long cost = sum[r+1]-sum[l];
    for(int p=l;p<r;p++)
    {
      min_self(dp[l][r],cost+dp[l][p]+dp[p+1][r]);
    } 
  }
}

cout<<dp[0][n-1]<<endl;

}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, n, m) for (int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

typedef long long ll;

/**
 * 不安なら ll を使う.
 * 小数は double を忘れない.
 * nC2の求め方 (1/2)*n*(n-1)
 * vector<型> 変数名(要素数, 初期値)
 * pair<型, 型> 変数名
 * map<型, 型> 変数名  // 連想配列
 * priority_queue<型> 変数名  // 最大値から出てくるヒープ
 * 比較するときは型まで注意
 * 区間の計算は累積和
*/

/* ===== コーナーケースに気をつけろ ===== */

int main()
{
    ll N;
    cin >> N;
    map<ll, ll> mp;
    vector<ll> A(N);
    REP(i, N)
    {
        ll a;
        cin >> a;
        A.at(i) = a;
        mp[a]++;
    }

    ll sum = 0;

    for (pair<ll, ll> p : mp)
    {
        sum += p.second * (p.second - 1) / 2;
    }

    REP(i, N)
    {
        ll ans = sum;
        ll a = A.at(i);
        ll b = mp[a];
        ans -= b * (b - 1) / 2;
        ans += (b - 1) * (b - 2) / 2;
        cout << ans << endl;
    }

    // for (pair<int, int> p : mp)
    // {
    //     cout << p.first << p.second << endl;
    // }
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  map<int, int>a;
  int ai;
  long si=0;
  for(int i=0; i<n; i++){
    cin >> ai;
    a[ai]++;
    si+=ai;
  }
  int q;
  cin >> q;
  int bi, ci;
  for(int i=0; i<q; i++){
    cin >> bi >> ci;
    si += long(ci-bi)*a[bi];
    a[ci]+=a[bi];
    a[bi]=0;
    cout << si << endl;
  }
  return 0;
}

Measured memory_bytes: 7556
a,b,c,x,y=map(int, input().split())
max_=max(x,y)
cost=100000000000
for i in range(max_+1):
  cost_=i*2*c+a*max(0,x-i)+b*max(0,y-i)
  cost=min(cost_,cost)
print(cost)

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

int main(void){
  long int a, b, x;

  cin >> a >> b >> x;

  long int ar, br;

  br = b / x;

  if(a == 0) ar = -1;
  else ar = (a-1) / x;

  cout << br - ar << endl;

  return 0;
}


Measured memory_bytes: 764