akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

// Union Find Tree
#define MAX_N 100010
struct UnionFind
{
	int par[MAX_N];
	int _rank[MAX_N];
	void init(int n)
	{
		for (int i = 0; i < n; ++i)
		{
			par[i] = i;
			_rank[i] = 0;
		}
	}
	int root(int x)
	{
		return par[x] == x ? x : par[x] = root(par[x]);
	}
	bool same(int x, int y)
	{
		return root(x) == root(y);
	}
	void unite(int x, int y)
	{
		x = root(x);
		y = root(y);
		if (x == y)
			return;
		if (_rank[x] < _rank[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (_rank[x] == _rank[y])
				++_rank[x];
		}
	}
};

int p[MAX_N];

void Main()
{
	int N, M; cin >> N >> M;
	UnionFind uf;
	uf.init(N);
	rep(i,N) {
		int _p; cin >> _p; --_p;
		p[i] = _p;
	}
	rep(i,M) {
		int x, y; cin >> x >> y;
		--x, --y;
		uf.unite(x,y);
	}
	int res = 0;
	rep(i,N) {
		if (i == p[i]) {
			++res;
			continue;
		}
		if (uf.same(i,p[i])) ++res;
	}
	cout << res << endl;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 1408
#include<cstdio>
#include<cstring>
char s[200005];
int f[200005];
int next[200005][27];
int pos[27];
char t[200005];

void preWork(int n){
    for(int i = 0; i < 26; i++) pos[i] = -1;
    for(int i = n; i >= 0; i--){
        for(int j = 0; j < 26; j++) next[i][j] = pos[j];
        if(i!=0) pos[s[i]-'a'] = i;
    }
}

int min(int a,int b){ return a>b?b:a; }

void getAnswer(int p,int size){
    if(f[p]==0){
        int find = -1;
        for(int i = 0; i < 26; i++){
            if(next[p][i]==-1){
                find = i;
                break;
            }
        }
        t[size] = find+'a';
    }
    else{
        int find = -1;
        for(int i = 0; i < 26; i++){
            int np = next[p][i];
            if(f[np]+1==f[p]){
                find = i;
                break;
            }
        }
        t[size] = find+'a';
        getAnswer(next[p][find],size+1);
    }
}

int main(){
    scanf("%s",s+1);
    int n = strlen(s+1);
    preWork(n);
    for(int i = n; i >= 0; i--){
        int ok = 1, minn = 1e7+7;
        for(int j = 0; j < 26; j++){
            if(next[i][j]==-1){
                ok = 0;
                break;
            }
            else minn = min(minn,f[next[i][j]]);
        }
        if(!ok) f[i] = 0;
        else f[i] = minn+1;
    }
    int ans = f[0]+1;
    //printf("%d\n",ans);
    getAnswer(0,1);
    for(int i = 1; i <= ans; i++) printf("%c",t[i]);
    printf("\n");
    return 0;
}


Measured memory_bytes: 23736
#include <iostream>
    using namespace std;
     
    int main()
    {
      int a,b,c,d,e,f;
      cin>>a>>b>>c>>d;
      
      e=a*b;
      f=c*d;
      
      if(e==f)
      cout<<e;
      else{
        if(e>f)
        cout<<e;
        if(e<f)
        cout<<f;
      }
      
    } 

Measured memory_bytes: 3584
import collections

N,M = map(int,input().split())
H = [int(h) for h in input().split()]
l = []
for m in range(M):
    a,b = map(int,input().split())
    if H[a-1] > H[b-1]:
        l.append(b)
    elif H[a-1] < H[b-1]:
        l.append(a)
    else:
        l.append(a)
        l.append(b)

print(N-len(collections.Counter(l)))

Measured memory_bytes: 90376
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[505][505];
long long b[505][505],c[505][505],f[505][505];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)if(j!=i)scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++)b[i][j]=b[i][j-1]+a[i][j];
		for(int j=n;j>=i;j--)c[i][j]=c[i][j+1]+a[j][i];
	}
	for(int j=1;j<=n;j++){
		for(int i=1;i<=j;i++)c[i][j]+=c[i-1][j];
		for(int i=j;i>=1;i--)b[i][j]+=b[i+1][j];
	}
	/*
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			for(int x=1;x<=n;x++)
				for(int y=1;y<=n;y++)
					if(x<y){
						if(x>=i&&y<=j)b[i][j]+=a[x][y];
					}else if(x>y){
						if(x>=j&&y<=i)c[i][j]+=a[x][y];
					}
		}
	*/
	/*
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++)printf("%lld ",b[i][j]);
		puts("");
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++)printf("%lld ",c[i][j]);
		puts("");
	}
	*/
	memset(f,63,sizeof(f));
	for(int i=2;i<=n;i++)f[i][1]=b[1][i-1]+c[0][i];
	for(int i=3;i<=n+1;i++)
		for(int j=2;j<i;j++)
			for(int k=1;k<j;k++)
				f[i][j]=min(f[i][j],f[j][k]+c[j-1][i]-c[k-1][i]+b[j][i-1]);
	long long ans=1e18;
	for(int i=1;i<=n;i++)ans=min(ans,f[n+1][i]);
	printf("%lld\n",ans);
	return 0;
}

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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	long N;
	cin >>N;
	vector<long> A(N, 0);
	long S=0;
	for (long i=0; i<N; i++) {
		cin >>A.at(i);
		S +=A.at(i);
	}
	long D=S;
	for (long i=0, SS=0; i<N; i++) {
		SS +=A.at(i);
		D=min(D, abs(S-SS-SS));
	}
	cout <<D <<endl;
	return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include <algorithm>
