akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef pair<int,int> PII;
const int N = 200010;
const int inf = 1e9;
int n,Q,b[N],sum0[N],sum1[N];
PII p[N];
struct Node{
	int l,r,mx;
}t[N*4];
void build(int x,int l,int r){
	t[x].l=l,t[x].r=r;
	t[x].mx = -inf;
	if(t[x].l==t[x].r) return;
	int mid = l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void change(int  x,int p,int v){
	t[x].mx = max(t[x].mx,v);
	if(t[x].l==t[x].r) return;
	int mid = t[x].l+t[x].r>>1;
	if(p<=mid) change(x<<1,p,v);
	else change(x<<1|1,p,v);
}
int query(int x,int l,int r){
	//cout<<x<<" "<<l<<' '<<r<<' '<<t[x].l<<" "<<t[x].r<<endl;;
	if(t[x].l==l && t[x].r==r) return t[x].mx;
	int mid = t[x].l+t[x].r>>1;
	if(r<=mid) return query(x<<1,l,r);
	else if(l>mid) return query(x<<1|1,l,r);
	else return max(query(x<<1,l,mid),query(x<<1|1,mid+1,r));
}
int main(){
	scanf("%d",&n);
	for(int i = 1;i<=n;i++)scanf("%d",b+i);
	for(int i =1;i<=n;i++){
		sum0[i] =sum0[i-1];
		sum1[i] = sum1[i-1];
		if(b[i]==0) sum0[i]++;
		else sum1[i]++;
	}
	build(1,0,n);
	scanf("%d",&Q);
	for(int i = 1;i<=Q;i++)scanf("%d%d",&p[i].X,&p[i].Y);
	sort(p+1,p+Q+1);
	change(1,0,0);
	int mx = 0,ans = 0;
	for(int i =1,j = 1;i<=n;i++){
		while(j<=Q && p[j].X==i){
			change(1,p[j].Y,mx+sum0[i-1]-sum1[i-1]);
			int tmp = query(1,i,p[j].Y);
			change(1,p[j].Y,tmp);
			j++;
		}
		ans = max(ans,query(1,i,i)+sum1[i]);
		ans = max(ans,mx+sum0[i]);
		//cout<<i<<endl;
		
		mx = max(mx,query(1,i,i)+sum1[i]-sum0[i]);
	//	cout<<ans<<endl;
	}
	printf("%d\n",n-ans);
	return 0;
} 

Measured memory_bytes: 13696
#pragma warning(disable: 4996)

#include <iostream>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <functional>
#include <cstdio>
#include <cctype>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
#include <numeric>
#include <string>
#include <set>
#include <tuple>
#include <utility>
#include <regex>
#include <deque>
#include <map>
#include <queue>
#include <stack>
using namespace std;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n, a;
	cin >> n;
	set<int> st;
	for (int i = 0; i < n; ++i) {
		cin >> a;
		st.insert(a);
	}
	cout << (st.size() == n ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 9600
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
int main() {
	int ans = 0;
	vector<int>v(3);
	for (int i = 0; i < 3; ++i)
		cin >> v[i];
	sort(v.begin(), v.end());
	ans += (v[1] - v[0]) / 2;
	v[0] += ans * 2;
	ans += v[2] - v[0];
	v[1] += v[2] - v[0];
	v[0] += v[2] - v[0];
	if (v[0] != v[1])
		++ans;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
a1, a2, a3, a4, a5 = map(int, input().split())
if a1 == 0:
    print('1')
if a2 == 0:
    print('2')
if a3 == 0:
    print('3')
if a4 == 0:
    print('4')
if a5 == 0:
    print('5')

Measured memory_bytes: 9116
import std.stdio, std.conv, std.string, std.range, std.algorithm, std.array,
  std.functional, std.container, std.typecons;

void main() {
  int N = readln.chomp.to!int;
  int[] d = readln.split.to!(int[]);

  d.sort();
  int l = d[(N / 2) - 1], r = d[N / 2];
  max(0, r - l).writeln;
}


Measured memory_bytes: 4316
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#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++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    string n;cin>>n;
    int m=n.size();
    int k;cin>>k;
    vector<vector<vector<int>>> dp(105, vector<vector<int>>(5, vector<int>(2)));
    dp[0][0][0]=1;
    int tmp;
    rep(i,m)rep(j,k+1){
        dp[i+1][j][1]+=dp[i][j][1];
        dp[i+1][j+1][1]+=9*dp[i][j][1];
        tmp=n[i]-'0';
        if(tmp==0)dp[i+1][j][0]=+dp[i][j][0];
        else{
            dp[i+1][j][1]+=dp[i][j][0];
            dp[i+1][j+1][1]+=(tmp-1)*dp[i][j][0];
            dp[i+1][j+1][0]+=dp[i][j][0];
        }
    }
    cout<<dp[m][k][0]+dp[m][k][1]<<endl;
}

Measured memory_bytes: 3676
N = int(input())
c = {}
for i in range(N):
    s = ''.join(sorted(input()))
    if s not in c:
        c[s] = 0
    else:
        c[s] += 1
r = sum([(v/2)*(2 + v - 1) for v in c.values()])
print(int(r))

Measured memory_bytes: 18580
#include <iostream>
#include <string>
using namespace std;
int main(void){
    string s;
    getline(cin, s);    
        //cout << s;
        for(int i = 0; i < s.size(); i++) {
            char c = s[i];
            if ('A' <= c && c <= 'Z') {
                c = c + 32;
            }
            else if('a' <= c && c <= 'z') {
                c = c - 32;
            }
            cout << c;
    }
    cout << endl;
}


Measured memory_bytes: 3192
#include <iostream>
using namespace std; typedef long long ll;
int main() {
  int n; cin>>n;
  ll a[n],b[n];
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++) cin>>b[i];
  ll c=0,d=0;
  for(int i=0;i<n;i++) c+=max(0LL,(b[i]-a[i])/2);
  for(int i=0;i<n;i++) d+=max(0LL,a[i]-b[i]);
  if (c-d>=0) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 384
S = input()
T = input()
s = {d:[] for d in set(S)}
t = {d:[] for d in set(T)}

for i, (j,k) in enumerate(zip(S,T)):
    s[j] += [i]
    t[k] += [i]
a = sorted(s.values())
b = sorted(t.values())

print('Yes' if a==b else "No")

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

void fnInput(vector<int>& rvnBallCnt, int& rnVarie)
{
  int nBallSiz;
  cin >> nBallSiz >> rnVarie;

  rvnBallCnt.resize(nBallSiz);
  for (int i = 0; i < nBallSiz; i++)
  {
    int nBall;
    cin >> nBall;
    rvnBallCnt[nBall - 1]++;
  }
}

int fnRewCount(vector<int>& rvnBallCnt, int nVarie)
{
  sort(begin(rvnBallCnt), end(rvnBallCnt));
  int nRewCnt = 0;

  for (int i = 0; i < rvnBallCnt.size() - nVarie; i++)
    nRewCnt += rvnBallCnt[i];

  return nRewCnt;
}

int main()
{
  vector<int> vnBallCnt;
  int nVarie;
  fnInput(vnBallCnt, nVarie);
  cout << fnRewCount(vnBallCnt, nVarie) << endl;

  return 0;
}

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

const long long int INF = 1e18;

struct edge{
    int to;
    long long int cost;
};

int V,E;// number of (vertices, edges)
vector<vector<edge>> graph;
vector<long long int> d;// shortest distances
vector<int> previous_node;

void Dijkstra(int s){// s = starting point
    priority_queue<
        pair<int, int>// temporarily keeping (shortest distance, vertex)
        , vector<pair<int, int>>, greater<pair<int, int>>// shorter ones first
    > pq;

    // initialize (INF)
    for(int i=0; i<V; i++){
        d[i] = INF;
    }
    d[s] = 0;
    pq.push({0,s});

    // search
    pair<int, int> current;// (shortest-distance confirmed, vertex)
    while(!pq.empty()){
        current = pq.top();
        pq.pop();

        int v = current.second;
        if(d[v] < current.first){
            continue;// no need to update d[v]
        }
        // else
        for(int i=0; i<graph[v].size(); i++){
            edge e = graph[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;// update minimum cost
                pq.push({d[e.to], e.to});
                previous_node[e.to] = v;// path : (v) --> (e.to)
            }
        }
    }
}

int main(){
    int s;// starting point

    int n;
    cin >> n;
    V = n;
    E = n-1;
    graph.resize(V);
    d.resize(V);
    previous_node.assign(V, -1);

    for(int i=0; i<E; i++){
        int u, v, w;
        cin >> u >> v >> w;
        u -= 1;
        v -= 1;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    int q, k;
    cin >> q >> k;
    s = k - 1;
    Dijkstra(s);// starting from s

    vector<int> x(q), y(q);
    for(int i=0; i<q; i++){
        cin >> x[i] >> y[i];
    }
    for(int i=0; i<q; i++){
        cout << d[x[i]-1] + d[y[i]-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 11136
#include <stdio.h>

int main(){

  int x, y;
  int r;

  scanf("%d%d", &x, &y);


  //ユークリッド
  r = x % y;

  while(r != 0){
    x = y;

    y = r;

    r = x % y;  
  }

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

  return 0;
}

Measured memory_bytes: 592
from itertools import product

H,W,K=map(int,input().split())
masu=[input() for _ in range(H)]
ans=0
ROW=list(product([False,True],repeat=H))
COL=list(product([False,True],repeat=W))
for row in ROW:
  for col in COL:
    cnt=0
    for i in range(H):
      for j in range(W):
        if row[i]==False and col[j]==False and masu[i][j]=="#":
          cnt+=1
    if cnt==K:
      ans+=1
print(ans)


Measured memory_bytes: 9200
#include<stdio.h>

 void ex(int *a,int *b){
      int tmp;
      tmp=*a;
      *a=*b;
      *b=tmp;
      }

 int main(){
     int a,b,c;
     scanf("%d%d%d",&a,&b,&c);
     if(a>b)ex(&a,&b);
     if(b>c)ex(&b,&c);
     if(a>b)ex(&a,&b);
     printf("%d %d %d\n",a,b,c);
     return 0;
     }


Measured memory_bytes: 2076
# include <algorithm>
# include <cassert>
# include <cctype>
# include <cstdio>
# include <cstdlib>
# include <cstring>
# include <cmath>
# include <iostream>
# include <map>
# include <queue>
# include <set>
# include <sstream>
# include <stack>
# include <string>
# include <vector>
# include <iomanip>

# define rep(i, n) for (int i = 0; i < (int)(n); i++)
# define irep(i, n) for (int i = int(n) - 1; i >= 0; i--)
# define FOR(i, m, n) for (int i = int(m); i < (int)(n); i++)

using namespace std;
typedef long long ll;


// %% begin matrix %%

typedef vector<int> vec;
typedef vector<vec> mat;

void pretty_print(mat g) {
  rep (i, g.size()) {
    rep (j, g[0].size()-1) {
      cout << g[i][j] << ' ';
    }
    cout << g[i][g[0].size()-1] << endl;
  }
}


mat mul(mat A, mat B) {
  mat C(A.size(), vec(B.size()));
  rep (i, A.size()) {
    rep (k, B.size()) {
      rep (j, B[0].size()) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  return C;
}

// %% end matrix %%


int main() {

  string S;
  cin >> S;

  vector<char> p = {'N', 'W', 'S', 'E'};
  map<char, int> dict;

  rep (i, p.size()) dict[p[i]] = 0;

  rep (i, S.size()) dict[S[i]]++;

  if (((dict['S'] > 0 || dict['N'] > 0) && dict['S'] * dict['N'] == 0) ||
      ((dict['W'] > 0 || dict['E'] > 0) && dict['W'] * dict['E'] == 0 )) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" <<endl;
  }
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
  int h,m,s;
  long S;

  cin>>S;

  if(S>=3600){
    h = S/3600;
    S = S-(3600*h);
  }
  else{
    h = 0;
  }

  if(S>=60){
    m = S/60;
    S = S-(60*m);
  }
  else{
    m = 0;
  }

  s = S;

  cout<<h<<":"<<m<<":"<<s<<endl;

  return 0;
}

Measured memory_bytes: 3084
#include<iostream>

using namespace std;

#define NUM_DAY 365
#define NUM_ALPHABET 26

int c[NUM_ALPHABET];
int s[NUM_DAY][NUM_ALPHABET];

int calc_total_score(int* type)
{
  int _last[NUM_ALPHABET];
  int score = 0;
  
  for(int d=1;d<=NUM_DAY;d++)
  {
    _last[type[d-1]]=d;
    for(int i=0;i<NUM_ALPHABET;i++)
    {
      score -= c[i] * (d - _last[d]);
    }
    score += s[d-1][type[d-1]];
  }
  
  return score;
}

int main()
{
  int D;
  cin >> D;
  
  
  for(int i = 0; i < NUM_ALPHABET; i++)
    cin >> c[i];
  
  
  for(int d=0;d<D;d++)
      for(int i = 0; i < NUM_ALPHABET; i++)
		cin >> s[d][i];

  int last[NUM_ALPHABET];

  
  for(int d=1;d<=D;d++)
  {
    int max_i = -1;
    int max_s = -1;
    
    for(int i = 0; i < NUM_ALPHABET; i++)
    {
      //calc max
      int di = d - 1;
      int score = c[i] * (d - last[i]) + s[d-1][i];
      if(score>max_s)
      {
        max_i = i;
        max_s = score;
      }
    }
    
    last[max_i] = d;
    cout << max_i + 1 << endl;
  }
  
  return 0;
}

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

int N, D;
int num[1000][1000];
int rad1[1000][1000], rad2[1000][1000];

int imos[2001][2001];
bool check(int X){
    int d = X/D, r = X%D;
    memset(imos, 0, sizeof(imos));

    for(int i=0; i<D; i++){
        for(int j=0; j<D; j++){
            if(rad2[i][j] > d+1) return false;
            if(rad2[i][j] <= d){
                imos[i][j]++;
                imos[i][j+D]--;
                imos[i+D][j]--;
                imos[i+D][j+D]++;
                continue;
            }

            if(rad1[i][j] == d){
                imos[i][j]++;
                imos[i][j+D]--;
                imos[i+D][j]--;
                imos[i+r+1][j+r+1]--;
                imos[i+D][j+r+1]++;
                imos[i+r+1][j+D]++;
            }else{
                imos[i][j]++;
                imos[i][j+r+1]--;
                imos[i+r+1][j]--;
                imos[i+r+1][j+r+1]++;
            }
        }
    }

    for(int i=0; i<=2*D; i++){
        for(int j=1; j<=2*D; j++) imos[i][j] += imos[i][j-1];
    }
    for(int i=1; i<=2*D; i++){
        for(int j=0; j<=2*D; j++) imos[i][j] += imos[i-1][j];
    }
    for(int i=0; i<D; i++){
        for(int j=0; j<D; j++){
            if(imos[i][j] + imos[i][j+D] + imos[i+D][j] + imos[i+D][j+D] == D*D) return true;
        }
    }
    return false;
}

int main(){
    cin >> N >> D;
    for(int i=0; i<N; i++){
        int x, y;
        cin >> x >> y;
        num[x%D][y%D]++;
    }

    for(int i=0; i<D; i++){
        for(int j=0; j<D; j++){
            while(rad1[i][j] * (rad1[i][j]+1) < num[i][j]) rad1[i][j]++;
            while(rad2[i][j] * rad2[i][j] < num[i][j]) rad2[i][j]++;
        }
    }

    int ng = -1, ok = 1e9;
    while(ok-ng>1){
        int mid = (ok+ng)/2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << endl;
    return 0;
}

Measured memory_bytes: 27648
a = map(int,raw_input().split())
a.sort()

count = 0

d = [0,0]

d[0] = a[2] - a[1]
d[1] = a[2] - a[0]
d.sort()

while d[0] != 0:
  d[0] -= 1
  d[1] -= 1 
  count += 1

if d[1] == 0:
  print count
  exit(0)

if d[1] % 2 == 1:
  d[1] += 1
  count += 1

count += d[1]/2
print count


Measured memory_bytes: 2568
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
const ll MOD = 1e9+7;


#define REP(i, N) for (ll i = 0; i < (N); i++)
#define REPP(i, a, b) for (ll i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((ll)(x).size())
//vvintを作る　マクロで　 #define vvint(N,M) vector<vector<ll>>

using namespace std;


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

    string n;
    cin >> n;

    for(ll i = 0; i < n.length();i++){
        if(n[i] == '7'){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for(int i = 0; i < n; i++)
void Yn(bool flg){cout<<(flg?"Yes":"No")<<endl;}
void YN(bool flg){cout<<(flg?"YES":"NO")<<endl;}
void yn(bool flg){cout<<(flg?"yes":"no")<<endl;}

signed main(){
  int N;
  string S;
  cin >> N >> S;
  REP(i,S.size()){
    int b = S.at(i) - 'A';
    b = (b + N)% 26;
    S.at(i) = 'A' + b;
  }
  cout << S << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,bool>h;
int main(){
	int n;
	cin>>n;
	int ans=0;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		if(!h[s]) {
			ans++;
			h[s]=true;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 17732
#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
#define INF (1LL << 60)
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,k,n) for(int i=(k);(i)<(n);(i)++)
#define REP(i,n) for(int i = 0;(i)<(n);(i)++)
#define REPR(i,n) for(int i = n; i >= 0; i--)
#define F first
#define S second

int main() {
	int n;
	cin >> n;
	vector<int> p(n);
	REP(i, n) cin >> p[i];
	int ans = 0;
	auto itr = max_element(ALL(p));
	int index = distance(p.begin(), itr);
	REP(i, n) {
		if (i == index) {
			ans += p[i] / 2;
		}
		else {
			ans += p[i];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
     string s, t, u;
     int a, b;
     cin >> s >> t >> a >> b >> u;
     if(s == u)a--;
     else b--;
     cout << a << " " << b;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N;
    cin >> N;
    vector<int> A(2 * N);
    rep(i, 2 * N) cin >> A[i];
    sort(all(A));
    ll ret = 0;
    rep(i, N) ret += A[2 * i];
    output(ret, 0);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const long long INF = 1LL << 60;
const int MOD = 1000000007;
signed main(void){
    int n; cin>>n;
    vector <pair <int,int>> a(n);
    priority_queue <pair<int,int>, vector <pair<int,int>>, greater <pair<int,int>>> pq;
    rep(i,n) {cin>>a[i].F; a[i].S = i; }
    set <int> se;
    se.insert(-1); se.insert(n);
    int ans = 0;
    sort(a.begin(),a.end(),greater<pair <int,int>>());
    se.insert(a[0].S);
    for(int i=1;i<n;i++){
        auto it = (--se.lower_bound(a[i].S));
        auto it2 = (se.lower_bound(a[i].S));
        //cout<<*it<<' '<<*it2<<endl;
        if(*it != -1&& (*it2) !=n){
            //cout<<*it2<<' '<<a[i].S<<endl;
            int l1 = abs(*it - a[i].S), r1 = abs(*it2 - a[i].S);
            int l2 = abs(*it - * (--it)), r2 = abs(*it2 - *(++it2));
            //cout<<a[i].F<<':'<<l2<<' '<<l1<<' '<<r1<<' '<<r2<<endl;
            ans += a[i].F*(l1*r2 + r1*l2);
            //cout<<a[i].F*(l1*r2 + r1*l2)<<endl;
        }else if(*it ==-1){
            int l = a[i].S+1;
            int r = abs(*it2 - *(++it2));
            ans += a[i].F*(r * l);
            //cout<<a[i].F<<':'<<l<<' '<<r<<endl;
        }else{
            int r = n-a[i].S;
            int l =abs(*it - *(--it));
            ans += a[i].F*(l*r);
            //cout<<a[i].F<<':'<<l<<' '<<r<<endl;
        }
        se.insert(a[i].S);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
int n,a[MAXN];
int res=0;
void solve1()//-
{
	cout<<res+2*a[n]<<endl;
	int x=a[n];
	for(int i=n-1;i>=1;--i)
	{
		printf("%lld %lld\n",x,a[i]);
		x-=a[i];
	}
}
void solve2()//+
{
	cout<<res-2*a[1]<<endl;
	int x=a[1];
	for(int i=2;i<n;++i)
	{
		printf("%lld %lld\n",x,a[i]);
		x-=a[i];
	}
	printf("%lld %lld\n",a[n],x);
}
int stk1[MAXN],stk2[MAXN];
int tp1=0,tp2=0;
void solve3()//+,-
{
	cout<<res<<endl;
	int zr=0;
	for(int i=1;i<=n;++i)
	{
		if(a[i]>0)
			stk1[++tp1]=a[i];
		else if(a[i]<0)
			stk2[++tp2]=a[i];
		else
			++zr;
	}
	assert(zr!=n);
	while(zr--)
		printf("%lld 0\n",stk1[tp1]);
	assert(tp1 && tp2);
	while(tp1!=1 && tp2!=1)
	{
		int x=stk1[tp1];
		--tp1;
		int y=stk1[tp1];
		--tp1;
		int z=stk2[tp2];
		--tp2;
		printf("%lld %lld\n",z,y);
		printf("%lld %lld\n",x,z-y);
		stk1[++tp1]=x+y-z;
	}
	if(tp1==1)
	{
		int x=stk1[tp1];
		while(tp2)
		{
			printf("%lld %lld\n",x,stk2[tp2]);
			x-=stk2[tp2--];
		}
	}
	else
	{
		int x=stk2[tp2];
		for(int i=1;i<tp1;++i)
		{
			printf("%lld %lld\n",x,stk1[i]);
			x-=stk1[i];
		}
		printf("%lld %lld\n",stk1[tp1],x);
	}
}
signed main()
{
	n=read();
	bool f1=false,f2=false;
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		res+=abs(a[i]);
		if(a[i]>0)
			f1=true;
		if(a[i]<0)
			f2=true;
	}
	sort(a+1,a+1+n);
	if(!f1)
		solve1();
	else if(!f2)
		solve2();
	else
		solve3();
	return 0;
}

Measured memory_bytes: 4736
from functools import reduce
mod=10**9+7
def nCk(n,k):
  c=reduce(lambda x,y: x*y%mod, range(n,n-k,-1))
  m=reduce(lambda x,y: x*y%mod, range(1,k+1))
  return c*pow(m,mod-2,mod)%mod

n,a,b=map(int,input().split())

ans=pow(2,n,mod)-nCk(n,a)-nCk(n,b)-1
ans%=mod
print(ans)

Measured memory_bytes: 3572
N, K = map(int, raw_input().split())
h = [0]*N
for i in range(N):
  h[i], = map(int, raw_input().split())
h.sort()
r = h[-1]-h[0]
for i in range(N-K+1):
  r = min(r, h[i+K-1]-h[i])
print r

Measured memory_bytes: 8964
#include <bits/stdc++.h>
#define ll long long
#define INF INT_MAX 
#define mod 1000000007
using namespace std;
int main(){
    int R,G,B,N;
    int count = 0;
    cin >> R >> G >> B >> N;
    
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            if((N>=(R*i+G*j)&&(N-(R*i+G*j))%B==0)){
                count++;
            } 
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
const int maxn=100000+7;
using namespace std;
struct qaq
{
	int v;
	bool odd;
}a[maxn];
int n,ans=0;
bool comp(qaq x,qaq y);
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i].v);
		a[i].odd=i%2;
	}
	sort(a+1,a+n+1,comp);
	for(int i=1;i<=n;++i)
	{
		if(a[i].odd!=i%2)
			++ans;
	}
	printf("%d",ans/2);
	return 0;
}
bool comp(qaq x,qaq y)
{
	return x.v < y.v;
}

Measured memory_bytes: 1024
from collections import defaultdict
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
names = defaultdict(int)
for i in range(N):
    name = s()
    if name[0] not in 'MARCH':
        continue
    names[name[0]] += 1

total = 0
cand = ''.join(names.keys())
import itertools
for p in itertools.combinations(cand, 3):
    total += names[p[0]] * names[p[1]] * names[p[2]]
print(total)



Measured memory_bytes: 3436
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>

using namespace std;

#define forn(I,N) for (int I = 0; I < (N); ++I)
#define fornd(I,N) for (int I = (N) - 1; I >= 0; --I)
#define forab(I,A,B) for (int I = (A); I <= (B); ++I)
#define forabd(I,A,B) for (int I= (B); I >= (A); --I)
#define FOREACH(I,A) for (__typeof__(A)::iterator I=A.begin(); I<A.end(); I++)
#define all(V) (V).begin(), (V).end()
#define pb push_back
#define mp make_pair

typedef long long int ll;

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

const ll mod = 1000000007;

int main() {
  int N, M;
  cin >> N >> M;

  vector<ll> S(N), T(M);
  
  forn(i, N) {
    cin >> S[i];
  }

  forn(j, M) {
    cin >> T[j];
  }

  vector<ll> res(M);
  forn(i, N) {
    ll tempSum = 0;
    forn(j, M) {
      ll buf = res[j];
      if (S[i] == T[j]) {
        res[j] = (res[j] + 1 + tempSum) % mod;
      }
      tempSum = (tempSum + buf) % mod;
    }
  }

  ll ans = 1;
  forn(i, M) {
    ans = (ans + res[i]) % mod;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <cstring>
#include <fstream>

using namespace std;

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

	int n, a, b;
	int res = 0;
	vector <pair<int, int>> v;

	cin >> n;

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

	res = v[0].first + v[0].second;

	for (int i = 1; i < n; i++)
	{
		res = min(res, v[i].first + v[i].second);
	}

	cout << res << '\n';

	return 0;
}


Measured memory_bytes: 1400
/* ex4_2
   kohei_suzuki */

#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>

int main(void){
    double short_hand, long_hand, hour, min;//短針,長針,時間,分
    double angle, ans;//角度,答え

    scanf("%lf %lf %lf %lf",&short_hand, &long_hand, &hour, &min);//入力受取
    angle = fabs(hour*30.0 + min/2.0 - min*6.0) / 180.0 * M_PI;//角度を求める

    ans = sqrt(pow(short_hand ,2.0)+ pow(long_hand, 2.0) - 2 * short_hand * long_hand * cos(angle));//余弦定理で答えを求める

    printf("%.9f\n",ans); //答えの出力
    return 0;
}

Measured memory_bytes: 2580
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn];
int l[maxn];
int r[maxn];
int n;
int ans;
inline int gcd(int a,int b){
	return b?gcd(b,a%b):a; 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	l[1]=a[1]; r[n]=a[n];
	for(int i=2;i<=n;i++) l[i]=gcd(l[i-1],a[i]);
	for(int i=n-1;i>=1;i--) r[i]=gcd(r[i+1],a[i]);
	ans=max(r[2],l[n-1]);
	for(int i=2;i<=n-1;i++)
		ans=max(ans,gcd(l[i-1],r[i+1]));
	cout<<ans<<endl;
	return 0;
}

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

int main(void){
	int n;
	cin >> n;
	std::vector<int> a(n), r(n);
	for (int i = 0; i < n; ++i){
		cin >> a[i];
	}
	long long ans = 0;
	for(int i = 0; i < n; ++i){
		if(i%2==0){
			ans += a[i];
		}else{
			ans -= a[i];
		}
	}
	r[0] = ans/2;
	for(int i = 1; i < n; ++i){
		r[i] = a[i-1] - r[i-1];
	}
	for(int i = 0; i < n; ++i){
		cout << 2*r[i];
		if(i!=n-1) cout << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 2048
#include<stdio.h>

int main()
{
    int a,c;
    scanf("%X%X",&a,&c);
    if(a==c){
        printf("=\n");
    }
    else if(a>c){
        printf(">\n");
    }
    else{
        printf("<\n");
    }


    return 0;
}


Measured memory_bytes: 128
#今日の精進
#KI
n,q=map(int,input().split())
Node=[0 for i in range(n+1)]
visited=[ False for i in range(n+1)]
from collections import deque
ki_list={i: [] for i in range(1,n+1)}
for i in range( n-1):
    a,b=map(int,input().split())
    ki_list[a].append(b)
    ki_list[b].append(a)
visited[1]=True
d=deque()
e=deque()
d.append(1)
#点の保存リスト
for _ in range(q):
    node,score=map(int,input().split())
    Node[node]+=score

while d:
    for some in d:               
        for point in ki_list[some]:
            if visited[point]==False:
                visited[point]=True
                Node[point]+=Node[some]
                e.append(point)
            elif visited[point]==True:
              pass

    d=e
    e=deque()
print(*Node[1:])
  

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int main(void){
	int64 N;
	while(cin >> N && N){
		vector<set<int64>> p(N, set<int64>());
		vector<int64> l;
		REP(i, N){
			int32 M;
			cin >> M;
			int64 x;
			REP(j, M){ cin >> x; p[i].insert(x); }
		}
		int32 K;
		cin >> K;
		l.resize(K);
		REP(i, K) cin >> l[i];

		int32 res = -1;
		bool ok = 1;
		REP(i, N){
			bool ok2 = 1;
			REP(j, K){
				if(p[i].find(l[j]) == p[i].end()) ok2 = 0;
			}
			if(ok2){
				if(res != -1) ok = 0;
				res = i+1;
			}
		}
		cout << (ok && res != -1 ? res : -1) << endl;
	}
}



Measured memory_bytes: 3408
// A - Airport Bus

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int T[100000];

int main() {
	int N, C, K;
	cin >> N >> C >> K;

	for (int i=0; i<N; i++) {
		cin >> T[i];
	}

	sort(T, T+N);

	queue<int> q;

	for (int i=0; i<N; i++) {
		q.push(T[i]);
	}

	int cnt = 0;
	while(! q.empty()) {
		cnt++;
		int c = 1;
		int t = q.front() + K;
		q.pop();

		while(! q.empty()) {
			if (c == C) break;
			if (q.front() > t) break;

			c++;
			q.pop();
		}
	}

	int ans = cnt;

	cout << ans << endl;

	return 0;
}

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

int main() {
  int n,m,x; cin >>n >>m >>x;
  vector<int> b(n+1);
  for (int i=0; i<m; i++){
    int buf; cin >>buf;
    b.at(buf) = 1;
  }
  
  int cost1=0, cost2=0;
  for (int i=0; i<=n; i++){
    if (i<=x) cost1 += b.at(i);
    else cost2 += b.at(i);
  }
  cout <<min(cost1,cost2) <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))
 
typedef long long ll;
 
using namespace std;
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s; cin>>s;
  
  s[3] = '8';
  cout<<s;
    
  return 0;
}

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

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using VP = vector<PII>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = INT64_MAX >> 1;
const int INF = INT_MAX >> 1;

inline int sqr(int x) { return (x * x); }
inline void printd(double x) { printf("%.10lf\n", x); }
inline void upsort(VI& x) { sort((x).begin(), (x).end()); }
inline void downsort(VI& x) { sort((x).begin(), (x).end(), greater<int>()); }
inline int absdiff(int a, int b) { return (a - b) * (static_cast<int>(a > b)*2 - 1); }
int gcd(int a, int b) { // 最大公約数
	if (a < b) return gcd(b, a);
	int r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
inline int lcm(int a, int b) { return a * b / gcd(a, b); } // 最小公倍数
#pragma endregion

signed main()
{	
	LL N, K;
	cin >> N >> K;
	VLL A(N);
	rbf(a, A) cin >> a;

	VLL mem(N, -1);
	LL pos = 1, cnt = 0;
	while (1) {
		if (mem[pos - 1] >= 0) break;
		mem[pos - 1] = cnt++;
		pos = A[pos - 1];
		if (cnt == K) break;
	}

	if (cnt < K) {
		LL amari = (K - mem[pos - 1]) % (cnt - mem[pos - 1]);
		rep(i, amari) {
			pos = A[pos - 1];
		}
	}

	COL(pos);
	return 0;
}

Measured memory_bytes: 6428
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 1010;

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//組み合わせの余りを求める
ll fac[MAX_N], finv[MAX_N], inv[MAX_N];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX_N; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll dp[101010];


//long longしか使わない
//素数は1より大きい
int main() {
	ll n;
	cin >> n;
	ll ans = 0;
	vector<ll>a(n + 1);
	for (ll i = 1;i <= n;++i) {
		ll target = i;
		ll res = n / i;
		for (ll j = 1;j <= res;++j) {
			a[i * j]++;
		}
	}
	for (ll i = 1;i <= n;++i) {
		ans += a[i] * i;
	}
	cout << ans << endl;
	return 0;
}


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

using namespace std;

int main(void)
{
    int n;
    cin >> n;

    bool approved = true;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a % 2 == 1) continue;
        approved &= (a % 3 == 0 || a % 5 == 0);
    }

    cout << (approved ? "APPROVED" : "DENIED") << endl;


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
#define MOD (long long int)(1e9+7)
#define ll long long int


int main(void){
	int n,m;
	cin>>n>>m;
	cout<<(n-1)*(m-1)<<endl;
	return 0;	
}


Measured memory_bytes: 256
#include "stdio.h"

int main(){
	int n, a[100], x, i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d", &a[i]);	
	}
	for(i=0;i<n-1;i++){
		printf("%d ", a[n-1-i]);	
	}
	printf("%d\n", a[0]);
	return 0;
}

Measured memory_bytes: 596
program main
   implicit none
   integer(8)::n,i,counter=0,counter0=0
   integer(8),allocatable,dimension(:)::a
   read(*,*)n
   allocate(a(n))
   read(*,*)a
   do i=1,n
      if(a(i)<0)then 
         counter=counter+1
         a(i)=-a(i)
      endif
      if(a(i)==0)counter0=counter0+1
   enddo
   call heapsort(n,a)
   if(mod(counter,2)==0 .or. counter0>0)then
      write(*,*)sum(a)
   else
      write(*,*)sum(a(2:n))-a(1)
   endif
   
contains
subroutine heapsort(n,array)
  implicit none
  integer(8),intent(in) :: n
  integer(8),intent(inout) :: array(1:n)
  
  integer(8) ::i,k,j,l
  integer(8) :: t
  
  if(n.le.0)then
     write(6,*)"Error, at heapsort"; stop
  endif
  if(n.eq.1)return

  l=n/2+1
  k=n
  do while(k.ne.1)
     if(l.gt.1)then
        l=l-1
        t=array(L)
     else
        t=array(k)
        array(k)=array(1)
        k=k-1
        if(k.eq.1) then
           array(1)=t
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j.le.k)
        if(j.lt.k)then
           if(array(j).lt.array(j+1))j=j+1
        endif
        if (t.lt.array(j))then
           array(i)=array(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
  enddo

  return
end subroutine heapsort
end program main


Measured memory_bytes: 1536
def solve():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))[::-1]
    cnt = [0]*(n+1)
    for x in a: cnt[x]+=1
    for x in b: cnt[x]+=1
    for x in cnt:
        if x  > n :
            print("No")
            return
    l = 0
    r = n-1;
    for i in range(n):
        if a[i] == b[i]:
            if b[l] != a[i] and a[l] != a[i]:
                b[l],b[i] = b[i],b[l]
                l+=1
            else:
                b[r],b[i] = b[i],b[r]
                r-=1
    print("Yes")
    print(" ".join(str(x) for x in b))

solve();


Measured memory_bytes: 122504
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long;
int main() {
  int n;
  cin >> n;
  vector<ll> a(n), sum(n + 1, 0);
  map<ll, ll> mp;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    sum[i + 1] = sum[i] + a[i];
    mp[sum[i]]++;
  }
  mp[sum[n]]++;
  ll ans = 0;
  for(auto p : mp) {
    ans += p.second * (p.second - 1) / 2;
  }
  cout << ans << endl;

  return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

//　タプルのソート
using T = tuple<ll, ll, ll>;
class CompareFirst{ public:
    bool operator()(T n1, T n2) {
        return get<0>(n1) < get<0>(n2);  // 降順
    }
};

void Main() {
    ll N; cin >> N;
    vector<ll> A(N); rep(i, N){cin >> A.at(i);}
    sort(A.begin(), A.end(), greater<ll>());  // 大きい方から取り出す
    // (score(=smaller), larger, smaller) の組を更新

    priority_queue<T, vector<T>, CompareFirst> q;
    q.push(make_tuple(A.at(1), A.at(0), A.at(1)));
    q.push(make_tuple(A.at(1), A.at(0), A.at(1)));
    ll ans = A.at(0);

    rep(i, N - 2){
        T t = q.top();
        q.pop();
        q.push(make_tuple(A.at(i + 2), get<1>(t), A.at(i + 2)));
        q.push(make_tuple(A.at(i + 2), get<2>(t), A.at(i + 2)));
        ans += get<0>(t);
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2e3 + 123;
const int mod = 1e9 + 7;

int n, k, ans = mod;
vector < int > g[N];
int cnt[N][N], now, mx[N][N];

void dfs (int v, int pr = 0, int len = 0) {
	cnt[now][len] ++;
	if (len == k / 2 + 1) mx[now][v] ++;
	for (int to : g[v])
		if (to != pr) {
			dfs (to, v, len + 1);
			if (v == now)
				mx[now][v] = max (mx[now][v], mx[now][to]);
			else mx[now][v] += mx[now][to];
		}
}

int main () {
	scanf ("%d%d", &n, &k);
	for (int i = 1;i < n;i ++) {
		int u, v;
		scanf ("%d%d", &u, &v);
		g[u].pb (v);
		g[v].pb (u);
	}
	for (int i = 1;i <= n;i ++) {
		now = i;
		dfs (i);
		for (int j = 1;j <= n;j ++) 
			cnt[now][j] += cnt[now][j - 1];
		if (k % 2) ans = min (ans, n - (cnt[now][k / 2] + mx[now][now]));
		ans = min (ans, n - cnt[now][k / 2]);
	}
	printf ("%d", max (ans, 0));
 	return 0;                                                  	
}


Measured memory_bytes: 35328
s = input().split(' ')
n = 0
if int(s[0]) > 0:
    n += 1
if int(s[1]) > 0:
    n += 1
if int(s[2]) > 0:
    n += int(s[2])
coupon = []
for times in range(1, n+1):
    if times == 1:
        ref = input().split(' ')
    if times == 2:
        micro = input().split(' ')
    if times > 2:
        coupon.append(input().split(' '))
price = int(ref[0]) + int(micro[0])
minPrice = price
for discount in coupon:
    price = int(ref[int(discount[0])-1]) + int(micro[int(discount[1])-1]) - int(discount[2])
    minPrice = min(minPrice, price)
ref.sort()
micro.sort()
price = int(ref[0]) + int(micro[0])
minPrice = min(minPrice, price)
print(minPrice)

Measured memory_bytes: 50804
//Badwaper gg
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define lowbit(x) x&(-x)
#define Z(x) (x>=mod?x-mod:x)
#define N 3010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
int G[N],F[N][N],P[N];
int n,S[N][N],mod,C[N][N];
inline int ksm(int a,int b,int mod)
{
	int ans=1;
	while(b){if(b&1)ans=1LL*ans*a%mod;b>>=1;a=1LL*a*a%mod;}
	return ans;
}
inline int Solve(int i)
{
	int sum=0;
	FOR(x,1,i+1)sum=Z(sum+1LL*S[i+1][x]*F[n-i][x-1]%mod);
	return sum;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),mod=read();
	FOR(i,0,n+1)G[i]=ksm(2,ksm(2,i,mod-1),mod);
	FOR(i,0,n+1)P[i]=ksm(2,i,mod);
	S[0][0]=1;
	FOR(i,1,n+1)
	{
		FOR(j,1,i)S[i][j]=Z(S[i-1][j-1]+1LL*S[i-1][j]*j%mod);
	}
	C[0][0]=1;
	FOR(i,1,n+1)
	{
		C[i][0]=1;
		FOR(j,1,i)C[i][j]=Z(C[i-1][j-1]+C[i-1][j]);
	}
	FOR(i,0,n+1)
	{
		F[i][0]=1;
		FOR(j,1,n+1)F[i][j]=1LL*F[i][j-1]*P[i]%mod;
	}
	int ans=0,c=1;
	FOR(i,0,n){ans=Z(ans+1LL*c*C[n][i]%mod*G[n-i]%mod*Solve(i)%mod);c=mod-c;}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 94160
#define _USE_MATH_DEFINES // M_PI
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rREP(i,a,n) for(int (i)=(n)-1; (i)>=(a);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 2147483647;
constexpr ll mod = 1000000007;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int H; cin >> H;
	int N; cin >> N;
	vector<pair<int, int>>AB(N);
	rep(i, N) {
		int a, b; cin >> a >> b;
		AB[i] = make_pair(a, b);
	}
	vector<ll>dp(H + 1, INF);
	dp[H] = 0;
	ll ans = INF;
	for (int i = H;i >= 1;--i) {
		if (dp[i] == INF)continue;
		rep(j, N) {
			if (i <= AB[j].first) {
				chmin(ans, dp[i] + AB[j].second);
			}
			else {
				chmin(dp[i - AB[j].first], dp[i] + AB[j].second);
			}
		}
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 384
#C - Energy Drink Collector
n,m = map(int,input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
abSorted = sorted(ab)
sumB = 0
sumMoney = 0
i = 0
while sumB + abSorted[i][1] < m:
    sumB += abSorted[i][1]
    sumMoney += abSorted[i][0] * abSorted[i][1]
    i += 1
sumMoney += abSorted[i][0] * (m - sumB)
print(sumMoney)

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

int a[3],sum=3;

int main(){
	cin >> a[0] >> a[1] >> a[2];
	for(int i=0;i<3;i++){
		for(int j=i+1;j<3;j++){
			if(a[i]==a[j]) sum-=1;
		}
	}
	cout << (sum?sum:1) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  int N;
  cin>>N;
  int count=0;
  bitset<8> A;
  rep(i,0,N){
    int X;
    cin>>X;
    if(X<3200)
      A.set(X/400);
    else
      count++;
  }
  int sum=A.count();
  cout<<max(1LL,sum)<<" "<<sum+count;
  }


Measured memory_bytes: 256
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=parseInt.(x)

function main()
	n,m = readline() |> split |> parseMap
	dp = (10^9)*ones(Int,m+1,2^n)
	dp[1,1] = 0
	for i in 1:m
		a,b = readline() |> split |> parseMap
		c = readline() |> split |> parseMap
		d = 0
		for j in 1:b
			d += 2^(c[j]-1)
		end
		for j in 1:2^n
			dp[i+1,j] = dp[i,j]
		end
		for j in 1:2^n
			dp[i+1,((j-1)|d)+1] = min(dp[i+1,((j-1)|d)+1],dp[i,j]+a)
		end
	end
	if dp[m+1,2^n] == 10^9
		println(-1)
	else
		println(dp[m+1,2^n])
	end
end
main()

Measured memory_bytes: 178940
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        outside:for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (x == 2) {
                ans++;
                continue;
            }
            if (x < 2 || x % 2 == 0)
                continue;
            int j = 3;
            while (j <= Math.sqrt(x)) {
                if (x % j == 0)
                    continue outside;
                j += 2;
            }
            ans++;
        }
        System.out.println(ans);
        sc.close();
    }
}


Measured memory_bytes: 42816
# 基本的に問題はここで解く。

# 1を回転させる。
input_1 = gets.chomp.split("")
input_2 = gets.chomp.split("")


(input_1.length).times do |i|
    if input_1 == input_2
        puts "Yes"
        exit
    end

    temp = input_1.shift
    input_1.push(temp)

end

puts "No"



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

int main(){
  bool is_prime[1000000];

  is_prime[0]=is_prime[1]=false;
  for(int i=2; i<1000000; i++){
    is_prime[i]=true;
  }

  for(int i=2; i*i<1000000; i++){
    if(is_prime[i]){
      for(int j=i*i; j<1000000; j+=i){
        is_prime[j]=false;
      }
    }
  }

  int n_prime[1000000];
  int cnt=0;

  for(int i=0; i<1000000; i++){
    if(is_prime[i]){
      cnt++;
    }
    n_prime[i]=cnt;
  }

  while(true){
    int n;
    cin >> n;

    if(cin.eof())
      break;

    cout << n_prime[n] << endl;
  }

  return 0;
}


Measured memory_bytes: 7936
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] s = sc.next().toCharArray();
        char m = 'o';
        char b = 'x';
        boolean[] ans = null;
        for (int i = 0; i < 4; i++) {
            boolean[] a = new boolean[n];
            if((i&1) == 1) a[0] = true;
            else a[0] = false;
            if((i>>1 & 1) == 1) a[n-1] = true;
            else a[n-1] = false;
            if(a[0] && s[0] == m) a[1] = a[n-1];
            else if(a[0] && s[0] == b) a[1] = !a[n-1];
            else if(!a[0] && s[0] == m) a[1] = !a[n-1];
            else if(!a[0] && s[0] == b) a[1] = a[n-1];
            for (int j = 1; j < n-2; j++) {
                if(a[j] && s[j] == m) a[j+1] = a[j-1];
                else if(a[j] && s[j] == b) a[j+1] = !a[j-1];
                else if(!a[j] && s[j] == m) a[j+1] = !a[j-1];
                else if(!a[j] && s[j] == b) a[j+1] = a[j-1];
            }
            if(((a[n-2] && s[n-2] == m) || (!a[n-2] && s[n-2] == b)) && a[n-3] != a[n-1]) continue;
            if(((a[n-2] && s[n-2] == b) || (!a[n-2] && s[n-2] == m)) && a[n-3] == a[n-1]) continue;
            if(((a[n-1] && s[n-1] == m) || (!a[n-1] && s[n-1] == b)) && a[n-2] != a[0]) continue;
            if(((a[n-1] && s[n-1] == b) || (!a[n-1] && s[n-1] == m)) && a[n-2] == a[0]) continue;
            ans = a;
            break;
        }
        if(ans == null) System.out.println(-1);
        else{
            StringBuilder sb = new StringBuilder();
            for(boolean c : ans){
                if(c) sb.append("S");
                else sb.append("W");
            }
            System.out.println(sb.toString());
        }
        sc.close();

    }

}


Measured memory_bytes: 24916