akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<"="<<x<<endl
#define uni(x) x.erase(unique(all(x)),x.end())

typedef long long ll;

ll L[200010],R[200010];
ll imos[1000010];

int main(){

  ll N,M;
  cin>>N>>M;
  rep(i,N){
    cin>>L[i]>>R[i];
  }
  vector<ll> ds;
  rep(i,N){
    ds.push_back(L[i]);
    ds.push_back(R[i]);
    ds.push_back(R[i]+1);
  }
  sort(all(ds));
  uni(ds);

  rep(i,N){
    ll l=lower_bound(all(ds),L[i])-ds.begin();
    ll r=lower_bound(all(ds),R[i]+1)-ds.begin();
    imos[l]++;
    imos[r]--;
  }

  ll mx=0;
  rep(i,1000000){
    imos[i+1]+=imos[i];
    mx=max(mx,imos[i]);
  }

  ll mxl=M+1,mxr=-1;
  rep(i,1000000){
    if(imos[i]==mx){
      mxl=min(mxl,ds[i]);
      mxr=max(mxr,ds[i]);
    }
  }


  if(mx%2==0){
    cout<<(mx-1)*M+(M-mxl)<<endl;
  }else{
    cout<<(mx-1)*M+mxr<<endl;
  }

  return 0;
}



Measured memory_bytes: 18596
#include <stdio.h>

int flag[112345]; //vetor de flags para cada numero de questao.
int kk[112345];

int main() {
  char s[3];
  int n, m, p, a, b, negativo=0;

  scanf("%d%d", &n, &m);

  a = b = 0;
  while (m--) {
    scanf("%d%s", &p, s);

    if (!flag[p] && s[0] == 'A'){
      a++;
      b+= kk[p];
      flag[p]= 1;
    }
    else if (s[0] == 'W')
      kk[p]++;
  }
  printf("%d %d\n", a, b);
  return 0;
}


Measured memory_bytes: 896
#正答
k=int(input())
a=set()
count=1
if k%2==0:
    print(-1)
else:
    #下の桁に７を足していく
    ai=7%k
    while 1:
        if ai==0:
            print(count)
            break
        elif ai in a:
            print(-1)
            break
        else:
            a.add(ai)
            ai=(ai*10+7)%k
            count+=1




Measured memory_bytes: 77900
#include <iostream>
#include <string>
#include <stack>
#include <queue>

using namespace std;

