akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MMOD 998244353
#define MAX 2010101
using namespace std;
using Edge=pair<ll,ll>;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
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(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  ll H,W,M;
  cin>>H>>W>>M;
  
  ll R[H+1],C[W+1];
  RREP(i,H) R[i]=0;
  RREP(i,W) C[i]=0;
  map<pair<ll,ll>,ll> B;
  REP(i,M){
    ll a,b;
    cin>>a>>b;
    R[a]++;
    C[b]++;
    B[MP(a,b)]++;
  }
  
  ll mxr=0,mxc=0;
  RREP(i,H) chmax(mxr,R[i]);
  RREP(i,W) chmax(mxc,C[i]);
  
  vector<ll> RR,CC;
  RREP(i,H){
    if(R[i]==mxr) RR.PB(i);
  }
  RREP(i,W){
    if(C[i]==mxc) CC.PB(i);
  }
  
  ll ans=mxr+mxc-1;
  bool CAN=false;
  REP(i,(ll)RR.size()){
    REP(j,(ll)CC.size()){
      if(B[MP(RR[i],CC[j])]!=1){
        co(ans+1);
        return 0;
      }
    }
  }
  
  co(ans);
  return 0;
}

Measured memory_bytes: 34980
/*
 * atcoder/abc130/a.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

int N;
int H[100];

void input() {
  cin >> N;
  loop(n,0,N) cin >> H[n];
}

void solve() {
  int max_ = -1;
  int count = 0;
  loop(n,0,N) {
    count += max_ <= H[n];
    chmax(max_, H[n]);
  }
  cout << count << endl;
}

int main() {
  // cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PP;
const ll MOD = 998244353;
ll T[100005]={0};
int main(){
  int n;cin>>n;
  ll max=0;
  for(int i=1;i<=n;i++){
    ll k;
    cin>>k;
    if(k>max)max=k;
    if((i==1&&k!=0)||(i!=1&&k==0)){
      cout<<0<<endl;
      return 0;
    }
    T[k]++;
  }
  ll ans=1;
  for(int i=1;i<=max;i++){
    for(int j=1;j<=T[i];j++){
      ans*=T[i-1];
      ans%=MOD;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;

struct Edge {int to; ll cost;};

int main() {
    int N_, M;
    cin >> N_ >> M;
    int N = 1;
    while (N < N_) N <<= 1;
    vector<vector<Edge>> G(5 * N - 2 + 2 * M);
    for (int i = 0; i < N - 1; ++i) {
        G[i].push_back(Edge{2 * i + 1, 0});
        G[i].push_back(Edge{2 * i + 2, 0});
    }
    for (int i = N - 1; i < 2 * N - 1; ++i) {
        G[i].push_back(Edge{i + 3 * N - 1, 0});
    }
    for (int i = 2 * N - 1; i < 3 * N - 2; ++i) {
        G[2 * i - 2 * N + 2].push_back(Edge{i, 0});
        G[2 * i - 2 * N + 3].push_back(Edge{i, 0});
    }
    for (int i = 3 * N - 2; i < 4 * N - 2; ++i) {
        G[i + N].push_back(Edge{i, 0});
    }
    rep(i, M) {
        int L, R;
        ll C;
        cin >> L >> R >> C;
        --L;
        vector<int> S;
        L += N - 1;
        R += N - 1;
        while (R - L) {
            if (!(L & 1)) {
                S.push_back(L);
                ++L;
            }
            if (!(R & 1)) {
                --R;
                S.push_back(R);
            }
            L = (L - 1) >> 1;
            R = (R - 1) >> 1;
        }
        for (int x : S) {
            G[x + 2 * N - 1].push_back(Edge{5 * N - 2 + i * 2, 0});
            G[5 * N - 1 + i * 2].push_back(Edge{x, 0});
        }
        G[5 * N - 2 + i * 2].push_back(Edge{5 * N - 1 + i * 2, C});
    }
    vector<ll> dist(5 * N - 2 + 2 * M, INF);
    vector<int> used(5 * N - 2 + 2 * M, 0);
    priority_queue<pair<ll, int>> pq;
    dist[4 * N - 2] = 0;
    pq.push(pair<ll, int>{0, 4 * N - 2});
    while (!pq.empty()) {
        int v = pq.top().second;
        pq.pop();
        if (used[v]) continue; 
        for (auto e : G[v]) {
            ll alt = dist[v] + e.cost;
            if (alt < dist[e.to]) {
                dist[e.to] = alt;
                pq.push(pair<ll, int>{-alt, e.to});
            }
        }
        used[v] = 1;
    }
    if (dist[4 * N + N_ - 3] == INF) cout << -1 << "\n";
    else cout << dist[4 * N + N_ - 3] << "\n";
    return 0;
}


Measured memory_bytes: 119832
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [map(int, input().split()) for _ in range(Q)]
B, C = [list(i) for i in zip(*BC)]

sum = 0
size = 10 ** 5 + 1
list = [0] * size
for a in A:
    list[a] += 1
    sum += a

for i in range(Q):
    sum = sum + C[i] * list[B[i]] - B[i] * list[B[i]]
    list[C[i]] += list[B[i]]
    list[B[i]] = 0
    print(sum)

Measured memory_bytes: 67176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
#define pb push_back
#define PI acos(-1.0)
#define EPS 1e-4
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fout(S,x)            cout<<fixed<<setprecision(x)<<(S)<<endl
#define present(c,x) ((c).find(x) != (c).end())
#define T() ll t;cin>>t;while(t--)
#define mem(input,b) memset(input,b,sizeof(input))
#define ff first
#define ss second
#define fread(input) freopen("input","r",stdin)
#define fwrite(b) freopen("b","w",stdout)
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define FOREACH(i,c) for (__typeof ((c).begin()) i = (c).begin() ; i != (c).end() ; i++)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
const int maxn=1e5+5;
const int mod=1e9+7;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;  } return 0;  }
int main(){
    fastio;
    ll n,m,r;
    cin>>n>>m>>r;
    ll R[r];
    for(int i=0;i<r;++i){
        cin>>R[i];
        R[i]--;
    }
    ll dist[205][205];
    for(int i=0;i<205;++i){
        for(int j=0;j<205;++j)
            if(i != j)
                dist[i][j] = 1e9;
    }
    ll a[m], b[m], c[m];
    for(int i=0;i<m;++i){
        cin>>a[i]>>b[i]>>c[i];
        --a[i];--b[i];
        dist[a[i]][b[i]]=c[i];
        dist[b[i]][a[i]]=c[i];
    }
    for(int k=0;k<n;++k)
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                chmin(dist[i][j],dist[i][k]+dist[k][j]);
    ll ans = 1e9;
    sort(R,R+r);
    do{
            ll disttry = 0;
            for(int i=0;i<r-1;++i){
                disttry += dist[R[i]][R[i+1]];
            }
            chmin(ans,disttry);
    } while (next_permutation(R,R+r));
    cout << ans << endl;
    return 0;
}    


Measured memory_bytes: 1024
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
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 (b<a) { a=b; return 1; } return 0; }
template<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion

void Main();

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


void Main(){
    int N, M;
    cin >> N >> M;
    cout << (N==M?"Yes":"No") << el;
}



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

using namespace std;

int main() 
{
	int Ans = 0;
	int N;
	int K;
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		int x;
		cin >> x;
		if (x > (K - x))
		{
			Ans += ((K - x) * 2);
		}
		else
		{
			Ans += (x * 2);
		}
	}
	cout << Ans << endl;
	return 0;
}

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

using namespace std;

using ll = long long;

int INF = 1e9 + 5;

template<typename T>
void min_self(T& a, T b)
{
    a = min(a,b);
}

template<typename T>
void max_self(T& a, T b)
{
    a = max(a,b);
}

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

    int N, W;
    scanf("%d%d", &N, &W);
    
    constexpr int maxV = 1e5 + 5;
    
    vector<ll> dp(maxV+1,INF);
    dp[0] = 0; // minimum weight  for value  =  j
    
    int weight, value;
    
    for(int i=0; i<N; ++i)
    {
        scanf("%d%d", &weight, &value);
        
        for(int j=maxV-value; j>=0; --j)
        {
            min_self(dp[j+value],dp[j]+weight);
        }
    }
    
    ll answer = 0;
    for(int j=0; j<=maxV; ++j)
    {
        if(dp[j] <= W)
        {
            max_self(answer,(ll)j);
        }
    }

    cout << answer;
    
}


Measured memory_bytes: 1024
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
using namespace std;

int sstoi(char a)
{
	stringstream ss;
	ss<<a;
	int b;
	ss>>b;
	return b;
}

int main() {
	string s;
	while(cin>>s&&s!="0")
	{
		int sum=0;
		for(int i=0;i<s.length();i++)
		{
			sum+=sstoi(s[i]);
		}
		cout<<sum<<endl;
	}
	return 0;
}

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

using namespace std ;

#define sz(v) (int)v.size()
#define ll long long
#define all(v)  v.begin() , v.end()
#define rall(v)  v.rbegin() , v.rend()
#define pf push_front
#define pb push_back
#define fast FastInputOutput() ;
#define Clear( container , value ) memset( container , value , sizeof container )
#define PI acos( -1.0 )
#define forn( t , v , be , n ) for( t v = be ; v < n ; v++ )
#define fore( x , j ) for( auto x : j )
#define se second
#define fr first
//#define c_b fflush(stdin);

const ll Long_max = numeric_limits < ll > :: max() ;
const int Int_max = numeric_limits < int > :: max() ;

void File_input( string pathIn ) {
    freopen( pathIn.c_str(), "r", stdin ) ;
}

void File_output( string pathOut ) {
    freopen( pathOut.c_str(), "w", stdout ) ;
}

int msg() {
    srand( time( 0 ) ) ;
    vector < string > st = {
        "Wish everyone high ratings!",
        "Good luck!",
        "Have fun!",
        "Please, read all the problems!",
        "Go Go fight!"
    } ;
    cerr << st[ rand() % sz( st ) ] ;
    return 0 ;
}


void Fkjhgffdd5567e667astInputOutput() {
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}

int main(){

   int a , b ;
   cin >> a >> b ;
   if( 16 - ( a + b ) >= 2 * abs( a - b ) ){
     cout << "Yay!\n" ;
   } else {
     cout << ":(\n" ;
   }

   return 0 ;
}


Measured memory_bytes: 256
n, x = list(map(int, input().split()))
a = list(map(int, input().split()))
y = 0
if a[0] > x:
    y = a[0] - x
    a[0] = x
for i in range(n-1):
    if a[i] + a[i+1] > x:
        y += a[i+1] + a[i] - x
        a[i+1] = x - a[i]
print(y)

Measured memory_bytes: 14544
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int A,B;
    cin>>A>>B;
    if(A%3==0||B%3==0||(A+B)%3==0)cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
using namespace std;
int main()
{
    map<string, bool> dict;
    int n;
    string x, y;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        if(x == "insert")
            dict[y] = 1;
        else
        {
            if(dict[y] == 1)
                cout << "yes" << endl;
            else cout << "no" << endl;
        }
    }
}



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

const int V = 1010;
const int E = 2010;
const int INF = 1 << 30;
struct Edge{ int from, to, cost; };
Edge edge[E];
int d[V];

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int v, e, r;
	cin >> v >> e >> r;
	
	int a, b, c;
	for(int i = 0; i < e; ++i){
		cin >> a >> b >> c;
		edge[i] = Edge{a, b, c};
	}
	
	fill(d, d + v, INF);
	d[r] = 0;
	
	int cnt = 0;
	while(true){
		bool update = false;
		for(int i = 0; i < e; ++i){
			Edge e1 = edge[i];
			if(d[e1.from] != INF && d[e1.to] > d[e1.from] + e1.cost){
				d[e1.to] = d[e1.from] + e1.cost;
				update = true;
			}
		}
		if(!update){ break; }
		cnt++;
		if(cnt == v - 1){
			cout << "NEGATIVE CYCLE" << endl;
			return 0;
		}
	}
	
	for(int i = 0; i < v; ++i){
		if(d[i] == INF)
			cout << "INF" << endl;
		else
			cout << d[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef pair<long long,pint> p3;
typedef long long ll;
const int inf   = 1e9+7;
const ll  longinf = 1LL<<60;
const int mod=1e9+7;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

struct UnionFind{
  int par[1010];
  UnionFind(int n){
    rep(i,n)par[i]=i;
    }
  int find(int n){
    if(par[n]==n)return n;
    return par[n]=find(par[n]);
    }
  void unite(int x,int y){
    x=par[x];
    y=par[y];
    par[x]=y;
    }
  };


int main(){
  int n,m;
  cin>>n>>m;
  ll xx;cin>>xx;
  ll ma[n];
  rep(i,n)ma[i]=0;
  p3 v[m];
  rep(i,m){
    int x,y;
    ll w;
    cin>>x>>y>>w;
    x--;y--;
    v[i]={w,{x,y}};
    }
  sort(v,v+m);
  int cnt1=m,cnt2=m;
  rep(j,m){
    ll ret=0;
    UnionFind uf(n);
    uf.unite(v[j].second.first,v[j].second.second);
    ret+=v[j].first;
  rep(i,m){
    int from=v[i].second.first,to=v[i].second.second;
    ll cost=v[i].first;
    if(uf.find(from)==uf.find(to))continue;
    uf.unite(from,to);
    ret+=cost;
    }
    if(ret<xx)cnt1--;
    if(ret<=xx)cnt2--;
    }
  ll ans1=1,ans2=1;
  rep(i,cnt1)ans1=2*ans1 %mod;
  rep(i,cnt2)ans2=2*ans2 %mod;
  if(cnt1!=m)ans1=2*ans1%mod;
  if(cnt2!=m)ans2=2*ans2%mod;
  cout<<(ans1-ans2+mod)%mod<<endl;
  return 0;         
  }

Measured memory_bytes: 256
while True:
    try:
        x = input()
        
        
        count = 0
        for a in range(10):
            for b in range(10):
                for c in range(10):
                    for d in range(10):
                        if a+b+c+d == x :
                            count += 1
        
        print count

    except EOFError:
        break

Measured memory_bytes: 5056
#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;
int main(){
  int n;cin>>n;
  int* l=new int[n];
  for(int i=0;i<n;i++){
  	cin>>l[i];
  }
  int m=*max_element(l,l+n);
  int s=accumulate(l,l+n,0);
  if(m*2<s) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


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

absaji = []
for i in range(N):
    absaji.append(abs(aji[i]))

#newaji = np.abs(aji)
minaji = min(absaji)

if sum(aji) < 0:
    sumaji = sum(aji) + minaji
else:
    sumaji = sum(aji) - minaji
print(sumaji)


Measured memory_bytes: 3060
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
const int INF = 1e9;
const ll mod = ll(1e9)+7;

int main() {
  ll n, k, total = 0;
  cin >> n >> k;
  ll min = 0, max = 0;
  rep(i, k) {
    min += i;
    max += n-i;
  }
  for(int i = k; i <= n+1; ++i) {
    total %= mod;
    total += (max - min + 1) % mod;
    if (i == n + 1) break;
    min += i;
    max += n - i;
  }
  cout << total << endl;
}


Measured memory_bytes: 3596
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXOPT=100;
const int MAXHAVE=100000;

int nopt,shave;
int opt[MAXOPT];

bool win[MAXHAVE+1];

bool solve() {
	win[0]=false;
	FORE(i,1,shave) {
		win[i]=false;
		REP(j,nopt) if(opt[j]<=i&&!win[i-opt[j]]) { win[i]=true; break; }
	}
	return win[shave];
}

void run() {
	scanf("%d%d",&nopt,&shave);
	REP(i,nopt) scanf("%d",&opt[i]);
	printf("%s\n",solve()?"First":"Second");
}

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


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

template <typename T>
void printlnVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << endl;
  }
}

template <typename T>
void printVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << " ";
  }
  cout << endl;
}

int main()
{
  int N;
  cin >> N;
  vector<string> ans = {"hon", "pon", "bon"};
  vector<int> A = {1, 1, 0, 2, 0, 0, 1, 0, 1, 0};
  cout << ans[A[N % 10]] << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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; }

typedef long long ll;
typedef pair<ll, ll> p;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  vector<ll> v(n);
  rep(i, n) cin >> v[i];
  mint res = 0;
  for (int i = 0; i <= 60; ++i) {
    mint count = 0;
    rep(j, n){
      if(v[j] & (1ll << i)) count += 1;
    }
    res += count * (mint(n)-count) * mint(pow(2, i));
    // cout << count << endl;
    // cout << res << endl;
  }
  cout << res << endl;
}


Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x) // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    for (ll i = 1; i <= 500000; i++)
    {
        if ((ll)(i * 1.08) == n)
        {
            cout << i << endl;
            exit(0);
        }
    }
    cout << ":(" << endl;
}

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

int main()
{
	string s;
	int ans=0;
	cin >> s;
	REP(i, s.size()) ans += (s[i] == '1');
	cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
V,E = 0,0

for i in range(1, n+1):
  V += i * (n-i+1)

for i in range(n-1):
  a,b = map(int,input().split())
  if a>b: a,b = b,a
  E += a * (n-b+1)

print(V-E)

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

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <map>
#include <queue>
#define mp make_pair
#define pb push_back
#define p push
#define FOR(a,c) for(int a = 0;a<c;a++)
#define ll long long
#define abs(x) (x<0 ? (-x) : x)
#define getI(a) scanf("%d",&a)
#define getII(a,b) scanf("%d %d",&a,&b)
#define getIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a,b) scanf("%lld %lld",&a,&b)
#define getLLL(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define BEND(c) (c).begin(),(c).end()
#define fi first
#define se second
#define PI 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfi(a) printf("%d",a);
#define pfii(a,b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a,b) printf("%lld%lld",a,b);
#define SIZE 1000000007

using namespace std;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vl;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<long long,long long>> vpl;
typedef pair<int,int> pii;
typedef pair <ll,ll> pll;
const  double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
/*ios_base::sync_with_stdio(false);cin.tie(0);*/

