akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  int N,M,x,ans,ans2;
  cin>>N>>M;
  int a[N],b[N],c[M],d[M];
  for(int i=0;i<N;i++) cin>>a[i]>>b[i];
  for(int i=0;i<M;i++) cin>>c[i]>>d[i];
  
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
    	x=abs(a[i]-c[j])+abs(b[i]-d[j]);
      	if(j==0){
          ans=x;
          ans2=j+1;
        }
      	if(x<ans){
          ans=x;
     	  ans2=j+1;
        }
    }
    cout<<ans2<<endl;
  }
}


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

#define ll long long

using namespace std;

ll n, k;
double ans, tot, cnt;

//int a[MAXN];

string s;

int main(){
	long long a;
	scanf("%lld",&a);
	cin >> s;
	long long b,c1,c2,c3;	
	c1=s[0]-'0',c2=s[2]-'0',c3=s[3]-'0';
	b=c1*100ll+c2*10ll+c3;
	printf("%lld", a*b/100ll);
	return 0;
}

/*

*/

//Flakire
//Lord Wang
//yxm9
//akdxl
//WYXak
//MifafaOvO
//AKarry5037
//deakX
//xyx
//Fraggay



Measured memory_bytes: 3832
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <functional>
#include "math.h"
#include <set>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define VI vector<int>
#define debug(x) cout<<#x<<": "<<x<<endl
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define MB 1000000007
#define NB 1000000000
#define N5 100007
#define ll long long int
int N;
int A[100001];

int main()
{
	cin >> N;
	REP(i,N){
		cin >> A[i];
	}
	REP(i,N){
		if(A[i]%2==0){
			if(A[i]%3!=0 && A[i]%5!=0){
				cout << "DENIED" << endl;
				return 0;
			}
		}
	}

	cout << "APPROVED";

}



Measured memory_bytes: 256
using Yorukatsu038.Questions;
using Yorukatsu038.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Yorukatsu038.Questions
{
    /// <summary>
    /// ABC103 B
    /// </summary>
    public class QuestionA : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var s = new LinkedList<char>(inputStream.ReadLine());
            var t = inputStream.ReadLine();

            for (int i = 0; i < t.Length; i++)
            {
                if (s.Zip(t, (a, b) => new { a, b }).All(p => p.a == p.b))
                {
                    yield return "Yes";
                    yield break;
                }
                s.AddLast(s.First.Value);
                s.RemoveFirst();
            }
            yield return "No";
        }
    }
}


namespace Yorukatsu038
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionA();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace Yorukatsu038.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace Yorukatsu038.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

Measured memory_bytes: 13524
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
#define p_b push_back
    
ll n,cnt,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
V ans;
U_MAP mp;
    
//-------------------------↓↓↓↓↓↓------------------------
    
//------ 自分を天才だと信じる ------
    
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>a>>b>>k;
    rrep(i,a,a+k){
        if(i>b)break;
        if(mp[i]==1)continue;
        mp[i]=1;
        ans.p_b(i);
    }
    rrrep(i,b,b-k+1){
        if(i<a)break;
        if(mp[i]==1)continue;
        mp[i]=1;
        ans.p_b(i);
    }
    sort(all(ans));
    rep(i,Size(ans))Cout(ans[i]);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define int long long
using namespace std;
vector<int> v;
int n, m;

int32_t main()
{
	//ios_base::sync_with_stdio(false);
	cin>>n>>m;
	multiset<int> st;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		v.pb(x);
		st.insert(x);
	}
	while(m--)
	{
		auto it = st.end();
		it--;
		if(*it == 0)
			break;
		st.erase(it);
		st.insert(*it/2);
	}
	int total = 0;
	for(auto it: st)
		total += it;
	cout<<total;
	
}

Measured memory_bytes: 5748
#include<iostream>
#include<set>
#include<string>
#include<algorithm>

using namespace std;

int m;

int main(){
  cin>>m;
  
  for(int ite=0;ite<m;ite++){
    string str;
    set<string> S;
    
    cin>>str;

    for(int i=1;i<str.size();i++){
      string Front=str.substr(0,i);
      string Back=str.substr(i,str.size()-i);

      string Front_r(Front);
      string Back_r(Back);

      reverse(Front_r.begin(),Front_r.end());
      reverse(Back_r.begin(),Back_r.end());
      
      S.insert(Front+Back);
      S.insert(Back+Front);
      S.insert(Front_r+Back);
      S.insert(Back+Front_r);
      S.insert(Front+Back_r);
      S.insert(Back_r+Front);
      S.insert(Front_r+Back_r);
      S.insert(Back_r+Front_r);

    }

    cout<<S.size()<<endl;
  }
      
      
  return 0;
}

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

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

  string s;
  cin >> s;

  for (int i = 0; i < s.size(); ++i) if (i % 2 == 0) cout << s.at(i); cout << endl;
  return 0;
}


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

