akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }
        public void Solve(ConsoleInput cin)
        {
            var n = cin.ReadInt;
            var d = cin.ReadIntArray(n);
            var ans = 0;
            Array.Sort(d);
            if(d[n/2] != d[n / 2 - 1])
            {
                ans = d[n / 2] - d[n / 2 - 1];
            }
            else
            {
                ans = 0;
            }
            WriteLine(ans);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}


Measured memory_bytes: 18784
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long LL;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define dumpMap(m) { for (auto it: m) cout << it.first << "=>" << it.second << ' '; }

const int MOD = 1000000007;

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

    string ans = (S == "ABC") ? "ARC" : "ABC";

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3612
def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(list(input().rstrip()) for i in range(n))
    B = list(list(input().rstrip()) for i in range(m))
    A = np.array(A)
    B = np.array(B)
    
    for i in range(n-m+1):
        for j in range(n-m+1):
            a_b = A[i:i+m,j:j+m]
            if (a_b==B).all():
                print('Yes');exit()
    print('No')
    
if __name__=='__main__':
    main()

Measured memory_bytes: 27188
#include <string>
#include<string.h>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<iostream>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fuck(x) cout<<x<<endl
#define mem(a,b) memset(a,b,sizeof a)
const int MAX=1e5+5;
class edge
{
public:
    int to,cost;
    edge(int to,int cost):to(to),cost(cost){}
};
typedef pair<long long ,long long> P;
vector<edge> G[MAX];
long long d[MAX];
int V;
void dij(int s)
{
    priority_queue<P,vector<P>,greater<P> > que;
    mem(d,0x3f);
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty())
    {
        P p=que.top();
        que.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++)
        {
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<=n;i++) G[i].clear();
        for(int i=1;i<n;i++)
        {
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            G[u].push_back(edge(v,w));
            G[v].push_back(edge(u,w));
        }
        int Q,K;
        cin>>Q>>K;
        dij(K);
        for(int i=0;i<Q;i++)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            cout<<d[u]+d[v]<<endl;
        }
    }
}


Measured memory_bytes: 9460
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<pair<ll,ll> > vec(N);
    rep(i,N){
        cin >> vec[i].second >> vec[i].first;
    }
    sort(all(vec));
    ll deadline = 0;
    ll workinghours = 0;
    bool possible = true;
    rep(i,N){
        workinghours += vec[i].second;
        deadline = vec[i].first;
        if (deadline < workinghours) possible = false;
    }
    if (possible) cout << "Yes" << endl;
    else cout << "No" << endl;
}



Measured memory_bytes: 3328
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
bool prime(int x){
    for(int i = 2; i * i <= x; i++){
        if ( x % i == 0 ) return false ;
    }
    return true ;
}
signed main(){
    fastio
    int x ;
    cin >> x ;
    for(int i = x; ; i++){
        if ( prime(i) ) {
            cout << i << endl;
            return 0 ;
        }
    }
    return 0; 
}

Measured memory_bytes: 3652
#define _USE_MATH_DEFINES
#define INF 100000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cstdio>

using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
 
static const double EPS = 1e-8;
 
const int tx[] = {0,1,0,-1};
const int ty[] = {-1,0,1,0};

ll GCD(ll a ,ll b){
  return b > 0 ? GCD(b,a%b) : a;
}

ll LCM(ll a ,ll b){
  return a / GCD(a,b) * b;
}

int main(){
  ll limit;
  int total_requirements;
  while(~scanf("%lld %d",&limit,&total_requirements)){
    if(limit == 0 && total_requirements == 0) break;
    vector<ll> requirements;
    for(int require_i = 0; require_i < total_requirements; require_i++){
      ll num;
      scanf("%lld",&num);
      requirements.push_back(num);
    }
    sort(requirements.begin(),requirements.end());

    ll gain = limit * (1 + limit) / 2LL;
    ll remaining_items = limit;

    ll lost = 0;
    ll set_size = 0;
    for(int S=1;S<(1<<total_requirements);S++){
      ll lcm = 1;
      for(int i=0;i<requirements.size();i++){
        if(S & (1<<i)){
          lcm = LCM(requirements[i],lcm);
          if(lcm > limit) break;
        }
      }
      if(lcm > limit) continue;

      ll sign = -1;
      if(__builtin_popcount(S) & 1){
        sign = 1;
      }
      ll first_item = lcm;
      ll num_of_item = limit / lcm;
      ll last_item = num_of_item * lcm;
      set_size += sign * num_of_item;
      lost += sign * num_of_item * (first_item + last_item) / 2LL;
    }
    
    remaining_items -= set_size;
    gain -= lost;
    if(remaining_items == 0){
      printf("%.8lf\n",0);
    }
    else{
      printf("%.8lf\n",(double)gain/(double)remaining_items);
    }
  }
}

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