/*
vi vec;

ll count(ll in, ll n )
{


    vector<ll> table(n) ;

    table[0]=abs((vec[1]-vec[0]));

    ll cur =0,cc=0;
    for (ll i = 1; i < n-1 ; i++)
    {


            cur =abs((vec[i+1]-vec[i-1]));
            cc=abs((vec[i]-vec[i-1]));
            int ctr=(cc>cur) ? 2 : 1 ;
            table[i]=(cc>cur) ? cur : cc ;
            //table[i]+=table[i-ctr];
    }

    for (ll i = 0; i < n ; i++)
    {

            cout<<table[i]<<" ";


    }
/*
    if(i == n){
        return mn;
    }

    return count(i,n,mn);

    return 0;
 }


int main()
{

    ios_base::sync_with_stdio(false);cin.tie(0);
    ll n;
    cin >>n;
    vec.resize(n);

    for (int i = 0; i <n ; ++i) {
        cin>>vec[i];
    }
    ll sum =0;
    for (int j = 0; j <n ; ++j) {
        sum+=vec[j];
    }


    cout << count(1,n);
    return 0;
}
*/


int dp[MX][3];

int main (){
    ll n,k;
    cin >> n;
    vvi vec(n);

    for (int i = 0; i <n ; ++i) {
        vec[i]=vi (3,0);
    }

    for (int m = 0; m <n ; ++m) {
        for (int i = 0; i <3 ; ++i) {
            cin>>vec[m][i];
        }
    }



    for (int t = 0; t <n ; ++t) {
        for (int i = 0; i <3 ; ++i) {
            for (int j = 0; j <3 ; ++j) {
                if(j!=i){
                    dp[t+1][i]=max(dp[t+1][i], dp[t][j]+vec[t][i]);
                }

            }
        }
    }
   int res= 0;
    for (int l = 0; l <3 ; ++l) {
        res=max(res,dp[n][l]);

    }
    cout <<res;

    //cout<<vec;
    return 0;

}

