akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long modpow(long long a, long long n)
{
    long long res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    long long n;
    cin >> n;
    long long ans = (modpow(10, n) - modpow(9, n) * 2 + modpow(8, n)) % mod;
    ans = (ans + mod) % mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
//#include<iostream>
#define pb push_back
#define pf push_front


using namespace std;	
typedef long long int lli;

lli n,k,l,m,t,a,b,r,c,temp1,temp2,x,y,temp,q,d,mod=1e9+7,w,p;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>x>>k>>d;
    if(x==0)
    {
    	if(k%2==0)cout<<0<<endl;
    	else cout<<d<<endl;
    }
    else 
    {
    	if(x<0)x=-1*x;
    	lli ci;
    	ci= (x/d);
    	
    	if(ci*d<x)ci++;
    	
    	
    	if(ci>=k)
    	{
    		lli ans=(x-(k*d));
    		if(ans<0)ans=-1*ans;
    		cout<<ans<<endl;
    	}
    	else
    	{
    		lli left = k-ci;
    		lli ans=(x-(ci*d));
    		
    		if(left%2==0)
    		{
    			cout<<abs(ans)<<endl;
    		}
    		else cout<<ans+d<<endl;
    	}
    }
    
    
}

Measured memory_bytes: 3652
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double old;

const int N = 200;

int a[N][N], used[N][N];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    int edges = 0;
    mt19937 rnd(228);
    uniform_int_distribution<> get(0, n - 1);
    while (edges < n - 1) {
        int v = get(rnd);
        int u = get(rnd);
        while (v == u || used[v][u]) {
            v = get(rnd);
            u = get(rnd);
        }
        used[v][u] = used[u][v] = 1;
        string s(n, '0');
        s[v] = s[u] = '1';
        cout << "? " << s << endl;
        int x;
        cin >> x;
        if (x) {
            a[v][u] = a[u][v] = 1;
            ++edges;
        }
    }
    cout << '!';
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i][j]) {
                cout << " (" << i << ',' << j << ')';
            }
        }
    }
    cout << endl;
    return 0;
}

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

using namespace std;

#define inf 1<<30
#define llong long long
#define usd unsigned
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<int, int> P;
typedef struct data{
	int now;
	int cost;
}data;
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};




int main(){
	int a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	cout << min(max(x,y)*c*2, min(min(x,y)*c*2 + (x<y?(y-x)*b:(x-y)*a), x*a+y*b)) << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		
		
		for(int i = 0; i < A.length; i++) {
			A[i] = sc.nextInt();
		}
		
		int count = 0;
		out: while(count >= 0) {
			for(int i = 0; i < A.length; i++) {
				if(A[i] % 2 == 0) {
					A[i] /= 2;
				}else{
					break out;
				}
			}
			count++;
		}
		System.out.println(count);
		
	}

}

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x3fffffffffffffff;
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; }
//template end

vector<int> g[100010]; map<pair<int,int>,int> mp;
int cnt[100010]={},ma=0,ans[100010];
void dfs(int v,int pre,int col){
    if(pre!=-1)ans[mp[{v,pre}]]=col; int nxt=0;
    for(int to:g[v])if(to!=pre){
        if(nxt==col)nxt++;
        dfs(to,v,nxt); nxt++;
    }
}

int main(){
    int n; scanf("%d",&n);
    rep(i,0,n-1){
        int a,b; scanf("%d%d",&a,&b); a--; b--;
        g[a].push_back(b); g[b].push_back(a);
        cnt[a]++; cnt[b]++; mp[{a,b}]=mp[{b,a}]=i;
    }
    rep(i,0,n)chmax(ma,cnt[i]);
    printf("%d\n",ma);
    dfs(0,-1,-1);
    rep(i,0,n-1)printf("%d\n",ans[i]+1);
    return 0;
}