#include<string>
#include<math.h>
#include <functional>
using namespace std;

int main(void) {
	string s;
	int ans = 0;
	cin >> s ;
	for (int i = 0;i < 4;i++) {
		if (s[i] == '+')
			ans++;
		else
			ans--;
	}
	cout << ans << endl;


	return 0;
}


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

using namespace std;

int n;

bool primes[101];
int factor[101];

int main(){
    cin >> n;

    for (int i = 0; i < 101; ++i) {
        primes[i] = true;
        factor[i] = 0;
    }

    primes[0] = false;
    primes[1] = false;
    for (int i = 2; i < 101; ++i) {
        if (primes[i]) {
            for (int k = i + i; k < 101; k += i) {
                primes[k] = false;
            }
        }
    }
    for (int k = 2; k <= n; ++k) {
        for (int i = 2; i <= k; ++i) {
            if (!primes[i]) continue;
            int cnt = 0;
            int t = k;
            while (t % i == 0) {
                t /= i;
                cnt++;
            }
            factor[i] += cnt;
        }
    }
    int ans = 0;
    int ans3 = 0;
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= n; j++) {
            for (int k = 2; k <= n; k++) {
                if (i == j || j == k || i == k) continue;
                if (factor[i] >= 2 && factor[j] >= 4 && factor[k] >= 4) ans3++;
            }
            if (i != j) {
                if (factor[i] >= 14 && factor[j] >= 4) ans++;
                if (factor[i] >= 24 && factor[j] >= 2) ans++;
            }
        }
        if (factor[i] >= 74) ans++;
    }
    cout << ans + ans3 / 2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<int,int> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
	int x,a;
	cin>>x>>a;
	if(x<a)cout<<0<<endl;
	else cout<<10<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

using namespace std;

int map[20][20];
int d[20][20];
int memo[20][20];
int w,h;
int saiki(int y,int x);

int main(){
  int kouzisuu;
  int a,b,ans;
  while(1){
    cin>>w>>h;
    if(!w && !h)break;
    for(int i=0;i<=h;i++){
      for(int j=0;j<=w;j++){
	map[i][j]=0;
	d[i][j]=0;
	memo[i][j]=0;
      }
    }
    cin>>kouzisuu;
    while(kouzisuu--){
      cin>>a>>b;
      d[b][a]=1;
    }
    memo[1][1]=1;
    ans=saiki(h,w);
    cout<<ans<<endl;
  }
}
int saiki(int y,int x){
  if(d[y][x]==1 || y<0 || x<0)return 0;
  if(memo[y][x]){
    return memo[y][x];
  }
  return memo[y][x]=map[y][x]=saiki(y,x-1)+saiki(y-1,x);
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

int main() {
  i64 n;
  cin >> n;
  if (n % 10 == n / 100) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}


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

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,k;
	cin>>n;
	vector<int> h(n),dp(n);
	for(int i=0;i<n;i++){
		cin>>h[i];
		dp[i]=0;
	}
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	for(int i=2;i<n;i++){
		dp[i]=min(abs(h[i]-h[i-1])+dp[i-1],abs(h[i]-h[i-2])+dp[i-2]);
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
 
int main() {

    ll n,m;
    cin>>n>>m;
    vector<ll> a(n);
    vector<ll> b(n);
    rep(i,n)    cin>>a[i]>>b[i];

    vector<pair<ll,ll>> c(n);
    rep(i,n) {
        c[i]=MP(a[i],b[i]);
    }
    sort(all(c));
    ll ans=0;
    rep(i,n) {
        if(m<=c[i].second) {
            ans+=m*c[i].first;
            break;
        }
        else {
            m-=c[i].second;
            ans+=(c[i].first*c[i].second);
        }
    }

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

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

using namespace std;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

// Aliases
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef string str;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// Constant variables
const long double PI = (acos(-1));
const long long MOD = 1000000007;

// I/O Asynchronizing
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

int main() {
    int r;
    cin >> r;
    cout << (r * r) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k,ans=(1<<30);
  cin >> n >> k;
  vector<int> h(n);
  for(int i=0;i<n;i++)cin >> h[i];
  sort(h.begin(),h.end());
  for(int i=0;i<n-k+1;i++)ans=min(ans,h[i+k-1]-h[i]);
  cout << ans << endl;
}  

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

#define max 100

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}

int main()
{
    int n, a, b, c;
    
    scanf("%d %d %d", &n, &a, &b);
    
    printf("%d", (int)fmin(n*a, b));
    
    return 0;
}




Measured memory_bytes: 128
n,m,l = map(int,input().split())

array_a=[]
array_b=[]
array_c=[[0 for i in range(l)] for j in range(n)]

for i in range(n):
	array_a.append(list(map(int,input().split())))

for j in range(m):
	array_b.append(list(map(int,input().split())))


for i in range(n):
	for j in range(m):
		for k in range(l):
			array_c[i][k]+=array_a[i][j] * array_b[j][k]
	print(" ".join(map(str,array_c[i])))
	
	





Measured memory_bytes: 6916
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  int a, b;
  cin >> a >> b;
  if(a == 1) a = 14;
  if(b == 1) b = 14;
  if(a > b) cout << "Alice" << endl;
  else if(a < b) cout << "Bob" << endl;
  else cout << "Draw" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public 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];
        for (int i = 0 ; i < n ; i++) {
            l[i] = sc.nextInt();
        }
        int[] d = new int[n + 1];
        for (int i = 1 ; i < n + 1 ; i++ ) {
            d[i] = d[i - 1] + l[i - 1];
            if (d[i] > x) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(n + 1);
    }

}