Measured memory_bytes: 6912
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)n; i++)
#define repp(i, m, n) for(int i = m; i < (int)n; i++)
#define reps(i, n) for(int i = 1; i <= (int)n; i++)
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
typedef pair<ll,ll> pal;

ll k, n, x[60], y[60], z[60], w[60];

bool hantei(ll a, ll b, ll c, ll d)
{
	int muri=0;
	rep(i, n) if(a>x[i] || b<x[i] || c>y[i] || d<y[i]) muri++;
	if(muri<=n-k) return true;
	return false;
}

int main()
{
	cin >> n >> k;
	rep(i, n) cin >> x[i] >> y[i];
	rep(i, n) z[i]=x[i], w[i]=y[i];
	sort(z, z+n);
	sort(w, w+n);
	ll ans=(z[n-1]-z[0])*(w[n-1]-w[0]);
	rep(i, n) repp(j, i+1, n) rep(p, n) repp(q, p+1, n)
	{
		if(hantei(z[i], z[j], w[p], w[q])) ans=min(ans, (z[j]-z[i])*(w[q]-w[p]));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    ll a[n];
    for(ll i = 0;i < n;i++){
    	cin >> a[i];
    }
    ll dp[n];
    dp[n-1] = 0;
    for(ll i = n-2;i >= 0;i--){
    	dp[i] = dp[i+1]+abs(a[i+1]-a[i]);
    	if(i <= n-3){
    		dp[i] = min(dp[i],dp[i+2]+abs(a[i+2]-a[i]));
    	}
    }
    cout << dp[0] << endl;
}


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

int main(void)
{
    int n; cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    long long ans = 0;
    long long step = 0;
    for (int i = 1; i < n; i++)
    {
        if (a[i] < a[i - 1] + step)
        {
            step = a[i - 1] + step - a[i];
            ans += step;
        }
        else
        {
            step = 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4768
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  int n, ans = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      for (int k = 1; k <= n; k++)
      {
        ans++;
      }
    }
  }
  printf("%d\n", ans);
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	M, D := nextInt(), nextInt()
	ans := 0
	// if M < 4 || D < 22 {
	// 	fmt.Println(0)
	// 	return
	// }
	for i := 4; i <= M; i++ {
		for j := 22; j <= D; j++ {
			d1 := j % 10
			d10 := (j / 10) % 10
			if d1 >= 2 && d10 >= 2 && i == d1*d10 {
				ans++
			}
		}
	}
	fmt.Println(ans)
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -a
	}
}

