akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <cstring>
#include <map>

using namespace std;

typedef long long ll;

int N,M;
string ss[101];
map<char,int> equ;
char cs[101];
int co[101];
bool isHead[1001];
int cnt;
int nums[101];

// Mツ古つづ個閉カツ篠堋づ可青板篠堋づーツ環づィツ督鳴づづゥ
void check(){
    do{
        // ツ陛サツ津カツ篠ョツつェツ湘ーツ個渉づーツ鳴楪つスツつキツつゥツづつ、ツつゥツチツェツッツク
        int sum=0;
        bool ok=true;
        for(int i=0;i<M;i++){
            if(isHead[cs[i]]&&nums[i]==0){
                ok=false;
                break;
            }
            sum+=co[i]*nums[i];
        }
        if(ok&&sum==0)cnt++;
    }while(next_permutation(nums,nums+M));
}

void solve(){
    for(int s=0;s<(1<<10);s++){
        int a=0;
        //vector<int> v;
        for(int i=0;i<10;i++){
            if((s>>i)&1){
                a++;
                nums[a-1]=i;
            }
        }
        if(a==M)
            check();
        //table[a].push_back(v);
  //      int bit=s;
  //      int x = bit & -bit, y = bit + x;
		//bit = ((bit & ~y) / x >> 1) | y;
  //      s=bit;
    }
    //int a=table[M].size();
    //for(int i=0;i<table[M].size();i++){
    //    for(int j=0;j<M;j++)nums[j]=table[M][i][j];
    //    check();
    //}
}

//void prePro(){
//    for(int s=0;s<(1<<10);s++){
//        int a=0;
//        vector<int> v;
//        for(int i=0;i<10;i++){
//            if((s>>i)&1){
//                a++;
//                v.push_back(i);
//            }
//        }
//        table[a].push_back(v);
//    }
//}

int main(){
    std::ios_base::sync_with_stdio(0);
    //prePro();
    while(cin>>N&&N){
        cnt=0;
        equ.clear();
        memset(isHead,0,sizeof(isHead));
        for(int i=0;i<N;i++)cin>>ss[i];
        // ツ暗ェツ篠淞陛サツ津カツ篠ョツづーツ催ャツ青ャツつオツづつィツつュ
        for(int i=0;i<N;i++){
            int mul=1;
            for(int j=ss[i].size()-1;j>=0;j--){
                if(i==N-1)equ[ss[i][j]]-=mul;
                else equ[ss[i][j]]+=mul;
                if(j==0&&ss[i].size()!=1)isHead[ss[i][j]]=true;
                mul*=10;
            }
        }
        M=equ.size();
        int id=0;
        // ツ係ツ青板づ閉カツ篠堋づーツ禿シツづェツづつィツつュ
        for(map<char,int>::iterator it=equ.begin();it!=equ.end();it++){
            cs[id++]=it->first;
            co[id-1]=it->second;
        }
        solve();
        cout<<cnt<<endl;
    }
    return 0;
}

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

signed main() {
    ll N,Q,prefixsum[100010];
    string s;
    cin>>N>>Q>>s;
    prefixsum[0] = 0;
    prefixsum[1] = 0;
    rep(i,2,N+1){
        prefixsum[i] = prefixsum[i-1];
        if (s[i-2]=='A' && s[i-1]=='C'){
            prefixsum[i]++;
        }
    }
    rep(i,0,Q){
        ll l,r;
        cin>>l>>r;
        l--;
        auto ans = prefixsum[r]-prefixsum[l];
        if (l-1>=0 && s[l-1]=='A' && s[l]=='C'){
            ans--;
        }
        cout<<ans<<endl;
    }
    return 0;
}


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

int head,tail,MAX,n,q,T=0;

struct process {
    string name;
    int time;
};

vector<process> Q(1000000);

bool isEmpty(){
    return head==tail;
}

void enqueue(process x){
    Q.at(tail)=x;
    if(tail==MAX){
        tail=0;
    }
    else tail++;
}

process dequeue(){
    process x=Q.at(head);
    if(head+1==MAX){
        head=0;
    }
    else head++;
    return x;
}



int main(){
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>Q.at(i).name>>Q.at(i).time;
    }

    MAX=1000000;
    head=0;
    tail=n;

    while(!isEmpty()){
        if(Q.at(head).time>q){
            T+=q;
            Q.at(head).time-=q;
            enqueue(dequeue());
        }
        else{
            T+=Q.at(head).time;
            cout<<Q.at(head).name<<' '<<T<<endl;
            dequeue();
        }
    }    
}