int main(){
  long long N,A,B;
  cin >> N >> A>> B;
  
  if ((B-A)<=2){
    cout<<1+N<<endl;
    return 0;
  }
  long long sum=0;
  long long maxsum=1+N;
  
  N=N-(A-1);
  sum=A;
  sum=sum+(B-A)*(N/2);
  if(N%2==1){
      sum=sum+1;
    }
  maxsum=max(maxsum,sum);
  cout<<maxsum;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>

using namespace std;

int main(void){
  string a[7] = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
  int i;
  string b;
  cin >> b;
  
  for(i = 0; i < 7;i++){
    if(a[i] == b){
      break;
  	}
  }
  cout << 7-i << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
using namespace std;
int main(void){
    int a, b;
    cin>>a>>b;
    if(a<=8&&b<=8){
        cout<<"Yay!"<<endl;
    }else{
        cout<<":("<<endl;
    }
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

ll fact[200001];
ll ifact[200001];

void gen_fact(){
  fact[0]= 1;
  ifact[0]= 1;
  rep(i, 200000){
    fact[i+1] = mod(fact[i]*(i+1), MOD);
    ifact[i+1] = modinv(fact[i+1], MOD);
  }
}

ll comb(ll n, ll k){
  ll tmp = mod(fact[n]*ifact[n-k], MOD);
  return mod(tmp*ifact[k],MOD);
}

/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N, M;
  cin >> N >> M;
  set<ll> primes;
  FOR(i,2, sqrt(M)+1){
    if(is_prime(i))primes.insert(i);
  }

  map<ll, ll> num;
  gen_fact();
  for(auto ip:primes){
    if(M==1)break;
    while(M%ip==0){
      num[ip]++;
      M/=ip;
    }
  }
  if(M!=1)num[M]=1;
  ll ans = 1;
  for(auto imp:num){
    ans = mod(ans * fact[N-1+imp.second], MOD);
    ans = mod(ans * ifact[N-1], MOD);
    ans = mod(ans * ifact[imp.second], MOD);
  }

  cout << ans;
  
  
  return 0;
}


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

int n;
vector<int> l;

bool isOK(int a,int b, int c){
  if(l[c]<l[a]+l[b]) return true;
  else return false;
}

int nibutan(int a,int b){
  int ok=b, ng=n;
  while(ng-ok>1){
    int middle = (ok+ng)/2;
    if(isOK(a,b,middle)) ok=middle;
    else ng=middle;
  }
  return ok-b;
}

int main(){
  cin>>n;
  l.resize(n);
  rep(i,n){
    cin>>l[i];
  }
  sort(l.begin(),l.end());
  ll ans=0;
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      ans+=nibutan(i,j);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3636
#include <stdio.h>

int main()
{
	char N[1000002];
	scanf("%s", N);
	
	int i, sum = 0, up = 0, tmp;
	for (i = 0; N[i] != 0; i++);
	for (i--; i >= 0; i--) {
		tmp = N[i] - '0' + up;
		if (tmp < 5) {
			sum += tmp;
			up = 0;
		} else if (tmp > 5) {
			sum += 10 - tmp;
			up = 1;
		} else {
			sum += 5;
			if (i == 0 || N[i-1] - '0' < 5) up = 0;
			else up = 1;
		}
	}
	printf("%d\n", sum += up);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2692
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin >> x;
    if (x < 100) {
        cout << 0 << endl;
    } else if ((x % 100) / (x / 100) < 5) {
        cout << 1 << endl;
    } else if ((x % 100) / (x / 100) == 5 && (x % 100) % (x / 100) == 0) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back	
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n, d, x;
int p[20][20];
int dp[12][100010];
// dp[i][j] := i????????????????????£?????????????????????j??????????¬??????\??????????????\?????????????????§???

int main(void){
	cin >> n >> d >> x;
	rep(i, d)rep(j, n) cin >> p[i][j];
	int ma = x;
	rep(day, d - 1){
		rep(i, 12)rep(j, ma + 1) dp[i][j] = 0;
		dp[0][ma] = 0;
		rep(i, n)REP(j, ma + 1){
			if(j + p[day][i] > ma) dp[i + 1][j] = dp[i][j];
			else dp[i + 1][j] = max(dp[i][j], dp[i + 1][j + p[day][i]] + p[day + 1][i]);
			// printf("dp[%d][%d] = %d\n", i + 1, j, dp[i + 1][j]);
		}
		int tmp = 0;
		rep(i, ma + 1) chmax(tmp, i + dp[n][i]);
		ma = tmp;	
	}
	printf("%d\n", ma);
	return 0;
}

Measured memory_bytes: 4512
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[3] = {1,0,-1};
int dy[3] = {1,0,-1};
const int MOD = 1000000007;

bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  int K,S,cnt=0; 
  cin >> K >> S;
  for(int i=0;i<=K;i++)
    for(int j=0;j<=K;j++){
      if(S-i-j >= 0 && S-i-j <= K)
        cnt++;
    }
  cout << cnt << endl;
  return 0;  
}



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

#define MAX_N 50;

int main(void){
    int N,res=0;
    scanf("%d",&N);
    int p[N],ps[N];
    for(int i=0;i<N;i++){
        scanf("%d",&p[i]);
        ps[i] = p[i];
    }
    sort(ps,ps+N);
    for(int i =0;i<N;i++){
        if(ps[i] != p[i])res++;
    }
    if(res<=2)printf("YES\n");
    else printf("NO\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5; 
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}

ll raise(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}


int n, x, t;

void solve()
{
    cin >> n >> x >> t;
    int k = ceil(1.0*n/x);
    nout(t*k);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

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

#define NL '\n'
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define ones __builtin_popcount
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%I64d",&x)
#define sd(x) scanf("%lf",&x)
#define ss(x) scanf("%s",x)
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REV(i,j,k) for(int i=j;i>=k;i--)
#define READ(f) freopen(f,"r",stdin)
#define WRITE(f) freopen(f,"w",stdout)
#define debug(x) cerr << "debug = " << x << "\n";
#define debugs(s,x) cerr << "debug : " << s << " = " << x << "\n";
#define cnd tree[idx]
#define lnd tree[idx*2]
#define rnd tree[(idx*2)+1]
#define lndp (idx*2),(b),((b+e)/2)
#define rndp (idx*2+1),((b+e)/2+1),(e)
#define X real()
#define Y imag()
#define Point complex<long double>
#define pi 2.0*acos(0.0)
#define EPS 1e-9
#define INF INT_MAX
#define MOD 1000000007
#define MAX 100005

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;


int mod(string num, int a)
{
    // Initialize result
    int res = 0;

    // One by one process all digits of 'num'
    for (int i = 0; i < num.length(); i++)
         res = (res*10 + (int)num[i] - '0') %a;

    return res;
}

int main()
{
    //READ("input.txt");
    //WRITE("out.txt");
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //uniform_int_distribution<int>(0, 10000)(rng)
    std::ios_base::sync_with_stdio(0);
int m,n;
cin>>m>>n;
if(m==n){
    cout<<"Yes"<<endl;
}
else{
    cout<<"No"<<endl;
}



    return 0;
}





Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class ilds1_4_d{
  public static void Main(){
    String[] str = Console.ReadLine().Split(' ');
    int n = int.Parse(str[0]);
    int k = int.Parse(str[1]);
    int[] w = new int[n];
    for(int i=0; i<n; i++){
      w[i] = int.Parse(Console.ReadLine());
    }
    int left = 0;
    int right = n * 10000;
    while(right - left > 1){
      int mid = (left + right)/2;
      if(check(mid, w, k, n)){
        right = mid;
      }
      else{
        left = mid;
      }
      //Console.WriteLine("{0} ~ {1}",left,right);
    }
    Console.WriteLine(right);
  }
  public static bool check(int p, int[] w, int k, int n){
    int count = 1;
    int cur = 0;
    for(int i=0; i<n; i++){
      if(p < w[i]){
        return false;
      }
      cur += w[i];
      if(cur > p){
        count++;
        cur = w[i];
      }
      else if(cur == p){
        count++;
        cur = 0;
      }
    }
    if(cur == 0){
      count--;
    }
    //Console.WriteLine("{0}: {1} <= {2}", p, count, k);
    return (count <= k);
  }
}



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

	int n, m, i, j, k, a, b, id, nn;
	cin >> n >> m;
	vector<vector<int>> adj(n + 1), adjr(n + 1);
	vector<long double> v(n + 1, 0), pp(n + 1, 0), vv(n + 1, 0);
	vector<int> ct(n + 1, 0);

	for (i = 0; i < m; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adjr[b].push_back(a);
		ct[a]++;
	}

	queue<int> q;
	q.push(n);

	while (!q.empty()) {
		id = q.front();
		q.pop();

		//cout << "Processing " << id << "\n";

		// calculate chance
		if (id == n) v[n] = 0;
		else {
			v[id] = 0;
			for (i = 0; i < adj[id].size(); i++) {
				v[id] += 1.0 / adj[id].size() * (v[adj[id][i]] + 1);
			}
		}

		for (auto p : adjr[id]) {
			ct[p]--;
			if (ct[p] <= 0) q.push(p);
		}
	}

	long double best = v[1], sv;

	pp[1] = 1.0;
	for (i = 1; i < n; i++) {
		nn = adj[i].size();
		for (auto p : adj[i]) {
			pp[p] += pp[i] * 1.0 / nn;
		}
		if (nn <= 1) continue;

		long double s = 0, ss;
		for (auto p : adj[i]) {
			s += 1.0 / nn * (v[p] + 1);
		}
		vv[i] = s;

		for (auto p : adj[i]) {
			sv = v[1] - pp[i] * (s - (s - 1.0 / nn * (v[p] + 1)) / (1.0 / nn) * (1.0 / (nn - 1)));
			best = min(best, sv);
		}

	}

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


	return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  int M;
  cin >> M;
  
  int i_max = int(M/N);
  int loop_flag = 1;
  for(int i = i_max; i > 0 && loop_flag == 1;i--){
  	if( M%i == 0){
      cout << i << endl;
      loop_flag = 0;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    long long n, x, ret = -1;
    std::cin >> n >> x;
    std::vector<long long> a(n), b(n);

    for (long long i = 0; i < n; i++) {
        std::cin >> a[i];
        b[i] = a[i];
    }

    for (long long k = 0; k < n; k++) {
        long long sum = k * x;

        for (long long i = 0; i < n; i++) {
            sum += b[i];
            b[i] = std::min(b[i], a[(i + n - k - 1) % n]);
        }

        if (ret > sum || ret == -1) ret = sum;
    }

    std::cout << ret << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include<cstdio>
#include <vector>
#include<queue>
#include<limits.h>
#include<string.h>
#include<functional>
#include<map>
#include<set>
#include<list>
#include<unordered_map>
#include<queue>
using namespace std;

signed main(){
	priority_queue<int>Q;
	string a;
	while (cin >> a, a != "end") {
		if (a == "insert") {
			int b; cin >> b;
			Q.push(b);
		}
		else {
			cout << Q.top() << endl;
			Q.pop();
		}
	}
}

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

int main() {
    int n, a[100];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = n-1; i > 0; i--) {
        cout << a[i] << " ";
    }
    cout << a[0] << endl;
    return 0;
}


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

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

    int n;
    cin >> n;

    int res = 0;
    rep(i, n){
        int l, r;
        cin >> l >> r;

        res += r - l + 1;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

struct Card{
  char suit;
  int value;
};
struct Card S[100000/2+2],T[100000/2+2];
void quicksort(struct Card *,int,int);
int partition(struct Card *,int,int);
void merge(struct Card *,int,int,int);
void mergesort(struct Card *,int,int);
int n;

int partition(struct Card *R,int s,int t){
  int i,j;
  struct Card x,k,m;
  x=R[t];
  i=s-1;
  for(j=s;j<t;j++){
    if(R[j].value<=x.value){
      i++;
      k= R[i];
      R[i]=R[j];
      R[j]=k;
    }
  }
  m=R[i+1];
  R[i+1]=R[t];
  R[t]=m;
  return i+1;
}
void quicksort(struct Card *R,int s,int t){
  int r;
  if(s<t){
    r=partition(R,s,t);
    quicksort(R,s,r-1);
    quicksort(R,r+1,t);
  }
}
void merge(struct Card *R,int left,int mid,int right){
  int i,j,m,l,s;
  l=mid-left;
  s=right-mid;
  for(i=0;i<l;i++){
    S[i]=R[left+i];
  }
  for(i=0;i<s;i++){
    T[i]=R[mid+i];
  }
    S[l].value=T[s].value=1000000000;
    i=j=0;
    for(m=left;m<right;m++){
      if(S[i].value<=T[j].value){
	R[m]=S[i++];
      }
      else {
	R[m]=T[j++];
	  }
    }
}

void mergesort(struct Card *R,int left,int right){
  int mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergesort(R,left,mid);
    mergesort(R,mid,right);
    merge(R,left,mid,right);
  }
}
int main(){
  int i,e,le=1;
  struct Card R[100000],K[100000];
  char D[20];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s %d",D,&e);
    R[i].suit=K[i].suit=D[0];
    R[i].value=K[i].value=e;
  }
  mergesort(R,0,n);
  quicksort(K,0,n-1);
  for(i=0;i<n;i++){
    //マージとクイックの結果を比較
    if(R[i].suit!=K[i].suit)
      le=0;//le==stable;
       }
    if(le==1)
      printf("Stable\n");
    else 
      printf("Not stable\n");
    for(i=0;i<n;i++){
      printf("%c %d\n",K[i].suit,K[i].value);
    }
    return 0;
  }




Measured memory_bytes: 4128
#include<iostream>
using namespace std;
int main(){
	int w,a,b,c;
	cin>>w>>a>>b;
	if(a>b)
	c=a-(b+w);
	else if(b>(a+w))
    c=b-(a+w);
    else if (a<=b&&b<=(a+w))
    c=0;
    cout<<c;

}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a, b, x;
    cin >> a >> b;
    x = (a + b) / 2;
    if((a + b) % 2 == 0)
    {
        cout << x << endl;
    }
    else
    {
    int y = (a + b) / 2 + 1;
    cout << y << endl;
    }
}


Measured memory_bytes: 3548
//ｺｯwwｺｯwwｺｹｯwwwｺｯwwｺｹｯwwwｺｹｯｺｯwwwｺｯwwｺｯwwｺｹｯwwwｺｯwwｺｹｯwwwｺｹｯｺｯwwwｺｹｰｰｰｰｯ!!!wwwwwｺｯwwｺｯwwｺｹｯwwwｺｯwwｺｹｯwwwｺｹｯｺｯwwwｺｯwwｺｯwwｺｹｯwwwｺｯwwwｺｹｯwwwｺｹｯｺｯwwwｺｹｰｰｰｰｯ!!!wwwwwｺｹｯｺｯｯｺｰｰｰｰ!!!!!!wwwwwwwwwww
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(Math.max(0 , a - b));
    }
}

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


int main(){
    int n,x,flag=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x%2==0){
            if(x%3!=0 && x%5!=0)
                flag=0;
        }
    }
    if(flag)
        cout<<"APPROVED";
    else
        cout<<"DENIED";
    return 0;
}