func pow(p, q int) int {
	res := p
	if q == 0 {
		return 1
	}
	for i := 0; i < q-1; i++ {
		res *= p
	}
	return res
}

func MinOf(vars ...int) int {
	min := vars[0]
	for _, i := range vars {
		if min > i {
			min = i
		}
	}
	return min
}

func MaxOf(vars ...int) int {
	max := vars[0]
	for _, i := range vars {
		if max < i {
			max = i
		}
	}
	return max
}

func gcdof2numbers(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcdof2numbers(b, a%b)
}

func lcmof2numbers(a int, b int) int {
	return a / gcdof2numbers(a, b) * b
}

// マイナスの場合は考慮していない
func fuctorial(a int) int {
	if a == 1 || a == 0 {
		return 1
	} else {
		return fuctorial(a-1) * a
	}
}

func NextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// 素因数分解したmapを返す
func primeFuctorize(n int) map[int]int {
	pf := map[int]int{}
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			pf[i]++
			n /= i
		}
	}
	if n != 1 {
		pf[n]++
	}
	return pf
}


Measured memory_bytes: 640
X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()))
*B, = sorted(map(int, input().split()))
*C, = sorted(map(int, input().split()))
ab = [i+j for i in A for j in B]
ab = sorted(ab, reverse=True)[:K]
abc= [i+j for i in ab for j in C]
abc.sort(reverse=True)
for i in abc[:K]:
    print(i)