Measured memory_bytes: 23764
#include<cstdio>
#include<iostream>
using namespace std;
int main() {
	string str;
	cin >> str;
	int flg = 0;
	if(str.size() > 5) flg = 1;
	for(int i = 0; i < str.size(); i++) {
		if(str[i] >= '0' && str[i] <= '9') flg |= 2;
		if(str[i] >= 'A' && str[i] <= 'Z') flg |= 4;
		if(str[i] >= 'a' && str[i] <= 'z') flg |= 8;
	}
	if(flg == 15) puts("VALID");
	else puts("INVALID");
	return 0;
}

Measured memory_bytes: 1156
N = int(input())
A = list(map(int,input().split()))

cnt = 0
for i in range(len(A)):
    if i==0:
        continue

    if A[i-1]-A[i]>0:
        cnt +=A[i-1]-A[i]
        A[i]=A[i-1]

print(cnt)

Measured memory_bytes: 32224
// https://atcoder.jp/contests/abc134/tasks/abc134_e

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

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define EPS (1e-9)
#define INF (1e9)
#define INFL (1e18)
#define MOD (1000000007)
#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))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define LEN(x) (sizeof(x) / sizeof(*(x)))
// ll gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// ll lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, t;
    //差分が小さくなるように重ねる
    cin >> n;
    multiset<int> mp;
    REP(i, n) {
        cin >> t;
        auto it = mp.upper_bound(-t);
        // int itv = *it;
        int mpsize = mp.size();
        if (it != mp.end()) {
            mp.erase(it);
            mp.insert(-t);
        } else {
            mp.insert(-t);
        }
    }
    cout << mp.size() << endl;

    return 0;
}


Measured memory_bytes: 4992
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

int main()
{
	int a,b;
	while(cin>>a>>b){
		if (a<b) cout<<"0"<<endl;
		else{
			cout<<a-b<<endl;
		}
	}
	return 0;
}


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

int main() {
	while(true){
		int n;
		cin>>n;
		if(n==0) return 0;
		vector<int>v(n);
		for(int i=0;i<n;i++){
			cin>>v[i];
		}
		int sum=0;
		for(int i=0;i<n;i++){
			sum+=v[i];
		}
		sort(v.begin(),v.end());
		cout<<(sum-v[0]-v[n-1])/(n-2)<<endl;
	}
	return 0;
}


Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
typedef long long           ll;
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}

ll max(ll a, ll b) {return (a > b ? a : b);}
ll min(ll a, ll b) {return (a < b ? a : b);}
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};
void yes_or_no(ll x) {
  if (x) cout << "YES\n"; else cout << "NO\n";
}
void solve_test() {
  ll ans = 0;
  ll n;
  cin>>ans; 
  ans^=1;
  cout << ans << "\n";
}
int main()
{
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
// cin >> t; while (t--)
  solve_test();
  return 0;
}


Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int x = 0;
		int max = x;
		int n = scan.nextInt();
		char[] c = scan.next().toCharArray();
		for (int i = 0; i < n; i++) {
			if (c[i] == 'I') {
				x++;
				if (x > max) {
					max = x;
				}
			}
			if (c[i] == 'D') {
				x--;
			}
		}
		System.out.println(max);
	}
}


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