Measured memory_bytes: 256
import itertools

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

T = [i + 1 for i in range(N)]
R = itertools.permutations(T)

def equal(X, Y):
    for x, y in zip(X, Y):
        if x != y:
            return False
    return True

p = -1
q = -1
idx = 0

for r in R:


    if equal(r, P):
        p = idx
    if equal(r, Q):
        q = idx
    idx += 1

print(abs(p - q))


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


int main(){
  string s;
  cin >> s;
  int n=s.size();
  if(s[n-1]=='s') s=s+"es";
  else s=s+'s';
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3628
#define MOD_TYPE 1

#pragma region Macros
#include <bits/stdc++.h>
using namespace std;

#if 0
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using Int = boost::multiprecision::cpp_int;
using lld = boost::multiprecision::cpp_dec_float_100;
#endif

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
//constexpr ll MOD = 1;
constexpr int INF = (int)1e9 + 10;
constexpr ll LINF = (ll)4e18;
constexpr double PI = acos(-1.0);
constexpr double EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define REPI(i, m, n) for (int i = m; i < (int)(n); ++i)
#define repi(i, n) REPI(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

struct io_init
{
  io_init()
  {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(30) << setiosflags(ios::fixed);
  };
} io_init;
template <typename T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
inline ll CEIL(ll a, ll b)
{
  return (a + b - 1) / b;
}
template <typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val)
{
  fill((T *)array, (T *)(array + N), val);
}
template <typename T, typename U>
constexpr istream &operator>>(istream &is, pair<T, U> &p) noexcept
{
  is >> p.first >> p.second;
  return is;
}
template <typename T, typename U>
constexpr ostream &operator<<(ostream &os, pair<T, U> &p) noexcept
{
  os << p.first << " " << p.second;
  return os;
}
#pragma endregion