Measured memory_bytes: 160944
#include <iostream>
using namespace std;
int main()
{
  long long a[87];
  a[0]=2;
  a[1]=1;
  int x;
  cin>>x;
  for (int i=2;i<=x;i++)
  {
    a[i]=a[i-1]+a[i-2];
  }
  cout<<a[x]<<endl;
  //system("pause");
  return 0;
}

Measured memory_bytes: 256
mod = 10**9+7
n = int(input())
def nth_bit(d):
    return (n>>d)&1

dp = [[0,0,0] for _ in range(61)]
dp[-1][0] = 1
for d in range(59,-1,-1):
    for s in range(3):
        for k in range(3):
            s2 = min(2,2*s+nth_bit(d)-k)
            if s2>=0:
                dp[d][s2] += dp[d+1][s]
ans = sum(dp[0])%mod
print(ans)

Measured memory_bytes: 62316
#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;

typedef long long ll;
typedef pair<int, int> P;

const int di[4] = {-1, 0, 1, 0};
const int dj[4] = { 0, 1, 0,-1};

bool color[404][404];
int H, W;

void input(){
	memset(color, false, sizeof(color));
	cin >> H >> W;
	rep (i, H) rep (j, W){
		char ch; cin >> ch;
		color[i][j] = (ch == '#');
	} // end rep
}