Measured memory_bytes: 20760
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

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

    int N, M;
    while (cin >> N >> M, N) {
        vector<int> h(N), w(M);
        REP (i, N) cin >> h[i];
        REP (i, M) cin >> w[i];
        vector<int> hh, ww;
        REP (i, N) {
            int sum = 0;
            FOR (j, i, N) {
                sum += h[j];
                hh.push_back(sum);
            }
        }
        REP (i, M) {
            int sum = 0;
            FOR (j, i, M) {
                sum += w[j];
                ww.push_back(sum);
            }
        }
        sort(hh.begin(), hh.end());
        sort(ww.begin(), ww.end());
        int ans = 0;
        for (int v : hh) {
            ans += upper_bound(ww.begin(), ww.end(), v) - lower_bound(ww.begin(), ww.end(), v);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 36928
#include<bits/stdc++.h>
using namespace std;
long long int M,D,sum;
vector<pair<int,int>> dot;
bool flag=0,flag1=1;
int main(){
	cin>>M>>D;
	for(int i=1;i<=M;i++){
		for(int j=22;j<=D;j++){
			int K=j/10,K2=j%10;
			if(K2<2)
				continue;
			if(K*K2==i){
				sum++;
			}
		}
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, i; cin >> N >> i;
  int ans = N-i+1;
  cout << ans << endl;
}


Measured memory_bytes: 3608
/*
sleep..sleep....sleep
*/
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int > pp;
typedef long long ll;
 
#define sz(x) (int)x.size() 
int const N=3e5+10,oo=1e9;
ll const OO=2e18;
double const eps=1e-8,PI=acos(-1);
int mod=oo+7;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(b/a,c);
    return 0;
}



Measured memory_bytes: 892
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int INF = 0x3f3f3f3f;
//static const auto _____ = []()
//{
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr);
//	return nullptr;
//}();
typedef long long ll;

int main(int argc, char *argv[]) {
    int N, V;
    cin >> N >> V;
    vector<ll> v(N + 1, 0);
    vector<ll> w(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i];
    }
    vector<vector<ll>> dp(N + 1, vector<ll>(V + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (j < v[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << dp[N][V];
    return 0;
}

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

using namespace std;

int const MMM = 100009;
int dp[MMM] , arr[MMM];
int n;

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ;i++)
        cin >> arr[i];
    dp[2] = abs(arr[2] - arr[1]);

    for(int i = 3 ; i <= n ; i++)
    {
        dp[i] = min(dp[i - 1] + abs(arr[i - 1] - arr[i]) , dp[i - 2] + abs(arr[i - 2] - arr[i]));
    }
    cout << dp[n];

    return 0;
}


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

int main()
{
    ll x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    ll ans;
    if(x / d >= k) {
        ans = x - d * k;
    } else {
        ll e = x / d;
        k -= e;
        x -= e * d;
        if(k % 2 == 1) x = abs(x - d);
        ans = x;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define N 3010

ll inv[N], fac[N], finv[N];

void make()
{
	fac[0] = fac[1] = 1;
	inv[1] = 1;
	finv[1] = finv[0] = 1;
	for(int i = 2; i < N; ++i)
	{
		fac[i] = i * fac[i - 1] % MOD;
		inv[i] = MOD - MOD/i * inv[MOD % i] % MOD;
		finv[i] = inv[i] * finv[i - 1] % MOD;
	}
}

ll C(ll n, ll k)
{
	if(n < k || n < 0) return 0;
	return fac[n] * finv[n - k] % MOD* finv[k] % MOD;
}

ll gcd(ll a, ll b)
{
	if(b == 0)
		return a;
	return gcd(b, a % b);
}
int n, m;
char a[N][N];
double dp[N][N];
double p[N];
double dpf(int i, int j)
{
	if(i == n)
		if(j >= m)
			return 1;
		else
			return 0;

	if(dp[i][j] >= 0)
		return dp[i][j];
	return dp[i][j] = p[i] * dpf(i + 1, j + 1) + (1 - p[i]) * dpf(i + 1, j);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(10);
	cin >> n;
	m = n/2 + 1; //>> m;
	for (int i = 0; i < n; ++i)
	{
		cin >> p[i];
	}
	dp[n][n + 1] = 1, dp[n][n] = 1;
	dp[0][0] = 1- p[0];
	dp[0][1] = p[0];
	for (int i = 1; i < n; ++i)
	{
		for(int j = 0; j <= n; ++j)
		{
			dp[i][j] = p[i] * dp[i-1][j-1] + (1 - p[i]) * dp[i-1][j];
		}
	}
	double ans = 0;
	for(int i = m; i <=n ;++i)
		ans += dp[n-1][i];
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 71936
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <vector>
#include <list>
#include <queue>
#include <stack>

using namespace std;


int main() {
	int n, x[200005], y[200005];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		y[i] = x[i];
	}
	sort(x, x + n);
	int cent1 = x[n / 2 - 1], cent2 = x[n / 2];
	for (int i = 0; i < n; i++) {
		if (y[i] >= cent2) {
			cout << cent1 << endl;
		}
		else if (y[i] <= cent1) {
			cout << cent2 << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3712
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] l = new int[n];
        int cnt = 1;
        int pos = 0;
        for (int i = 0; i < n; i++) {
            l[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            pos += l[i];
            if (pos <= x) {
                cnt++;
            } else {
                break;
            }
        }
        System.out.println(cnt);

        sc.close();
    }
}


Measured memory_bytes: 24788
#include <stdio.h>
int main()
{
	int a[10005];
	int b[10005];
	int i, n;
	long long sum = 0;
	long long ans = 0;
	scanf("%d", &n);
	for(i = 1 ; i <= n ; i++)
	{
		scanf("%d", &a[i]);
	}
	for(i = 1 ; i <= n ; i++)
	{
		scanf("%d", &b[i]);
	}
	for(i = 1 ; i <= n ; i++)
	{
		if(a[i] > b[i])
		{
			sum = sum + (a[i] - b[i]);
		}
		else
		{
			ans = ans + (b[i] - a[i]) / 2;
		}
	}
	if(sum > ans)
	{
		printf("No\n");
	}
	else
	{
		printf("Yes\n");
	}
	return 0;
}

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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N; cin >> N;
    int ans = 1;
    while(ans <= N) ans *= 2;
    cout << ans / 2 << endl;
}

Measured memory_bytes: 3644
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int t[] = new int[n];
        
        int  i = 0;
        while(i<n){
            t[i] = scanner.nextInt();
            i++;
        }
        
        i =  n-1;
        while(i > 0){
            System.out.print(t[i] + " ");
            i = i -1;
        }
        System.out.print(t[0]); 

        System.out.println("");
    }
}



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

namespace ABC083B_SomeSums
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            int n = input[0];
            int a = input[1];
            int b = input[2];
            int ans = 0;

            for(int i = 1; i <= n; i++)
            {
                int sum = 0;
                foreach (var item in i.ToString())
                {
                    sum += (int)(item - '0');
                }
                if (a <= sum && sum <= b)
                {
                    ans += i;
                }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
#include<cstdio>
long long const p=1e9+7;
long long ext_gcd(long long a,long long b,long long &x,long long &y){
    if(b==0){x=1;y=0;return a;}
    long long q=a/b, g=ext_gcd(b,a-q*b,x,y), z=x-q*y;
    x=y; y=z;
    return g;
}
long long inv(long long value){
    long long x,y;
    ext_gcd(value,p,x,y);
    return (x+p)%p;
}
long long fact[200000],factinv[200000],powa[200000],powb[200000];
long long ncr(int n,int r){
    return fact[n]*factinv[r]%p*factinv[n-r]%p;
}
int n,c;
//x(m)=引き分けのないゲームがちょうどm回行われる確率
long long x(int m){
    //printf("%d %d %lld %lld\n",m-1,n-1,ncr(m-1,n-1),(powa[n]*powb[m-n]%p+powa[m-n]*powb[n]%p));
    return ncr(m-1,n-1)*(powa[n]*powb[m-n]%p+powa[m-n]*powb[n]%p)%p;
}
//y(m)=引き分けでないゲームがm回行われるまでに、引き分けを含めたゲームが行われる回数の期待値
long long y(int m){
    return m*100LL%p*inv(100-c)%p;
}
long long xtest[200000];
int main(){
    int a,b;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    //前計算
    fact[0]=1;
    for(int i=1;i<2*n;i++)fact[i]=fact[i-1]*i%p;
    for(int i=0;i<2*n;i++)factinv[i]=inv(fact[i]);
    long long adiv100=a*inv(a+b)%p,bdiv100=b*inv(a+b)%p;
    //printf("%lld %lld\n",adiv100,bdiv100);
    powa[0]=1;
    powb[0]=1;
    for(int i=1;i<2*n;i++)powa[i]=powa[i-1]*adiv100%p;
    for(int i=1;i<2*n;i++)powb[i]=powb[i-1]*bdiv100%p;
    //本計算
    long long ans=0;
    for(int m=n;m<2*n;m++){
        ans+=x(m)*y(m)%p;
    }
    printf("%lld\n",(ans+p)%p);
    return 0;
}

Measured memory_bytes: 6400
#include <iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <string>
#include <set>
#include <bitset>

using namespace std;
#define ff(i,n,m) for(int i=n;i<m;i++)
#define i64 int64_t
#define tos(x) to_string(x)

int main() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> s(n);
	vector<pair<int, int>> g(m);
	ff(i, 0, n) {
		cin >> s.at(i).first >> s.at(i).second;
	}
	ff(i, 0, m) {
		cin >> g.at(i).first >> g.at(i).second;
	}
	ff(i, 0, n) {
		int nearest;
		int distance=1000000000;
		ff(j, 0, m) {
			int x = abs(g.at(j).first - s.at(i).first)
				+ abs(g.at(j).second - s.at(i).second);
			if (x < distance) {
				nearest = j;
				distance = x;
			}
		}
		cout << nearest+1 << endl;
	}
	return 0;
}

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

int main(){
  ll ret = 0;
  ll n;
  cin >> n;
  vector<ll> S(n);
  for(ll i = 0; i < n; i++){
    cin >> S[i];
  }
  ll q;
  cin >> q;
  
  for(ll i = 0; i < q; i++){
    ll t;
    cin >> t;
    ret += min(1l,upper_bound(S.begin(), S.end(), t) - lower_bound(S.begin(), S.end(), t));
  }
  cout << ret << endl;
}

Measured memory_bytes: 3576
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>


int main(void){
    long n,k,q,i;
    scanf("%ld%ld%ld",&n,&k,&q);
    long a[q],p[n],point[n];
    for(i=0;i<q;i++){
        scanf("%ld",&a[i]);
    }
    for(i=0;i<n;i++){
        p[i]=0;
        point[i]=0;
    }
    for(i=0;i<q;i++){
        // for(j=0;j<n;j++){
        //     if(j!=a[i]-1) p[j]--; 
        // }
        p[a[i]-1]++;
    }
    for(i=0;i<n;i++){
        point[i]=k-q+p[i];
        if(point[i]>0) printf("Yes\n");
        if(point[i]<=0) printf("No\n");
        // printf("%ld",point[i]);
    }
    // printf("\n");
    return 0;
}


Measured memory_bytes: 2944
#include <stdio.h>
#include <string.h>
int main(){
  char s[100001];
  int f=0;
  scanf("%s",&s);
  for(int i=strlen(s)-1;i>0;i--){
    if(s[i]=='m'){//dream
      if(s[i--]=='m'&&s[i--]=='a'&&s[i--]=='e'&&s[i--]=='r'&&s[i]=='d')f=1;  
      else f=0;
     }
    else if(s[i]=='e'){//erase
      if(s[i--]=='e'&&s[i--]=='s'&&s[i--]=='a'&&s[i--]=='r'&&s[i]=='e')f=1; 
      else f=0;
     }
    else if(s[i]=='r'&&s[i-5]=='e'){//eraser 
      if(s[i--]=='r'&&s[i--]=='e'&&s[i--]=='s'&&s[i--]=='a'&&s[i--]=='r'&&s[i]=='e') f=1;
      else f=0;
      }
    else if(s[i]=='r'&&s[i-6]=='d'){//dreamer
      if(s[i--]=='r'&&s[i--]=='e'&&s[i--]=='m'&&s[i--]=='a'&&s[i--]=='e'&&s[i--]=='r'&&s[i]=='d') f=1;
      else f=0;
      }
    if(f==0) break;
  }
 if(f==1) printf("YES\n");
 else printf("NO\n");
 return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <climits>
using namespace std;
#define	int long long
const int INF=1e18;
const int MAX_V=2000;
int v,g[MAX_V][MAX_V],r;
void warshall(){
  for(int k=0;k<v;k++)
    for(int i=0;i<v;i++)
      for(int j=0;j<v;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
signed main(){
  int e;
  cin>>v>>e;
  for(int i=0;i<v;i++) for(int j=0;j<v;j++) g[i][j]=i==j?0:INF;
  for(int i=0,a,b,c;i<e&&cin>>a>>b>>c;i++) g[a][b]=c;
  warshall();
  //for(int i=0;i<v;i++) for(int j=0;j<v;j++) if(INF/2<g[i][j]&&g[i][j]<INF) r++;                                              
  for(int i=0;i<v;i++) if(g[i][i]) r++;
  if(r){
    cout<<"NEGATIVE CYCLE"<<endl;
    return 0;
  }
  for(int i=0;i<v;i++){
    for(int j=0;j<v;j++){
      if(j) cout<<" ";
      if(g[i][j]>=INF/2) cout<<"INF";
      else cout<<g[i][j];
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3560
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<map>
#include<vector>

using namespace std;


#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define MOD 1000000007

#define IMIN INT_MIN;
#define IMAX INT_MAX;


int main(){
    int N, M;
    cin >> N >> M;
    vector<int> s(M), c(M);
    vector<int> ans(N, -1);
    rep(i, M) {
        cin >> s[i] >> c[i];
        if (ans[s[i]-1] != -1 && ans[s[i]-1] != c[i]) {
            cout << -1 << endl;
            exit(0);
        }
        ans[s[i]-1] = c[i];
    }
    //rep(i, N) cout << ans[i] << endl;
    // check if front
    if (N == 3) {
        if (ans[0] == -1) ans[0] = 1;
        else if (ans[0] == 0) {
            cout << -1 << endl;
            exit(0);
        }
    }
    if (N == 2) {
        if (ans[0] == -1) ans[0] = 1;
        else if (ans[0] == 0) {
            cout << -1 << endl;
            exit(0);
        }
    }
    int a = 0;
    rep(i, N) {
        if (ans[i] != -1) a += ans[i];
        a *= 10;
    }
    cout << a / 10 << endl;



	return 0;
}


Measured memory_bytes: 256
n,m = input().split()
n = int(n)
m = int(m)

data = []
for i in range(n):
	data.append(list(map(int, input().split())))

ans = [0 for i in range(m)]
for i in range(n):
	for j in range(data[i][0]):
		ans[data[i][j+1] - 1] += 1

count = 0
for a in ans:
	if a == n:
		count += 1
print(count)


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


int main(){
  vector<int> a(3);
  for(int i=0;i<3;i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  reverse( a.begin(),a.end() );
  int ans = 0;
  if( abs( a.at(1) - a.at(0) ) < abs( a.at(2) - a.at(0) ) ){
    ans += abs( a.at(1) - a.at(0) );
    ans += abs( a.at(2) - a.at(1) );
    cout << ans << endl;
  }else{ 
	ans += abs( a.at(2) - a.at(0) );
    ans += abs( a.at(1) - a.at(2) );
    cout << ans << endl;
  }
  
  return 0;
        
        
       
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=55,INF=1<<30;

ll dp[MAX][MAX][MAX*MAX+3000];

int main(){
    
    int N,K;cin>>N>>K;
    
    dp[0][0][0]=1;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=N*N;k++){
                if((i-j)*2>=2){
                    dp[i+1][j+2][k+2*(i-j)-2]+=dp[i][j][k]*(i-j)*(i-j);
                    dp[i+1][j+2][k+2*(i-j)-2]%=mod;
                }
                
                if((i-j)*2>=0){
                    dp[i+1][j+1][k+2*(i-j)]+=2*dp[i][j][k]*(i-j);
                    dp[i+1][j+1][k+2*(i-j)]%=mod;
                }
                
                dp[i+1][j][k+2*(i-j)+2]+=dp[i][j][k];
                dp[i+1][j][k+2*(i-j)+2]%=mod;
                
                dp[i+1][j+1][k+2*(i-j)]+=dp[i][j][k];
                dp[i+1][j+1][k+2*(i-j)]%=mod;
            }
        }
    }
    
    cout<<dp[N][N][K]<<endl;
}


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

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> h(n);

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    int cnt = 0;
    int max = 0;
    for (int i = 0; i < n; ++i) {
        if (i != n-1 && h[i] >= h[i+1]) {
            ++cnt;
            continue;
        }
        max = (max < cnt) ? cnt : max;
        cnt = 0;
    }

    cout << max << endl;

    return 0;
}
        

Measured memory_bytes: 640
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


N =  int(sys.stdin.readline())
K =  int(sys.stdin.readline())

ans = 1
for _ in range(N):
    ans = min(ans * 2, ans + K)
print(ans)

Measured memory_bytes: 64876
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>

#define Mkp make_pair

using namespace std;

typedef long long LL;

const int N = 200005;

int n;
int a[N];
LL s[N], ans = (LL)1e18;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
  for (int i = 2; i < n - 1; ++i) {
    int l1 = 0, r1 = i;
    for (int md; l1 < r1; ) {
      md = (l1 + r1) >> 1;
      if (s[md] < s[i] - s[md]) {
        l1 = md + 1;
      } else {
        r1 = md;
      }
    }
    int l2 = i, r2 = n;
    for (int md; l2 < r2; ) {
      md = (l2 + r2) >> 1;
      if (s[md] - s[i] < s[n] - s[md]) {
        l2 = md + 1;
      } else {
        r2 = md;
      }
    }
    vector<pair<LL, LL> > a;
    vector<pair<LL, LL> > b;
    if (l1 < i) a.push_back(Mkp(s[l1], s[i] - s[l1]));
    if (l1 > 1) --l1, a.push_back(Mkp(s[l1], s[i] - s[l1]));
    if (l2 < n) b.push_back(Mkp(s[l2] - s[i], s[n] - s[l2]));
    if (l2 > i + 1) --l2, b.push_back(Mkp(s[l2] - s[i], s[n] - s[l2]));
    for (auto p : a) {
      for (auto q : b) {
        LL a1 = max(max(p.first, p.second), max(q.first, q.second));
        LL a2 = min(min(p.first, p.second), min(q.first, q.second));
        ans = min(ans, a1 - a2);
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    constexpr i64 mod = 1000000007;
    i64 n, k;
    std::cin >> n >> k;

    i64 s = 0;
    while (k <= n + 1) {
        s = (s + ((2 * n - k + 1) * k / 2 - (k - 1) * k / 2 + 1) % mod) % mod;
        k++;
    }

    std::cout << s << std::endl;

    return 0;
}


Measured memory_bytes: 3632
#pragma region RegionDefs
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "boost/multi_array.hpp"
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define all(x) begin(x),end(x)
using namespace std;
template<class T=int> using P  = pair<T, T>;
template<class T=int> using V  = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
//時間が厳しいとき使う
#define INI(...) int __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
template<class T>bool chmax(T &a, const T &b) {if (a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#pragma endregion RegionDefs

void solve()
{
    IN(h, n);
    rep(i, n)
    {
        IN(a);
        h -= a;
    }
    cout << (h <= 0 ? "Yes" : "No") << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int generate(int x,int a,int b,int c){
    return (a*x+b)%c;
}

int main(void){
    int n,a,b,c,x,sum,i,line[100];
    for(;sum=0,scanf("%d %d %d %d %d",&n,&a,&b,&c,&x),n;){
        for(i=0;i<n;i++)
            scanf("%d",&line[i]);
        i=0;
        while(sum <= 10000){
           if(line[i] == x){
               i++;
           }
            if(i == n)
                break;
            sum++;
            x=generate(x,a,b,c);
        }
        if(i  != n)
            printf("-1\n");
        else
            printf("%d\n",sum);
    }
    return 0;
}

Measured memory_bytes: 612
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int inf=0x7fffffff;
const int mod=1e9+7;
const int eps=1e-6;
typedef long long ll;
typedef unsigned long long ull;
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
int st[N][N];
signed main()
{
    IOS;
    int x;
    cin>>x;
    cout<<x/500*1000+(x%500)/5*5<<endl;
}


Measured memory_bytes: 256
// finish date: 2018/01/11
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>

#define bigmod 1000000007
using namespace std;

#define FOR(i, a, b) for(int i=a;i<b;i++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long

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

int factorial(int n) {
    int ans = 1;
    FOR(i, 1, n + 1) {
        ans = ans * i;
    }
    return ans;
}

int main() {
    int W, a, b;
    cin >> W >> a >> b;
    int ans = 0;
    bool con1, con2, con3;
    con1 = a <= b && b <= a + W;
    con2 = a <= b + W && b + W <= a + W;
    con3 = b <= a && a <= b + W;
    if (con1 || con2 || con3) ans = 0;
    else ans = abs(a - b) - W;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		String a = sc.next();
		String b = sc.next();
		
		// 計算
		String result = "D";
		if(a.equals(b)) result = "H";
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}



Measured memory_bytes: 21076
#include <iostream>
#include <string>
#include <set>
using namespace std;

int main() {
    int n;
    int a[200];
    int b[200];
    int c[60];
    int mc;
    cin >> n;
    ///for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n-1;i++) cin >> b[i];
    ///for(int i=0;i<n-1;i++) cin >> c[i];
    
    int sum = b[0];
    for(int j=1;j<n-1;j++){
        if(b[j] > b[j-1]) sum = sum + b[j-1];
        else sum = sum + b[j];
    }
    sum = sum + b[n-2];
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k,r,s,p;
  string t;
  cin >> n >> k >> r >> s >> p >> t;
  int ans=0;
  for(int i=0;i<n;i++){
    if(i>=k && t[i]==t[i-k]){t[i]='k';continue;}
    ans+=t[i]=='r'?p:t[i]=='s'?r:s;
  }
  cout << ans << endl;
}
   
    

Measured memory_bytes: 3764
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int H = sc.nextInt();
            int W = sc.nextInt();
            if (H == 0 && W == 0) {
                break;
            } else{
                for (int i=0;i < H ; i++){
                    for(int j=0;j < W ; j++){
                        if (i == 0|| j == 0 || i == H-1 || j == W-1){
                            System.out.print("#");
                            }else{
                            System.out.print(".");
                        }
                        }
                    System.out.println( );
                    }
                }
            System.out.println( );
            }
        }
    }


Measured memory_bytes: 34548
#include <iostream>
using namespace std;
int main(void){
int a,b,c,d,n,i,s=0;
cin>>a>>b;
cin>>n;
for(i=0;i<n;i++){
    cin>>c>>d;
    if(c<b&&a<d)
    s=1;
}
cout<<s<<endl;
          return 0;
}
 


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

int main(){

	int bh, bm, ah;
	int am, total, si;

	cin >> bh >> bm >> ah >> am >> si;
	total = ((ah * 60) + am) - ((bh * 60) + bm);
	total = total - si;
	if(total > 0)
		cout << total << endl;
	else
		cout << "0" << endl;



	return 0;
}

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

int maximum;

int main() {
  string s;
  cin >> s;
  vector<int> v(s.size(), 0);
  rep (i, s.size()) {
    if (s.at(i) == 'A' || s.at(i) == 'T' || s.at(i) == 'G' || s.at(i) == 'C') {
        if (i != 0) v.at(i) = v.at(i - 1) + 1;
        if (i == 0) v.at(i) = 1;
    }
  }
  rep (i, s.size()) {
    maximum = max(maximum, v.at(i));
  }
  cout << maximum << endl;
  return 0;
}


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

using namespace std;

int main() {
	vector<int> g1{1,3,5,7,8,10,12}, g2{4,6,9,11}, g3{2};
	vector<vector<int>> group{g1, g2, g3};
	int x, y;
	cin >> x >> y;
	for(auto g : group) {
		bool include_x = find(g.begin(), g.end(), x) != g.end();
		bool include_y = find(g.begin(), g.end(), y) != g.end();
		if(include_x && include_y) {
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
	return 0;
}


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

#define y1 dmytxdy
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n;
int ans[505][505];

int main(){
	n=readint();
	if(n==1) return printf("1\n1\n"),0;
	int k;
	if(n&1){
		k=(n+1)/2;
		if(k&1) k++;
		for(int i=1;i<=k;i++){
			for(int j=1;j<=k;j++){
				if(i&1) ans[i][j]=(i+j)%k+1;
				else ans[i][j]=(i+j)%k+1+k;
			}
		}
		for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) if(ans[i][j]>n) ans[i][j]-=k;
	}
	else{
		k=n/2;
		if(k&1) k++;
		for(int i=1;i<=k;i++){
			for(int j=1;j<=k;j++){
				if(i&1) ans[i][j]=(i+j)%k+1;
				else ans[i][j]=(i+j)%k+1+k;
			}
		}
		for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) if(ans[i][j]>n) ans[i][j]-=k;
	}
	printf("%d\n",k);
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++) printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 2176
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	N, _ := strconv.Atoi(sc.Text())

	sc.Scan()
	M, _ := strconv.Atoi(sc.Text())

	maps := make([][]bool, N)
	for i := 0; i < N; i++ {
		maps[i] = make([]bool, N)
	}

	for i := 0; i < M; i++ {
		sc.Scan()
		a, _ := strconv.Atoi(sc.Text())

		sc.Scan()
		b, _ := strconv.Atoi(sc.Text())

		maps[a-1][b-1] = true
		maps[b-1][a-1] = true
	}

	arr := make([]int, N)
	for i := 0; i < N; i++ {
		arr[i] = i
	}

	count := 0
	for _, ar := range permutate(arr) {
		ok := true
		for i := 1; i < len(ar); i++ {
			if !maps[ar[i-1]][ar[i]] {
				ok = false
				break
			}
		}

		if ok {
			count++
		}
	}

	fmt.Println(count)
}

func permutate(input []int) (res [][]int) {
	var helper func([]int, int)
	res = [][]int{}

	helper = func(arr []int, n int) {
		if n == len(arr)-1 {
			tmp := make([]int, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
		} else {
			for i := n; i < len(arr); i++ {
				tmp := arr[n]
				arr[n] = arr[i]
				arr[i] = tmp
				helper(arr, n+1)
				tmp = arr[n]
				arr[n] = arr[i]
				arr[i] = tmp
			}
		}
	}
	helper(input, 1)
	return res
}


Measured memory_bytes: 1408
A, B, C, X, Y = map(int, input().split())
if X == Y:
    if A + B < C + C:
        print(A * X + B * Y)
    else:
        print(C * X + C * Y)
elif X > Y:
    if A + B < C + C:
        print(A * X + B * Y)
    elif A < 2 * C:
        print(A * X + 2 * C * Y - A * Y)
    else:
        print(2 * C * X)
else:
    if A + B < C + C:
        print(A * X + B * Y)
    elif B < 2 * C:
        print(B * Y + 2 * C * X - B * X)
    else:
        print(2 * C * Y)

Measured memory_bytes: 3064
if __name__ == '__main__':

	n = int(input())

	for i in range(n):
		tmp = ""
		tmp2 = ""
		line = list(map(int,input()))
		ans = sorted(line)
		for j in ans:
			tmp += str(j)

		ans2 = sorted(ans,reverse=True)
		for k in ans2:
			tmp2 += str(k)

		print(int(tmp2) - int(tmp))




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

#define is_uruu main
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(a);i>(b);--i)
    
int selectionSort(int A[],int N){
	int count=0;
	FOR(i,0,N-1){
		int minj=i;
		FOR(j,i+1,N){
			if(A[minj] > A[j])minj = j;
		}
		if(minj != i){
			swap(A[i], A[minj]);
			count++;
		}
	}
    return count;
}
    
int is_uruu(){
	int N, count, A[100];
	cin >> N;
	FOR(i,0,N)cin >> A[i];
	
	count = selectionSort(A, N);
	
	FOR(i,0,N-1)cout << A[i] << " ";
	cout << A[N-1] << endl << count << endl;
	return 0;
}


Measured memory_bytes: 3136
import math
import string


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


N, M = map(int, input().split())
cs = [None]*N
for i in range(M):
    s, c = map(int, input().split())
    #print(s, c)
    if cs[(s-1)] == None:
        cs[(s-1)] = c
    elif cs[s-1] != c:
        print(-1)
        exit()


def check(x):
    s = str(x)
    if not(len(s) == N):
        return False
    for i in range(N):
        if not(cs[i] == None or cs[i] == int(s[i])):
            return False
    return True


for i in range(10000):
    if check(i):
        print(i)
        exit()
print(-1)


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

function main()
	n,q = readline() |> split |> parseMap
	s = readline() |> chomp
	t = [Int(s[i]) for i in 1:n]
	o = Tuple{Int,Char}[(0,'a') for i in 1:q]
	for i in 1:q
		a,b = split(readline())
		o[i] = (Int(a[1]),b[1])
	end
	ll = 0
	rr = n+1
	while rr-ll>1
		m = (ll+rr)>>1
		now = m
		for i in 1:q
			if now==0||now==n+1
				break
			end
			if t[now]==o[i][1]
				if o[i][2]=='L'
					now -= 1
				else
					now += 1
				end
			end
		end
		if now==0
			ll = m
		else
			rr = m
		end
	end
	l = 0
	r = n+1
	while r-l>1
		m = (l+r)>>1
		now = m
		for i in 1:q
			if now==0||now==n+1
				break
			end
			if t[now]==o[i][1]
				if o[i][2]=='L'
					now -= 1
				else
					now += 1
				end
			end
		end
		if now==n+1
			r = m
		else
			l = m
		end
	end
	println(r-ll-1)
end

main()

Measured memory_bytes: 156572
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int k=sc.nextInt();
		long ans = 0;
		for(int a=1; a<=k; a++) {
			for(int b=1; b<=k; b++) {
				for(int c=1; c<=k; c++) {
					ans += gcd(a,b,c);
				}
			}
		}
		System.out.println(ans);
		sc.close();
	}

	private long gcd(long a, long b, long c) {
		return gcd(gcd(a,b), c);
	}

	private long gcd(long a, long b) {
		if(b==0) {
			return a;
		}else {
			return gcd(b, a%b);
		}
	}
}


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 2e5 + 100;
const int LOG = 20;
const int mod = 1e9 + 7;
const int MX = 2e5 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;


dbl dp[301][301][301];
int n;

dbl get(int i1, int i2, int i3) {
    if (i1 == 0 && i2 == 0 && i3 == 0) {
        return 0;
    }
    if (dp[i1][i2][i3] > -10) {
        return dp[i1][i2][i3];
    }
    dbl p = (i1 + i2 + i3);
    p = p / n;
    p = 1 / p;

    dbl res = p;
    if (i1 > 0) {
        dbl p1 = i1;
        p1 = p1 / (i1 + i2 + i3);
        res += get(i1 - 1, i2, i3) * p1;
    }
    if (i2 > 0) {
        dbl p1 = i2;
        p1 = p1 / (i1 + i2 + i3);
        res += get(i1 + 1, i2 - 1, i3) * p1;
    }
    if (i3 > 0) {
        dbl p1 = i3;
        p1 = p1 / (i1 + i2 + i3);
        res += get(i1, i2 + 1, i3 - 1) * p1;
    }
    dp[i1][i2][i3] = res;
    dout <<i1 <<" "<<i2<<" "<<i3<<" : "<<res<<" "<<p<<endl;
    return res;
}

void solve() {
    for (int i = 0; i <= 300; ++i) {
        for (int j = 0; j <= 300; ++j) {
            fill(dp[i][j], dp[i][j] + 301, -1000);
        }
    }

    cin >> n;
    int i1 = 0, i2 = 0, i3 = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (x == 1) {
            i1++;
        } else if (x == 2) {
            i2++;
        } else {
            i3++;
        }
    }
    cout << get(i1, i2, i3) << "\n";
}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;

    while (t--)
        solve();
    dout << endl << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}


Measured memory_bytes: 426496
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int64_t, int64_t>;
constexpr int64_t kInf = INT64_MAX / 2L;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t N;
  cin >> N;
  vector<int64_t> A(N + 2, 0);
  int64_t sum = 0;
  for (int64_t i = 1; i <= N; ++i) {
    cin >> A[i];
    sum += abs(A[i] - A[i - 1]);
  }
  sum += abs(A[N]);

  for (int64_t i = 1; i <= N; ++i) {
    int64_t result = sum;
    result -= abs(A[i] - A[i - 1]);
    result -= abs(A[i] - A[i + 1]);
    result += abs(A[i - 1] - A[i + 1]);
    cout << result << endl;
  }
  return 0;
}


Measured memory_bytes: 4004
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    int min = (int)Math.pow(10, 9);
    int max = 1;
    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
      if (a[i] < min) {
        min = a[i];
      }
      if (a[i] > max) {
        max = a[i];
      }
    }
    System.out.println(max - min);
  }
}

