akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <set>
using namespace std;

int N, P[100100], R[100100];

int main()
{
	scanf ("%d", &N);
	for (int i = 1; i <= N; i++) scanf ("%d", &P[i]), R[P[i]] = i;

	multiset<int> pos = { 0, 0, N + 1, N + 1, R[N] };
	long long ans = 0;
	for (int i = N - 1; i >= 1; i--){
		int r = R[i];
		auto I = pos.lower_bound(r);
		auto J = I; J--;
		auto K = I; K++;
		auto L = J; L--;
		ans += (1ll * (*J - *L) * (*I - r) + 1ll * (*K - *I) * (r - *J)) * i;
		pos.insert(r);
	}

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

	return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
using ll = long long;
using namespace std;

int main() {
	int a, b;
	string s;
	cin >> a >> b >> s;
	bool ans = true;
	int tmp = 0;
	rep(i, a) {
		tmp = s[i] - '0';
		if (0 > tmp || tmp > 9)ans = false;
	}
	for (int i = a + 1; i < a + b + 1;i++) {
		tmp = s[i] - '0';
		if (0 > tmp || tmp > 9)ans = false;
	}
	if (s[a] != '-')ans = false;

	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m, p;
  cin >> n >> m >> p;
  vector<vector<int>> rg(n);
  vector<long long> a(m), b(m), c(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    c[i] -= p;
    rg[b[i]].push_back(a[i]);
  }
  vector<int> reachable(n);
  reachable[n - 1] = true;
  queue<int> que;
  que.push(n - 1);
  while (que.size()) {
    int cur = que.front();
    que.pop();
    for (int nbr : rg[cur]) {
      if (reachable[nbr]) continue;
      reachable[nbr] = true;
      que.push(nbr);
    }
  }
  vector<vector<long long>> edge;
  for (int i = 0; i < m; i++) {
    if (reachable[a[i]] && reachable[b[i]]) {
      edge.push_back({a[i], b[i], -c[i]});
    }
  }
  for (auto v : edge) {
    cerr << v[0] << " " << v[1] << " " << v[2] << endl;
  }
  const long long inf = 1LL << 60;
  vector<long long> dist(n, inf);
  dist[0] = 0;
  for (int i = 0; i < n; i++) {
     for (auto v : edge) {
       if (dist[v[0]] != inf && dist[v[1]] > dist[v[0]] + v[2]) {
         dist[v[1]] = dist[v[0]] + v[2];
         if(i == n - 1) {
           //cerr << "here" << endl;
           cout << -1 << endl;
           return 0;
         }
       }
     }
  }
  if (dist[n - 1] == inf) cout << -1 << endl;
  else cout << max(0LL, -dist[n - 1]) << endl;
  return 0;
}
    

Measured memory_bytes: 896
S = input()
N = [int(i) for i in S]

cnt = 0
for i in range(len(N)-1):
    if N[i] == 0:
        if N[i] == N[i+1]:
            N[i+1] = 1
            cnt += 1
    else:
        if N[i] == N[i+1]:
            N[i+1] = 0
            cnt += 1
print(cnt)

Measured memory_bytes: 3956
//Fast Zeta conversion
//cf. http://d.hatena.ne.jp/todo314/20120614/1339695202

#include<stdio.h>

long long max(long long a,long long b){if(a>b){return a;}return b;}

long long pow(long long a, long long n){
  long long r=1,i;
  for(i=0;i<n;i++){r*=a;}
  return r;
}

typedef struct{
  long long fi;
  long long se;
}data;

data d[262144];

void marge(long long x,long long y){
  if(x==y){return;}
  long long nf,ns;
  if(d[x].fi > d[y].fi){
    nf=d[x].fi;
    if(d[x].se > d[y].fi){
      ns=d[x].se;
    }
    else{
      ns=d[y].fi;
    }
  }
  else{
    nf=d[y].fi;
    if(d[x].fi > d[y].se){
      ns=d[x].fi;
    }
    else{
      ns=d[y].se;
    }
  }
  d[x].fi=nf;
  d[x].se=ns;
}

int main(){
  long long r=0,i,j,n,x,a[262144];
  scanf("%lld",&n);
  x=pow(2,n);
  for(i=0;i<x;i++){scanf("%lld",&a[i]);
    d[x-i-1].fi=a[i];d[x-i-1].se=0;
  }
  for(i=0;i<n;i++){
    for(j=0;j<x;j++){
      if((j>>i & 1) == 0){
        marge(j,(j|(1<<i)));
      }
    }
  }
  for(i=x-2;i>=0;i--){
    r=max(r,d[i].fi+d[i].se);
    printf("%lld\n",r);
  }
  return 0;
}

Measured memory_bytes: 9088
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<ctime>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y-1);(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

int used[60][60],dx[]={1,0,-1,0},dy[]={0,1,0,-1};

pii dfs(vector<string> &mp,int y,int x){
  if(mp[y][x]=='#')
    return pii(0,0);
  if(mp[y][x]=='B')
    return pii(0,2);
  if(mp[y][x]=='W')
    return pii(0,1);
  if(used[y][x])
    return pii(0,0);
  used[y][x]=1;
  pii re=pii(1,0),tmp;
  rep(i,4){
    tmp=dfs(mp,y+dy[i],x+dx[i]);
    re.X+=tmp.X;
    re.Y|=tmp.Y;
  }
  return re;
}

int main(){
  clock_t St,Et;
  St=clock();
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int i,j,k;
  while(1){
    int w,h;
    cin>>w>>h;
    if(w==0)break;
    vector<string> mp(h+2,string(w+2,'#'));
    rep(i,h){
      cin>>mp[i+1];
      mp[i+1]="#"+mp[i+1]+"#";
    }
    //   rep(i,h+2)cout<<mp[i]<<endl;
    fill(used[0],used[0]+60*60,0);
    int rew=0,reb=0;
    for(int i=1;i<=h;i++)
      for(int j=1;j<=w;j++)
	if(!used[i][j]&&mp[i][j]=='.'){
	  pii tmp=dfs(mp,i,j);
	  if(tmp.Y==1){
	    rew+=tmp.X;
	  }else if(tmp.Y==2){
	    reb+=tmp.X;
	  }
	}
    //   rep(i,h+2){rep(j,2+w)cout<<used[i][j];cout<<endl;}
    cout<<reb<<" "<<rew<<endl;
  }
  double hoge=2;
  while((clock()-St)/CLOCKS_PER_SEC<5.0){
    hoge*=1.0001;
  }
  return 0;
}

Measured memory_bytes: 1464
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long
#define pb push_back

int main() {
  int N, K;
  int r, s, p;
  string T;
  cin >> N >> K;
  cin >> r >> s >> p;
  cin >> T;
  ll sum = 0;
  string te = "";

  // K回目までのじゃんけん
  rep(i, K){
    if (T[i] == 'r'){
      sum += p;
      te += "p";
    } else if (T[i] == 's') {
      sum += r;
      te += "r";
    } else {
      sum += s;
      te += "s";
    }
  }

  // K回以降の手を決める
  for(int i = K; i < N; i++){
    if (T[i] == 'r' && te[i - K] != 'p'){
      sum += p;
      te += "p";
    } else if (T[i] == 's' && te[i - K] != 'r') {
      sum += r;
      te += "r";
    } else if (T[i] == 'p' && te[i - K] != 's')  {
      sum += s;
      te += "s";
    } else {
      te += "0";
    }
    // cout << sum << endl;
  }
 
  cout << sum << endl;

}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main(int argc, char const* argv[])
{
	int pm,pe,pj,n;

	while( cin >> n && n != 0 ){
		for( int i = 0;i < n;i++ ){
			cin >> pm >> pe >> pj;

			if( pm == 100 || pe == 100 || pj == 100 || ( pm + pe ) / 2 >= 90 || (pm + pe + pj) / 3 >= 80 ) cout << 'A' << endl;
			else if( ( pm + pe + pj ) / 3 >= 70 || (( pm + pe + pj ) /3 >= 50 && (pm >= 80 || pe >= 80)) ) cout << 'B' << endl;
			else cout << 'C' << endl;
		}
	}
	return 0;
}

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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int N, M, C;
V B;
vector<V> A;

int main() {
    cin >> N >> M >> C;
    B.resize(M);
    VECCIN(B);
    A.resize(N);
    FOREACH(a, A) a.resize(M);
    REP(i, N) VECCIN(A[i]);
    int cnt = 0;
    REP(i, N) {
        int sum = 0;
        REP(j, M) sum += A[i][j] * B[j];
        sum += C;
        if(sum > 0) cnt++;
    }
    cout << cnt << "\n";
    return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!

N = int(input())

h_i = []
h_i = list(map(int, input().split()))
#print(h_i)

c_i = [0 for i in range(N)]

for i in range(N):
    if i == 0: pass
    elif i == 1: c_i[i] = abs(h_i[i] - h_i[i-1]) 
    else:
        c_i[i] = min(c_i[i-1] + abs(h_i[i] - h_i[i-1]), c_i[i-2] + abs(h_i[i] - h_i[i-2]))

print(c_i[-1])

Measured memory_bytes: 13928
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        int N = int.Parse(Console.ReadLine());
        int[] C = new int[26];
        for(int i=0;i<26;i++){
            C[i] = 50;
        }
        for(int q=0;q<N;q++){
            string s = Console.ReadLine();
            int[] Cq = new int[26];
            for(int i=0;i<s.Length;i++){
                Cq[s[i]-'a']++;
            }
            for(int i=0;i<26;i++){
                C[i] = Math.Min(C[i],Cq[i]);
            }
        }
        for(int i=0;i<26;i++){
            for(int j=0;j<C[i];j++){
                sb.Append((char)('a'+i));
            }
        }
        sb.Append("\n");
    }
}