int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if(a+b>c+d){
		cout << "Left" << endl;
	}else if(a+b==c+d){
		cout << "Balanced" << endl;
	}else{
		cout << "Right" << endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);

		while (true) {
			String A = sc.next();
			if (A.equals("0")) {
				break;
			}
			char X[] = A.toCharArray();
			int sum =0;
			for (int i=0; i<X.length; i++) {
			sum += X[i] - '0';
			}
			System.out.println(sum);
		}
	}
}



Measured memory_bytes: 26280
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mod 1000000007
#define inf 1e18
#define PI 3.14159265358979323846264338327950L
#define w(x) int x; cin>>x; while(x--)
using namespace std;
bool sieve[2000006];
void sieve_make() 
{
	memset(sieve,true,sizeof(sieve));
	sieve[0]=sieve[1]=false;
	for(int i=2;i*i<2000006;i++)
	{
		if(sieve[i])
		{
			for(int j=i*i;j<2000006;j+=i)
				sieve[j]=false;
		}
	}
}

int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
int modexp(int a,int b,int c)
{
	if(a==0) return 0;
	if(b==0) return 1;

	int ans;
	if(b%2==0)
	{
		int small=modexp(a,b/2,c);
		ans=(small*small)%c;
	}
	else
	{
		int small=modexp(a,b-1,c);
		ans=(a%c);
		ans=(small*ans)%c;
	}
	return (ans+c)%c;
}
bool sign(int x)
{
	if(x>0)
		return true;
	return false;
}
int kadane(int* a,int n)
{
	int loc=a[0],glo=a[0];
	for(int i=1;i<n;i++)
	{
		loc=max(a[i],loc+a[i]);
		glo=max(glo,loc);
	}
	return glo;
}

int dp[100005];
int dfs(vector<int>* adj,int sv,bool col,bool* vis,int n)
{
	if(sv==n-1)
		return 1;
	
	int ans=0;
	for(auto i:adj[sv])
	{
		if(!vis[i])
		{
			vis[i]=1;
			if(col)
				ans+=dfs(adj,i,!col,vis,n);
			else
				ans+=dfs(adj,i,!col,vis,n)+dfs(adj,i,col,vis,n);
			vis[i]=0;
		}
	}
	return ans;
}

int32_t main()
{
	ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
	
	
	
	
	int n;
	cin>>n;
	bool ok=0;
	int cnt=0;
	while(n--)
	{
		int x,y;
		cin>>x>>y;
		if(x==y)
			cnt++;
		else
			cnt=0;
		if(cnt==3)
			ok=1;
	}

	if(ok)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	
}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin>>a>>b;
  int diff=b-a;
    int sum;
  for(int i=1;i<diff;i++){
      sum+=i;
  }
  int ans=sum-a;
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <stack>
#include <regex>

#define mod 1000000007
#define INF2 9999999999
#define INF (1<<30)
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)
#define P pair<int, int>

using namespace std;
using ll = int64_t;

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

void solve(){
    string s, t;
    cin >> s >> t;

    for(int i = 0; i < s.length(); i++){
        s = s.substr(1, s.length()-1)+s[0];
        if(s == t){
            cout << "Yes" << endl;
            return ;
        }
    }
    cout << "No" << endl;
}

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <functional>
#include <set>
#define DB cerr<<"D"<<endl
#define pb push_back
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";}
using P=pair<double,int>;
const ll M = 998244353;
void add(ll& x, ll y) {x+=y; x%=M;}
void chmax(ll& x, ll y) {if (x<y) x=y;}
const int up[]={1,-1,0,0}, lf[]={0,0,1,-1};
bool vaild(int x, int y, int hh, int ww){return 0<=x&&x<hh&&0<=y&&y<ww;}

int main() {
  int a,b; cin>>a>>b;
  char ch='x';
  if (a+b==15) ch='+';
  if (a*b==15) ch='*';
  cout<<ch<<endl;
}

Measured memory_bytes: 256
import math
def digsum(A):
  n = math.floor(math.log10(A))
  tmp = 0
  for i in range(n,0,-1):
    tmp += A // (10**i)
    A = A % (10**i)
  return tmp + A
  