bool check(int i, int j, int d){
	int ni = i + di[d];
	int nj = j + dj[d];
	if (ni < 0 || ni >= H || nj < 0 || nj >= W) return false;
	if (color[i][j] == color[ni][nj]) return false;
	return true;
}

bool used[404][404];

ll solve(){
	ll ans = 0LL;
	ll b = 0LL, w = 0LL;
	rep (i, H){
		rep (j, W){
			if (used[i][j]) continue;
			b = 0LL;
			w = 0LL;
			queue<P> que;
			used[i][j] |= true;
			que.push(P(i,j));
			while(!que.empty()){
				P p = que.front(); que.pop();
				int ci = p.first, cj = p.second;
				if (color[ci][cj]){
					++b;
				}else{
					++w;
				} // end if
				rep (d, 4){
					if (!check(ci,cj,d)) continue;
					int ni = ci + di[d];
					int nj = cj + dj[d];
					if (used[ni][nj]) continue;
					used[ni][nj] |= true;
					que.push(P(ni,nj));
				} // end rep
			} // end while
			ans += b * w;
		} // end rep
	} // end rep
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	input();
	
	ll res = solve();
	cout << res << endl;

	return 0;
}

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

int main(){
  long long int n,a,b,blue=0,tmp=0;
  cin>>n>>a>>b;
  
  while(n/(a+b)>0){
    tmp+=n/(a+b);
    blue+=a*tmp;
    n=n%(a+b);
  }

  if(n<a){blue+=n;}
  else{blue+=a;}
  
  cout<<blue<<endl;
  
  return 0;
}


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

const int MAXN = 305;

int n;
char s[MAXN][MAXN];

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%s", s[i]);
	
	int res = 0;
	for(int x = 0; x < n; x++){
		bool ok = true;
		for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++){
			if(s[i][j] != s[(j + x) % n][(i - x + n) % n]){
				ok = false;
			}
		}
		if(ok)res += n;
	}
	printf("%d\n", res);
	
    return 0;
}


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

const int MAXN = 100010;
int a[4][MAXN], dp[4][MAXN];
int n;

int calc(int pos, int last) {
    if(pos == n+1) return 0;
    int &y = dp[last][pos];
    if(y != -1) return y;
    y = INT_MIN;
    for(int i=1; i<=3; ++i) {
        if(i == last) continue;
        y = max(y, a[i][pos] + calc(pos+1, i));
    }
    return y;
}

int main() {
    memset(dp, -1, sizeof(dp));
	cin >> n;
	for(int i=1; i<=n; ++i) {
	    for(int j=1; j<=3; ++j) {
	        cin>>a[j][i];
	    }
	}
	cout<<calc(1, 0)<<endl;
	return 0;
}

Measured memory_bytes: 15648
# 迷路読み込み
h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]

ans=0
for i in range(h):
    ans+=maze[i].count('.')

for i in range(h):
    maze[i]=['#']+maze[i]+['#']
maze=[['#' for i in range(w+2)]]+maze+[['#' for i in range(w+2)]]
# 迷路　BFS
import collections
from collections import deque
def clear_maze(sx, sy, gx, gy):

    INF=-10**9
    distance = [[INF for i in range(w+1)] for j in range(h+1)]
    #    distance = [[None]*field_x_length]*field_y_length
    def bfs():
        d = deque()
        d.appendleft((sx, sy))
        distance[sx][sy] = 0

        while len(d):
            x, y = d.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and  0 <= ny  and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    d.appendleft ((nx, ny))
                    distance[nx][ny] = distance[x][y] + 1

        return distance[gx][gy]

    return bfs()
v=clear_maze(1,1,h,w)