Measured memory_bytes: 35972
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()
using namespace std;

bool canMakeRec(vector<int> ns) {
  if (ns.size() == 0) return true;
  int first = ns[0];  // どの順番に役を作っても結果は変わらないので、まず最初の数に着目する。配列はソートされているのでこれは使える数字の中で最小になる
  if (count(all(ns), first) >= 3) {  // 同じ数字が3個以上ある
    vector<int> nsNew = ns;  // 現在の数字をコピー
    rep(i,3) nsNew.erase( find(all(nsNew), first) );  // 3個消す
    if (canMakeRec(nsNew)) return true;
  }
  if (count(all(ns), first+1) > 0 && count(all(ns), first+2)) {  // 3つの連続する数字がある
    vector<int> nsNew = ns;  // 現在の数字をコピー
    rep(i,3) nsNew.erase( find(all(nsNew), first + i) );  // 3個消す
    if (canMakeRec(nsNew)) return true;
  }
  return false;
}

bool canMake(vector<int> ns) {
  sort(all(ns));
  // まず2つ組を作る
  int prev = -1;
  rep(i, ns.size()-1) {
    if (prev != ns[i] && ns[i] == ns[i+1]) {
      vector<int> nsNew = ns;  // 現在の数字をコピー
      nsNew.erase(nsNew.begin() + i);  // 2つ消す
      nsNew.erase(nsNew.begin() + i);
      if (canMakeRec(nsNew)) return true;
    }
    prev = ns[i];
  }
  return false;
}