void solve()
{
  int n;
  cin >> n;
  int d[100][2];
  rep(i, n) rep(j, 2)
  {
    cin >> d[i][j];
  }
  rep(i, n - 2)
  {
    if (d[i][0] == d[i][1] and d[i + 1][0] == d[i + 1][1] and d[i + 2][0] == d[i + 2][1])
    {
      Yes(1);
      return;
    }
  }
  Yes(0);
}

int main()
{
  solve();
}


Measured memory_bytes: 3652
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>
using namespace std;
using i32 = int; using i64 = long long int; using f64 = double; using str = string;
template <typename T> using vec = vector<T>;
template <typename T> using heap = priority_queue<T>;
void in() {}; template <typename T, typename...TS> void in(T &&x, TS &&...xs) { cin>>x; in(move(xs)...); };
template <typename T> void _out(const char *sep, const char *end, T &&x) { cout<<x<<end; };
template <typename T, typename...TS> void _out(const char *sep, const char *end, T &&x, TS &&...xs) { cout<<x<<sep; _out(sep, end, move(xs)...); }
#define indef(t, ...) t __VA_ARGS__; in(__VA_ARGS__)
#define get(t) []{ t _; cin >> _; return _; }()
#define put(...) _out("", "", __VA_ARGS__)
#define out(...) _out(" ", "\n", __VA_ARGS__)
#define times(n, i) for (i32 i =  0 ; i <  (n); ++i)
#define range(a, b, i) for (i32 i = (a); i <  (b); ++i)
#define upto(a, b, i) for (i32 i = (a); i <= (b); ++i)
#define downto(a, b, i) for (i32 i = (a); i >= (b); --i)
#define all(xs) (xs).begin(), (xs).end()
#define sortall(xs) sort(all(xs))
#define reverseall(xs) reverse(all(xs))
#define even(x) (((x) & 1) == 0)
#define odd(x) (((x) & 1) == 1)
#define append emplace_back
#define findge lower_bound
#define findgt upper_bound
const i64 MOD = 1000000007;
const f64 EPS = 1e-10;