if v==-10**9:
    print(-1)
else:
    print(ans-v-1)

Measured memory_bytes: 40304
a, b, k = gets.split.map(&:to_i)
if a + k >= b
then
  for i in a..b
    puts i
  end
else
  ak = a + k - 1
  bk = b - k + 1
  for i in a..ak
    puts i
  end
  if ak >= bk
  then
    for i in (ak + 1)..b
      puts i
    end
  else
    for i in bk..b
      puts i
    end
  end
end

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

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll sum = accumulate(A.begin(), A.end(), 0LL) / 2;
    ll not_one = 0;
    for (int i = 1; i < N; i += 2)
        not_one += A[i];
    ll one = (sum - not_one) * 2;
    cout << one;
    ll prev = one;
    rep(i, N - 1) cout << " " << (prev = A[i] * 2 - prev);
    cout << endl;
    return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using P = pair<int, int>;
const int MX = 100005;
const P None = P(-1e9, -1e9);
const P Any = P(-1e9,1e9);
int n, k, a, b, v, p, ans[MX];
vector<int> G[MX];
P ran[MX];
void dfs(int p, int t){
	for(int nx: G[t]) if(nx != p){
		dfs(t,nx);
		if(ran[nx] == None) ran[t] = None;
		else if(ran[t] != Any && ran[nx] != Any && (ran[t].first + ran[nx].first) % 2 == 0) ran[t] = None;
		else{
			ran[t].first = max(ran[nx].first-1, ran[t].first);
			ran[t].second = min(ran[nx].second+1, ran[t].second);
		}
		if(ran[t].first > ran[t].second) ran[t] = None;
		if(ran[t] == None) return;
	}
}
void dfs_2(int p, int t){
	for(int nx: G[t]) if(nx != p){
		if(ans[nx] == 1e9) ans[nx] = ans[t] + (ans[t]+1 <= ran[nx].second ? 1 : -1);
		dfs_2(t,nx);
	}
}
int main(){
	scanf("%d", &n);
	fill(ran, ran+n, Any);
	fill(ans, ans+n, (int)1e9);
	rep(i,n-1){
		scanf("%d%d", &a, &b);
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	scanf("%d", &k);
	rep(i,k){
		scanf("%d%d", &v, &p);
		ran[v-1] = P(p,p);
		ans[v-1] = p;
	}
	dfs(0,0);
	if(ran[0] == None) puts("No");
	else{
		ans[0] = ran[0].first;
		dfs_2(0,0);
		puts("Yes");
		rep(i,n) printf("%d\n", ans[i]);
	}
}

Measured memory_bytes: 13824
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
count = 0
for i in range(0, N):
    A = list(map(int, input().split()))
    judge = 0
    for j in range(0, M):
        judge = judge+A[j]*B[j]
    if judge+C>0:
        count = count+1
print("{}".format(count))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
#define MAXN 100005
typedef long long int64;
using namespace std;
template<class T>
void read(T &res) {
	res = 0;char c = getchar();T f = 1;
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int N,a[MAXN];
int L[MAXN],tot,ans,cnt1[MAXN],cnt2[MAXN],pre[MAXN],suf[MAXN];
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) read(a[i]);
    for(int i = 1 ; i <= N ; i += 2) {
        cnt1[a[i]]++;
    }
    for(int i = 2 ; i <= N ; i += 2) {
        cnt2[a[i]]++;
    }
    for(int i = 1 ; i <= 100000 ; ++i) {
        pre[i] = max(pre[i - 1],cnt2[i]);
    }
    for(int i = 100000 ; i >= 1 ; --i) {
        suf[i] = max(suf[i + 1],cnt2[i]);
    }
    ans = N;
    for(int i = 1 ; i <= 100000 ; ++i) {
        ans = min(ans,N / 2 - cnt1[i] + N / 2 - max(pre[i - 1],suf[i + 1]));
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
    Solve();
	return 0;
}


Measured memory_bytes: 2176
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	a := make([][]int, 3)
	for i := 0; i < 3; i++ {
		a[i] = make([]int, 3)
		a[i][0] = readI()
		a[i][1] = readI()
		a[i][2] = readI()
	}
	n := readI()
	for i := 0; i < n; i++ {
		b := readI()
		for j := 0; j < 3; j++ {
			for k := 0; k < 3; k++ {
				if a[j][k] == b {
					a[j][k] = 0
				}
			}
		}
	}

	for i := 0; i < 3; i++ {
		if a[i][0] == 0 && a[i][1] == 0 && a[i][2] == 0 {
			fmt.Println("Yes")
			return
		}
		if a[0][i] == 0 && a[1][i] == 0 && a[2][i] == 0 {
			fmt.Println("Yes")
			return
		}
	}
	if a[1][1] == 0 {
		if (a[0][0] == 0 && a[2][2] == 0) || (a[0][2] == 0 && a[2][0] == 0) {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}

/*-----------Input utils-----------*/

var sc = bufio.NewScanner(os.Stdin)

func init() {
	if len(os.Args) >= 2 {
		if os.Args[1] == "debug" {
			debug()
		}
	}
	const buf = 200100
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, buf), buf)
}