N = int(input())
ans = 10**9
for i in range(1,N//2+1):
  ans = min(ans, digsum(i) + digsum(N-i))
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	int a,b,c;
	cin >> a >> b >> c;
	bool poor = false;
	if(a==b){
		if(a!=c)poor = true;
	}
	else if(b==c){
		if(b!=a)poor = true;
	}
	else if(a==c){
		if(a!=b)poor = true;
	}
	if(poor) cout <<"Yes\n";
	else cout <<"No\n";
	return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

#define MAXXY 1000001
ll facs[MAXXY*2+1];

// x^n in mod
ll modpow(ll x, ll n, ll mod){
  if(n==0) return 1;

  if(n%2==0){
    return modpow(x*x%mod, n/2, mod) % mod;
  }else{
    return x * modpow(x, (n-1), mod) % mod;
  }
}

// n! in mod
ll fac(ll n){
  return facs[n];
}

// nCr in mod
ll comb(ll n, ll r){
  if(n<0 || n<r || r<0)return 0;
  ll fn = fac(n);
  ll fr = fac(r);
  ll fn_r = fac(n-r);
  
  ll d = (modpow(fr, MOD-2, MOD) * modpow(fn_r, MOD-2, MOD)) % MOD;
  ll u = fn%MOD;
  
  ll result = u * d % MOD;
 
  return result;
}

int main(){
  ll x,y;cin>>x>>y;
  ll total = (x+y)/3;
  facs[0]=1;
  rep(i, total+1)facs[i+1] = (facs[i]*(i+1))%MOD;
  if((x+y)%3){ cout<<0<<endl; return 0; }

  ll s = (2*x-y)/3;
//  ll t = (2*y-x)/3;

  cout<<comb(total, s)<<endl;

  return 0;
}



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

ll solve() {
    ll N, A, B;
    cin >> N >> A >> B;
    string S;
    cin >> S;
    ll nab = 0, nb = 0;
    vector<int> ans;
    for ( char c : S ) {
        int ok = 0;
        if ( c == 'a' ) {
            if ( nab < A+B ) ok = 1;
        } else if ( c == 'b' ) {
            if ( nab < A+B && nb < B ) ok = 1;
            nb++;
        }
        if ( ok == 1 ) {
            nab++;
        }
        ans.push_back(ok);
    };

    for ( int i = 0; i < ans.size(); i++ ) {
        string x = ans[i] ? "Yes" : "No";
        cout << x << "\n";
    }    
    return 0;
}

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

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

using namespace std;

#define fi first
#define se second

int main()
{
    int n, d=1, k;
    cin >> n;
    long long A[n], S1[n+1], S2[n+1], r;
    vector <long long> V1, V2, R;
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    while (V1.size() < n)
    {
        V1.push_back(A[d]);
        d += 2;
        d %= n;
    }
    d = 0;
    while (V2.size() < n)
    {
        V2.push_back(A[d]);
        d += 2;
        d %= n;
    }
    S1[0] = 0;
    S2[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        S1[i] = S1[i-1] + V1[i-1];
        S2[i] = S2[i-1] + V2[i-1];
    }
    r = S1[n];
    k = n / 2;
    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            R.push_back(r - 2*(S2[i/2+k+1] - S2[i/2+1]));
        }
        else
        {
            R.push_back(r - 2*(S1[i/2+k+1] - S1[i/2+1]));
        }
    }
    cout << R[n-1] << " ";
    for (int i = 0; i < n-1; i++)
    {
        cout << R[i] << " ";
    }
    return 0;
}


Measured memory_bytes: 6132
def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res
from fractions import gcd
a, b = map(int, input().split())
print(len(set(prime_factorize(gcd(a, b))))+1)

Measured memory_bytes: 5560
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ZERO(a) memset(a,0,sizeof(a))

bool s[14], h[14], c[14], d[14];

void init_card() {
    ZERO(s); ZERO(h); ZERO(c); ZERO(d);
}

int main() {
    init_card();
    int n;
    cin >> n;
    rep(i,n) {
        char p;
        int a;
        cin >> p >> a;
        if(p=='S') s[a] = true;
        if(p=='H') h[a] = true;
        if(p=='C') c[a] = true;
        if(p=='D') d[a] = true;
    }
    
    FOR(i,1,14) if(!s[i]) printf("S %d\n", i);
    FOR(i,1,14) if(!h[i]) printf("H %d\n", i);
    FOR(i,1,14) if(!c[i]) printf("C %d\n", i);
    FOR(i,1,14) if(!d[i]) printf("D %d\n", i);

    return 0;
}

Measured memory_bytes: 1144
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vll vector<ll>
#define pll pair<ll,ll>
#define vp vector<pll>
#define test int tcase; cin>>tcase; for(int tc = 1; tc <= tcase; tc++)
#define inp(a,n,f) ll a[n+f];for(ll hh=f;hh<n+f;hh++)cin>>a[hh];
#define printdecimal(k) cout<<fixed<<setprecision(k);
#define ub upper_bound
#define lb lower_bound
#define mapp map<ll,ll>
#define mem(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(),v.end()
#define qll queue<ll>
#define sll set<ll>
#define inf LLONG_MAX
#define fileio freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout)
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}