Measured memory_bytes: 19584
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */



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

    ll n, k; cin >> n >> k;
    vector<ll> a(n), f(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> f[i];
    sort(a.begin(), a.end());
    sort(f.rbegin(), f.rend());

    ll sum = accumulate(a.begin(), a.end(), 0);
    //if (sum <= k) { cout << 0 << endl; return 0; };

    ll ng = -1, ok = 1e13;
    auto check = [&](ll mid) {
        if(mid == -1) return false;
        ll cnt = 0;
        rep(i, n) if(a[i]*f[i]>mid) {
            cnt += (a[i]*f[i]-mid + f[i]-1) / f[i];            
        }
        return cnt <= k;
    };
    while(ok-ng > 1) {
        ll mid = (ok+ng) / 2;
        (check(mid)? ok:ng) = mid;
    }
    cout << ok << endl;
    
    return 0;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define drep(i,x,y) for(int i=x; i>=y; --i)

using namespace std;

deque<int> L, R;
int n, ans;
char s[100100];

int main()
{
	scanf("%d%s",&n,s+1);
	drep(i,n,2) if (s[i] == '<') R.push_front(i);
	rep(i,1,n) {
		int res;
		if (s[i] == '>') {
			if (!R.size()) res = n-i+1;
			else if (L.size() >= R.size()) res = n - L[R.size()-1] + 1;
			else res = R[L.size()];
		} else {
			if (!L.size()) res = i;
			else if (L.size() <= R.size()) res = R[L.size()-1];
			else res = n - L[R.size()] + 1;
		}
		ans = max(ans, res);

		if (s[i] == '>') L.push_front(i);
		if (!R.empty() && R.front() == i+1) R.pop_front();
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 3492
import numpy as np

H, N = map(int, input().split())
A = []
B = []

for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
A = np.array(A)
B = np.array(B)
DP = np.zeros(H + 1)

for i in range(1, H + 1):
  DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)

print(int(DP[-1]))



Measured memory_bytes: 27356
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
void Say(bool say, string a = "Yes", string b = "No"){cout << (say ? a : b) << endl;};

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

ll comb(ll n, ll r){
    ll a = 1, b = 1;
    for(ll i = 0; i < r; i++){
        a *= (n - i);
        b *= (i + 1);
        ll c = gcd(a, b);
        a /= c;
        b /= c;
    }
    return a / b;
}

int main(){

    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll>vec(N);
    map<ll, ll>cnt;
    for(ll i = 0; i < N; i++){
        cin >> vec[i];
        cnt[vec[i]]++;
    }
    sort(vec.begin(), vec.end(), greater<ll>());
    ll sum = 0, ans = 0;
    for(ll i = 0; i < A; i++)sum += vec[i];
    if(vec[0] == vec[A - 1]){
        for(ll a = A; a <= B; a++){
            ans += comb(cnt[vec[A - 1]], a);
        }
    }
    else{
        ll a = 0;
        for(ll i = 0; i < A; i++){
            if(vec[i] == vec[A - 1])a++;
        }   
        ans = comb(cnt[vec[A - 1]], a);    
    }
    printf("%.9f\n", 1.0 * sum / A);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main(){
  int W, H, x, y;
  cin >> W >> H >> x >> y;
  cout << fixed << setprecision(9) << (double)W*H/2 << " ";
  if ((double)x == (double)W/2 && (double)y == (double)H/2) cout << "1" << endl;
  else cout << "0" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define M 100
using namespace std;
int a[M+1],b[M+1],n;

void input(void){
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++) scanf("%d",&b[i]);
}

void process(void){
    int i,mx;
    for(i=2;i<=n;i++) a[i]+=a[i-1];
    for(i=n-1;i>=1;i--) b[i]+=b[i+1];
    mx=a[1]+b[1];
    for(i=2;i<=n;i++) mx=max(mx,a[i]+b[i]);
    printf("%d\n",mx);
}

int main(){
    input();
    process();

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <numeric>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define PUSH(n,v) for(int i=0; i<(n); i++) {int j; cin >> j; v.push_back(j);}
#define ALL(v) v.begin(), v.end()
#define print(s) cout << (s) << endl

vector<double> seq;

void solve55(double a) {
    seq.clear();
    seq.push_back(a);
    for (int i = 1; i < 10; i++) {
        if (i % 2 == 1) {
            seq.push_back(seq.back() * 2);
        }else {
            seq.push_back(seq.back() / 3);
        }
    }
    double sum = 0;
    REP(i,10) {
        sum += seq[i];
    }
    printf("%.6f\n", sum);
}

int main() {
    double a;
    while(cin >> a) {
        solve55(a);
    }
    return 0;
}

Measured memory_bytes: 1256
N = int(input())
S = list(input())
ws = [0]*N
es = [0]*N
# 自分より前のWと自分より後のEの数だけ振り向かせる
for i in range(N-1):
    if S[i] == 'W':
        ws[i+1] += ws[i]+1
    else:
        ws[i+1] = ws[i]
for i in range(N-1, 0, -1):
    if S[i] == 'E':
        es[i-1] += es[i]+1
    else:
        es[i-1] = es[i]
ans = []
for w, e in zip(ws, es):
    ans.append(w+e)
print(min(ans))

Measured memory_bytes: 84800
Input = str(input())

dic_list={
    "a":"b",
    "b":"c",
    "c":"d",
    "d":"e",
    "e":"f",
    "f":"g",
    "g":"h",
    "h":"i",
    "i":"j",
    "j":"k",
    "k":"l",
    "l":"m",
    "m":"n",
    "n":"o",
    "o":"p",
    "p":"q",
    "q":"r",    
    "r":"s",
    "s":"t",
    "t":"u",
    "u":"v",
    "v":"w",
    "w":"x",
    "x":"y",
    "y":"z",
}


print(dic_list[Input])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
using namespace std;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
#define lld long double
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> vp;
typedef vector<tuple<ll, ll, ll>> vt;
//vector<vector<ll>> vv(n, vector<ll>(n));

int main()
{
	int n,ans=0;
	cin >> n;
	REP(i,n)
	{
		int a, b;
		cin >> a >> b;
		ans += b - a + 1;
	}
	cout << ans << endl;
}

Measured memory_bytes: 764
n,m=map(int,input().split())
A = [[0 for j in range(m)]for i in range(n)]
B = [0 for j in range(m)]
for i in range(n):
    A[i]=list(map(int,input().split()))
for j in range(m):
    B[j]=int(input())
for i in range(n):
    print(sum([A[i][j]*B[j] for j in range(m)]))


Measured memory_bytes: 6032
#include<stdio.h>

#define BUILD(X,Y) (X-1)*3+Y-1

void star();
void check(int m[][10]);
void output(int m[][10]);

int main(void)
{
    int num;
    int in[12][10] = {0};
    int i;

    scanf("%d",&num);
    for(i=0;i<num;i++){
        check(in);
    }

    output(in);

    return 0;

}

void check(int m[][10])
{
    int b,f,r,v;
    scanf("%d %d %d %d",&b,&f,&r,&v);
    m[BUILD(b,f)][r-1] += v;
    return;
}

void output(int m[][10])
{
    int i,j;
    for(i=0;i<12;i++){
        for(j=0;j<10;j++){
            printf(" %d",m[i][j]);
        }
        printf("\n");
        if(i%3==2 && i!=11)
            star();

    }

    return ;
}

void star()
{
    int i;
    for(i=0;i<20;i++)
        printf("#");
    printf("\n");
    return ;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vstr s(h);
    rep(i, h) cin >> s[i];
    
    vvint ans(h, vint(w, -1));
    int id = 0;
    rep(i, h) {
        bool cake = false;
        rep(j, w) {
            if (s[i][j] == '#') {
                cake = true;
                break;
            }
        }
        if (cake == false) continue;
        bool found = false;
        id++;
        rep(j, w) {
            if (s[i][j] == '.') ans[i][j] = id;
            else {
                if (found) id++;
                else found = true;
                ans[i][j] = id;
            }
        }
    } 

    rep(j, w) {
        rep(i, h) {
            if (i == 0) continue;
            if (ans[i][j] == -1) ans[i][j] = ans[i-1][j];
        }
        rrep(i, h) {
            if (i == h-1) continue;
            if (ans[i][j] == -1) ans[i][j] = ans[i+1][j];
        }
    }
    
    rep(i, h) rep(j, w) printf("%d%s", ans[i][j], j != w-1 ? " " : "\n");
    return 0;
}

Measured memory_bytes: 1280
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

N = int(input())
a = list(map(int,input().split()))
from fractions import gcd
seg = SegmentTree(N , gcd , 0)
for i in range(N):
    seg.assign(i , a[i])
seg.build()
ans = 1
for i in range(N):
    ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
print(ans)

Measured memory_bytes: 100748
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < n; i++)
using namespace std;
int main(){
  
  int a,b;
  cin >> a >> b;
  
  if(a == b){
    cout << "Yes" <<endl;
  }else{
    cout << "No" <<endl;
  }
}

Measured memory_bytes: 256
I,i,H=input,int,range
n,L,R,A,C=i(I()),[0],[0],0,0
for _ in H(n):l,r=map(i,I().split());L+=[l];R+=[r]
L=sorted(L)[::-1];R.sort()
for j in H(n//2+1):C+=(L[j]-R[j])*2;A=max(A,C)
print(A)

Measured memory_bytes: 18340
/*
*/

//#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-8
#define M_PI 3.141592653589793
#define bsize 512

#define ldouble long double
using namespace std;

#define bs 1000000007

const int N = 300031;

long long L[1000];

int main(){
//	freopen("apache.in","r",stdin);
//	freopen("apache.out","w",stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	L[0]=2;
	L[1]=1;
	for (int i=2;i<=86;i++){
		L[i]=L[i-1]+L[i-2];
	}

	int x;
	cin>>x;
	cout<<L[x]<<endl;

	cin.get(); cin.get();
	return 0;
}


Measured memory_bytes: 768
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<functional>
#include<queue>
#include<stack>
#include<string.h>
#include<list>
#include<limits>
#include<bitset>
#define MOD 10007LL
#define MAX 300001
using namespace std;
typedef long long int ll;
const ll INF=1e98;
typedef pair<int,int> P;
int main() {    
    int n;
    cin>>n;
    ll a[MAX]={};
    for(int i=0;i<3*n;i++){
        cin>>a[i];
    }
    priority_queue<ll,vector<ll>,greater<ll>> aq;
    ll sum=0;
    for(int i=0;i<n;i++){
        aq.push(a[i]);
        sum+=a[i];
    }
    ll ansa[MAX];
    ansa[n-1]=sum;
    for(int i=n;i<2*n;i++){
        aq.push(a[i]);
        sum+=a[i];
        sum-=aq.top();
        aq.pop();
        ansa[i]=sum;
    }
    sum=0;
    ll ansb[MAX];
    priority_queue<ll> bq;
    for(int i=3*n-1;i>=2*n;i--){
        bq.push(a[i]);
        sum+=a[i];
    }
    ansb[2*n]=sum;
    for(int i=2*n-1;i>=n;i--){
        bq.push(a[i]);
        sum+=a[i];
        sum-=bq.top();
        bq.pop();
        ansb[i]=sum;
    }
    ll ans=-INF;
    for(int i=n-1;i<2*n;i++){
        ans=max(ans,ansa[i]-ansb[i+1]);
    }
    cout<<ans<<endl;
}

                           


Measured memory_bytes: 8820
#include<bits/stdc++.h>
#define pb push_back
typedef long long ll;
#define mod pow(10,9)+7
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s;
	cin >> s;
	int len = s.length();
	if (s[len - 1] == 's')
	{
		s.push_back('e');
		s.push_back('s');
	}
	else
	{
		s.push_back('s');
	}
	cout << s << '\n';
	return 0;
}


Measured memory_bytes: 3624
// AOJ 0245: Time Sale
// 2017.12.16 bal4u@uu

#include <stdio.h>
#include <string.h>

#define QMAX 300000
typedef struct { char r, c, t; int d, b; } Q;
Q q[QMAX+2]; int top, end;

#define WALL 64
#define COR  32

typedef struct { int d, s, e; } G;
G sell[10];
char map[22][22];
char mk[22][22][101][1024];
char buf[50], *p;
int mv[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

int in()
{
	int n = 0;
	while (*p >= '0') n = 10*n + (*p++ & 0xf);
	p++;
	return n;
}

int main()
{
	int X, Y, r, c, n, i, j, sr, sc, ans;
	int d, t, b, r2, c2, max;

	while (fgets(p=buf, 10, stdin) && *p != '0') {
		X = in(), Y = in();
		memset(map, WALL, sizeof(map));
		for (r = 1; r <= Y; r++) {
			fgets(p=buf, 50, stdin);
			for (c = 1; c <= X; c++) {
				if (*p == '.') map[r][c] = COR;
				else if (*p == 'P') sr = r, sc = c, map[r][c] = COR;
				else map[r][c] = *p & 0xf;
				p += 2;
			}
		}
		fgets(p=buf, 5, stdin);
		n = *p & 0xf, max = 0;
		for (i = 0; i < n; i++) {
			fgets(p=buf, 50, stdin);
			j = in();
			sell[j].d = in(), sell[j].s = in(), sell[j].e = t = in();
			if (t > max) max = t;
		}

		ans = 0;
		memset(mk, 0, sizeof(mk));
		q[0].r = sr, q[0].c = sc, q[0].t = 0, q[0].d = 0, q[0].b = 0;
		top = 1;
		while (top) {
			r = q[--top].r, c = q[top].c, t = q[top].t, d = q[top].d, b = q[top].b;

			if (d > ans) ans = d;
			if (t >= max) continue;
			if (mk[r][c][t][b]) continue;
			mk[r][c][t][b] = 1;

			for (i = 0; i < 4; i++) {
				r2 = r + mv[i][0], c2 = c + mv[i][1];
				if ((j = map[r2][c2]) > 10) continue;
				if (!(b & (1 << j)) && sell[j].s <= t && t < sell[j].e) {
					d += sell[j].d;
					b |= 1 << j;
				}
			}
			for (i = 0; i < 4; i++) {
				r2 = r + mv[i][0], c2 = c + mv[i][1];
				if (map[r2][c2] & COR) {
					q[top].r = r2, q[top].c = c2, q[top].t = t+1, q[top].d = d, q[top++].b = b;
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

int main(){
    
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a.at(i);
    }

    bool increase=true,reset=true;
    int count=1;
    for(int i=1; i<n; i++){
        if(reset){
            if(a.at(i)==a.at(i-1)) continue;
            else if(a.at(i)>a.at(i-1)){
                increase=true;
                reset=false;
            }
            else{
                increase=false;
                reset=false;
            }
        }
        else{
            if(increase){
                if(a.at(i)<a.at(i-1)){
                    count++;
                    reset=true;
                }
            }
            else{
                if(a.at(i)>a.at(i-1)){
                    count++;
                    reset=true;
                }
            }
        }
    }
    cout << count << endl;
}

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,m,ky[4]={-1,0,1,0},kx[4]={0,1,0,-1};
bitset<1069> a[1069];
queue<pair<pair<long long,long long>,long long>> q;

int main()
{
	long long i,j,it,y,x,w,yy,xx;
	string s;
	
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)
	{
		cin>>s;
		for(j=1;j<=m;j++)
		{
			if(s[j-1]=='.')
			{
				a[i][j]=0;
			}
			else
			{
				a[i][j]=1;
				q.push(mp(mp(i,j),0));
			}
		}
	}
	for(;!q.empty();)
	{
		y=q.front().fr.fr;
		x=q.front().fr.sc;
		w=q.front().sc;
		q.pop();
		for(it=0;it<4;it++)
		{
			yy=y+ky[it];
			xx=x+kx[it];
			if(yy>0&&xx>0&&yy<=n&&xx<=m&&!a[yy][xx])
			{
				q.push(mp(mp(yy,xx),w+1));
				a[yy][xx]=1;
			}
		}
	}
	printf("%lld\n",w);
}

Measured memory_bytes: 24628
import copy
import heapq

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
rem = 10 ** 9 + 7

"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def ipmultiplerow(n):
    a = []
    for i in range(n):
        a.append(ip())
    return a
def printrow(a):
    for i in a:
        print(i)

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


n,m = ips()
a = iprow()
a.sort(reverse=True)
#print(a)
heapq._heapify_max(a)
for i in range(m):
    b = _heappop_max(a)
    #print(b, a)
    b//=2
    _heappush_max(a,b)
print(sum(a))


Measured memory_bytes: 14912
// AOJ 2255 6/2(1+2)
// 2018.3.18 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX 2500
int ans[MAX];
char buf[210];
char op[128];

int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int update(int *ans, int pos, int val)
{
	int i;
	for (i = 0; i < pos; i++) if (ans[i] == val) return pos;
	ans[pos++] = val;
	return pos;
}

int calc(int *ans, int xs, int *x, int ys, int *y, int op)
{
	int i, j, pos;

	pos = 0;
	for (i = 0; i < xs; i++) for (j = 0; j < ys; j++) {
		switch (op) {
		case '+': pos = update(ans, pos, x[i] + y[j]); break;
		case '-': pos = update(ans, pos, x[i] - y[j]); break;
		case '*': pos = update(ans, pos, x[i] * y[j]); break;
		case '/': if (y[j] != 0) pos = update(ans, pos, x[i] / y[j]); break;
		}
	}
	return pos;
}

int closing(int pos)
{
	int n = 1;
	while (n > 0) {
		if (buf[pos] == '(') n++;
		else if (buf[pos] == ')') n--;
		pos++;
	}
	return pos-1;
}

int expr(int *ans, int fr, int to);

int num(int *ans, int fr, int to)
{
	if (buf[fr] == '(') return expr(ans, fr+1, to-1);
	*ans = 0;
	while (isdigit(buf[fr])) *ans = 10 * *ans + (buf[fr++] & 0xf);
	return 1;
}

int expr(int *ans, int fr, int to)
{

	int i, f, sz;
	int a[MAX], b[MAX], as, bs;

	sz = 0, f = 0;
	for (i = fr; i < to; i++) if (op[buf[i]]) {
		if (buf[i] == '(') i = closing(i+1);
		else {
			as = expr(a, fr, i);
			bs = expr(b, i + 1, to);
			sz += calc(ans + sz, as, a, bs, b, buf[i]);
			f = 1;
		}
	}
	if (!f) sz = num(ans, fr, to);
	return sz;
}

int main()
{
	int i, sz, cnt;

	op['+'] = 1, op['-'] = 2, op['*'] = 3, op['/'] = 4;
	op['('] = 10, op[')'] = 11;
	while (scanf("%s", buf) && *buf != '#') {
		sz = expr(ans, 0, strlen(buf));
		qsort(ans, sz, sizeof(int), cmp);
#if 0
printf("ans: n=%d: ", sz);
for (i = 0; i < sz; i++) printf("%d ", ans[i]); printf("\n");
#endif
		cnt = 1; for (i = 1; i < sz; i++) {
			if (ans[i] != ans[i - 1]) cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int H, W;
string A[600];
bool used[600][600];
int cnt = 0;
vector<pair<int, int>> islands[500 * 500 + 500];
vector<pair<int, int>> target;

string ret;
string dir_s = "URDL";

int cur_r = 0, cur_c = 0, cur_dir = 0;


bool move(int dir) {
    cout << "? " << dir_s[dir] << endl;
    cin >> ret;
    return ret == "YES";
}

void move() {
    if (move(cur_dir)) {
        cur_r += dr[cur_dir];
        cur_c += dc[cur_dir];
        if (move((cur_dir + 3) % 4)) {
            cur_dir = (cur_dir + 3) % 4;
            cur_r += dr[cur_dir];
            cur_c += dc[cur_dir];
        }
        target.push_back(make_pair(cur_r, cur_c));
    } else {
        cur_dir = (cur_dir + 1) % 4;
    }
}

void dfs(int r, int c, int group) {
    if (used[r][c]) return;
    bool edge = false;
    REP(k, 4) {
        int nr = r + dr[k];
        int nc = c + dc[k];
        if (nr < 0 || nr >= H || nc < 0 || nc >= W || A[nr][nc] == '.') {
            edge = true;
        }
    }
    if (edge) {
        islands[group].push_back(make_pair(r, c));
    }
    used[r][c] = true;
    REP(k, 4) {
        int nr = r + dr[k];
        int nc = c + dc[k];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W && !used[nr][nc] && A[nr][nc] == '#') {
            dfs(nr, nc, group);
        }
    }
}

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

    cin >> H >> W;
    REP(i, H) cin >> A[i];

    REP(i, H) REP(j, W) if (!used[i][j] && A[i][j] == '#') {
        dfs(i, j, cnt);
        cnt++;
    }

    REP(i, cnt) {
        sort(islands[i].begin(), islands[i].end());
    }

    while (move(3)) {
        cur_c -= 1;
    }

    int sr = cur_r;
    int sc = cur_c;
    target.push_back(make_pair(cur_r, cur_c));

    do {
        move();
    } while (cur_dir != 0 || cur_r != sr || cur_c != sc);

    sort(target.begin(), target.end());
    target.erase(unique(target.begin(), target.end()), target.end());
    //for (auto p: target) cout << "(" << p.first << "," << p.second << ")" << endl;
    //cout << endl;


    REP(i, cnt) {
        if (target.size() != islands[i].size()) continue;
        bool ok = true;
        int r1 = target.front().first;
        int c1 = target.front().second;
        int r2 = islands[i].front().first;
        int c2 = islands[i].front().second;
        REP(j, (int)target.size()) {
            if (target[j].first - r1 != islands[i][j].first - r2 || target[j].second - c1 != islands[i][j].second - c2) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "! " << islands[i].front().first - target.front().first << " " << islands[i].front().second - target.front().second << endl;
            return 0;
        }
    }
}



Measured memory_bytes: 32400
N = int(input())
A = list(map(int, input().split()))

if 0 in A:
    print(0)
else:
    ans = 1
    a = sorted(A, reverse=True)
    for i in a:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            break
    else:
        print(ans)

Measured memory_bytes: 21544
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		PrimeNumberGenerator pg = new PrimeNumberGenerator();
		
		while(true){
			String str = br.readLine();
			int n = Integer.parseInt(str);
			
			if(n == 0){
				break;
			}
			
			System.out.println(pg.countGoldBach(n));
		}
	}

}

class PrimeNumberGenerator {
    private boolean[] isPrime= new boolean[100000001];
    private int[] prime = new int[110000];
 
    public PrimeNumberGenerator() {
        //Date from = new Date();
        Arrays.fill(isPrime, true);
 
        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;
        
        prime[1] = 2;
 
        for(int i = 2; i <= Math.sqrt( isPrime.length ); i++){
            /*
            if(i % 2 == 0){
                isPrime[i] = false;
                continue;
            }
            */
 
            if(isPrime[i] == false){
                continue;
            }
 
            for(int j = i * 2; j <= isPrime.length - 1; j += i){
                isPrime[j] = false;
            }
        }
        
        for(int i = 3, j = 2; i < prime.length ; i++){
        	if(isPrime[i]){
        		prime[j] = i;
        		j++;
        	}
        }
        //Date to = new Date();
        //System.out.println("init takes "+ (to.getTime() - from.getTime())+ "milli sec");
    }
 
    public boolean isPrime(int index){
        if(index % 2 == 0 && index != 2){
            return false;
        }
        return isPrime[index];
    }
    
    public int countGoldBach(int n){
    	int count = 0;
    	
    	for(int i = 2; i <= n/2 ; i++){
    		if(isPrime[i] && isPrime[n - i]){
    			count++;
    		}
    	}
    	
    	return count;
    }
    
    public long sumOfPrime(int n){
    	int sum = 0;
    	for(int i = 1; i <= n; i++){
    		sum += prime[i];
    	}
    	
    	return sum;
    }
}

Measured memory_bytes: 129820
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

n = int(input())
nn = factorization(n)
#print(nn)
ans = 0

if n == 1:
    print(0)
    exit()

for i in range(len(nn)):
    ans += 1
    cnt = 1
    dif = 2
    cnt += dif
    while cnt <= nn[i][1]:
        ans += 1
        dif += 1
        cnt += dif
print(ans)

Measured memory_bytes: 63300
n, m = [int(i) for i in input().split(" ")]
c = [0 for i in range(0, m)]

for k in range(0, n):
    a = [int(i) for i in input().split(" ")]
    for j in range (1, a[0] + 1):
        c[a[j] - 1] += 1

s = 0
for i in range(0, m):
    if c[i] == n:
        s += 1

print(s)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 9223372036854775807;
const ll mininf = -9223372036854775807;
const ll nax = 0;
int n;
unordered_map<int, int>arr;

int main(){
	IOS
	cin >> n;
	bool berak=0;
	while(n--){
		int z;
		cin >> z;
		if(arr[z]!=0){
			berak=1;
			break;
		}
		arr[z]=1;
	}
	if(!berak){
		cout << "YES" << '\n';
	}
	else{
		cout << "NO" << '\n';
	}
}

Measured memory_bytes: 11360
m,d=map(int, input().split())
cnt=0
for i in range(1,m+1):
    for j in range(1,d+1):
        jj=list(str(j))
        if len(jj)==2 and int(jj[0]) >= 2 and int(jj[1]) >= 2 and int(jj[0])*int(jj[1]) == i:
            cnt+=1
print(cnt)

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(){
    char c1,  c2, c3;
    cin >> c1 >> c2 >> c3;
    int ans = 0;
    if(c1 == '1')ans = ans + 1;
    if(c2 == '1')ans = ans + 1;
    if(c3 == '1')ans = ans + 1;
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <unordered_set>
#include <ctime>
#include <numeric>
#include <cstdint>

using llint = long long int;

using namespace std;
struct UnionFind {
  
  vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

  UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
    for(int i = 0; i < N; i++) par[i] = i;
  }

  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y) { // xとyの木を併合
    int rx = root(x); //xの根をrx
    int ry = root(y); //yの根をry
    if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
    par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
  }

  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};

void solve(void){

  int n, m;
  std::cin >> n >> m;
  UnionFind uf(n);

  for(int i=0; i<m; i++){
    int a, b;
    std::cin >> a >> b;
    a--; b--;
    uf.unite(a,b);
  }

  std::vector<int> members(n);
  for(int i=0; i<n; i++){
    members[uf.root(i)]++;
  }
  int biggest = 0;
  for(int i=0; i<n; i++){
    biggest = std::max(biggest, members[i]);
  }
  std::cout << biggest << std::endl;
  
  return;
}
int main(void){
  solve();
  return 0;
}





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

int main() {
  ll a[300010];
  int n;
  cin>>n;
  for (int i=0; i<3*n; i++) {
    scanf("%lld",a+i);
  }

  sort(a,a+3*n);
  ll ans=0;
  int j=3*n-2;
  for (int i=0; i<n; i++) {
    ans+=a[j];
    j-=2;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int N;cin>>N;
  int sum=0,ret=0;

  map<int,int>mp;
  mp[0]++;
  for(int t=0;t<N;t++){
    int a;
    cin>>a;
    sum+=a;
    ret+=mp[sum];
    mp[sum]++;
  }
  cout<<ret<<"\n";
  return 0;
}


Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int a,b;
  cin>>a>>b;
  cout<<a/__gcd(a,b)*b<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define LOL cout<<'\n';
#define MOD 1000000007
#define sz(x) ((int)x.size())
#define INF LONG_LONG_MAX
#define NINF LONG_LONG_MIN

void solve(){
	int n; cin>>n;
	int ans=8;
	if(n>=600) ans--;
	if(n>=800) ans--;
	if(n>=1000) ans--;
	if(n>=1200) ans--;
    if(n>=1400) ans--;
	if(n>=1600) ans--;
	if(n>=1800) ans--;
	cout<<ans;LOL
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int _=1; //cin>>_;
  for(int i=1 ; i<=_ ; i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
  return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<long long, long long >
#define ll long long
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define maxn 10000000000000
#define endl '\n'
#define trace(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
int mod(int x,int y)
{
  int s;
  s = abs(x)/y;
  if(x<0)s--;
  return x-y*s;
}
int dir8[2][8] = {{1,-1,0,0,1,-1,1,-1},{0,0,1,-1,1,-1,-1,1}};
int dir4[2][4] = {{1,-1,0,0},{0,0,1,-1}};
ll m,n,row,col,k;
ll memo[100006];
ll ara[100006];
ll dp(ll i)
{
  if(i == n-1)return 0;
  if(memo[i]!=-1)return memo[i];
  ll p1=maxn;
  for(ll x= 1; i+x < n && x<= k; x++)
  {
    p1 = min(p1, dp(i+x) + abs(ara[i]-ara[i+x]));
  }
  memo[i] =p1;
  return p1;
}
void solve()
{
  scanf("%lld%lld",&n,&k);
  for(int w=0;w<n;w++)scanf("%lld",&ara[w]);
  ll ans = dp(0);
  printf("%lld\n",ans);
}
void test()
{
  int t;
  //scanf("%d",&t);
  t=1;
  for(int test=1;test<=t;test++)
  {
    memset(memo,-1,sizeof memo);
    solve();
  }
}
int main()
{
  test();
  return 0;
}


Measured memory_bytes: 6528
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int maxm = 200005;
const ll inf = 0x3f3f3f3f3f3f;
const int mod = 1e9 + 7;
struct Edge
{
	int from, to, next;
	ll dist;
	Edge(int _f, int _t, ll _d, int _n) :from(_f), to(_t), next(_n), dist(_d) {}
	Edge() {}
};

struct HeapNode
{
	ll d;
	int u;
	HeapNode(ll _d, int _u) :d(_d), u(_u) {}
	HeapNode() {}
	bool operator<(const HeapNode &b)const
	{
		return d > b.d;
	}
};

struct Dijkstra
{
	int n;
	ll d[maxn];
	bool done[maxn];
	Edge edges[maxm<<1];
	int head[maxn];
	int tot;
	int path[maxn];
	void init(int n)
	{
		tot = 0;
		this->n = n;
		for (int i = 1;i <= n;i++)d[i] = inf;
		memset(done, 0, sizeof(done));
		memset(head, -1, sizeof(head));
	}
	void addedge(int u, int v, ll dist)
	{
		edges[tot] = Edge(u, v, dist, head[u]);
		head[u] = tot++;
	}

	void dijkstra(int s)
	{
		priority_queue<HeapNode>Q;
		d[s] = 0;
		path[s] = 1;
		Q.push(HeapNode(d[s], s));
		while (!Q.empty())
		{
			HeapNode x = Q.top();Q.pop();
			int u = x.u;
			if (done[u])continue;
			done[u] = 1;
			for (int i = head[u];~i;i = edges[i].next)
			{
				Edge &e = edges[i];
				if (d[e.to] > d[u] + e.dist)
				{
					d[e.to] = d[u] + e.dist;
					path[e.to] = path[u] % mod;
					Q.push(HeapNode(d[e.to], e.to));
				}
				else if (d[e.to] == d[u] + e.dist)
				{
					(path[e.to] += path[u]) %= mod;
				}
			}
		}
	}



}d1, d2;
bool on[maxm];
int u[maxm], v[maxm];
ll d[maxm];

ll sqr(ll a)
{
	return a*a%mod;
}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	int s, t;
	scanf("%d %d", &s, &t);
	d1.init(N);
	d2.init(N);
	for (int i = 1;i <= M;i++)
	{
		scanf("%d %d %lld", &u[i], &v[i], &d[i]);
		d1.addedge(u[i], v[i], d[i]), d1.addedge(v[i], u[i], d[i]);
		d2.addedge(u[i], v[i], d[i]), d2.addedge(v[i], u[i], d[i]);
	}

	d1.dijkstra(s);
	d2.dijkstra(t);
	ll themin = d1.d[t];
	for (int i = 1;i <= M;i++)
	{
		if (d1.d[u[i]] + d[i] + d2.d[v[i]] == themin)
			on[i] = 1;
		else if (d1.d[v[i]] + d[i] + d2.d[u[i]] == themin)
		{
			swap(u[i], v[i]);
			on[i] = 1;
		}
	}
	ll ans = sqr(d1.path[t]);
	for (int i = 1;i <= M;i++)
		if (on[i])
		{
			if (d1.d[u[i]] * 2ll < themin&&d2.d[v[i]] * 2ll < themin)
				ans = (ans - (sqr(d1.path[u[i]]) *sqr(d2.path[v[i]]) % mod)+mod) % mod;
		}
	for (int i = 1;i <= N;i++)
		if (d1.d[i] * 2ll == themin&&d1.d[i]+d2.d[i]==themin)
			ans = (ans - (sqr(d1.path[i]) * sqr(d2.path[i])) % mod+mod) % mod;
	cout << ans << endl;
}

Measured memory_bytes: 29268
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
	int n,l;
	cin >> n >> l;
	vector<string> s(n);
	rep(i,n)cin >> s[i];
	sort(ALL(s));

	rep(i,n)cout<<s[i];cout<<endl;
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  
  int ans = n;
  
  for (int i = n; i < 1000; i++) {
  	if(ans == ans/111*111) {
    	break;
    }
  	else {
    	ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <cmath>

using namespace std;

int main()
{
    int n;
    cin >> n;
    map<int, int> counts;
    int a;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        if (counts.count(a))
            counts[a]++;
        else
            counts[a] = 1;
    }
    int ans = 0;
    while (!counts.empty())
    {
        auto cur_it = counts.rbegin();
        auto cur = cur_it->first;
        auto cnt = cur_it->second;
        if (cnt == 1)
            counts.erase(cur);
        else
            counts[cur] = cnt - 1;
        int need = 1;
        while (need <= cur)
            need *= 2;
        need -= cur;
        auto it = counts.find(need);
        if (it != counts.end())
        {
            ans++;
            if (it->second == 1)
                counts.erase(it->first);
            else
                counts[it->first] = it->second - 1;
        }
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 10112
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
using namespace std;
long long int b[600000];
char ba[600000];
int main() {
	long long int i, n;
	scanf("%s", ba+1);
	n = strlen(ba+1);
	long long int t = 0;
	for (i = 1; i <= n+1; i++) {
		if (ba[i] == '<') {
			t++;
			b[i - 1] = t;
		}
		else {
			if (t != 0) b[i - 1] = t + 1;
			t = 0;
		}
	}
	t = 0;
	for (i = n; i >= 0; i--) {
		if (ba[i] == '>') {
			t++;
			if (b[i] == 0) b[i] = t;
			else {
				if (b[i] < t) b[i] = t;
			}
		}
		else {
			if (b[i] < t+1) b[i] = t+1;
			t = 0;
		}
	}
	long long int cnt = 0;
	for (i = 0; i <= n; i++) cnt += b[i];
	printf("%lld", cnt-n-1);
	return 0;
}

Measured memory_bytes: 4608
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>
#include <numeric>

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

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

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }


int main() {
    int n;
    cin >> n;
    auto black = make_v(n, n+1, 0);
    auto white = make_v(n, n+1, 0);
    vector<int> b(n, 0), w(n, 0), sumb(n+1, 0), sumw(n+1, 0);
    for (int i = 0; i < 2*n; ++i) {
        char c; int a;
        cin >> c >> a;
        partial_sum(b.rbegin(), b.rend(), sumb.rbegin()+1);
        partial_sum(w.rbegin(), w.rend(), sumw.rbegin()+1);
        for (int j = n; j >= 0; --j) {
            if(c == 'B') black[a-1][j] = sumw[j] + sumb[a];
            if(c == 'W') white[a-1][j] = sumw[a] + sumb[j];
        }
        if(c == 'B') b[a-1]++;
        else w[a-1]++;
    }
    auto dp = make_v(n+1, n+1, INF<int>);
    dp[0][0] = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if(i < n) dp[i+1][j] = min(dp[i+1][j], dp[i][j] + black[i][j]);
            if(j < n) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + white[j][i]);
        }
    }
    cout << dp[n][n] << "\n";
    return 0;
}


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

a = [int(x) for x in input().strip().split()]

suff = []

mod = 10**9+7

s = 0
suff.append(s)
for i in range(n-1, -1, -1):
    s = (s%mod + a[i]%mod)%mod
    suff.append(s)


res = 0

for i in range(n):
    
    curr = (suff[n-1-i]%mod * a[i]%mod)%mod
    res = (res%mod + curr%mod)%mod

print(res)




Measured memory_bytes: 101880
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		int n;

		Scanner stdIn = new Scanner(System.in);
		List<String> cards = new ArrayList<>();

		n = stdIn.nextInt();

		for(int i = 0; i <= n; i++) {
			cards.add(stdIn.nextLine());
		}

		for(int i = 1; i < 14; i++) {
			if(!(cards.contains("S " + i))) {
				System.out.println("S " + i);
			}
		}
		for(int i = 1; i < 14; i++) {
			if(!(cards.contains("H " + i))) {
				System.out.println("H " + i);
			}
		}
		for(int i = 1; i < 14; i++) {
			if(!(cards.contains("C " + i))) {
				System.out.println("C " + i);
			}
		}
		for(int i = 1; i < 14; i++) {
			if(!(cards.contains("D " + i))) {
				System.out.println("D " + i);
			}
		}
	}
}

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

using namespace std;

typedef long long L11;

#define res(i,a,b) for(int i=a;i<=b;++i)

int main() {

	int N;
	L11 Y;

	cin >> N >> Y;

	bool exist = false;

	L11 total = 0;
	vector<int> sum;

	int i = 0, j = 0, k = 0;

	res(i, 0, N) {
		for (j = 0; i + j <= N;++j) {
			//res(k, 0, N) {	//ループ三回では非常に計算量が多い

			k = N - (i + j);
			total = 10000 * i + 5000 * j + 1000 * k;
			//cout << total << endl;
			if (total == Y ) {
				sum.push_back(i);
				sum.push_back(j);
				sum.push_back(k);
				exist = true;
			}
		}
		if (exist)break;
	}	


	if (exist==true) {
		for (int i = 0; i < sum.size(); ++i)
			cout << sum[i] << " ";
	}
	if(exist==false)
		cout << "-1 -1 -1" << endl;

}

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

int A[300000], B[300000];

int main() {
	
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		cin >> A[i];
		B[i] = A[i];
	}
	
	sort(A, A + N);
	
	for(int i = 0; i < N; i++){
		if(B[i] < A[N / 2]){
			cout << A[N / 2] << endl;
		}else{
			cout << A[N / 2 - 1] << endl;
		}
	}
	
	return 0;
}


Measured memory_bytes: 3712