int main() {
  string s;
  while (cin >> s) {
    vector<int> ns(14);
    vector<int> freq(10);  // freq[i]: 数iが現れた回数
    rep(i,13) {
      ns[i] = s[i] - '0';
      freq[ns[i]]++;
    }
    vector<int> ans;

    for (int i = 1; i <= 9; i++) {
      ns[13] = i;
      if (freq[i] < 4 && canMake(ns)) ans.push_back(i);
    }

    if (ans.size() == 0) cout << 0;
    else {
      cout << ans[0];
      rep(i, ans.size()-1) cout << " " << ans[i+1];
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1208
# coding: utf-8

# In[10]:

import sys
#import math
#input = sys.stdin.readline
N = int(input())


# In[13]:

sum_ = 0
#print(math.sqrt(N))
#print(int(math.sqrt(N)))
#print(int(N**0.5))
rn = N**0.5
if rn%1 == 0:
    rn -= 1
for i in range(1, int(rn)+1):
    if N%i == 0 and i < N//i-1:
        #print(i)
        #print(N/i-1)
        sum_ += N/i-1
print(int(sum_))


# In[ ]:





Measured memory_bytes: 3060
N,M = map(int,input().split())
X=[]
for i in range(M):
  p,y = map(int,input().split())
  X +=[[i,p,y,0]]
X=sorted(X,key=lambda x:x[2])
R=[0]*(N+1)
for i in range(M):
  X[i][3]=R[X[i][1]]+1
  R[X[i][1]] += 1
X=sorted(X,key=lambda x:x[0])
for i in range(M):
  id_A='0'*(6-len(str(X[i][1])))+str(X[i][1])
  id_B='0'*(6-len(str(X[i][3])))+str(X[i][3])
  print(id_A+id_B)

Measured memory_bytes: 30592
package main

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

func solution(n, k int, a []int) []int {
        c := 0
        for k > 0 && c < 100 {
                memo := make([]int, n)
                for i := 0; i < n; i++ {
                        lo := max(0, i-a[i])
                        hi := min(n-1, i+a[i])
                        memo[lo]++

                        if hi+1 < n {
                                memo[hi+1]--
                        }

                }

                for i := 1; i < n; i++ {
                        memo[i] += memo[i-1]
                }
                a = memo
                k--
                c++
        }
        return a
}

func min(x, y int) int {
        if x < y {
                return x
        }
        return y
}

func max(x, y int) int {
        if x > y {
                return x
        }
        return y
}

func main() {
        r := bufio.NewReader(os.Stdin)
        var n, k int
        fmt.Fscan(r, &n, &k)
        a := make([]int, n)
        for i := range a {
                fmt.Fscan(r, &a[i])
        }
        nums := solution(n, k, a)
        for i, num := range nums {
                if i == len(nums)-1 {
                        fmt.Println(num)
                } else {
                        fmt.Printf("%v ", num)
                }
        }
}

Measured memory_bytes: 14216
// BinarySearchTree.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
using namespace std;
int m;

struct Node {
	int key;
	Node* parent, * left, * right;
};

Node* root, * NIL;

void insert(int k)
{
	Node* y = NIL;
	Node* x = root;
	Node* z;

	z = (Node*)malloc(sizeof(Node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while (x != NIL)
	{
		y = x;
		if (z->key < x->key) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}
	z->parent = y;
	if (y == NIL) {
		root = z;
	}
	else {
		if (z->key < y->key) {
			y->left = z;
		}
		else {
			y->right = z;
		}
	}
}

void inorder(Node* u)
{
	if (u == NIL) return;
	inorder(u->left);
	printf(" %d", u->key);
	inorder(u->right);
}
void preorder(Node* u)
{
	if (u == NIL) return;
	printf(" %d", u->key);
	preorder(u->left);
	preorder(u->right);
}

Node* find(Node* x, int key)
{
	while (x != NIL && key != x->key) {
		if (key < x->key) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}
	return x;
}

int main()
{
	string cmd;
	int k;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> cmd;
		if (cmd == "insert") {
			cin >> k;
			insert(k);
		}
		else if (cmd == "find") {
			cin >> k;
			if (find(root, k) != NIL)
				printf("yes\n");
			else
				printf("no\n");
		}
		else if (cmd == "print") {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}
	return 0;
}



Measured memory_bytes: 22000