signed main()
{
    fastio;
    //fileio;
	ll n,i,k,j;
	cin>>n>>k;
	inp(a,n,0);
	ll dp[n];
	for(i=2;i<n;i++)
		dp[i]=inf;		
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	for(i=2;i<n;i++)
		for(j=max(0LL,i-k);j<i;++j)
			dp[i]=min(dp[j]+abs(a[i]-a[j]),dp[i]);
	cout<<dp[n-1];
}

Measured memory_bytes: 1792
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int n, a[100000], to[100000], s[100000], m;
bool v[100000];

int rec(int c){
	if(to[c] >= 0) return to[c];
	if(a[c] == 0) return to[c] = c;
	if(v[c]){
		rep(i, m) to[s[i]] = -1;
		return to[c] = -1;
	}
	s[m++] = c;
	v[c] = 1;
	return to[c] = rec(c + a[c]);
}
int main()
{
	cin >> n;
	rep(i, n) cin >> a[i], to[i] = -1;
	rep(i, n) if(to[i] < 0){
		m = 0;
		rec(i);
	}
	
	queue<pi> q;
	q.push(mp(0, 0));
	memset(v, 0, sizeof(v));
	while(!q.empty()){
		int c = q.front().second;
		int cost = q.front().first; q.pop();
		
		if(v[c]) continue;
		if(c >= n - 7){
			cout << cost + (c != n-1) << endl;
			break;
		}
		v[c] = 1;
		for(int i = 1; i <= 6; i++) if(to[c + i] >= 0 && !v[to[c+i]]){
			q.push(mp(cost + 1, to[c + i]));
		}
	}
	
	return 0;
}

Measured memory_bytes: 1576
#include "bits/stdc++.h"
using namespace std;
#define forn(i, x, n) for (int i = x; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long double ld;
typedef long long ll;

int main() {
    int mx = 0;
    int n;
    scanf("%d",&n);
    vector<int> vec;
    forn(i, 0, n) {
        int ai;
        scanf("%d",&ai);
        vec.push_back(ai);
        mx = max(mx, ai);
    }
    int mid = mx / 2;
    int md = INT_MAX;
    int d;
    forn(i, 0, n) {
        if (vec[i] == mx) continue;
        int td = abs(vec[i] - mid);
        if (vec[i] > mid && mx%2 == 1) td--;
        if (td < md) {
            md = td;
            d = vec[i];
        }
    }
    printf("%d %d\n",mx,d);
    return 0;
}


Measured memory_bytes: 892
#include <iostream>

using namespace std;

typedef unsigned long long ull;
#define INF 1ULL << 34

int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;

  int maxN = max(X,Y);
  ull ans = INF, price;
  for (int i = 0; i <= maxN; ++i) {
    price = (max((X - i),0) * A) + (max((Y - i),0) * B) + (C * i * 2);
    ans = min(ans, price);
  }

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


Measured memory_bytes: 256
from functools import reduce
import numpy as np

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

def gcd_list(arg_list):
    return reduce(gcd, arg_list)

N, X = tuple(map(int, input().split(" ")))
Xs = [X] + list(map(int, input().split(" ")))
Xs = map(abs, np.diff(Xs))
r = gcd_list(Xs)
print(r)


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const string YES = "Yes";
const string NO = "No";
const ll mod = 1e9+7;



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

    ll a,b; cin >> a >> b;
    ll ans = max({a+b, a-b, a*b});
    cout << ans << endl;
    return 0;  
}



Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>

using namespace std;

#define ll long long

void solve()
{
    string S;
    cin >> S;
    if ((S[0] == S[1] && S[2] == S[3] && S[0] != S[2]) || (S[0] == S[2] && S[1] == S[3] && S[0] != S[1]) || (S[0] == S[3] && S[1] == S[2] && S[0] != S[1]))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

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


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define INF 10000000000
using namespace std;

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

  vector<long long int> v(h + 250);

  for(int i = 0; i < h + 250; i++) v[i] = INF;
  
  for(int i = 1; i <= h; i++) cin >> v[i];

  for(int i = 1; i <= h; i++){
    cout << "node " << i << ": key = " << v[i] << ", ";

    if(v[i/2] != INF) cout << "parent key = " << v[i/2] << ", ";
    if(v[i*2] != INF) cout << "left key = " << v[i*2] << ", ";
    if(v[i*2 + 1] != INF) cout << "right key = " << v[i*2 + 1] << ", ";

    cout << endl;
    
  }

  return 0;

}



Measured memory_bytes: 3084
//↓見なくていいよ！ここから--------------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  myerr("-----start-----");
  var start = new Date();
  Main();
  var end = new Date() - start;
  myerr("----- end -----");
  myerr("time : " + (end) + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}