typedef pair<int, int> P;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		priority_queue<P> pq;
		for (int i = 0; i < n; i++) {
			P p;
			cin >> p.second;
			vector<int> hyou(21, 0);
			int a;
			for (int j = 0; j < 10; j++) {
				cin >> a;
				if (j != 9) {
					if (a == 10) {
						hyou[j*2] = a;
						hyou[j*2+1] = -1;
					} else {
						hyou[j*2] = a;
						cin >> hyou[j*2+1];
					}
				} else {
					if (a == 10) {
						hyou[j*2] = a;
						cin >> hyou[j*2+1] >> hyou[j*2+2];
					} else {
						hyou[j*2] = a;
						cin >> hyou[j*2+1];
						if (a+hyou[j*2+1] == 10) {
							cin >> hyou[j*2+2];
						}
					}
				}
			}
			p.first = 0;
			for (int j = 0; j < 9; j++) {
				p.first += hyou[j*2];
				if (hyou[j*2] == 10) {
					p.first += hyou[j*2+2];
					if (hyou[j*2+3] == -1) {
						p.first += hyou[j*2+4];
					} else {
						p.first += hyou[j*2+3];
					}
				} else {
					p.first += hyou[j*2+1];
					if (hyou[j*2]+hyou[j*2+1] == 10) {
						p.first += hyou[j*2+2];
					}
				}
			}
			p.first += hyou[18]+hyou[19]+hyou[20];
			pq.push(p);
		}
		while (!pq.empty()) {
			P pp = pq.top();
			pq.pop();
			stack<int> str;
			str.push(pp.second);
			while (!pq.empty() && (pq.top()).first == pp.first) {
				str.push((pq.top()).second);
				pq.pop();
			}
			while (!str.empty()) {
				cout << str.top() << ' ' << pp.first << endl;
				str.pop();
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1200
#include<stdio.h>
#define MAX 100959
#define SENTINEL 1000000000
#define TRUE 1
#define FAULSE 0
#define PP 100

typedef struct {
  char suit;
  int value;
} Card;

 Card L[MAX/2+2];
 Card R[MAX/2+2];
 
 void mergeSort( Card A[], int n, int left, int right );
 void quickSort( Card A[], int n, int p, int r);
 int partition( Card A[], int n, int p, int r);
 void merge( Card A[], int n, int left, int mid, int right) ;
 
 int main(){
  int n, i, v;
   Card A[MAX], B[MAX];
  char CC[10];
  int stable = 1;
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ) {
    scanf("%s %d", CC, &v);
    A[i].suit = B[i].suit = CC[0];
    A[i].value = B[i].value = v;
  }
  
  

  mergeSort(A, n, 0, n);
  quickSort(B, n, 0, n-1);

  for ( i = 0; i < n; i++ ){
    if ( A[i].suit != B[i].suit ) stable = FAULSE;
  }

  if ( stable == TRUE ) {
  	printf("Stable\n");
  } else {
  	printf("Not stable\n");
  }
  
  int z;
  
  for ( i = 0; i < n; i++ ) {
    printf("%c %d\n", B[i].suit, B[i].value);
  }
}

 
void mergeSort( Card A[], int n, int left, int right ) {
  int mid;
  if ( left+1 < right ){
    mid = (left + right)/2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

void quickSort( Card A[], int n, int p, int r) {
  int q;
  if ( r > p ){
    q = partition(A, n, p, r);
    quickSort(A, n, q + 1, r);
    quickSort(A, n, p, q - 1);
  }
}

int partition( Card A[], int n, int p, int r) {
  int i, j;
   Card t, x;
  x = A[r];
  i = p - 1;
  for ( j = p; j < r; j++ ){
    if ( A[j].value <= x.value ){
      i++;
      t = A[i]; A[i] = A[j]; A[j] = t;
    }
  }
  t = A[i+1]; 
  A[i+1] = A[r]; 
  A[r] = t;
  return i +1;
}

void merge( Card A[], int n, int left, int mid, int right) {
  int i, j, k, n1, n2;
   n1 = mid - left;
   n2 = right - mid;
  for ( i = 0; i < n2; i++ ) R[i] = A[mid + i];
  for ( i = 0; i < n1; i++ ) L[i] = A[left + i];
  L[n1].value = R[n2].value = SENTINEL;
  i = j = 0;
  for ( k = left; k < right; k++ ){
    if ( L[i].value <= R[j].value ){
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}




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

#define int long long

const int N = 5e3 + 10;

int n , k , p[N] , w[N] , vis[N] , ans = -1e18 , upd , Rt;
int dpe[N] , siz[N] , sum[N] , cnt;

void dfs(int u){
	if(vis[u]) return;
	vis[u] = true , dpe[u] = cnt;
	siz[cnt]++ , sum[cnt] += w[u] , dfs(p[u]);
}

void Updata(int u , int step){
	if(step == 0) return;
	upd += w[p[u]] , Rt = max(Rt , upd);
	Updata(p[u] , step - 1);
}

signed main(){
	scanf("%lld %lld" , &n , &k);
	for(int i = 1; i <= n; i++) scanf("%lld" , &p[i]);
	for(int i = 1; i <= n; i++) scanf("%lld" , &w[i]);
	for(int i = 1; i <= n; i++) if(!vis[i]) cnt++ , dfs(i);
	for(int i = 1; i <= n; i++){
		int step = k % siz[dpe[i]] , Re = k / siz[dpe[i]];
		if(Re) step += siz[dpe[i]] , Re--;
		upd = 0 , Rt = -1e18 , Updata(i , step);
		ans = max(ans , max(Rt , Rt + sum[dpe[i]] * Re));
	}
	printf("%lld" , ans);
	return 0;
}

Measured memory_bytes: 3880
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {

  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll N,a,max=1,sec=0,maxpos,secpos;
  cin >> N;
  for (ll i = 0; i < N; ++i) {
  	cin >> a;
    if (max < a) {
      max = a;
      maxpos = i;
    }
    if (i != maxpos && sec < a && a <= max) {
      sec = a;
      secpos = i;
    }
  }
  
  for (ll i = 0; i < N; ++i) {
  	if (i == maxpos) cout << sec << endl;
    else cout << max << endl;
  }

  return 0;
}

Measured memory_bytes: 1664
from collections import Counter
N,K=map(int,input().split())
N=list(map(int,input().split()))
A=Counter(N)
C=list(A.values())
C.sort(reverse=True)
if len(C)<=K:
    print(0)
else:
    ans=sum(C[-(len(C)-K):])
    print(ans)

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

#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define count_one(a) __builtin_popcount(a)  // Returns the number of set bits(1) in a number(a). In long long use __builtin_popcountll(a)
#define parity(i)   __builtin_parity(i)  //even parity 0 and odd parity 1
#define blz(a)   __builtin_clz(a) //Returns the number of leading zeroes in a number(a)
#define btz(a)   __builtin_ctz(a) //Returns the number of trailing zeroes in a number(a)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define ll long long
#define pb push_back
#define PI M_PI
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main()
{
     IOS
     int a,b,c,d;

     cin>>a>>b>>c>>d;

     while(true)
     {
          c = c-b;
          if(c<=0)
               {
                    cout<<"Yes\n";
                    return 0;
               }
          a = a-d;
          if(a<=0)
               {
                    cout<<"No\n";
                    return 0;
               }
     }
     return 0;
}



Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;

int		main(void)
{
	int N, A, B;
	string S;
	cin >> N >> A >> B;
	cin >> S;
	int sum = 0, O = 0;
	for (int i = 0; i < N; i++)
	{
		if (S[i] == 'a')
		{
			cout << (sum < A+B ? "Yes" : "No") << endl;
			sum++;
		}
		else if (S[i] == 'b')
		{
			O++;
			if (sum < A+B && O <= B)
			{
				cout << "Yes" << endl;
				sum++;
			}
			else
				cout << "No" << endl;
		}
		else
			cout << "No" << endl;
	}
}



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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

bool dfs(ll v, const vector<vector<ll>> &g, vector<bool> &used,
         vector<ll> &match) {
    used[v] = true;
    rep(i, g[v].size()) {
        ll u = g[v][i], w = match[u];
        if (w < 0 || !used[w] && dfs(w, g, used, match)) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

int main() {
source:
    ll n;
    cin >> n;
    ll a[n], b[n];
    ll c[n], d[n];
    rep(i, n) { cin >> a[i] >> b[i]; }
    rep(i, n) { cin >> c[i] >> d[i]; }

    vector<vector<ll>> g(2 * n);
    rep(i, n) {
        rep(j, n) {
            if (a[i] < c[j] && b[i] < d[j]) {
                g[i].push_back(j + n);
                g[j + n].push_back(i);
            }
        }
    }
    vector<ll> match(2 * n, -1);
    vector<bool> used(2 * n);
    ll result = 0;
    rep(i, 2 * n) {
        if (match[i] < 0) {
            used = vector<bool>(2 * n, false);
            if (dfs(i, g, used, match)) {
                result++;
            }
        }
    }

    cout << result << endl;
    return 0;
}



Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <numeric>
#include <sstream>
#include <queue>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define PUSH(n,v) for(int i=0; i<(n); i++) {int j; cin >> j; v.push_back(j);}
#define ALL(v) v.begin(), v.end()
#define print(s) cout << (s) << endl

void solve112(int n) {
    vector<int> v;
    PUSH(n,v);
    sort(ALL(v));
    long s = 0;
    REP(i,n) {
        s += (n-i-1) * v[i];
    }
    cout << s << endl;
}

int main() {
    int n;
    while (cin >> n, n) {
        solve112(n);
    }
    return 0;
}

Measured memory_bytes: 1324
count = int(input())
params = []

for i in range(count):
    params.append(tuple(map(int, input().split())))

maxNum = max(params, key= lambda n : n[1])

sosuList = [1] * (maxNum[1] + 1)
sosuList[0] = 0
sosuList[1] = 0

for i in range(2, len(sosuList)):
    if sosuList[i] == 1:
        for j in range(i + i, len(sosuList), i):
            sosuList[j] = 0

ruisekiwaList = [0] * (len(sosuList) + 1)

for i in range(2, len(sosuList)):
    ruisekiwaList[i + 1] = ruisekiwaList[i] 
    if sosuList[i] == 1 and sosuList[int((i + 1) /2)] == 1:
        ruisekiwaList[i + 1] += 1

for tup in params:
    minNum, maxNum = tup
    result = ruisekiwaList[maxNum + 1] - ruisekiwaList[minNum]
    print(result)

Measured memory_bytes: 18912
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

class Combination {
public:
    Combination(ll max_num, ll mod) {
        fact_.resize(max_num + 1, 1);
        inv_fact_.resize(max_num + 1, 1);
        mod_ = mod;
        for (ll i = 2; i <= max_num; i++) {
            fact_[i] = i * fact_[i - 1] % mod_;
            inv_fact_[i] = MODpow(fact_[i], mod_ - 2);
            assert(fact_[i] * inv_fact_[i] % mod_ == 1);
        }
    }
    ll operator()(ll n, ll m) const {
        if (m < 0 || m > n) return 0;
        return fact_[n] * inv_fact_[n - m] % mod_ * inv_fact_[m] % mod_;
    }
    ll fact(ll n) const {
        return fact_[n];
    }
private:
    vector<ll> fact_, inv_fact_;
    ll mod_;
};

ll N, A, B, C, D;
vector<vector<ll>> memo;
Combination comb(2001, MOD);

//i人をj人のグループだけを使って分ける方法の数
ll f(ll i, ll j) {
    ll k = i / j;

    return comb.fact(i) * MODpow(MODpow(comb.fact(j), k), MOD - 2) % MOD * MODpow(comb.fact(k), MOD - 2) % MOD;
}

//i人をj人以下のグループだけを使って場合分けする数
ll solve(ll i, ll j) {
    if (i == 0) {
        return 1;
    }
    if (i < 0) {
        return 0;
    }
    if (j == A - 1) {
        return 0;
    }

    if (memo[i][j] != -1) {
        return memo[i][j];
    }

    //j人ちょうどのグループをk個とする
    ll result = solve(i, j - 1);
    for (ll k = C; k <= D; k++) {
        if (j * k > i) {
            break;
        }

        ll tmp = solve(i - j * k, j - 1);

        //i人からj * k人選ぶ方法
        (tmp *= comb(i, j * k)) %= MOD;

        //j * k人をk個のグループに分ける方法
        (tmp *= f(j * k, j)) %= MOD;

        (result += tmp) %= MOD;
    }

    return memo[i][j] = (result % MOD);
}

int main() {
    cin >> N >> A >> B >> C >> D;
    memo.resize(N + 1, vector<ll>(N + 1, -1));
    cout << solve(N, B) << endl;
}

Measured memory_bytes: 8192
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template<int Modulo = MOD> struct Mint {
	Int val;
	constexpr Mint(Int v = 0) noexcept : val(v% Modulo) {
		if (val < 0) v += Modulo;
	}
	constexpr int getmod() { return Modulo; }
	constexpr Mint operator - () const noexcept { return val ? Modulo - val : 0; }
	constexpr Mint operator + (const Mint& r) const noexcept { return Mint(*this) += r; }
	constexpr Mint operator - (const Mint& r) const noexcept { return Mint(*this) -= r; }
	constexpr Mint operator * (const Mint& r) const noexcept { return Mint(*this) *= r; }
	constexpr Mint operator / (const Mint& r) const noexcept { return Mint(*this) /= r; }
	constexpr Mint& operator += (const Mint& r) noexcept {
		val += r.val;
		if (val >= Modulo) val -= Modulo;
		return *this;
	}
	constexpr Mint& operator -= (const Mint& r) noexcept {
		val -= r.val;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr Mint& operator *= (const Mint& r) noexcept {
		val = val * r.val % Modulo;
		return *this;
	}
	constexpr Mint& operator /= (const Mint& r) noexcept {
		Int a = r.val, b = Modulo, u = 1, v = 0;
		while (b) {
			Int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = val * u % Modulo;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr bool operator == (const Mint& r) const noexcept {
		return this->val == r.val;
	}
	constexpr bool operator != (const Mint& r) const noexcept {
		return this->val != r.val;
	}
	friend ostream& operator << (ostream& os, const Mint<Modulo>& x) noexcept {
		return os << x.val;
	}
	friend istream& operator >> (istream& is, Mint<Modulo>& x) noexcept {
		Int tmp; is >> tmp;
		x = Mint<Modulo>(tmp);
		return is;
	}
	friend constexpr Mint<Modulo> modpow(const Mint<Modulo>& a, Int n) noexcept {
		Mint res(1), tmp = a;
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}
};

using mint = Mint<>;

vector<int> seen;
vector<vector<Int>> G;
mint ans;
Int N, K;

void dfs(Int v, Int dist) {
	seen[v] = 1;
	Int temp;
	if (dist==0) {
		temp = K - 1;
	}
	else {
		temp = K - 2;
	}

	for (const auto& nv : G[v]) {
		if (seen[nv]) {
			continue;
		}
		ans *= temp;
		dfs(nv, dist + 1);
		temp--;
	}

}

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	
	cin >> N >> K;

	G.resize(N);
	Int a, b;
	for (Int i = 0; i < N-1; i++) {
		cin >> a >> b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	ans = K;
	seen.resize(N, 0);

	dfs(0, 0);//頂点0を根とする

	cout << ans << "\n";
}


Measured memory_bytes: 9600
import sys
sys.setrecursionlimit(30000)

v,e=map(int,input().split())

class node:
    def __init__(self, i):
        self.edge=[]
        self.low=0
        self.num=0
        self.visited=False
        self.child=[]
        self.id=i
        
nodes=[node(i) for i in range(v)]
for _ in range(e):
    s,t=map(int,input().split())
    nodes[s].edge.append(t)
    nodes[t].edge.append(s)
    
num=0
def dfs(node):
    global num
    node.num=num
    num+=1
    node.visited=True
    node.low=node.num
    for e in node.edge:
        if not nodes[e].visited:
            dfs(nodes[e])
            node.low=min(node.low, nodes[e].low)
            node.child.append(e)
        else:
            node.low=min(node.low, nodes[e].num)
            
dfs(nodes[0])
            
if len(nodes[0].child)>=2: print(0)
for node in nodes[1:]:
    for e in node.child:
        if node.num <= nodes[e].low:
            print(node.id)
            break
        
            
    
    


Measured memory_bytes: 22120
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    rep(i ,T) {
        int N, D;
        cin >> N >> D;
        if (N % 2 == 0) D ^= 127;
        cout << 127 * (N-1) + D << endl;
    }

    return 0;
}


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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int N = 1e5 + 10;

int n, m, x[N], y[N];

int cnt[N];

bool can[N];

int main()
{
	gii(n, m);
	for (int i = 1; i <= m; ++i)
		gii(x[i], y[i]);
	for (int i = 1; i <= n; ++i) cnt[i] = 1;
	can[1] = 1;
	for (int i = 1; i <= m; ++i)
	{
		if (can[x[i]])
		{
			if (cnt[x[i]] == 1)
				can[x[i]] = 0;
			can[y[i]] = 1;
		}
		--cnt[x[i]];
		++cnt[y[i]];
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		if (can[i]) ++ans;
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 1536
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}

// index が条件を満たすかどうか

int main() {
	int n,N;
	cin >> N;
	n = N;
	int x = 0;
	while (n != 0) {
		x = x + n % 10;
		n = n / 10;
	}
	if (N % x == 0) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws Exception{
		int num = 998244353;

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		int t = Integer.parseInt(bf.readLine());
 		long sum = 0;
 		for(int i = 1;i<=t;i++){
 			sum+= (long)(i)*((long)(t/i)*(long)((t/i+1))/(long)(2));
 		}
 		
 		out.println(sum);
	 		
 		out.close();
 		
 		
 		
 	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	




Measured memory_bytes: 25932
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void){
   int W,a,b;
   cin>>W>>a>>b;
   if(b-a-W>0) cout<<b-a-W;
   else if(a-b-W>0) cout<<a-b-W;
   else cout<<0;
   return 0;
}


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

class Hello{
static void Main(){
string [] str=Console.ReadLine().Split(' ');
List<int> ans=new List<int>();


ans.Add(int.Parse(str[0]));
ans.Add(int.Parse(str[1]));
ans.Add(int.Parse(str[2]));

ans.Sort();

Console.WriteLine("{0} {1} {2}",ans[0],ans[1],ans[2]);

}
}


Measured memory_bytes: 19904
// https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_b

package main

import "fmt"

func main() {
	var N, K int
	var s []byte

	fmt.Scanf("%d", &N)
	fmt.Scanf("%s", &s)
	fmt.Scanf("%d", &K)

	c := s[K-1]
	for i := range s {
		if s[i] != c {
			s[i] = '*'
		}
	}
	fmt.Println(string(s))
}


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

int main() {
    int H, W; cin >> H >> W;
    int M = 10;
    vector<vector<int>> C(M, vector<int>(M));
    rep(i, M) rep(j, M) cin >> C[i][j];
    rep(k, M) rep(i, M) rep(j, M) {
        C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
    }
    int ans = 0;
    rep(i, H) rep(j, W) {
        int a; cin >> a;
        if(a == -1) continue;
        ans += C[a][1];
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vec<int> A(N);
    for(int i=0;i<N;i++) cin >> A[i];
    int ans = 1e9;
    for(int x=-100;x<=100;x++){
        int now = 0;
        for(int i=0;i<N;i++) now += (x-A[i])*(x-A[i]);
        ans = min(ans,now);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<int> cnt(M, 0);
    for (int i = 0, K; i < N; i++) {
        cin >> K;
        for (int j = 0, A; j < K; j++) {
            cin >> A;
            cnt[A - 1]++;
        }
    }
    cout << count_if(cnt.begin(), cnt.end(), [N](int i) { return i == N; }) << endl;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll, ll> Pll;
typedef pair<int, Pii > P1;

#define rep(i,n) for(int i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define mp1(a,b,c) P1(a,P(b,c))
#define get_arsize(a) (sizeof(a)/sizeof(a[0]))

const ll MOD = 1000000007;
const double EPS = 1e-10;
const int MAX = 200000;

int main() {
	int k, n, max=0, before_a = 0;
	cin >> k >> n;
	int a, d, begin;
	rep(i,n) {
		cin >> a;
		d = a - before_a;
		if (i == 0) {
			begin = a;
		}
		if (i == n-1) {
			d = (k-a) + begin > d ? (k-a) + begin : d;
		}
		if(max < d) {
			max = d;
		}
		before_a = a;
	}
	cout << k - max << endl;
  return 0;
}


Measured memory_bytes: 256
let n = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map(String.init).lazy.map { Int($0)! }

var acc = 0
var min = 0

for num in a {
  if min > num {
    acc = acc &+ (min - num)
  } else {
    min = num
  }
}

print(acc)


Measured memory_bytes: 21144
#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
 
typedef long long ll;
typedef pair<int, int> point;
 
const int MAXN = 2e5 + 5, off = 1 << 18, inf = 1e9;
 
bool bio[2 * off];
vector<point> T[2 * off];
 
vector<point> Compress(vector<point> v) {
  vector<point> ret;
  sort(v.begin(), v.end());
 
  ret.push_back(v[0]);
  FOR(i, 1, sz(v)) {
    if(v[i].second < ret.back().second) {
      ret.push_back(v[i]);
    }
  }
 
  return ret;
}
 
int Query(int x, int a) {
  if(!bio[x]) {
    T[x] = Compress(T[x]);
    bio[x] = true;
  }
 
  int i = lower_bound(T[x].begin(), T[x].end(), point(a, -inf)) - T[x].begin(); --i;
  return T[x][i].second;
}
 
int Ask(int x, int lo, int hi, int a, int b) {
  if(lo >= b || hi <= a) {
    return inf;
  }
  if(lo >= a && hi <= b) {
    return Query(x, a);
  }
 
  int mid = (lo + hi) >> 1;
 
  return min(
             Ask(x * 2 + 0, lo, mid, a, b),
             Ask(x * 2 + 1, mid, hi, a, b)
             );
}
 
void upd(int i, point p) {
  i += off;
  for(; i; i /= 2) {
    T[i].push_back(p);
  }
}
 
int a[MAXN];
vector<int> l[MAXN];
 
int n;
 
int dp[MAXN];
 
void solve() {
  int global = 0, delta = 0;
 
  FOR(i, 1, n + 1) {
    delta = 1 - a[i];
    global += delta;
 
    for(auto x: l[i]) {
      int val = Ask(1, 0, off, x, i);
      val = min(val, dp[x - 1]);
      upd(i, {x, val});
    }
 
    upd(i, {i + 1, dp[i - 1] - delta + a[i]});
    upd(i, {0, inf});
 
    dp[i] = Query(i + off, MAXN);
  }
 
  cout << dp[n] + global << endl;
}
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
 
  cin >> n;
  REP(i, n) cin >> a[i + 1];
 
  int q; cin >> q;
  REP(i, q) {
    int x, y; cin >> x >> y;
    l[y].push_back(x);
  }
 
  solve();
}

Measured memory_bytes: 113208
#include <stdio.h>
int main (){
	
	// find the maximum number of apple pies we can make with what we have now
	// a = apple 
	// p = pices of apple
	int a, p;
	scanf("%d %d", &a, &p);
	
	int slice = a*3;
	int totalSlice = slice + p;
	int total = totalSlice/2;
	printf ("%d", total);
	
	return 0;
}

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

int main(){
    int n,priv,a;
    int part=1;
    int sub=0;
    cin >> n;

    cin >> a;
    priv = a;

    for(int i=1; i<n; i++){
        cin >> a;
        if((a-priv)*sub < 0){
            part++;
            sub = 0;
        }else{
            sub += a - priv;
            if(sub > 0){
                sub = 1;
            }else if(sub < 0){
                sub = -1;
            }
        }
        priv = a;
    }

    cout << part << endl;
}

Measured memory_bytes: 384
import java.util.*;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[] = new int[n];
		for (int i = 0; i < n; ++i)
			a[i] = sc.nextInt();
		sc.close();
		String ans[] = { "YES", "NO" };
		int an = 0;
		Arrays.sort(a);
		int t = a[0];
		for (int i = 1; i < n; ++i) {
			if (t == a[i]) {
				an = 1;
				break;
			}
			t = a[i];
		}
		System.out.println(ans[an]);
	}
}


Measured memory_bytes: 66264
#include<bits/stdc++.h>
long long n,ans;
int s;
int main()
{
    scanf("%lld",&n);
    for(int i=sqrt(n);i>0;--i) 
        if(n%i==0){ans=n/i;break;}
    while(ans>0)++s,ans/=10;
    printf("%d\n",s); 
}

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

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

    vector<int> L;
    int l;
    for(int i=0;i<2*N;i++){
        cin >> l;
        L.push_back(l);
    }
    sort(L.begin(),L.end());

    int ans=0;
    for(int i=0;i<2*N;i+=2){
        ans+=L[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> P;
typedef pair<ll,ll> PLL;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

//dpTable
int dp[100050];

int main(){
    string S,T;
    cin >> S >> T;
    int Ss = S.size(),Ts = T.size();
    int ans = 100000;
    for (int i = 0; i < Ss - Ts + 1; i++) {
        int hoge = 0;
        for (int j = i; j < Ts + i; j++) {
            if (S.at(j) != T.at(j - i)) hoge++;
        }
        ans = min(ans,hoge);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <climits>
using namespace std;

typedef long long ll;

int result;
int N;
int a[100000];

int res = 0;

int main()
{
	cin >> N;
	int x;
	for(int i = 0;i < N;i++)
	{
		cin >> a[i];
	}

	sort(a,a + N);


	int cou = 1;
	for(int i = 1;i < N;i++)
	{
		if(a[i - 1] != a[i])
		{
			if(cou > a[i - 1]) res += cou - a[i - 1];
			else if(cou < a[i - 1]) res += cou;
			cou = 0;
		}
		cou++;
	}
	if(cou > a[N - 1]) res += cou - a[N - 1];
	else if(cou < a[N - 1]) res += cou;
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>//万头，CSP可用
using namespace std;
short n,m,an[105][105];//short节省空间，an表示最后的计数器
char a[105][105];//注意输入的时候使用char数组
bool flag[105][105];
int main()
{
    cin>>n>>m;//输入n*m
    for(int i=1;i<=n;i++)//输入不多说 
        for(int j=1;j<=m;j++) {
            cin>>a[i][j];
            if(a[i][j]=='#') flag[i][j]=1;//注意，这里如果输如的是#那就把这里的标志（后面会用的）记为1
            else flag[i][j]=0;}//其他的，变为0
    for(int i=1;i<=n;i++) //开始疯狂枚举
        for(int j=1;j<=m;j++) 
        {
            if(flag[i-1][j]==1) an[i][j]++;//如果四面八方有雷，计数器++
            if(flag[i][j-1]==1) an[i][j]++;//同上
            if(flag[i+1][j]==1) an[i][j]++;//同上
            if(flag[i][j+1]==1) an[i][j]++;//同上
            if(flag[i-1][j+1]==1) an[i][j]++;//同上
            if(flag[i+1][j-1]==1) an[i][j]++;//同上
            if(flag[i+1][j+1]==1) an[i][j]++;//同上
            if(flag[i-1][j-1]==1) an[i][j]++;//同上
        }
    for(int i=1;i<=n;i++) 
    {
        for(int j=1;j<=m;j++) 
        {
            if(a[i][j]=='#') cout<<'#';//如果是雷，输出雷
            else cout<<an[i][j];//输出雷的个数
        }
        cout<<endl;//每一行后面记得换行
    }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    long long int n, a, b;
    scanf("%lld %lld %lld", &n, &a, &b);
    long long int times = n / (a + b);
    long long int sur = n - (a + b) * times;

    if (sur <= a) {
        printf("%lld\n", a * times + sur);
    } else {
        printf("%lld\n", a * times + a);
    }

    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main(){
    unsigned long N, K, ans = 0, v[100001];
    scanf("%lu%lu", &N, &K);
    for(unsigned long i = 1; i <= K; ++i)v[i] = i;
    for(unsigned long i = 2; i <= K; ++i)if(v[i] == i)for(unsigned long j = i; j <= K; j += i)v[j] = (v[j] / i) * (i - 1);
    for(unsigned long i = 1; i <= K; ++i)v[i] = (v[i] + v[i - 1]) % 1000000007;
    for(unsigned long i = K, p = 0; i; ){
        unsigned long t = K / i, r = 1, n = N, a = t;
        while(n){
            if(n & 1){
                r *= a;
                r %= 1000000007;
            }
            a *= a;
            a %= 1000000007;
            n >>= 1;
        }
        ans += (r + p) * v[i];
        i = K / (t + 1);
        p = 1000000007 - r;
    }
    printf("%lu\n", ans % 1000000007);
    return 0;
}

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

int main() {
  long long int S = 0;
  int N = 0;
  cin >> N;
  for (int i = 1; i < N+1; i++) {
    if ( i%5 != 0 && i%3 != 0 ) {
      S += i;
    }
  }
  cout << S << endl;
}
    


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#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 > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  ll n,p;
  cin>>n>>p;
  ll ans = 1;
  ll t = p;
  for(ll i = 2; i * i <= p; i++) {
    ll cnt = 0;
    while(t % i == 0) {
      t /= i;
      cnt++;
    }
    ans *= (ll)pow(i, cnt / n);
  }
  for(ll i = 2; i * i <= p; i++) {
    ll cnt = 0;
    if(p % i == 0) {
      ll j = p / i;
      cnt = 0;
      while(t % j == 0) {
        t /= j;
        cnt++;
      }
      ans *= (ll)pow(j, cnt / n);
    }
  }
  if(t != 1 && n == 1) {
    ans *= p;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
N, M = map(int, input().split())
def fib(n) :
    a, b = 1, 1
    if n==0 :
        return a
    elif n==1 :
        return b
    else :
        for i in range(n-1):
            a, b = b, a+b
        return b
a=[]
b=1

for i in range(M):
    a.append(int(input()))
    if a[i]-a[i-1] == 1 :
        b=0

def rest(num) :
    return num % 1000000007
c=0
if b==0 :
    print(c)
else :
    for i in range(M+1):
        if i == 0 == M :
            c += rest(fib(N))
        elif i == 0:
            c += rest(fib(a[i]-1))
        elif i == M:
            c = rest(c * fib(N-a[i-1]-1))
        else :
            c = rest(c * fib(a[i]-a[i-1]-2))
    print(c)


Measured memory_bytes: 7032
#include <bits/stdc++.h>
#define vi vector<int>
#define ll long long
#define pb push_back
#define ii pair<int, int>
#define MAX int(1e5)+5
#define qi queue<int>
#define si stack<int>
#define mii map<int, int>
#define msi map<string, int>
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
using namespace std;

int n, arr[MAX], dp[MAX], k;
const int INF = 1e9+5;

int main(int argc, char** argv) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = INF;
	}

	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j <= i+k; j++)
			if (j < n)
				dp[j] = min(dp[j], dp[i]+abs(arr[i]-arr[j]));
	}

	cout << dp[n-1] << '\n';


	return 0;
}






Measured memory_bytes: 1152
#include <stdio.h>
#define N 101

int main(){
 
  int i,j,n,k,y;
  int Graph1[N][N],Graph2[N][N];
 
  for(i = 1;i <= 100;i ++)
    {
      for(j = 1;j <= 100;j ++)
	{
	  Graph1[i][j] = 0;
	  Graph2[i][j] = 0;
	}
    }
  scanf("%d",&n);
  
  for(i = 1;i <= n;i ++)
    {
      scanf("%d%d",&y,&k);
    
      for(j = 1;j <= k;j ++)
	{
	  scanf("%d",&Graph1[i][j]);
     
	}
    }
 
  for(i = 1;i <= n;i ++)
    {
      for(j = 1;j <= n;j ++)
	{
	  Graph2[i][Graph1[i][j]]=1;
	}
    }
 
  for(i = 1;i <= n;i ++)
    {
      for(j = 1;j < n;j ++)
	{
	  printf("%d ",Graph2[i][j]);
	}
      printf("%d\n",Graph2[i][n]);
    }
  return 0;
}

Measured memory_bytes: 680
#include<bits/stdc++.h>
using namespace std;
#define int long long
int diff[10];
int num[]={1,2,3,4,5,6,7,8,9,10};

bool check(){
  int A[3][3],mod = num[9];
  for(int i=0;i<10;i++)if(diff[i]>0&&num[i]!=diff[i])return 0;
  for(int i=0;i<9;i++) A[i/3][i%3] = num[i];


  int used[20]={};
  for(int i=0;i<3;i++){
    int a=0,b=0;    
    for(int j=0;j<3;j++)a+=A[i][j],b+=A[j][i];
    a%=mod,b%=mod;
    used[a]++;
    used[b]++;
    if(used[a]!=(i+1)*2)return 0;    
  }
  
int a =A[0][0]+A[1][1]+A[2][2],b = A[0][2]+A[1][1]+A[2][0];
used[a%mod]++,used[b%mod]++;
 return used[a%mod] == 8;
}

signed main(){

  while(1){
    int Exit = 1;
    for(int i=0;i<10;i++)cin>>diff[i],Exit*=(diff[i]<0);
    if(Exit) return 0;

  for(int i=0;i<10;i++)num[i] = i+1;

  int ans=0;
  do{
    ans+=check();
  }while(next_permutation(num,num+10));
  cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3032
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include<time.h>
#include<stdlib.h>
#define pb push_back
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/__gcd((a),(b))
#define clr(x) x.clear()
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vi>
#define mp make_pair
#define hell 1000000007
 
using namespace std;
 
int main()
{
    IOS
    int n;
    cin>>n;
    double dp[3000];
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        double p;
        cin>>p;
        for(int j=i;j>0;j--)
        {
            dp[j]=dp[j]*(1-p)+dp[j-1]*p;
        }
        dp[0]=dp[0]*(1-p);
    }
    double res=0;
    for(int i=0;i<=n;i++)
    {
        int heads=i;
        int tails=n-i;
        if(heads>tails)
            res=res+dp[i];
    }
    cout<<fixed<<setprecision(10)<<res;
    return 0;
}


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


void solve(long long N, long long R){
    if(N>=10)cout<<R<<endl;
    else
        cout<<R+100*(10-N)<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long R;
    scanf("%lld",&R);
    solve(N, R);
    return 0;
}


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

using namespace std;

typedef long long LL;

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define fin "\n"


#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}

template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}

typedef vector<int> V;
typedef vector<V> VV;


namespace _DSU{
#define SZ 500000
    int mem[2][SZ];
}
class UnionFind{
private:
    int *par,*rank;
    int find(int x){
	if (par[x] == x) return x;
	else return par[x] = find(par[x]);
    }
public:
    UnionFind(int n,int *par,int *rank) :par(par),rank(rank){
	for(int i = 0; i < n; i++)par[i] = i,rank[i] = 0;
    }
    UnionFind(int n):UnionFind(n,_DSU::mem[0],_DSU::mem[1]){}
    bool unite(int x, int y){
	x = find(x);y = find(y);
	if (x == y)return false;
	if (rank[x] < rank[y]) par[x] = y;
	else{
	    par[y] = x;
	    if (rank[x] == rank[y])rank[x]++;
	}
	return true;
    }
    bool same(int x, int y){
	return find(x) == find(y);
    }
};

int main(){
    int N,M;
    cin>>N>>M;
    VV r(M+1);
    REP(i,N){
        int K;
        cin>>K;
        REP(j,K){
            int L;
            cin>>L;
            r[L].push_back(i);
        }
    }
    UnionFind uf(N);
    for(auto &it:r){
        if(it.size()){
            for(auto &jt:it){
                uf.unite(it.front(),jt);
            }
        }
    }
    REP(i,N)if(uf.same(0,i)==false){
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;

    return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>

using namespace std;

/* template */

using ll = long long;

void debug_out() { std::cout << std::endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n-1)); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n-1ll)); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    int weight;
    edge(int f,int t,int w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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

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

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

bool isPalindrome(string s){
    string t = s;
    reverse(all(t));
    return s==t;
}

constexpr ll LNF = 1e18+7;

constexpr int INF = 1e9+7;



vector<int> dx = {-1,0,1,0,-1,1,-1,1};
vector<int> dy = {0,-1,0,1,1,-1,-1,1};

/* template */

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m; cin >> n >> m;
    graph g(3*n);
    rep(i,0,m){
        int u,v; cin >> u >> v;
        u--; v--;
        g[u].emplace_back(v+n);
        g[u+n].emplace_back(v+n*2);
        g[u+n*2].emplace_back(v);
    }
    int s,t; cin >> s >> t;
    s--; t--;
    queue<int> que;
    que.push(s);
    vector<int> seen(3*n,-1);
    seen[s] = 0;
    while(!que.empty()){
        int x = que.front(); que.pop();
        for(auto &nx: g[x]){
            if(seen[nx]>=0) continue;
            que.push(nx);
            seen[nx] = seen[x] + 1;
        }
    }
    if(seen[t]<0) cout << -1 << endl;
    else cout << seen[t]/3 << endl;
}

Measured memory_bytes: 17792
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
const int MAX=1e5;

int main(){
	lli N;
    cin>>N;
	lli A[MAX+1];
	rep1(i,N) cin>>A[i];

	bool ans=true;
	lli sum=0;
	rep1(i,N) sum+=A[i];
	
	if(sum%(N*(N+1)/2)!=0) ans=false;
	else{
		lli t=sum/(N*(N+1)/2);
		rep1(i,N)A[i]-=i*t;
		rep1(i,N-1)if(A[i]<A[i+1]||(A[i]-A[i+1])%N!=0) ans=false;
	}
	
	if(ans)cout<<"YES";
	else cout<<"NO";
}


Measured memory_bytes: 1152
#include "iostream"
#include "algorithm"

using namespace std;

int A, B, C;

int main() {
    cin >> A >> B >> C;

    int m;

    m = max(A, max(B, C));

    int x = 0;

    x += m - A;
    x += m - B;
    x += m - C;

    if (x % 2 == 0) {
        cout << x / 2 << endl;
    } else {
        cout << x / 2 + 2 << endl;
    }
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define INF 1e+9


int main() {
	vector<int> v;
	int s;
	cin >> s;
	v.push_back(s);
	for (int i = 0;; i++) {
		if (v[i] % 2 == 0)v.push_back(v[i] / 2);
		else v.push_back((3*v[i])+1);
		auto x = find(v.begin(), v.end()-1, v[i + 1]);
		if (x != v.end()-1) { s = i+2; break; }
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
S = input()
# print(S)
stack = []
ans = 0
for c in S:
    if stack and stack[0] != c:
#         print("stack={}, c={} pop!".format(stack, c))
        stack.pop()
        ans += 2
    else:
#         print("stack={}, c={} append!".format(stack, c))
        stack.append(c)
#     print("c={0}, st={1}".format(c, stack))
print(ans)

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

int main() 
{
	int n , ans = 0;
	cin >> n ;
	int a[n];
	for(int i = 0 ; i < n ; i++)
		cin >> a[i];
	for(int i = 1 ; i < n-1 ; i++)	
		if((a[i]>a[i-1] && a[i]<a[i+1]) || (a[i]>a[i+1] && a[i]<a[i-1]))
			ans++;
			
	return  cout << ans ,0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 100005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int N;
int a[MAXN],cnt[MAXN],val[MAXN][2];
int64 dp[MAXN][2];
void Solve() {
	read(N);
	for(int i = 1 ; i <= N ; ++i) {
		read(a[i]);
		int k = -1,x = a[i];
		while(x) {++k;x >>= 1;}
		cnt[i] = k;
	}
	for(int i = 1 ; i <= N ; ++i) {
		dp[i][0] = 1e16;dp[i][1] = 1e16;
		int s = cnt[i],t = cnt[i];
		if(a[i] != (1 << cnt[i])) ++t;
		val[i][0] = s;val[i][1] = t;
		for(int j = 0 ; j <= 1 ; ++j) {
			dp[i][0] = min(dp[i][0],dp[i - 1][j] + t - min(t,val[i - 1][j]));
			dp[i][1] = min(dp[i][1],dp[i - 1][j] + t - min(s,val[i - 1][j]));
		}
	}
	out(min(dp[N][0],dp[N][1]));enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
}


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

typedef struct {
	int *par, *size, *height;
} UF_forest;

void UF_initialize(UF_forest *F, int n)
{
	int i;
	F->par = (int*)malloc(sizeof(int) * (n + 1));
	F->size = (int*)malloc(sizeof(int) * (n + 1));
	F->height = (int*)malloc(sizeof(int) * (n + 1));
	for (i = 1; i <= n; i++) {
		F->par[i] = i;
		F->size[i] = 1;
		F->height[i] = 1;
	}
}

void UF_merge(UF_forest *F, int u, int v)
{
	for (; F->par[u] != u; u = F->par[u]);
	for (; F->par[v] != v; v = F->par[v]);
	if (u == v) return;
	else if (F->height[u] > F->height[v]) {
		F->par[v] = u;
		F->size[u] += F->size[v];
	} else {
		F->par[u] = v;
		F->size[v] += F->size[u];
		if (F->height[u] == F->height[v]) F->height[v]++;
	}
}

int UF_root(UF_forest *F, int v)
{
	for (; F->par[v] != v; v = F->par[v]);
	return v;
}

int main()
{
	int N, Q;
	scanf("%d %d", &N, &Q);
	
	int i, t, u, w;
	UF_forest F;
	UF_initialize(&F, N);
	for (i = 1; i <= Q; i++) {
		scanf("%d %d %d", &t, &u, &w);
		if (t == 0) UF_merge(&F, u, w);
		else if (UF_root(&F, u) == UF_root(&F, w)) printf("1\n");
		else printf("0\n");
	}
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 3836