i64 n;
str s;

i32 main()
{
    in(n, s);
    i64 v = 0, w = 0;
    times(n, i) {
        if (s[i] == '(') {
            v++;
        }
        else {
            v--;
        }
        if (v < 0) {
            w++;
            v++;
        }
    }
    str ans = "";
    if (w > 0) {
        times(w, _) {
            ans += '(';
        }
    }
    times(n, i) {
        ans += s[i];
    }
    if (v > 0) {
        times(v, _) {
            ans += ')';
        }
    }
    out(ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

int main(){

  ll n,k;
  cin >> n >> k;

  string s;
  cin >> s;

  if(s[k-1]=='A')s[k-1]='a';
  else if(s[k-1]=='B')s[k-1]='b';
  else s[k-1]='c';

  for(int i=0;i<n;i++)cout << s[i];
  cout << endl;

}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<ll> vec;

void solve() {
	int n, k; cin >> n >> k;
	vector<int> a(n);
	rep(i, n)cin >> a[i];
	vector<bool> exi(1 << n, false);
	rep(i, (1 << n)) {
		int s = 0;
		rep(j, n) {
			if (i&(1 << j))s += a[j];
		}
		if (s == k)exi[i] = true;
	}
	rep(i, (1 << n)) {
		if (!exi[i])continue;
		rep(j, n) {
			if (i&(1 << j))continue;
			exi[i ^ (1 << j)] = true;
		}
	}
	int ans = n;
	rep(i, (1 << n)) {
		int tmp = 0;
		rep(j, n) {
			if (i&(1 << j))tmp++;
		}
		if (!exi[i]) {
			ans = min(ans, n - tmp);
		}
	}
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(8);
	//init();
	solve();
	stop
		return 0;
}



Measured memory_bytes: 3140
using System;
using System.Collections.Generic;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            //List<List<int>> abc = new List<List<int>>();
            int[,] abc = new int[3, N];
            int[,] dp = new int[3, N+3];
            for(int i=0;i<N;i++)
            {
                string[] sabc = Console.ReadLine().Split(' ');
                abc[0, i] = int.Parse(sabc[0]);
                abc[1, i] = int.Parse(sabc[1]);
                abc[2, i] = int.Parse(sabc[2]);
            }
            dp[0, 0] = abc[0, 0];dp[1, 0] = abc[1, 0];dp[2, 0] = abc[2, 0];
            for(int i=1;i<N;i++)
            {
                for(int j=0;j<3;j++)
                {
                    for(int k=0;k<3;k++)
                    {
                        if (j != k) 
                        {
                            dp[j, i] = Math.Max(dp[j, i], dp[k,i-1] + abc[j, i]);
                        }
                    }
                }
            }
            int ans = 0;
            for (int i = 0;i<3;i++)
            {
                if(ans < dp[i,N-1])
                {
                    ans = dp[i, N-1];
                }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 48436
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <deque>
#include <string>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <map>
#include <unordered_map>
#include <bitset>

#define _crt_secure_no_warnings
#define FREEELO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define mp make_pair
#define INF 0x3F3F3F3F3F3F3F3F
#define MAX 300001
#define MOD 1000000007LL
#define ALPHABET 128
#define loop(i, n) for (int i = 1; i <= (n); i++)
#define loop0(i, n) for (int i = 0; i < (n); i++)
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll, ll> llll;
typedef pair<int, int> ii;
typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> umll;

ll pw(ll a, ll b) {
    if (b == 1) return a;
    if (b == 0) return 1LL;
    if (b % 2) return (a * pw(a, b - 1)) % MOD;
    return pw((a * a) % MOD, b / 2);
}

int main() {
    ll n;
    cin >> n;
    ll ans = pw(10, n) - (2ll * pw(9, n) - pw(8, n)) % MOD + MOD;
    cout << ans % MOD << endl;
}

Measured memory_bytes: 3180
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<iomanip>
#include<utility>
#include<cmath>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
const int MAX=100000;
const int INFTY=1<<30;

class edge
{
public:
	int t,w;
	edge(int in_t=0,int inw=0):t(in_t),w(inw){}
};

vector<edge> G[MAX];
int n,d[MAX];
bool visited[MAX];
int count;

void bfs(int s)
{
	for(int i=0;i<n;i++)d[i]=INFTY;
	queue<int> q;
	q.push(s);
	d[s]=0;
	int u;
	edge e;
	
	while(!q.empty())
	{
		u=q.front();q.pop();
		for(int i=0;i<G[u].size();i++)
		{
			e=G[u][i];
			if(d[e.t]==INFTY)
			{
				d[e.t]=d[u]+e.w;
				q.push(e.t);
			}
		}
	}
	
	return;
}

int getdiameter()
{
	bfs(0);
	int maxv=0,tgt=0;
	for(int i=0;i<n;i++)
	{
		if(d[i]==INFTY)continue;
		else if(maxv<d[i])
		{
			maxv=d[i];
			tgt=i;
		}
	}
	
	bfs(tgt);
	maxv=0;
	for(int i=0;i<n;i++)
	{
		if(d[i]==INFTY)continue;
		maxv=max(maxv,d[i]);
	}
	
	return maxv;
}

int main()
{
	cin>>n;
	int s,t,w;
	for(int i=0;i<n-1;i++)
	{
		cin>>s>>t>>w;
		G[s].push_back(edge(t,w));
		G[t].push_back(edge(s,w));
	}
	cout<<getdiameter()<<endl;
	return 0;
}

Measured memory_bytes: 9820
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
int64_t INF = 1000000007;
// int64_t INF = 9223372036854775807;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    string s,t;
    cin >> s >> t;
    string res = "Yes";
    if(s.size()+1 != t.size()) res = "No";
    rep(i,s.size()){
        if(s.at(i) != t.at(i)) res = "No";
    }
    cout << res << endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <ctime>
#include <cstdlib>
#define rep(i, N) for (long i = 0; i < (N); i++)
#define swap(a, b) (a += b, b = a - b, a -= b)
using namespace std;
int main()
{
    int A, B;
    cin >> A >> B;
    if (abs(A - B) % 2 == 0)
    {
        cout << abs(A - B) / 2 + min(A, B) << endl;
    }
    else
    {
        cout << "IMPOSSIBLE" << endl;
    }
}


Measured memory_bytes: 256
<?php

main();


function main() {
	while (($line = trim(fgets(STDIN))) != 0) {
		$n = intval($line);
		$count = 0;
		$sum = 0;
		$now = 2;
		while ($count < $n) {
			if (isPrime($now)) {
				$count++;
				$sum += $now;
			}
			$now++;
		}
		echo $sum . "\n";
	}
}


function isPrime($n) {
	if ($n == 2 || $n == 3) {
		return true;
	}
	if ($n < 2 || $n % 2 == 0) {
		return false;
	}
	if ($n < 9) {
		return true;
	}
	if ($n % 3 == 0) {
		return false;
	}

	$r = intval(sqrt($n));
	$f = 5;
	while ($f <= $r) {
		if ($n % $f == 0 || $n % ($f + 2) == 0) {
			return false;
		} else {
			$f += 6;
		}
	}
	return true;
}

Measured memory_bytes: 6612
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1000000007;

int main(){
    int N;
    while(cin >> N){
        vector<pair<int,int>> p(2*N);
        for(int i=0;i<2*N;i++){
            cin >> p[i].first;
            p[i].second = (i < N ? 1 : -1);
        }
        sort(p.begin(), p.end());
        int sum = 0;
        long long res = 1;
        for(const auto& pr : p){
            if(sum * pr.second < 0){
                res *= abs(sum);
                res %= MOD;
            }
            sum += pr.second;
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 1792
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> earliestNDBeg(vector<int> v) {
	vector<int> res(v.size(), 0);
	for (int i = 1; i < v.size(); ++i) {
		if (v[i] >= v[i-1]) {
			res[i] = res[i-1];
		} else {
			res[i] = i;
		}
	}
	return res;
}

vector<int> earliestNIBeg(vector<int> v) {
	vector<int> res(v.size(), 0);
	for (int i = 1; i < v.size(); ++i) {
		if (v[i] <= v[i-1]) {
			res[i] = res[i-1];
		} else {
			res[i] = i;
		}
	}
	return res;
}

int main() {
	int N; scanf("%d", &N);
	vector<int> A(N, 0);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &A[i]);
	}

	vector<int> refBackND = earliestNDBeg(A);
	vector<int> refBackNI = earliestNIBeg(A);

	vector<int> res(N, 1);
	for (int i = 1; i < N; ++i) {
		int makeNDScore = (refBackND[i] == 0 ? 1 : res[refBackND[i] - 1] + 1);
		int makeNIScore = (refBackNI[i] == 0 ? 1 : res[refBackNI[i] - 1] + 1);
		res[i] = min(makeNIScore, makeNDScore);
	}

	printf("%d", res[N-1]);
	return 0;
}

Measured memory_bytes: 1784
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<bool> is_prime(1000000, true);
    for(int i=2;i<1000000;++i) {
        if(!is_prime[i]) continue;
        if(i >= n && is_prime[i]) {
            cout << i << endl;
            return 0;
        }
        int j = i+i;
        while(j < 1000000) {
            is_prime[j] = false;
            j += i;
        }
    }
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  int ans = 0;
  for (int rot = 0; rot < n; rot++) {
    int ok = 1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        ok &= (s[i][j] == s[j][i]);
      }
    }
    ans += ok;
    for (int i = 0; i < n; i++) {
      s[i] = s[i].substr(1) + s[i].substr(0, 1);
    }
  }
  cout << ans * n << '\n';
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;
int pri[100100],phi[100100],tot=0;
int n,kk,ans=0;
inline int poww(int a,int b,int mod)
{
	int res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
inline void prep()
{
	phi[1]=1;
	int i=2,j=1;
	while(i<=100000)
	{
		if(!phi[i])
		{
			pri[++tot]=i;
			phi[i]=i-1;
		}
		j=1;
		while((j<=tot)&&(pri[j]*i<=100000))
		{
			if(i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
			else
			{
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			++j;
		}
		++i;
	}
}
signed main()
{
	prep();
	scanf("%lld%lld",&n,&kk);
	prep();
	int i=1;
	while(i<=kk)
	{
		ans+=phi[i]*poww(kk/i,n,mod);
		ans%=mod;
		++i;
	}
	printf("%lld\n",ans);
	return 0;
}

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

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
typedef std::pair<int, int> pii;
#define X first
#define Y second
#define double long double
typedef double db;
using namespace std;

const int MaxN = 200100;
const int Mod = 1e9 + 7;

int N;

void solve() {
  if (N % 2 == 1) {
    cout << N*(N-1)/2 - (N-1)/2 << endl;
    FOR(i, 1, N+1) FOR(k, i+1, N+1) {
      if (i + k != N) cout << i << " " << k << endl;
    }
  }
  else {
    cout << N*(N-1)/2 - N/2 << endl;
    FOR(i, 1, N+1) FOR(k, i+1, N+1) {
      if (i + k != N + 1) cout << i << " " << k << endl;
    }
  }
}

void load() {
  cin >> N;
}

int main() {
  ios_base::sync_with_stdio(false);
  load();	
  solve();
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    vector<vector<ll>> a(n+1);
    for (int i = 1; i <= n; ++i) REP(j,3){
        int A;
        cin >> A;
        a[i].push_back(A);
    }
    ll dp[n+10][3];
    REP(i,n+10) REP(j,3) dp[i][j] = 0;
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (int i = 1; i <= n; ++i) REP(j,3) REP(k,3) {
        if (k == j) continue;
        dp[i][j] = max(a[i][j]+dp[i-1][k], dp[i][j]);
    }
    ll ans = 0;
    REP(i,3) ans = max(ans, dp[n][i]);
    cout << ans << std::endl;
    return 0;
}

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

int N;
const int MAX_N = 1e5+10;
vector<int> g[MAX_N];
vector<pair<int,int>> edges;
map<pair<int,int>,int> col;
int C = 1;

void dfs(int at, int skip)
{
	int co = 0;
	for(int i=0;i<g[at].size();++i){
		auto p = make_pair(min(at, g[at][i]), max(at, g[at][i]));
		if(col.count(p)) continue;
		if(++co == skip) ++co;
		col[p]=co;
		dfs(g[at][i], co);
	}
}

void solve()
{
	int node=-1;
	for(int i=1;i<=N;++i){
		if(node == -1 || g[i].size() > g[node].size()){
			node = i;
		}
	}
	for(int i=0;i<g[node].size();++i){
		col[make_pair(min(node, g[node][i]), max(node, g[node][i]))] = C++;
	}
	for(int i=0;i<g[node].size();++i){
		dfs(g[node][i], i+1);
	}
	cout << C-1 << "\n";
	for(int i=0;i<N-1;++i){
		cout << col[edges[i]] << "\n";
	}
	return;
}

int main()
{
	cin >> N;
	int a, b;
	for(int i=0;i<N-1;++i){
		cin >> a >> b;
		edges.emplace_back(min(a,b),max(a,b));
		g[a].push_back(b);
		g[b].push_back(a);
	}
	solve();
	return 0;
}


Measured memory_bytes: 15864
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef pair<int, int>P;
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
typedef vector<vector<ll>> mat;
typedef vector<int> vec;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll qp(ll a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };



void solve() {
    ll a, b, c, d, e , m, n, k, x, y, l,r, h, w;
    string s, t;
    ll ans = 0;
    double dans = 0;
    string sans = "Yes";
    vector<ll> ar;
    vector<string> sr;
    vector<vector<char>> arr;

    cin >> n >> m;

    ans = n*(n-1)/2 + m*(m-1)/2;


    std::cout << ans << endl;

    // std::cout << sans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    solve();
    // stop
        return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 1e5 + 5 ; 
int n, m, T, num, cnt, idnex, fa[N] ; 
struct Q {
	int a, b, c ; 
} q[N] ;
int fd( int x ) {
	return ( x == fa[x] ) ? x : fa[x] = fd(fa[x]) ;
}
void merge( int x, int y ) {
	int u = fd(x), v = fd(y) ; 
	if( u != v ) -- num, fa[u] = v, ++ cnt ; 
}
signed main()
{
	n = gi(), m = gi(), T = gi() ; 
	rep( i, 1, n ) fa[i] = i ; num = n ;
	rep( i, 1, T ) {
		q[i].a = gi(), q[i].b = gi(), q[i].c = gi() ;
		if( q[i].c == 0 ) ++ idnex, merge( q[i].a, q[i].b ) ; 
	}
	if( m <= n - 1 ) {
		if( m < n - 1 ) puts("No") ;
		else if( T == idnex ) puts("Yes") ;
		else puts("No") ;
		exit(0) ;
	}
	int l = n, r = cnt + ( num * ( num - 1 ) ) / 2 ;
	rep( i, 1, T ) {
		if( q[i].c == 1 )
		if( fd(q[i].a) == fd(q[i].b) ) {
			puts("No") ; exit(0) ;
		}
	}
	if( m >= l && m <= r ) puts("Yes") ;
	else puts("No") ;
	return 0 ;
}

Measured memory_bytes: 3456