//↑見なくていいよ！ここまで--------------------------------------------------
function Main(){
	var N = nextInt();
	var first = N;
	var set = new Set();
	var output = 0;
	
	while(true){
		var list = getDivisorList(N);
		var isOK = false;
		for(var i = 0; i < list.length; i++){
			if(isPrime(list[i])){
				for(var j = 0; j < 33; j++){
					var z = Math.pow(list[i],j);
					if(!set.has(z) && N % z == 0){
						set.add(z);
						output++;
						N /= z;
						isOK = true;
						break;
					}
				}
			}
		}
		myerr(N);
		if(!isOK){
			break;
		}
	}
	if(first == 1){
		myout(0);
	}else{
		myout(output - 1);
	}
	
}
function getDivisorList(val){
  var list = [];
  for(var i = 1; i * i <= val; i++){
    if(val % i == 0){
      list.push(i);
      if(i * i != val){
        list.push(val / i);
      }
    }
  }
  list.sort(function(a,b){ return a - b; });
  return list;
}
function isPrime(val){
  if(val == null || val <= 1 || (val != 2 && val % 2 == 0)){
    return false;
  }else if(val == 2){
    return true;
  }
  var root = Math.floor(Math.sqrt(val));
  for(var i = 3; i <= root; i += 2){
    if(val % i == 0){
      return false;
    }
  }
  return true;
}

Measured memory_bytes: 34276
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
    int i, j;
    string s;

    cin >> s;
    if (s == "AAA" || s == "BBB") {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }

    return 0;
}


Measured memory_bytes: 764
N = int(input())
A = []
maxNum=-1
secNum=-1
maxI=-1
for i in range(N):
    A.append(int(input()))
    if(maxNum<A[i]):
        secNum=maxNum
        maxNum=A[i]
        maxI=i
    elif(secNum<A[i]):
        secNum=A[i]

for i in range(len(A)):
    if(i!=maxI):
        print(maxNum)
    else:
        print(secNum)


Measured memory_bytes: 12532
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

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

vector<Pll> graph[100000];
vector<int> color(100000, -1);

void dfs(int node, int parent, int c) {
    color[node] = c;
    for(Pll child: graph[node]) {
        if(child.first == parent || color[child.first] != -1) continue;
        dfs(child.first, node, (c+child.second)%2);
    }
}

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n,u,v,w;
    cin >> n;
    for(int i=0;i<n-1;++i) {
        cin >> u >> v >> w;
        --u; --v; w %=2;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    dfs(0, -1, 0);

    for(int i=0;i<n;++i){
        cout << color[i] << endl;
    }
}


Measured memory_bytes: 9856
//  Copyright © 2020 Pradeep Singh. All rights reserved.

/*
Zeckendrof's theorem : Each positive number can be represented as a sum of three fibonacci numbers such that no two
consecutive fib number is used.
binomial : C(n,r) = C(n-1,r-1)+C(n-1,r) , C(n,0)=1
catalan : C(2*n,n)/(n+1);
*/


#include<bits/stdc++.h>
#include<algorithm>
using namespace std;

#define ff first
#define ss second
#define int long long
#define str(a) to_string(a)
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SORT(c) sort(c.begin(),c.end())
#define mod 1000000007
#define max_heap priority_queue<int>
#define min_heap priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcount(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define start(t) int x;cin>>x;while(x--)
#define inf LLONG_MAX
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define endl "\n"


vector<vector<double> > dp(3001, vector<double>(3001, -1));
double rec(int i, int heads, vector<double>& prob) {
	if (heads == 0) return 1;
	if (i == 0)	return 0;
	if (dp[i][heads] > -0.9)
		return dp[i][heads];
	return dp[i][heads] = rec(i - 1, heads - 1, prob) * prob[i] + rec(i - 1, heads, prob) * (1 - prob[i]);
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int n; cin >> n;
	vector<double> prob(n + 1);
	// cerr << dp.size() << " " <<
	for (int i = 1; i <= n; i++)	cin >> prob[i];
	cout << ps(rec(n, (n + 1) / 2, prob), 10) << endl;


}


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

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
#define test cout<<"test"<<endl;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
void debug(vector<vector<ll>>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j]<<" ";cout<<endl;}};
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}
//m.emplace(x,0).fi->second++;

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n;cin>>n;
  vector<P>p(n);
  for(i=0;i<n;i++)cin>>p[i].fi>>p[i].se;
  sort(ALLR(p));
  cout<<p[0].fi+p[0].se<<endl;
  return 0;
}

Measured memory_bytes: 1792
n = int(input())
words = []
for i in range(n) :
	s = input()
	words.append(s)