Measured memory_bytes: 11092
#include <stdio.h>
#include <limits.h>

int main(){
    int A, B, r;
    scanf("%d %d", &A, &B);
    
    r = A + B;
    r = (r < (A - B))? A - B : r;
    r = (r < (A * B))? A * B : r;
    printf("%d\n", r);
    
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>

#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
#define rep_r(i,s,n)for(int i = n-1;i>=0;i--)
#define rep_re(i,s,n)for(int i = n;i>=0;i--)
using namespace std;
typedef long long ll;
static const ll MOD = 1e9 + 7;
static const ll INF = 1e25;
static const ll MAX_N = 100001;
static const ll MAX_M = 100001;

ll a[100001] = {};
ll p[100001] = {};
ll uf(ll i) {
	if (p[i] == i) return i;
	return p[i] = uf(p[i]);
}

int main() {
	ll n, m; cin >> n >> m;
	repe(i, 1, n) {
		cin >> a[i];
		p[i] = i;
	}
	rep(i, 0, m) {
		ll x, y; cin >> x >> y;
		if (uf(x) != uf(y))p[uf(x)] = uf(y);
	}
	ll ans = 0;
	repe(i, 1, n)if (uf(i) == uf(a[i]))ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef long double ld;

#define llset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define en '\n'
#define S second
#define F first
#define pll pair<ll,ll>
#define PB push_back

const ll N = 1e6+7;
ll mod = 1e9+7;
#define calncr for(int i=1  ;i<=1e6;i++) fac[i] = (fac[i-1]*i)%mod;
ll fac[N] = {0};

ll gen_base(const ll before, const ll after) {
    auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::mt19937 mt_rand(seed);
    int base = std::uniform_int_distribution<ll>(before+1, after)(mt_rand);
    return base % 2 == 0 ? base-1 : base;
}

ll pow(ll a,ll b)
{
    if(!b)
        return 1;
    ll p = pow(a,b/2);
    if(b%2)
        return (a*((p*p)%mod))%mod;
    else
        return (p*p)%mod;
}

ll modInv(ll a)
{
    //cout<<a<<" "<<mod<<en;
    return pow(a%mod,mod-2);
}

ll nCr(ll n,ll r)
{
    return (fac[n]*modInv((fac[r]*fac[n-r])%mod))%mod;
}

ll hashf(ll r,ll x,ll mod)
{
    return (x+r)%mod;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    fac[0] = 1;
    calncr;
    ll n,x,t;
    cin>>n>>x>>t;
    cout<<t*ll(ceil((ld)n/(ld)x))<<en;
}


Measured memory_bytes: 11464
f=lambda A,x,B,C:(A*x+B)%C
while 1:
    N,A,B,C,X=map(int,input().split())
    if not N and not A and not B and not C and not X:break
    Y=list(map(int,input().split()))
    T=X
    c=[[] for _ in range(N)]

    sl=0
    for i in range(10005):
        if T==Y[sl]:
            sl+=1
            if sl==N:break
        T=f(A,T,B,C)
    if i>10000:i=-1
    print(i)



Measured memory_bytes: 5620
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	cin>>s;
	if (s=="Sunny") cout<<"Cloudy"<<endl;
	if (s=="Cloudy") cout<<"Rainy"<<endl;
	if (s=="Rainy") cout<<"Sunny"<<endl;
	return 0;
}

Measured memory_bytes: 256
//(bool) ? (if true) : (if false)
//63LL - __builtin_clzll(n)
//(x&-x)
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define fst first
#define snd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pf push_front
#define sz size()
#define FORN(i,j,n) for(long long i=j; i<(long long)n;i++) 
#define FOR(i,n) FORN(i,0,n)
#define FORIT(i,x) for( auto i = x.begin() ; i != x.end() ; i++ )
#define LIM 262150
#define ones(x) __builtin_popcount(x)
#define trace(x)    cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
using namespace std;
 
typedef long long ll ;
typedef unsigned long long ull ;
typedef vector <int> vi;
typedef vector <long long> vll;
typedef pair <int,int> ii;
typedef vector <string> vs;
typedef vector <ii> vii;
const ll MAX = 2e5+5;
const ll MOD = 1e9+7;
int n;
ll arr[MAX];
ll sum = 0;
ll ans = 0;
ll a ;
int main() {
	fastio;
	cin >> n;
	FOR(i,n) cin>> arr[i];
	FOR(i,n) sum = (sum + arr[i])%MOD;
	sum = sum*sum;
	sum = sum%MOD;
	ans += sum;
	FOR(i,n){
		arr[i] = arr[i]%MOD;
        a = arr[i]*arr[i];
		a = a %MOD;
        ans -= a;
        ans += MOD;
        ans = ans % MOD;		
	} 
	if(ans%2 == 1){ 
	    ans += MOD;
        ans /=2;
        ans = ans%MOD;
        cout<< ans << '\n';
		return 0;
    }		 
	cout<< (ans>>1) << '\n';
	return 0;
}

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

int main() {
    ll n, m;
    cin >> n >> m;

    ll ans = 0;
    if (m - 2 * n >= 0)
        ans += n + (m - 2 * n) / 4;
    else
        ans += m / 2;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3596
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<iomanip>

#define INF 1<<29

using namespace std;

int main(void) {
	int h, w;
	cin >> h >> w;
	vector<string>S(h);
	for (int i = 0; i < h; i++) {
		cin >> S[i];
	}
	const int dx[8] = { 1,0,-1,0,1,-1,-1,1 };
	const int dy[8] = { 0,1,0,-1,1,1,-1,-1 };
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (S[i][j] == '#') {
				continue;
			}

			int num = 0;
			for (int d = 0; d < 8; d++) {
				const int ni = i + dy[d];
				const int nj = j + dx[d];

				if (ni < 0 || h <= ni)continue;
				if (nj < 0 or w <= nj)continue;

				if (S[ni][nj] == '#')num++;
			}
			S[i][j] = char(num + '0');
		}
	}
	for (int i = 0; i < h; i++) {
		cout << S[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int gcd(int a, int b)
{
	int temp;

	if (a < b) { temp = a; a = b; b = temp; }
	if (b < 1) return -1;

	if (a % b == 0) return b;
	return gcd(b, a % b);
}


int main(void) {
	int n, x, i, ans;
	scanf("%d %d", &n, &x);
	int y[n];
	for (i = 0; i<n; i++) {
		scanf("%d", &y[i]);
	}
	if (n == 1) {
		y[0] = y[0] - x;
		if (y[0] < 0) {
			y[0] = -y[0];
		}
		printf("%d", y[0]);
	}
	else {
		for (i = 0; i < n; i++) {
			y[i] = y[i] - x;
			if (y[i] < 0) {
				y[i] = -y[i];
			}
		}
		ans = gcd(y[0], y[1]);
		for (i = 2; i < n - 1; i++) {
			ans = gcd(ans, y[i]);
		}
		printf("%d", ans);
	}

	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, c;
    cin >> n >> m >> c;
    int b[100];
    for (int i = 0; i < m; i++) cin >> b[i];
    int a[100][100];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cin >> a[i][j];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) sum += a[i][j]*b[j];
        if (sum+c > 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  double a,b,x;
  cin>>a>>b>>x;
  cout<<fixed<<setprecision(8);
  if (x<=a*a*b/2){
    double theta=atan(a*b*b/(2*x));
    cout<< theta*180/M_PI;
  }
  else{
    double theta=atan(2*b/a-2*x/(a*a*a));
    cout<< theta*180/M_PI;

  }
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int n, max = 0, sum = 0;
	int l[100];

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &l[i]);
		if (l[i] > max) {
			sum += max;
			max = l[i];
		}
		else {
			sum += l[i];
		}
	}

	if (max < sum) puts("Yes");
	else puts("No");
}

Measured memory_bytes: 128
#include<iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <map>

using namespace std;

void setMinPathLength(map<long long ,long long>* T,long long K ,long long length ,long long* minPaths){
    minPaths[K] = length;
    for(auto itr = T[K].begin(); itr != T[K].end(); ++itr) {
        if (minPaths[itr->first] == -1){
            setMinPathLength(T,itr->first ,length + itr->second , minPaths);
        }
    }
}

int main()
{
    // 整数の入力
    long long N,a,b,c,i,Q,K,x,y;
    map<long long ,long long> *T;
    long long * minPaths;
    cin >> N;
    T = new map<long long,long long>[N+1];
    minPaths = new long long[N+1];
    for (i= 1;i<N;i++){
        cin >> a;
        cin >> b;
        cin >> c;
        T[a][b] = c;
        T[b][a] = c;
    }

    for (i=1;i<=N;i++){
            minPaths[i] = -1;
    }

    cin >> Q;
    cin >> K;
    setMinPathLength(T,K,0,minPaths);

    for (i=0;i<Q;i++){
        cin >> x;
        cin >> y;
        cout << minPaths[x] + minPaths[y] << endl;
    }
    return 0;
}

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

using namespace std;

/**/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define wt(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define wt(x...)
#endif
/**/

#define LL long long
const int MAXN = 212345;
const int INF  = 0x3f3f3f3f;



int main () {

	ios_base::sync_with_stdio(false);  cin.tie(NULL); 

	int n; cin >> n;
	std::vector<int> b;
	b.emplace_back(INF);
	for (int i = 0; i < n - 1; ++i) {
		int x; cin >> x;
		b.emplace_back(x);
	}
	b.emplace_back(INF);

	LL ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += min (b[i], b[i-1]);
	}

	cout << ans << '\n';



	return 0;
}



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

#define REP(i,n) for(int i=0;i<n;++i)
#define RREP(i,n) for(int i=n-1;i>=0;--i)
#define FOR(i,m,n) for(int i=m;i<n;++i)
#define RFOR(i,m,n) for(int i=m-1;i>=n;--i)
#define ALL(v) v.begin(),v.end()
#define PB(a) push_back(a)
#define INF 1000000001
#define MOD 1000000007

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

using namespace std;

void dfs(const vector<string> &v, vector<vector<bool>> &b, int x, int y, int& cnt) {
	b[y][x] = true;
	cnt++;
	REP(i, 4) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx<v[y].size() && nx >= 0 && ny >= 0 && ny<v.size() &&v[ny][nx] == '.' && !b[ny][nx])
			dfs(v, b, nx, ny,cnt);
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h, w;
	while (cin >> w >> h&&h) {
		vector<string> v(h);
		REP(i, h) {
			cin >> v[i];
		}
		vector<bool> b(w, false);
		vector<vector<bool> > visited(h, b);
		int y=0, x=0;
		REP(i, h) {
			if (v[i].find('@')!=size_t(-1)) {
				y = i;
				x = v[i].find('@');
			}
		}
		int cnt = 0;
		dfs(v, visited, x, y, cnt);
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 3028
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

ll mypow(ll a, ll b) {
    ll ret = 1;
    while (b--) {
        ret *= a;
    }
    return ret;
}

int main() {
    ll n;
    cin >> n;
    vector<ll> cnt(9);
    rep(i, n) {
        ll a;
        cin >> a;
        if (a >= 3200) a = 3200;
        cnt[a / 400]++;
    }

    ll no = 0;
    rep(i, 8) {
        if (cnt[i] == 0) no++;
    }

    if (no == 8 && cnt[8] != 0) {
        cout << 1 << " ";
    } else {
        cout << 8 - no << " ";
    }

    cout << 8 - no + cnt[8] << "\n";

    return 0;
}

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

int max(int a,int b){
  if(a>b) return a;
  else return b;
}
double min(double a,double b){
  if(a<b) return a;
  else return b;
}
int absolute(int a,int b){
  if(a-b<0) return -(a-b);
  else return a-b;
}
int sum_keta(int n){
  if(n==0) return 0;
  return n%10 + sum_keta(n/10);
}
int main(void){
  int N; cin >> N;
  vector<string> s(N);
  for(int i=0;i<N;i++){
    cin >> s.at(i);
  } 
  int M; cin >> M;
  vector<string> t(M);
  for(int i=0;i<M;i++){
    cin >> t.at(i);
  }
  
  int localmax=0;
  for(int i=0;i<N;i++){
    int count = 0;
  	for(int j=i;j<N;j++){
      if(s.at(i) == s.at(j)) count++;
    }
    for(int k=0;k<M;k++){
      if(s.at(i) == t.at(k)) count--;
    }
    localmax = max(localmax,count);
  }
  cout << localmax << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <queue>
using namespace std;
int Col[300000], Row[300000];
int main() {
    int n, m, k, x, y;
    scanf("%i%i%i", &n, &m, &k);
    queue<pair<int, int>> Enemies;
    for (int i = 0; i < k; i++) {
        scanf("%i%i", &x, &y);
        x--, y--;
        Row[x]++, Col[y]++;
        Enemies.push(make_pair(x, y));
    }


    int maxCol = Col[0], maxRow = Row[0],
        n_maxRow = 0, n_maxCol = 0;
    for (int i = 1; i < n; i++) {
        if (maxRow < Row[i])
            maxRow = Row[i];
    }
    for (int i = 1; i < m; i++) {
        if (maxCol < Col[i])
            maxCol = Col[i];
    }
    for (int i = 0; i < n; i++) {
        if (maxRow == Row[i])
            n_maxRow++;
    }
    for (int i = 0; i < m; i++) {
        if (maxCol == Col[i])
            n_maxCol++;
    }


    int cnt = 0;
    while (!Enemies.empty()) {
        x = Enemies.front().first,
        y = Enemies.front().second;
        Enemies.pop();

        if (Row[x] == maxRow && Col[y] == maxCol) {
            cnt++;
        }
    }

    printf("%i", maxRow + maxCol - (n_maxRow * 1ll * n_maxCol == cnt));
}


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

#define iota(i,n,b,s) for(int i=int(b);i!=int((b)+(s)*(n));i+=(s))
#define range(i,n,m) iota(i,(((n)>(m))?((n)-(m)):((m)-(n))),(n),((n)>(m)?-1:1))
#define rep(i,n) iota(i,(n),0,1)
#define loop for(;;)

#define INF (1e9)
#define EPS (1e-9)
#define cons(a,b) (make_pair(a,b))
#define car(a) (a.first)
#define cdr(a) (a.second)
#define cadr(a) (car(cdr(a)))
#define cddr(a) (cdr(cdr(a)))
#define all(a) a.begin(), a.end()
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;

typedef long long Integer;
typedef double Real;
typedef vector<int> vi;
typedef vector<string> vs;
typedef map<string,int> Dictionary;
const Real PI = acos(-1);

template<class S, class T>
ostream& operator<<(ostream& os, pair<S,T> p) {
  os << '(' << car(p) << ", " << cdr(p) << ')';
  return os;
}

template<class T>
ostream& operator<<(ostream& os, vector<T> v) {
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

int dx[] = { -1, 0, 1, 0 };
int dy[] = {  0, -1, 0, 1 };

enum Day {
  Sat = 0,
  Sun = 1,
  Mon, Tue, Wed, Thu, Fri
};

Day zeller(int y, int m, int d) {
  if (m == 1 || m == 2) {
    --y; m += 12;
  }
  int Y = y % 100;
  int c = y / 100;
  int gamma = 5 * c + c / 4; // Gregorian (1582 <= y)
  //int gamma = 6 * c + 5; // Julian (4 <= y <= 1582)
  int h = d + int(26 * (m+1) / 10)
    + Y + Y / 4 + gamma;
  h %= 7;
  return Day(h);
}

string show_day (Day a) {
  switch (a) {
    case Mon: return "Monday";
    case Tue: return "Tuesday";
    case Wed: return "Wednesday";
    case Thu: return "Thursday";
    case Fri: return "Friday";
    case Sat: return "Saturday";
    case Sun: return "Sunday";
    default: return "Holiday";
  }
}

int main() {

  loop {
    int a,b;
    cin >> a >> b;
    if (!cin) break;
    if (!a && !b) break;
    cout << show_day(zeller(2004, a, b)) << endl;
  }
  return 0;
}

Measured memory_bytes: 1196
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
#define fixed cout.setf(ios::fixed);
#define Precise cout.precision(7);
using namespace std;
int main()
{
    ll l,r,d,i,ans=0;
    cin>>l>>r>>d;
    for(i=l;i<=r;i++)
    {
        if(i%d==0)ans++;
//        cout<<i;
    }
    cout<<ans<<endl;


    return 0;
}





Measured memory_bytes: 3608
#include <iostream>

using namespace std;

const int MOD = 1e9+7;

int pow(int x, int n) {
	long long ret = 1;
  	for (int i = 0; i < n; ++i) {
     	ret = (ret * x) % MOD; 
    }
  	return ret;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  
  	int N;
  	cin >> N;
  
	long long ret = pow(10,N);
  	ret = (ret - pow(9,N) + MOD) % MOD;
  	ret = (ret - pow(9,N) + MOD) % MOD;
  	ret = (ret + pow(8,N) + MOD) % MOD;
  	cout << ret << endl;
}


Measured memory_bytes: 3624
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int a[4],b[4],c[4],d[3];
char e[4]="+-*";
int fl(int p){
  int i;
  if(p==3){
    int sm=c[0],sn;
    for(i=0;i<3;i++){
      if(0){
      }else if(d[i]==0){
	sm+=c[i+1];
      }else if(d[i]==1){
	sm-=c[i+1];
      }else if(d[i]==2){
	sm*=c[i+1];
      }
    }
    if(sm==10){
      cout<<"((("<<c[0]<<" "<<e[d[0]]<<" "<<c[1]<<") "<<e[d[1]]<<" "<<c[2]<<") "<<e[d[2]]<<" "<<c[3]<<")"<<endl;
      return 1;
    }
    if(0){
    }else if(d[0]==0){
      sm=c[0]+c[1];
    }else if(d[0]==1){
      sm=c[0]-c[1];
    }else if(d[0]==2){
      sm=c[0]*c[1];
    }
    if(0){
    }else if(d[2]==0){
      sn=c[2]+c[3];
    }else if(d[2]==1){
      sn=c[2]-c[3];
    }else if(d[2]==2){
      sn=c[2]*c[3];
    }
    if(0){
    }else if(d[1]==0){
      sm+=sn;
    }else if(d[1]==1){
      sm-=sn;
    }else if(d[1]==2){
      sm*=sn;
    }
    if(sm==10){
      cout<<"(("<<c[0]<<" "<<e[d[0]]<<" "<<c[1]<<") "<<e[d[1]]<<" ("<<c[2]<<" "<<e[d[2]]<<" "<<c[3]<<"))"<<endl;
      return 1;
    }
  }else{
    for(i=0;i<3;i++){
      d[p]=i;
      if(fl(p+1))
	return 1;
    }
  }
  return 0;
}
int fm(int p){
  int i;
  if(p==4){
    if(fl(0))
      return 1;
  }else{
    for(i=0;i<4;i++){
      if(b[i]){
	b[i]=0;
	c[p]=a[i];
	if(fm(p+1))
	  return 1;
	b[i]=-1;
      }
    }
  }
  return 0;
}
int main(){
  while(cin>>a[0]>>a[1]>>a[2]>>a[3]&&(a[0]||a[1]||a[2]||a[3])){
    memset(b,-1,sizeof(b));
    if(fm(0)==0)
      cout<<0<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#C
import bisect
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()

bi = [0 for i in range(N)]
for i in range(N):
    b = B[i]
    c = bisect.bisect_right(C,b)
    bi[i]+=(N-c)

S = sum(bi)
rui = [0]
for bii in bi:
    rui.append(rui[-1]+bii)

rui = rui[::-1]
ans = 0
for i in range(N):
    a = A[i]
    ind = bisect.bisect_right(B,a)
    #print(ind,rui[N-ind])
    ans+=(S-rui[N-ind])

    
    
print(ans)
#print(rui)

Measured memory_bytes: 25460
L = [(512,768,512)] + [(256>>i,896>>i,256>>i) for i in xrange(9)]

def put(f,x,y):
    for yy,b in zip(xrange(y-1,y+2),L[x]):
        f[yy] = f[yy] ^ b

def solve(F):
    for i in xrange(1<<10):
        f = [0] + F + [0]
        ret = []
        for x in (x for x in xrange(10) if (1<<x & i) != 0):
            put(f,x,1)
            ret.append((x,0))
        f.pop(0)
        for y in xrange(9):
            for x in (x for x in xrange(10) if (1<<(9-x) & f[y]) != 0):
                put(f,x,y+1)
                ret.append((x,y+1))
        if f[9] == 0:
            return ret
    
for _ in xrange(input()):
    F = [int(raw_input().replace(" ",""),2) for _ in xrange(10)]
    P = solve(F)    
    print "\n".join([" ".join("1" if (x,y) in P else "0" for x in xrange(10))\
                         for y in xrange(10)])

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

#define REP( i, n )     for( int (i) = 0; (i) < (n); (i)++ )
#define ALL( a )        (a).begin(), (a).end()

using namespace std;
using ll = long long;
using P = pair<int, int>;

template<class T>bool chmax( T& a, const T& b ) { if( a < b ) { a = b; return 1; } return 0; }
template<class T>bool chmin( T& a, const T& b ) { if( a > b ) { a = b; return 1; } return 0; }

const int INF = 1e9 + 1;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main(){
    int a, b; cin >> a >> b;
    int c = a + b;
    if( c == 3 ) cout << 3 << endl;
    else if( c == 4 ) cout << 2 << endl;
    else  cout << 1 << endl;
}

/*

*/

Measured memory_bytes: 256
//***********************
//Author:kibi11
//Quarantine Days
//***********************

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define N 2e5+1
#define MOD 1000000007
#define dd double
#define fr(i, n) for(int i = 0; i < n; i++)
#define fr1(i,a,b) for(int i=a;i<b;i++)
#define frr(i,a,k) for(int i=a;i>=k;i--)
#define same int t;cin>>t;while(t--)
#define check(x) cout << (#x) << " is " << (x) << endl;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define f first
#define s second
#define XOX
#define pi = 3.14159265358979323846

//////////////////////////////////////////////////////////////////////////
/////////////////DEBUGING ZONE//////////////////////////////

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
///////////////////////////////////////////////////////////////////////////
 
ll powermod(ll base, ll exp, ll mod) {
	ll result = 1;
	while (exp != 0) {
		if ((exp % 2) == 1) {
			result = (result * base) % mod;
		}
		base = (base * base) % mod;
		exp /= 2;
	}
	return result;
}

///////////////////////////////////////////////////////////////////////////
//Fuctions if any:
std::vector<ll> v(N);
int n;
bool see(ll mid,ll k)
{
	ll count=0;
	fr(i,n)
	{
		count+=(v[i]-1)/mid;
	}
	// cout<<count<<endl;
	return count<=k;
}





///////////////////////////////////////////////////////////////////////////
int main() 
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt = clock();
//ios_base& scientific (ios_base& str);

ll k;
cin>>n>>k;
// vector<int> v(n);
fr(i,n) cin>>v[i];
ll min=1;
ll max=*max_element(v.begin(), v.end());
ll mid;
while(min!=max)
{
	
	mid=(min+max)/2;
	// debug(min,max,mid);
	if(see(mid,k))
	{
		max=mid;
	}
	else
	{
		min=mid+1;
	}
	// debug(min,max,mid);

}
cout<<max<<endl;
cerr << "TIME = " << (double) 1.0 * (clock() - tt) / CLOCKS_PER_SEC << " seconds" << endl;
return 0;
}

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

using namespace std;

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

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

    vector<int> cnt(63, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 63; j++) {
            if ((a[i] & (1LL << j)) > 0) {
                cnt[j]++;
            }
        }
    }

    long long res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 63; j++) {
            if ((a[i] & (1LL << j)) > 0) {
                cnt[j]--;
                res += ((1LL << j) % 1000000007) * (n - i - cnt[j] - 1);
            } else {
                res += ((1LL << j) % 1000000007) * cnt[j];
            }

            res %= 1000000007;
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 2560
import java.util.Arrays;
import java.util.Scanner;
 
//At Boss's Expense
public class Main{
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean[] prime = new boolean[1000001];
        Arrays.fill(prime, true);
        prime[1] = false;
        for(int i=2;i<1000001;i++){
            if(prime[i]){
                for(int j=i*2;j<1000001;j+=i)prime[j]=false;
            }
        }
        while(true){
            int n = sc.nextInt();
            int x = sc.nextInt();
            if((n|x)==0)break;
            int[] p = new int[n];
            boolean[] f = new boolean[x+1];
            f[0] = true;
            for(int i=0;i<n;i++){
                p[i]=sc.nextInt();
                for(int j=p[i];j<=x;j+=p[i])f[j]=true;
            }
            int max = 0;
            for(int i=1;i<=x;i++){
                if(!f[i]){
                    for(int j=0;j<n;j++){
                        if(i-p[j]>=0 && f[i-p[j]]){
                            f[i] = true;
                            break;
                        }
                    }
                }
                if(f[i] && prime[i])max = i;
            }
            System.out.println(max==0?"NA":max);
        }
    }
}

Measured memory_bytes: 59600
n=input()
for i in range(n):
    s=raw_input()
    L=[s[0]]
    for i in range(1,len(s),3):
        if s[i:i+2]=="->" and s[i+2] not in L:
            L.append(s[i+2])
        elif s[i:i+2]=="<-" and s[i+2] not in L:
            L.insert(0,s[i+2])
    print "".join(L)

Measured memory_bytes: 4244
#include <stdio.h>

int main() {
    int a[100] = {0};
    int min;
    int number;
    int count = 0;
    int i;
    int j;
    int temp;

    scanf("%d", &number);
    for (i = 0; i < number; i++){
        scanf("%d", &a[i]);
    }

    for (i = 0; i < number; i++) {
        min = i; //????°??????´???
        for (j = i; j < number; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        
        if (a[i] > a[min]) {
            temp = a[min];
            a[min] = a[i];
            a[i] = temp;
            count++;
        }
    }
    
    for (i = 0; i < number - 1; i++) {
        printf("%d ", a[i]);
    }
    printf("%d", a[number - 1]);
    printf("\n%d\n", count);

    return 0;
}

Measured memory_bytes: 600
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    import math
    while N > 0:
        n = (-1 + math.sqrt(1 + 8*N)) / 2
        n = int(-(-n//1))
        print(n)
        N -= n


if __name__ == '__main__':
    main()


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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

void f(ll x){
    ll sum = 0, X = x;
    while(X){
        sum += X%10;
        X /= 10;
    }
    if(x%sum==0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

int main(){
    ll n; cin>>n;
    f(n);
}


Measured memory_bytes: 3584
import sys
input = sys.stdin.readline
from collections import Counter
from operator import itemgetter

def main():
    n = int(input())
    v = list(map(int, input().split()))

    x = Counter(v[0:n:2])
    y = Counter(v[1:n:2])
    max_x, x_ = max(x.items(), key=itemgetter(1))
    max_y, y_ = max(y.items(), key=itemgetter(1))
    if max_x == max_y:
        x[max_x] = 0
        y[max_y] = 0
        sec_x = max(x.values())
        sec_y = max(y.values())
        y_ = max(sec_x, sec_y)

    print(n - x_ - y_)

main()


Measured memory_bytes: 18720
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
const ll MOD=1000000007,MOD2=998244353,INF=1e18;



int main() {
    int N;
    cin>>N;
    vector<int> H(N);
    rep(i,N)cin>>H.at(i);
    bool j=true;
    H.at(0)--;
    rep(i,N-1){
        if(H.at(i+1)<H.at(i))j=false;
        else if(H.at(i+1)==H.at(i))continue;
        else{H.at(i+1)--;}
    }
    if(j){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
}


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

int main() {
	int n,m,a,b,c,sum=0;
	string s;
	cin>>s;
	for(int i=0;i<12;i++){
	    if(i!=3){
	        cout<<s[i];
	    }
	    else{
	        cout<<s[i]<<' ';
	    }
	}
	cout<<'\n';
	return 0;
}


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

int main()
{ 
  int n, k ;
  cin >> n >> k ;

  int64_t calcu = k ;
  for(int i = 1 ; i < n ;i++)
  {
    calcu *= k - 1 ;
  }

  cout << calcu << endl ;
}


Measured memory_bytes: 256
N,M=map(int, input().split(" "))
city=[]

for i in range(M):
    p, y=map(int, input().split(" "))
    city.append([i,p,y])

city.sort(key=lambda x: (x[1],x[2]))

index=1
for i in range(M):
    if i>0:
        if city[i-1][1] != city[i][1]:
            index=1
    
    city[i][2]=index
    index+=1

city.sort(key=lambda x: x[0])

for i in range(M):
    print(str(city[i][1]).zfill(6)+str(city[i][2]).zfill(6))

Measured memory_bytes: 30800
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
using ll = long long;
using namespace std;
const int INF = 1e9;

int main() {

    int N;
    cin >> N;
    map<string, int> M;

    rep(i, N) {
        string s;
        cin >> s;
        M[s]++;
    }

    int ma = 0;
    for (auto itr = M.begin(); itr != M.end(); itr++) {
        ma = max(ma, itr->second);
    }

    vector<string> ans;
    for (auto itr = M.begin(); itr != M.end(); itr++) {
        if (ma == itr->second)
            ans.push_back(itr->first);
    }

    sort(ans.begin(), ans.end());
    rep(i, ans.size()) cout << ans[i] << endl;

    return 0;
}

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

void fnInput(string& rsMaxNum)
{
  cin >> rsMaxNum;
}

int fnDgtDP(string sMaxNum)
{
  // dp[i][j][k] :=  i: 上位 i 桁目まで決定
  //                 j: small(数字を自由に選べる)か
  //                 k: {3,5,7} を選んだかのflag
  //                 の条件を満たす数値の数
  int dp[11][2][8] = {};
  dp[0][0][0] = 1;

  int nLen = sMaxNum.size();

  for (int i = 0; i < nLen; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 8; ++k)
      {
        if (!dp[i][j][k]) continue;

        if (j == 1)                    // small ([0, 9] から数字を選べる)か
        {
          if (!k) dp[i + 1][1][0] += dp[i][1][0];            // nothing

          dp[i + 1][1][k | 1] += dp[i][1][k];                // +3
          dp[i + 1][1][k | 2] += dp[i][1][k];                // +5
          dp[i + 1][1][k | 4] += dp[i][1][k];                // +7
        }
        else                           // not small ([0, d] から数字を選べる)か
        {
          int nDgt = sMaxNum[i] - '0';

          if (!k)        dp[i + 1][1][0]     += dp[i][0][0]; // nothing

          if (nDgt == 3) dp[i + 1][0][k | 1] += dp[i][0][k]; // +3
          if (3 < nDgt)  dp[i + 1][1][k | 1] += dp[i][0][k]; // +3
          if (nDgt == 5) dp[i + 1][0][k | 2] += dp[i][0][k]; // +5
          if (5 < nDgt)  dp[i + 1][1][k | 2] += dp[i][0][k]; // +5
          if (nDgt == 7) dp[i + 1][0][k | 4] += dp[i][0][k]; // +7
          if (7 < nDgt)  dp[i + 1][1][k | 4] += dp[i][0][k]; // +7
        }
      }
  return dp[nLen][0][7] + dp[nLen][1][7];
}

int main()
{
  string sMaxNum;

  fnInput(sMaxNum);
  cout << fnDgtDP(sMaxNum) << endl;
  
  return 0;
}

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

int main()
{
  int n;
  while (cin >> n) {
    if (n == 0)
      break;

    vector<int> board(6000, 0);
    board[0] = (1 << 5) - 1; // sentinel
    while (n--) {
      int d, p, q;
      cin >> d >> p >> q;

      --q;
      for (int i = 6000-1; i > 0; --i) {
	if (d == 1) {
	  // hor
	  int block = 0;
	  for (int j = 0; j < p; ++j)
	    block |= (1 << (q+j));
	  
	  if (board[i-1] & block) {
	    board[i] |= block;
	    break;
	  }
	} else {
	  // ver
	  if (board[i-1] & (1 << q)) {
	    for (int j = 0; j < p; ++j)
	      board[i+j] |= (1 << q);
	    break;
	  }
	}
      }

      int vanish = 0;
      for (int i = 1; i < 6000; ++i) {
	if (board[i] == (1 << 5) -1) {
	  ++vanish;
	} else if (vanish > 0) {
	    board[i-vanish] = board[i];
	    board[i] = 0;
	}
      }
    }

    int ans = 0;
    for (unsigned int i = 1; i < board.size(); ++i)
      ans += __builtin_popcount(board[i]);
    cout << ans << endl;
  }
  return 0;
}

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

class Main{
    public static void main(String[] Args) throws IOException{
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int n = Integer.parseInt(br.readLine());
        String in;
        final int[] m = new int[n+1];
        in = br.readLine();
        m[0] = Integer.parseInt(in.substring(0, in.indexOf(' ')));
        m[1] = Integer.parseInt(in.substring(in.indexOf(' ')+1));
        for(int i = 2; i<=n; i++){
            in = br.readLine();
            m[i] = Integer.parseInt(in.substring(in.indexOf(' ')+1));
        }
        final int[][] cost = new int[n][n+1];
        for(int len = 2; len<=n; len++){
            for(int l = 0; l<=n-len; l++){
                int res = Integer.MAX_VALUE;
                for(int i = 1; i<len; i++){
                    res = Math.min(res, cost[l][i]+m[l]*m[l+i]*m[l+len]+cost[l+i][len-i]);
                }
                cost[l][len] = res;
            }
        }
        System.out.println(cost[0][n]);
    }
}

Measured memory_bytes: 24780
#include <iostream>
#define maxn 1000050
using namespace std;
int a[maxn];
int b[maxn];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            b[i]=1000000000;
        }
        int l=0;
        for(int i=0;i<n;i++)
        {
            int v=lower_bound(b,b+l,a[i])-b;
            b[v]=a[i];
            l=max(l,v+1);
        }
        cout<<l<<endl;
    }
}






Measured memory_bytes: 3856
#MLE注意！

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    s = input().rstrip()
    res = s.count('R') * s.count('G') * s.count('B')

    cnt = 0
    for j in range(1, n-1):
        for k in range(1, j+1):
            if j+k >= n:
                continue
            if s[j-k] != s[j] and s[j+k] != s[j] and s[j-k] != s[j+k]:
                cnt += 1

    print(res - cnt)

if __name__ == '__main__':
    main()


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

const int N = 1000 * 100 + 10;
int n, a[N], tt = 0;
string ans[2] = {"First\n", "Second\n"};

void solve() {
	long long sum = 0;
	bool one = false;
	int cnt[2] = {0, 0};
	for (int i = 0; i < n; i++) {
		 one |= a[i] == 1;
		sum += a[i] - 1;
		cnt[a[i] & 1]++;
	}
	if (one) {
		cout << ans[(sum + 1 + tt) & 1];
		exit(0);
	}
	if (n == 1) {
		cout << ans[(sum + 1 + tt) & 1];
		exit(0);
	}
	if (cnt[0] & 1) {
		cout << ans[tt & 1];
		exit(0);
	}
	if (cnt[1] >= 2) {
		cout << ans[(1 + tt) & 1];
		exit(0);
	}
	for (int i = 0; i < n; i++)
		if (a[i] & 1) {
			a[i]--;
			break;
		}
	long long g = a[0];
	for (int i = 1; i < n; i++)
		g = __gcd(1LL * a[i], g);
	for (int i = 0; i < n; i++)
		a[i] /= g;
	tt++;
	solve();
}

int main() { 
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	solve();
	return 0;
}


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

int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  vector<int> e(N+1), w(N+1);
  int num_e = 0;
  for(int i=0; i<N; i++){
    if(S.at(i)=='E'){
      num_e++;
    }
    e.at(i+1) = num_e;
    w.at(i+1) = i+1-num_e;
  }
  int ans = N;
  for(int i=0; i<N; i++){
    int nw = w.at(i);
    int ew = e.at(N)-e.at(i+1);
    ans = min(ans,nw+ew);
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 6100