func debug() {
	testFile, err := os.Open("./test/sample-1.in")
	if err != nil {
		fmt.Fprintln(os.Stderr, "There is no testfile.")
		os.Exit(1)
	}
	sc = bufio.NewScanner(testFile)
}

func readS() string {
	sc.Scan()
	return sc.Text()
}

func readR() []rune {
	return []rune(readS())
}

func readI() int {
	i, _ := strconv.Atoi(readS())
	return i
}

func readF() float64 {
	f, _ := strconv.ParseFloat(readS(), 64)
	return f
}


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

int main(void){
    int n,q;
    ll k;
    cin>>n>>k>>q;
    int x[n];
    rep(i,n) x[i]=k;
    rep(i,q) {
    int a;
    cin>>a;
    x[a-1]++;
    }
    rep(i,n) if(x[i]>q){
        cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
    long long a,b,k;
    cin>>a>>b>>k;
    if(a>=k){
        a=a-k;
    }
    else{
        if(k<=a+b){
            b=(a+b)-k;
            a=0;
        }
        else{
            if(k>a+b){
                a=0;
                b=0;
            }
        }
    }
    cout<<a<<" "<<b;
    return 0;
}


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

using namespace std;

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

	long long n, k, i, j;
	cin >> n >> k;
	vector<long double> s(n + 1, 0);
	vector<long long> p(n + 1, 0);
	for (i = 1; i <= n; i++) {
		cin >> p[i];
		s[i] = s[i - 1] + (p[i] + 1.0) / 2.0;
	}

	long double ans = 0;
	for (i = 0; i + k <= n; i++) {
		ans = max(ans, (s[i + k] - s[i]));
	}

	cout << setprecision(10) << fixed << ans << "\n";

	return 0;
}


Measured memory_bytes: 4992
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var numArray = input.Select(x => long.Parse(x)).ToArray();

            var amari = numArray[0] % numArray[1];
            var hiku = numArray[1] - amari;
            
            if (amari >= hiku)
            {
                Console.WriteLine(hiku);
            }
            else
            {
                Console.WriteLine(amari);
            }
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
// 15:47

double distance(int x1, int y1, int x2, int y2) {
  return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
  int n;
  cin >> n;
  int town[n][2];
  rep (i, n) {
    cin >> town[i][0] >> town[i][1];
  }

  double sum = 0;
  rep (i, n) {
    rep (j, n) {
      sum += distance(town[i][0], town[i][1], town[j][0], town[j][1]);
    }
  }
  cout << fixed << setprecision(8) << sum / n << endl;
  return 0;
}

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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

signed main(){
	int r=read(),g=read(),b=read();
	
	int num = 100*r+10*g+b;
	
	if(num%4==0) cout << "YES";
	else	cout << "NO";
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;

class Program
{
    static void Main()
    {
        var AB = ReadLine().Split().Select(long.Parse).ToArray();
        var A = AB[0];
        var B = AB[1];

        WriteLine(Xor(A == 0 ? 0 : A - 1) ^ Xor(B));
    }
    static long Xor(long x)
    {
        if (x == 0) return 0;
        switch (x % 4)
        {
            case 0: return x;
            case 1: return 1;
            case 2: return x + 1;
            case 3: return 0;
            default: return 0;
        }
    }
}



Measured memory_bytes: 13396
N, M =map(int,input().split())
li = [int(input()) for _ in range(N)]
li.sort()
count = int(len(li))
remaining = M-sum(li)

while(True):
  if remaining >= int(li[0]):
    count += 1
    remaining -= int(li[0])
  else:
    break
    
print(count)

Measured memory_bytes: 3064
$t=gets.chop
def f c,a,b,p=0
a=a.to_i
b=b.to_i
case c
when 'print'
puts $t[a..b]
$t
when 'reverse'
$t[0...a]+$t[a..b].reverse+$t[b+1..-1]
when 'replace'
$t[0...a]+p+$t[b+1..-1]
end
end
gets.to_i.times do
$t=f *gets.split
end


Measured memory_bytes: 7060
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char b;
    scanf("%c",&b);
    if(b=='A')
        printf("T\n");
    if(b=='T')
        printf("A\n");
    if(b=='C')
        printf("G\n");
    if(b=='G')
        printf("C\n");
    return 0;
}


Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var input = new List<int>(10);
        for (int i = 0; i < 10; i++)
        {
            input.Add(int.Parse(Console.ReadLine()));
        }

        for (int i = 0; i < 3; i++)
        {
            var max = input.Max();
            Console.WriteLine(max);
            input.Remove(max);
        }
    }
}

Measured memory_bytes: 9912