int main(){
    int n;
    cin>>n;
    int p[100001]={0};
    int ans=0;
    for (int i=1; i<=n; i++) {
        cin>>p[i];
    }
    for (int i=1; i<=n; i++) {
        if(p[i]==i){
            swap(p[i], p[i+1]);
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define MODULO 1000000007
#define PI 3.14159265359
typedef long long int ll;

bool iscoc(int a,int b,int c)
{
	if(a==b || b==c || c==a)
	return false;
	if(((a+b)>c && (a+c)>b )&& (b+c)>a)
	return true;
	else
	return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int A[n];
    for(int i=0;i<n;++i)
    {
   	 cin>>A[i];
	}
	int res=0;
	for(int i=0;i<n-2;++i)
	{
		for(int j=i+1;j<n-1;++j)
		{
			for(int k=j+1;k<n;++k)
			{
				if(iscoc(A[i],A[j],A[k]))
				{
				res++;
			//	cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
			    }
			}
		}
	}
	cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 3636
N, K = map(int, input().split())
A = list(map(int, input().split()))
BIT_NUM = K.bit_length()

X = 0
flag = False
for i in reversed(range(BIT_NUM)):
    cnt = 0
    for a in A:
        if a >> i & 1:
            cnt += 1
    if flag:
        if N - cnt > cnt:
            X |= 1 << i
        continue
    kbit = (K >> i) & 1
    if N - cnt > cnt and kbit:
        # kbitが立っていないところでXのビットを立てると、XがKより大きくなってしまう
        X |= 1 << i
    else:
        if kbit:
            # 以降はKとの大小比較を考えなくても良い
            flag = True

print(sum([X ^ a for a in A]))


Measured memory_bytes: 14708
#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <functional>
#include <iostream>
#include <cassert>
#include <cfloat>
#include <climits>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

int main() {
	string S;
	cin >> S;
	int res = 0;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'g') {
			res++;
		}
		else {
			res--;
		}
	}
	if (res < 0) {
		res = 0;
	}

	cout << res/2 << endl;
	
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define EPS 1e-14

#define all(v) v.begin(),v.end()
#define INF
#define mp make_pair
#define pb

#define fi first
#define se second


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

typedef long long ll;
int s[30*2+10][30*2+10];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int main(){
	int t=0;
	while(1){
		//cout<<++t<<endl;
		rep(y,70){
			rep(x,70){
				s[y][x]=-1;
			}
		}
		int w,h;
		cin >> w >> h;
		//cout << w << " " << h << endl;
	
		if(w==0) break;
		rep(y,h*2+1){
			rep(x,w*2+1){
				if(y==0||x==0||y==h*2||x==w*2){
					s[y][x] = -1;
				}else if(x%2==0 && y%2==0){
					s[y][x] = -1;
				}else if((x+y)%2==0){
					s[y][x] = 0;
				}else{
					cin >> s[y][x];
					if(s[y][x]==1) s[y][x]=-1;
				}
			}
		}
		// rep(y,60){
		// 	rep(x,60){
		// 		printf("%c ",(s[y][x]==-1)? '#':' ');
		// 	}
		// 	cout << endl;
		// }
		// cout << endl;

		queue<pii> que;
		que.push(mp(1,1));
		while(!que.empty()){
			int x = que.front().fi;
			int y = que.front().se;
			//cout<<"@ "<<x<<" "<<y<<endl;
			//s[y][x] = dist.front();
			if(y == h*2-1 &&x == w*2-1){
				break;
			}
			int d = s[y][x];
			rep(i,4){
				int nx = x + dx[i];
				int ny = y + dy[i];
				if( nx>=0 && ny>=0 &&
					nx<w*2+1  && ny<h*2+1  &&
					s[ny][nx]==0){
					s[ny][nx] = d+1;
					que.push(mp(nx,ny));
				}
			}
			que.pop();
		}
		// rep(y,60){
		// 	rep(x,60){
		// 		printf("%2d ",s[y][x]);
		// 	}
		// 	cout << endl;
		// }
		//cout << endl;
		if(s[h*2-1][w*2-1]==0){
			cout << 0 << endl;
		}else{
			cout << s[h*2-1][w*2-1]/2+1 << endl;
		}
		//cout<<"fin"<<endl;
	}
	return 0;
}

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

using namespace std;

long long inf=1000000007;

int main(){
	long long n;
	cin>>n;
	vector<vector<long long>> hoge(10,vector<long long>(10));

	for(long long i=1;i<=n;i++){
		string s=to_string(i);
		long long a=s.at(0)-'0';
		long long b=*s.rbegin()-'0';

		hoge.at(a).at(b)++;
	}

	long long ans=0;

	for(long long i=0;i<=9;i++){
		for(long long j=0;j<=9;j++){
			ans+=hoge.at(i).at(j)*hoge.at(j).at(i);
		}
	}

	cout<<ans<<endl;

	return 0;
}


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

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

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

const double eps = 1e-10;

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

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

void step(string& s) {
  string t(s.size()-1, '0');
  REP(i, s.size()-1) {
    t[i] += abs(s[i]-s[i+1]);
  }
  swap(s, t);
}

// 1-stepすすめると0, 1, 2だけになる
//

int comb_parity(int64 a, int64 b) {
  int64 ret = 1;
  while (a) {
    if (a%2 == 0 && b%2) ret = 0;
    a /= 2;
    b /= 2;
  }
  return ret;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int64 N, M;
  cin >> N >> M;
  cout << N*(N-1)/2 + M*(M-1)/2 << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define MINF -1000000000
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair

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

using namespace std;

typedef pair<int,int> pii;

int f[100][10];
int p[100][11];
int n;

int solve(int x[], int num){
  if(num == 10){

    int c = 0;
    REP(i,10){
      if(x[i] == 0){
        c++;
      }
    }
    if(c == 10){
      return MINF;
    }

    int res = 0;
    REP(i,n){
      int count = 0;
      REP(j,10){
        if(x[j] == 1 && f[i][j] == 1){
          count++;
        }
      }
      res += p[i][count];
    }
    return res;
  }

  int res = MINF;
  REP(i,2){
    if(i == 0){
      x[num] = 1;
      res = max(res, solve(x, num + 1));
    }else{
      x[num] = 0;
      res = max(res, solve(x, num + 1));
    }
  }

  return res;
}

int main(){

  scanf("%d", &n);

  REP(i,n){
    REP(j,10){
      scanf("%d", &f[i][j]);
    }
  }

  REP(i,n){
    REP(j,11){
      scanf("%d", &p[i][j]);
    }
  }

  int x[10] = {};
  printf("%d\n", solve(x, 0));

  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int main(){
    int x,a,b;
    cin>>x>>a>>b;
    if(b-a<=x&&b-a>0)cout<<"safe"<<endl;
    else if(b-a>=x+1)cout<<"dangerous"<<endl;
    else cout<<"delicious"<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>

using namespace std;

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

long long int INF = 1e18;
int const TREE_SIZE = 1 << 20;
long long int seg_tree[TREE_SIZE] = {};
long long int c_diff[TREE_SIZE] = {}; // 子との差

long long int find(int a, int b, int index, long long int diff, int l, int r){
	
	// [a, b) の最小値を求める
	
	seg_tree[index] += diff;
	c_diff[index] += diff;
	
	if(r <= a || b <= l){
		return INF;
	}
	if(a <= l && r <= b){
		return seg_tree[index];
	}
	
	long long int ret = INF;
	ret = min(ret, find(a, b, index * 2, c_diff[index], l, (l + r) / 2));
	ret = min(ret, find(a, b, index * 2 + 1, c_diff[index], (l + r) / 2, r));
	c_diff[index] = 0;
	return ret;
}

long long int add(int a, int b, int index, long long int num, long long int diff, int l, int r){
	
	// [a, b) に num を足す
	
	seg_tree[index] += diff;
	c_diff[index] += diff;
	
	if(r <= a || b <= l){
		//cout << l << " " << r << " " << seg_tree[index] << " " << c_diff[index] << endl;
		return seg_tree[index];
	}
	if(a <= l && r <= b){
		seg_tree[index] += num;
		c_diff[index] += num;
		//cout << l << " " << r << " " << seg_tree[index] << " " << c_diff[index] << endl;
		return seg_tree[index];
	}
	
	long long int ret = INF;
	ret = min(ret, add(a, b, index * 2, num, c_diff[index], l, (l + r) / 2));
	ret = min(ret, add(a, b, index * 2 + 1, num, c_diff[index], (l + r) / 2, r));
	c_diff[index] = 0;
	//cout << l << " " << r << " " << ret << endl;
	return seg_tree[index] = ret;
}

int main(){
	
	int n, q;
	cin >> n >> q;
	
	for(int i = 0; i < q; i++){
		long long int num, a, b, c;
		cin >> num;
		if(num == 0){
			cin >> a >> b >> c;
			add(a, b + 1, 1, c, 0, 0, TREE_SIZE / 2);
		}else{
			cin >> a >> b;
			cout << find(a, b + 1, 1, 0, 0, TREE_SIZE / 2) << endl;
		}
	}
	
	return 0;
}


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

int x[1005];

int main(){
while(1){	
	
	int n, m, p;
	cin >> n >> m >> p;
	if(n == 0 and m == 0 and p == 0) break;
	
	double sum = 0;
	for(int i=0; i < n; i++){
		cin >> x[i];
		sum += x[i] * 100;
	}
	
	if(x[m - 1] == 0) cout << 0 << endl;
	else{
		sum = sum - sum / 100 * p;
		//cout << sum << endl;
		sum = sum / x[m - 1];
		cout << (int)sum << endl;
	}
	
	//init
	for(int i = 0; i < n; i++) x[i] = 0;
	
}//end
	
	return 0;
}


Measured memory_bytes: 2996
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int n;
	while(cin>>n){
		int cost[100][100]={0},t[100],b[100];
		rep(i,n)cin>>t[i]>>b[i];
		rep(j,n)if(j)rep(i,n-j){
			int mn=1<<30,c;
			rep(k,j)if(mn>(c=cost[k][i]+cost[j-k-1][i+k+1]+t[i]*b[i+k]*t[i+k+1]*b[i+j]))mn=c;
			cost[j][i]=mn;
		}
		cout<<cost[n-1][0]<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate など
#include <cassert>    // assert
#include <stdexcept>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

#define NDEBUG 1
// debug用出力 https://trap.jp/post/998/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << H << " ";
    debug_out(T...);
}
#ifdef NDEBUG
#define debug(...)
#else
#define debug(...) debug_out(__VA_ARGS__)
#endif

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

// constexpr inline ll MOD = 1'000'000'007;

constexpr int max_n = 300000;
int n;
ll k;
vector<int> as(max_n);
vector<int> a_log(max_n);
map<int, int> a_map;
int count_begin, count_end;

int main()
{
    // 入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>k;
    REP(i,n){
        cin>>as[i+1];
    }

    a_log[0] = 1;
    a_map.insert(make_pair(a_log[0], 0));
    REP(i,n+2){
        a_log[i+1] = as[a_log[i]];
        auto it = a_map.find(a_log[i+1]);
        if (it != a_map.end())
        {
            count_begin = it->second;
            count_end = i+1;
            debug(count_begin, count_end);
            break;
        }
        a_map.insert(make_pair(a_log[i+1], i+1));
    }

    k = (k < count_begin) ? k : ((k - count_begin) % (count_begin - count_end) + count_begin);
    cout << a_log[k] << endl;

    return 0;
}


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

using ll = long long int;
using P = pair<int, int>;
using P3 = pair<ll,P>;
using PP = pair<P, P>;
constexpr int INF = 1 << 30;
constexpr ll MOD = ll(1e9) + 7;
constexpr int di[] = {0, 1, 0, -1};
constexpr int dj[] = {1, 0, -1, 0};
constexpr double EPS = 1e-8;

bool solve(){
    int a, b;
    cin >> a >> b;
    int ans = -1;
    for(int i=1;i<=10000;i++){
        if(i*8/100 == a && i*1/10 == b){
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return false;
}

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

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

#define rep(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ROF(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef long long ll;
#define inf 999999999 

main(){
  int n; cin >> n;
  set<int> st;
  rep(i,n){
    int d; cin >> d;
    st.insert(d);
  }
  cout << st.size() << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define F first
#define S second
#define int long long
#define mod 1000000007
#define mmod 998244353
#define all(v) v.begin(), v.end()
#define INF LLONG_MAX/3
using namespace std;
int mypow(int fa, int fb, int fc) {
	if (fb == 0)return 1;
	if (fb % 2)return mypow(fa, fb - 1, fc)*fa%fc;
	int z = mypow(fa, fb / 2, fc);
	return z * z%fc;
}
int k(int fa) {
	int x = 0;
	while (fa) {
		x++;
		fa /= 10;
	}
	return x;
}
int gcd(int fa, int fb) {
	if (fb == 0)return fa;
	return gcd(fb, fa%fb);
}
map<int, int> m;
string s[100000];
queue<char> q;
signed main() {
	int n, a, b, c;
	cin >> n >> a >> b >> c;
	f(i, n) {
		cin >> s[i];
	}
	f(i, n) {
		if (s[i] == "AB") {
			if (a == 0 && b == 0) {
				puts("No");
				return 0;
			}
			if (a == 1 && b == 1 && c == 0) {
				int cnt = 0;
				for (; i < n&&s[i] == "AB"; i++, cnt++) {
				}
				if (s[i] == "AC" || i == n) {
					f(j, cnt) {
						if (j % 2)q.push('B');
						else q.push('A');
					}
					if (cnt % 2)a++, b--;
					i--;
				}
				else if (s[i] == "BC") {
					f(j, cnt) {
						if (j % 2)q.push('A');
						else q.push('B');
					}
					if (cnt % 2)b++, a--;
					i--;
				}
			}
			else if (a <= b) {
				a++, b--;
				q.push('A');
			}
			else {
				a--, b++;
				q.push('B');
			}
		}
		if (s[i] == "AC") {
			if (a == 0 && c == 0) {
				puts("No");
				return 0;
			}
			if (a == 1 && c == 1 && b == 0) {
				int cnt = 0;
				for (; i < n&&s[i] == "AC"; i++, cnt++) {
				}
				if (s[i] == "AB" || i == n) {
					f(j, cnt) {
						if (j % 2)q.push('C');
						else q.push('A');
					}
					if (cnt % 2)a++, c--;
					i--;
				}
				else if (s[i] == "BC") {
					f(j, cnt) {
						if (j % 2)q.push('A');
						else q.push('C');
					}
					if (cnt % 2)c++, a--;
					i--;
				}
			}
			else if (a <= c) {
				a++, c--;
				q.push('A');
			}
			else {
				a--, c++;
				q.push('C');
			}
		}if (s[i] == "BC") {
			if (c == 0 && b == 0) {
				puts("No");
				return 0;
			}
			if (c == 1 && b == 1 && a == 0) {
				int cnt = 0;
				for (; i < n&&s[i] == "BC"; i++, cnt++) {
				}
				if (s[i] == "AC" || i == n) {
					f(j, cnt) {
						if (j % 2)q.push('B');
						else q.push('C');
					}
					if (cnt % 2)c++, b--;
					i--;
				}
				else if (s[i] == "AB") {
					f(j, cnt) {
						if (j % 2)q.push('C');
						else q.push('B');
					}
					if (cnt % 2)b++, c--;
					i--;
				}
			}
			else if (c <= b) {
				c++, b--;
				q.push('C');
			}
			else {
				c--, b++;
				q.push('B');
			}
		}
	}
	puts("Yes");
	while (q.size()) {
		cout << q.front() << endl;
		q.pop();
	}
}

Measured memory_bytes: 6868
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int tab[10][10], ssn[10000], num[6];
void init () {
	for (int id = 0; id < 10000; id++) {
		for (int j = 4, tmpId = id; j >= 1; j--, tmpId /= 10)
			num[j] = tmpId % 10;
		for (int j = 1; j <= 4; j++)
			num[j] = tab[ num[j - 1] ][ num[j] ];
		ssn[id] = id * 10 + num[4];
	}
}
void change (int numOfSsn) {
	for (int j = 5; j >= 1; j--) {
		num[j] = numOfSsn % 10;
		numOfSsn /= 10;
	}
}
bool judge (int ssn) {
	for (int j = 1; j <= 5; j++) {
		for (int i = 0; i < 10; i++) {
			change(ssn);
			if (num[j] == i) continue;
			num[j] = i;
			for (int k = 1; k <= 5; k++)
				num[k] = tab[ num[k - 1] ][ num[k] ];
			if (num[5] == 0) return true;
		}
	}

	for (int j = 2; j <= 5; j++) {
		change(ssn);
		if (num[j - 1] == num[j])  continue;
		swap(num[j - 1], num[j]);
		for (int k = 1; k <= 5; k++)
			num[k] = tab[ num[k - 1] ][ num[k] ];
		if (num[5] == 0) return true;
	}
	return false;
}
int main()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			scanf("%d", &tab[i][j]);
	init();
	int ans = 0;
	for (int i = 0; i < 10000; i++)
		if (judge (ssn[i]))  ans++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2796
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 1000010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

ll MOD = MODBASE;

ll binPowMod(ll a, ll b) {
    a %= MOD;
    ll res = 1;
    while (b > 0) {
        if (b & 1LL) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1LL;
    }
    return res;
}

ll add(ll a, ll b) {
    return (a + b) % MOD;
}

ll sub(ll a, ll b) {
    return (a - b + MOD) % MOD;
}

ll mul(ll a, ll b) {
    return a * b % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n;
    cin >> n;
    ll res = binPowMod(10, n);
    res = sub(res, binPowMod(9, n));
    res = sub(res, binPowMod(9, n));
    res = add(res, binPowMod(8, n));
    cout << res;
    return 0;
}


Measured memory_bytes: 3648
a, b = list(map(int, input().split()))

if a > 0 and b > 0:
  print("Positive")

elif a < 0 and b < 0:
  if abs(b - a) % 2 == 1:
    print("Positive")

  else:
    print("Negative")

elif a <= 0 and b >= 0:
  print("Zero")

Measured memory_bytes: 3060
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	var aList = input[1].split(" ").map(x => parseInt(x, 10));
	//文字列から10進数に変換するときはparseIntを使います
	var n = parseInt(input[0], 10);
    
    let length = aList[0];
    let sum = 0;
    for (let i = 1; i < n; i++) {
        const elem = aList[i];
        if(length > elem) {
            sum += length - elem;
        }
        if(length < elem) {
            length = elem;
        }
    }
    
	//出力
	console.log('%d', sum);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 50168
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int count = 0;
        int[] p = new int[n];
        for (int i = 0; i < p.length; i++)
            p[i] = sc.nextInt();
        for (int i = 0; i <= n - 3; i++) {
            int max = p[i];
            if (max < p[i + 1])
                max = p[i + 1];
            if (max < p[i + 2])
                max = p[i + 2];
            int min = p[i];
            if (min > p[i + 1])
                min = p[i + 1];
            if (min > p[i + 2])
                min = p[i + 2];
            if (p[i + 1] == (p[i] + p[i + 1] + p[i + 2] - max - min))
                count++;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007

void solve()
{
	string s;
	cin>>s;
	if(s[0]==s[s.size()-1])
	{
		if(s.size()%2==0)
			cout<<"First";
		else
			cout<<"Second";
	}
	else
	{
		if(s.size()%2!=0)
			cout<<"First";
		else
			cout<<"Second";
	}
	return;
}

int main()
{
	fast;
	ll q=1;
	// cin>>q;
	while(q--)
		solve();
	return 0;
}



Measured memory_bytes: 3724
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e12;
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;
struct C{
    P p;
    double r;
    C(const P& p, const double& r) : p(p), r(r) {}
    C(){}
};

P unit(const P &p){
    return p/abs(p);
}
VP crosspointCC(C a, C b){
    VP ret;
    if(a.r < b.r) swap(a,b);
    double dist = abs(b.p-a.p);
    P dir = a.r*unit(b.p-a.p);
    if(EQ(dist, a.r+b.r) || EQ(dist, a.r-b.r)){
        ret.push_back(a.p +dir);
    }else if(a.r-b.r < dist && dist < a.r+b.r){
        double cos = (a.r*a.r +dist*dist -b.r*b.r)/(2*a.r*dist);
        double sin = sqrt(1 -cos*cos);
        ret.push_back(a.p +dir*P(cos, sin));
        ret.push_back(a.p +dir*P(cos, -sin));
    }
    return ret;
}

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

        VP p(n);
        vector<double> r(n);
        for(int i=0; i<n; i++){
            int x,y;
            cin >> x >> y >> r[i];
            p[i] = P(x, y);
        }

        double lb=0, ub=200;
        for(int rep=0; rep<50; rep++){
            double mid = (lb +ub)/2;
            vector<C> c(n);
            for(int i=0; i<n; i++){
                c[i] = C(p[i], r[i]*mid);
            }
            VP cand = p;
            for(int i=0; i<n; i++){
                for(int j=i+1; j<n; j++){
                    VP ret = crosspointCC(c[i], c[j]);
                    cand.insert(cand.end(), ret.begin(), ret.end());
                }
            }
            bool ok = false;
            for(int i=0; i<(int)cand.size(); i++){
                bool allin = true;
                for(int j=0; j<n; j++){
                    if(abs(cand[i] -c[j].p) > c[j].r +EPS){
                        allin = false;
                        break;
                    }
                }
                if(allin){
                    ok = true;
                    break;
                }
            }
            if(ok){
                ub = mid;
            }else{
                lb = mid;
            }
        }
        cout << fixed << setprecision(10);
        cout << lb << endl;
    }
    return 0;
}


Measured memory_bytes: 3400
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#include <numeric>
#define IINF 1000000000
#define INF 3223372036854775807
#define MOD 1000000007
#define mod 1000000007
#define INT_MAX_ 2147483647
#define EPS (1e-10)
#define REP(i, a, n) fo-r (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
//#define rep(i,n)for (ll i = 0; i < (ll)(n); i++)
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
#define me memset
#define bit(n,k) ((n>>k)&1)
//#define leng length()
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
#define invp(a,p)pom(a,p-2,p)
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp1(pair<Pll,ll> a,pair<Pll,ll> b){
        return a.fi.se>b.fi.se;
}
ll cmp2(pair<Pll,ll> a,pair<Pll,ll> b){
        return a.se<b.se;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_t=clock();
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //------------------------------
    ll a,b,c,k;cin>>a>>b>>c>>k;
    ll cnt=0;
    while(b<=a){
        cnt++;
        b*=2;
    }
    while(c<=b){
        cnt++;
        c*=2;
    }
    if(cnt<=k)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    //------------------------------
    //fclose(stdin);
    //fclose(stdout);
    //ll end_t=clock();cout<<"time="<<end_t-begin_t<<"ms"<<endl;
    //------------------------------- 
    return 0;
}
//----------------------------------------------------------------------











































Measured memory_bytes: 3648
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define revrep(i, n) for(ll i = n-1; i >= 0; i--)
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll Mypow(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}

ll INFL = 1LL << 60;//10^18 = 2^60
int INF = 1 << 30;//10^9
ll MOD  = 1000000007;
//vector<int> dy = {0,0,1,-1};
//vector<int> dx = {1,-1,0,0};


int main(){
  string S;
  cin >> S;
  if(S[0] == S[1] || S[1] == S[2] || S[2] == S[3]){
    cout << "Bad" << endl;
  }else{
    cout << "Good" << endl;
  }
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int>a(n);
  vector<int>b(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i] >> b[i];
  int maxx = *max_element(a.begin(), a.end());
  int minn = *min_element(b.begin(), b.end());
  int ans = 0;
  vector<pair<int,int>>p(n);
  for (int i = 0; i < n; ++i) 
    p[i] = {minn - a[i] + 1, b[i] - maxx + 1};
  sort(p.begin(), p.end());
  //for (auto& e: p)
  //  cout << e.first << ' ' << e.second << '\n';
  int t = INT_MAX;
  for (int i = 0; i < n-1; ++i)
  {
    t = min(t, p[i].second);
    ans = max(ans, p[i+1].first + t);
  }
  for (int i = 0; i < n; ++i) {
    int cur = b[i] - a[i] + 1;
    cur += max(0, minn - maxx + 1);
    ans = max(ans, cur);
}
cout << ans << '\n';
}



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

int main() {
  int N,a,b,c,d;
  cin >> N ;
  a = N/1000;
  b = (N-1000*a)/100;
  c = (N-1000*a-100*b)/10;
  d = N-1000*a-100*b-10*c;
  if((a==b && b==c) || (b==c && c==d)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x) cout<<#x<<" = "<<(x)<<endl;
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  ll n; cin >> n;
  ll ans = n-1;
  for (ll i=2; i*i <= n; ++i) {
    if (n % i == 0) {
      ans = min(ans, i+n/i-2);
    }
  }
  COUT(ans);
  return 0;
}

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

using namespace std;

using int64 = long long;

int main()
{
  int N, A[100000], B[100000], C[100000];

  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  for(int i = 0; i < N; i++) cin >> B[i];
  for(int i = 0; i < N; i++) cin >> C[i];
  sort(A, A + N);
  sort(B, B + N);
  sort(C, C + N);

  int latte = 0;
  int sum[100000] = {};
  for(int i = 0; i < N; i++) {
    while(latte < N && A[i] >= B[latte]) ++latte;
    if(latte == N) break;
    sum[latte]++;
  }


  int64 ret = 0;
  int malta = 0, all = 0;
  for(int i = 0; i < N; i++) {
    all += sum[i];
    while(malta < N && B[i] >= C[malta]) ++malta;
    if(malta == N) break;
    ret += 1LL * all * (N - malta);
  }
  cout << ret << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1e9 + 7;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    s[n] = 'R';
    char dir = 'R';
    int cnt = 1;
    vector<int> child(n, 0);
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'R') {
            if (dir == 'R') {
                cnt++;
            } else {
                child[i - cnt] += cnt / 2 + cnt % 2;
                child[i - cnt - 1] += cnt / 2;
                dir = 'R';
                cnt = 1;
            }
        } else {
            if (dir == 'L') {
                cnt++;
            } else {
                child[i - 1] += cnt / 2 + cnt % 2;
                child[i] += cnt / 2;
                dir = 'L';
                cnt = 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << child[i];
        if (i != n - 1)
            cout << " ";
        else
            cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3868
#include <iostream>
#include<string>
#include<vector>

using namespace std;

int corattu(int num) {
	if (num % 2 == 0)return num / 2;
	return 3 * num + 1;
}


int main()
{
	int a;

	cin >> a;

	int ans = 4;

	while (true) {
		if (a == 1 || a == 2 || a == 4)break;

		a = corattu(a);
		ans++;
	}

	cout << ans << endl;




	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

int main() {
    int x; //入力される秒数
    int a, b, c; //時間
    
    //入力
    //printf("秒数を入力→ ");
    scanf("%d", &x);
    
    //処理
    a = x / 3600;
    b = x % 3600 / 60;
    c = x % 3600 % 60;
    
    
    //出力
    printf("%d:%d:%d\n", a, b, c);//h, m, s
    
    return 0;
}


Measured memory_bytes: 2104
n = int(input())
MOD = 10**9 + 7

memo = [{} for _ in range(n+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1],t[i] = t[i],t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False

    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Measured memory_bytes: 48220
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N, K, Q, A):
    score = [K + -1 * Q] * N
    for i in range(len(A)):
        score[A[i]] += 1

    for i in range(N):
        if score[i] <= 0:
            print(NO)
        else:
            print(YES)


def main():
    N, K, Q = map(int, input().split())
    A = []
    for i in range(Q):
        A.append(int(input()) - 1)
    solve(N, K, Q, A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 11352
n, k = map(int, input().split())
p = list(map(int, input().split()))

s = 0
ans = 0

for i, j in enumerate(p):
    s+= (j+1)/2
    if i == k-1:
        ans = s
    if i > k-1:
        s -= (p[i-k]+1)/2
        ans = max(ans, s)
print(ans)

Measured memory_bytes: 25060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
const ll INF = 1e16;

void solver(ll X, ll &ans){

    vector<ll> move_sum;
    ll buf{}, ans_buf{};
    for(ll i = 0; ; ++i){
        buf += i;

        if(buf >= X){
            ans_buf = i;
            break;
        }
    }
    ans = ans_buf;
    return;
}

int main(){

    ll X; 
    cin >> X;

    ll ans;
    solver(X, ans);

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

Measured memory_bytes: 3640
n, m = map(int, input().split(' '))
problem = [0] * n
ok=0
pen=0
i=0

while i < m:
    p, result = input().split(' ')
    p = int(p) - 1
    if problem[p] < 0:
        pass
    else:
        if result == 'WA':
            problem[p] += 1
        else:
            ok += 1
            pen += problem[p]
            problem[p] = -1
    i+=1
print('{} {}'.format(ok, pen))

Measured memory_bytes: 3828
#include <stdio.h>

int main(){
    long int N, X, sum=0;

    scanf("%ld", &N);

    X = N;

    while(1){
        if(N > 0){
            sum += N % 10;
            N /= 10;
        }
        else
            break;
    }

    if(X % sum == 0)
        printf("Yes\n");
    else
        printf("No\n");
    
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
multiset<int>s;
multiset<int>::iterator it;
int x[200005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int a=1;a<=n;a++)
    {
        scanf("%d",&x[a]);
        s.insert(x[a]);
    }
        int d=n+1;
        d/=2;
        it=s.begin();
        for(int a=1;a<d;a++)
            it++;
        for(int a=1;a<=n;a++)
        {
            if(x[a]<=*it)
            {
                it++;
                printf("%d\n",*it);
                it--;
            }
            else
                printf("%d\n",*it);
        }

}



Measured memory_bytes: 12288
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

A = np.array([lr() for _ in range(3)])
N = ir()
B = np.zeros_like(A, np.bool)
for _ in range(N):
    b = ir()
    if np.any(A==b):
        i = np.where(A==b)
        B[i[0], i[1]] = True

bl = np.any([np.all(row) for row in B])
if np.any(np.all(B, axis=0)):
    bl = True
if np.all(np.diag(B)):
    bl = True
B = B[:, ::-1]
if np.all(np.diag(B)):
    bl = True
print('Yes' if bl else 'No')


Measured memory_bytes: 12452