used = set()
flag = True
old_w = words[0]
used.add(old_w)
for word in words[1:] :
	if word in used :
		flag = False
		break
	else :
		used.add(word)
	#print(used)
	if old_w[-1] != word[0] :
		flag = False
		break
	old_w = word
print("Yes" if flag else "No")

Measured memory_bytes: 3064
import sys
from decimal import Decimal, ROUND_DOWN

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

a, b = map(Decimal, input().split())

ans = (a*b).quantize(Decimal('1'), rounding=ROUND_DOWN)
print(ans)


Measured memory_bytes: 9964
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fr first
#define sc second
typedef long long ll;
const long long llinf=LLONG_MAX;
const int inf=INT_MAX;
const int nmax=1e5+5;
const int mod=1e9+7;
using namespace std;
int n,a[nmax],i,ans;
int main()
{
	//freopen("sol.in","r",stdin);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)
	 if(a[i]==i)
	 {
		ans++;
		if(i!=n)swap(a[i],a[i+1]);
	 }
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    b = False
    for _ in range(N):
        if int(input())%2 != 0:
            b = True
            break
            
    if b:
        print("first")
    else:
        print("second")

if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define ALL(n) begin(n), end(n)
using ll = long long;

#define MAX 2 * 1000005

int main()
{
    int n;
    cin >> n;
    vector<int> l(MAX, 0);
    n;
    rep(i, n - 1)
    {
        int a;
        cin >> a;
        // 社員番号 a の人の数を計測
        l[a]++;
    }
    rep(i, n) { cout << l[i + 1] << endl; }

    return 0;
}

Measured memory_bytes: 11164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const long double PI = (acos(-1));
#define rep(i, x, n) for (int i = x; i < (int)(n); i++)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
int main(){
    int n, sum = 0, ans = 0; sc(n);
    vector<int> a(n);
    rep(i, 0, n) sc(a[i]);
    rep(i, 0, n) sum += a[i];
    if (sum % n <= n/2) sum /= n;
    else sum = sum / n + 1;
    rep(i, 0, n) ans += (a[i]-sum) * (a[i]-sum);
    cout << ans << endl;
    return 0;
}

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

void solve() {
    int x;
    cin >> x;

    int now = 100, ans = 0;
    while (now < x) {
        ans++;
        now += now / 100;
    }
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

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

int main(void){
    int N,K;
    int a[100000+10];
    int ans = 0;
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
        if (a[i] >= K) {
            ans++;
        }
    }
    printf("%d\n",ans);

}


Measured memory_bytes: 512
function Main(input) {
    input = input.split("\n").map(Number);
    var flag = false;
    var max = 0;
    input.shift();
    input.forEach(function(val){
        if(max<val){
            max = val;
            flag = false;
        }else if(max == val){
            flag = true;
        }
    })
    var next = 0;
        input.forEach(function(val){
            if(next<val&&val!=max) next = val;
    })
    input.forEach(function(val){
        console.log((flag||(val!=max))?max:next);
    })
}Main(require("fs").readFileSync("/dev/stdin","utf8").trim());


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

int  main() {
    int a, b;
    char op;
    while (1) {
        cin >> a >> op >> b;
        if (op == '+') {
            cout << a + b << endl;
        } else if (op == '-') {
            cout << a - b << endl;
        } else if (op == '*') {
            cout << a * b << endl;
        } else if (op == '/') {
            cout << a / b << endl;
        } else if (op == '?') {
            break;
        }
    }
    return 0;
}



Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int N,D,ans=0;
  cin>>N>>D;
  while(N--){
    int X,Y;
    cin>>X>>Y;
    if(X*X+Y*Y<=D*D)ans++;
  }
  cout<<ans<<endl;
}

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

int main() {

	int maxSoFar = 0; 

	int n; 
	cin >> n; 
	int h[n]; 

	for(int i = 0; i < n; i++) {
		int height; 
		cin >> height; 
		if(height >= maxSoFar) {
			h[i] = 1; 
			maxSoFar = height; 
		}
		else {
			h[i] = 0; 
		}
	}

	int m = 0;

	for(int i = 0; i < n; i++) {
		m += h[i]; 
	} 

	cout << m << endl; 

	return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int A, B;
	cin >> A >> B;
	if (max(A, B) > 8) {
		cout << ":(";
	}
	else {
		cout << "Yay!";
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;

const ll INF = 9223372036854775807;
const int inf = 2147483647;

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

string s,t;
string res;
bool flag = false;
int main() {
    cin >> s >> t;
    //int res = s.size();
    REP(i,s.size()+1){
        if(s==t){
            flag = true;
        }
        s = s.back()+s.substr(0,s.size()-1);
    }
    if(flag){
        res = "Yes";
    }else{
        res = "No";
    }
    put(res);
    //put(s.back()+s.substr(0,s.size()-1));
    return 0;
}


Measured memory_bytes: 256