akhauriyash/Code-Regression huggingface dataset:
// Problem : C - Ubiquity
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// $%U%$
// Mere bas ka nahi hai
// still i'm trying
// apna time aayega
//
//        .--------------.  
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |  
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'                          		  
//
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x,ll y,ll m){if(y<=0)return 1;ll p=power(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
vector<ll> fac((int)1e6+5);
ll nCr(ll n,ll r,ll m){
	if(r>n)return 0;
	ll a=1,b=1,i;
	return ((fac[n]%m)*power((fac[r]*fac[n-r])%m,m-2,m))%m;
}
#define Test int t;cin>>t;while(t--)
#define endl '\n'
const ll mod=(ll)1e9+7;
void solve()
{
	ll n;
	cin >> n;
	if(n==1)
	{
		cout << 0 << endl;
		return;
	}
	ll ans=0;
	vector<ll> po2,po8;
	ll temp2=1;
	ll temp8=1;
	for(ll i=0;i<=(ll)1e6;++i)
	{
		po2.push_back(temp2);
		po8.push_back(temp8);
		temp2=(temp2*2)%mod;
		temp8=(temp8*8)%mod;
	}
	for(ll i=2;i<=min(n,n);++i)
	{
		ans+=(((nCr(n,i,mod)*po8[n-i])%mod)*(po2[i]-2+mod)%mod)%mod;
		ans%=mod;
	}
	cout << ans << endl;
}
int main()
{
	fac[0]=1;
	for(int i=1;i<=(int)1e6;++i)
	{
		fac[i]=fac[i-1]*i;
		fac[i]%=mod;
	}
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//Test
	solve();
	return 0;
}


Measured memory_bytes: 26984
n = gets.to_s.to_i
rr = ll = 0
ary = []

# p '('.ord #=> 40

n.times do
  s = gets.to_s.chomp.bytes
  # nil while s = s.sub("()", "")
  l = r = 0
  s.each do |c|
    if c == 40 # p '('.ord #=> 40
      l += 1
    elsif l == 0
      r += 1
    else
      l -= 1
    end
  end
  
  if l == 0
    rr += r
  elsif r == 0
    ll += l
  else
    ary << [r, l]
  end
end

ary.sort_by!{|(r,l)| r - l }.each do |(r,l)|
  ll -= r
  break if ll < 0
  ll += l
end

puts ll == rr ? "Yes" : "No"

Measured memory_bytes: 33172
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int main(){
	string s;
	cin>>s;
	int c[3]={};
	for(char a:s) c[a-'a']++;
	sort(c,c+3);
	if(c[2]-c[0]<=1){
		puts("YES");
	}else{
		puts("NO");
	}
}


Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <string.h>
#include <math.h>
#include <map>
#include <time.h>
using namespace std;

int main(){ 
	int N, a[101], ans;
	double ave = 0., min = 1e9;
	cin >> N;
	for (int i = 0; i < N; ++i){
		cin >> a[i];
		ave += a[i];
	}

	ave /= N;

	for (int i = 0; i < N; ++i){
		if (fabs(a[i] - ave) < min){
			min = fabs(a[i] - ave);
			ans = i;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int p,x,y,u,v,n;
void SBT(int pl = 0,int ql = 1,int pr = 1,int qr = 0 ){
	int pm = pl + pr , qm = ql + qr ;
	if( pm > n || qm > n ) return ;
	if( p*qm*qm > pm*pm ){
		y=pm,x=qm;
		SBT( pm , qm , pr , qr );
	}
	if( p*qm*qm < pm*pm ){
		u=pm,v=qm;
		SBT( pl , ql , pm , qm );
	}
}
int main(){
	while(cin>>p>>n,p){
		SBT();
		cout<<u<<'/'<<v<<' '<<y<<'/'<<x<<endl;
	}
}


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

typedef int64_t Int;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

int main() {
    Int r;
    cin >> r;
    print(3 * r * r);
    return 0;
}

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

int main(){
	int N,K;
	string S;
	cin >> N >> K >> S;
	
	char t='z';
	for(int i=0;i<N;i++)t=min(t,S[i]);
	
	string R=S;
	reverse(R.begin(),R.end());
	S+=R;
	
	int m=1,c=0;
	for(int i=0;i<2*N;i++){
		if(S[i]==t)c++;
		else{
			m=max(m,c);
			c=0;
		}
	}
	
	vector<int> A;
	c=0;
	for(int i=0;i<2*N;i++){
		if(S[i]==t){
			c++;
			if(c==m)A.push_back(i);
		}else c=0;
	}
	
	if(K>20)K=20;
	if(m*pow(2,K-1)>=N){
		string ans="";
		for(int i=0;i<N;i++)ans+=t;
		cout << ans << endl;
		return 0;
	}
	
	vector<string> ans;
	
	if(K==1){
		for(auto a:A){
			if(a-m+N<2*N)ans.push_back(S.substr(a-m+1,N));
		}
	}
	else{
		for(auto a:A){
			if(a>=N-1){
				string b=S.substr(a-N+1,N);
				string br=b;
				reverse(br.begin(),br.end());
				b+=br;
				for(int k=2;k<K;k++){
					b=b.substr(m*pow(2,k-2),N);
					br=b;
					reverse(br.begin(),br.end());
					b+=br;
				}
				b=b.substr(N-m*pow(2,K-2),N);
				ans.push_back(b);
			}
		}
	}
	
	sort(ans.begin(),ans.end());
	cout << ans[0] << endl;
	return 0;
}

Measured memory_bytes: 11904
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int N,K;
  ll S;
  cin >> N >> K >> S;
  
  vector<ll> v(N);
  for(int i = 0; i < K; i++){
    v[i] = S;
  }
  for(int i = K; i < N; i++){
    if(S == 1000000000){
      v[i] = 1;
    } else { 
      v[i] = S+1;
    }
  }
  for(int i = 0; i < N; i++){
    if(i == N-1){
      cout << v[i] << endl;
    } else { 
      cout << v[i] << " ";
    }
  }
}

Measured memory_bytes: 2048
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <map>


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

  int n;
  std::int64_t k;
  std::cin >> n >> k;

  std::map<int, std::int64_t> nmap;
  for (int i = 0; i < n; i++) {
    int a, b;
    std::cin >> a >> b;
    nmap[a] += b;
  }
  std::int64_t cnt = 0;
  for (const auto& e : nmap) {
    cnt += e.second;
    if (cnt >= k) {
      std::cout << e.first << std::endl;
      break;
    }
  }

  return EXIT_SUCCESS;
}


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


int main(int argc, char** argv){
  int N;
  cin >> N;
  int h[N];
  for(int cnt0=0; cnt0<N; cnt0++) cin >> h[cnt0];
  
  int cmax = 0;
  int ans = 0;
  int pos = 0;
  while(1){
    if(pos == N-1) {
      ans += h[N-1];
      break;
    }
    if(h[pos] == 0){
      pos++;
      continue;
    }
    for(int cnt0 = pos; cnt0 < N-1; cnt0++){
      if(h[cnt0] > h[cnt0+1]){
        ans += h[cnt0] - h[cnt0+1];
        for(int cnt1 = pos; cnt1 <= cnt0; cnt1++) h[cnt1] = h[cnt0+1];
        pos = cnt0+1;
        break;
      }
      if(cnt0 == N-2) {
        ans += h[N-1];
        for(int cnt1 = pos; cnt1 < N; cnt1++) h[cnt1] = 0;
        pos++;
      }
    }
  }
  
  printf("%d", ans);
  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
using namespace std;
long long MOD = 1e9 + 7;

string S;
int N;

int main() {
	cin >> N >> S;
	int ans = 0;
	S += string(" ");
	for (int n = 1; n <= N; n++) {
		if (S[n] != S[n - 1])ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<cmath>
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e9+5;
int main()
{
    int x;
    cin>>x;
    if(x)
        cout<<0<<"\n";
    else
        cout<<1<<"\n";
    cerr<<"\nTime elapsed:"<< 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 3592
#!/usr/bin/env python3
import fractions

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f**2 <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    A, B = map(int, input().split())
    C = fractions.gcd(A,B)
    if C == 1:
        print(1)
    else:
        ans = prime_factorize(C)
        print(len(set(ans)) + 1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 5048
from math import factorial
n, m = map(int, input().split())
MOD = 1000000007
if abs(n - m) == 1:
    ans = max(n, m)
elif n == m:
    ans = 2
else:
    ans = 0
ans *= ((factorial(min(n, m)) % MOD)) ** 2
ans %= MOD
print(ans)


Measured memory_bytes: 4028
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    static Set<Integer> MEMO = new HashSet<>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();

        MEMO.add(a);
        solve(a);

        System.out.println(MEMO.size() + 1);

    }

    private static void solve(int a) {
        int tmp = 0;
        if (a % 2 == 0) {
            tmp = a / 2;
        } else {
            tmp = 3 * a + 1;
        }

        if (MEMO.contains(tmp)) {
            return;
        } else {
            MEMO.add(tmp);
        }

        solve(tmp);
    }
}


Measured memory_bytes: 21844
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define FOR(i,a,n) for(i=(a);i<(n);i++)
int MAX(int a,int b){ return a>b?a:b; }
int MIN(int a,int b){ return a<b?a:b; }
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
char s[17],t[17]="CODEFESTIVAL2016"; 
int main(void)
{
	int i,ans=0;
	scanf("%s",s);
	FOR(i,0,16){
		if(s[i]!=t[i]) ans++;
	}
	printf("%d\n",ans);
	return 0;
}
    

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
typedef pair<ll, ll> Pair;
template <class T> T input() {T t; cin>>t; return t;}
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define FIND(x,key) x.find(key) != x.end()
#define IN_RANGE_V2(v,k,x,y) (0<=x+dx[k]&&x+dx[k]<v[y].size()&&0<=y+dy[k]&&y+dy[k]<v.size())
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define PRINT_ARRAY_H(a) REPALL(__i,a) {cout<<a[__i]<<(__i != a.size()-1 ? " " : "");} newline;
#define PRINT_ARRAY_V(a) REPALL(__i,a) {cout<<a[__i]<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
#define cspace ' '
#define sspace " "
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};
//const VI dx = {1, 1, 0, -1, -1, -1, 0, 1};
//const VI dy = {0, 1, 1, 1, 0, -1, -1, -1};

void solve()
{
    ll a, b, c, d, n, m, l, r, k, x, y, z, ans = 0ll;
    string s, t;
    cin>>n;
    Yes(n>=30);
}

int main()
{
    cout<<fixed<<setprecision(20);
    int __t = 1;
    //cin>>__t;
    REP(i,__t) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3628
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	sum := 0
	maxPrice := 0
	for i := 0; i < n; i++{
		var p int
		fmt.Scan(&p)
		sum += p

		if maxPrice < p {
			maxPrice = p
		}
	}
	fmt.Println(sum - maxPrice/2)
}

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

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> vec(N);
    int S=0;
    int m=100000;
    for(int i=0; i<N; i++){
        cin >> vec[i];
        m = min(m, vec[i]);
        S += vec[i];
    }

    int count=N;
    while(S+m <= X){
        S += m;
        count++;
    }

    cout << count << endl;

}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

  	int X, A, B; cin >> X >> A >> B;
    cout << (X-A)%B << endl;
}


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

//const int INF = 1001001001;
//const ll INF = 1000000000000000000;

ll a, b, v, w, t;

int main() {
	int cnt = 1;
	rep(i,5) {
		int x;
		cin >> x;
		if (x == 0) {
			cout << cnt << endl;
			return 0;
		}
		cnt++;
	}
	return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    vector<ll> move(5);
    ll n; cin >> n;
    REP(i, 5) cin >> move[i];
    cout << (ll)ceil((double)n / *min_element(ALL(move))) + 4 << endl;
    return 0;
}

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

double rate(int water, int sugar) {
    if (water == 0 && sugar == 0) return -0.1;
    else return 100*sugar/(double)(water + sugar);
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    int answater = 0, anssugar = 0;
    for(int O = 0; O <= 30; O++) {
        int water = 0;
        int sugar = 0;
        for(int i = 1; i <= O; i++) {
            water = 100 * A * i + 100 * B * (O - i);
            if (water > F) continue;
            for(int j = 0; j <= 3000; j++) {
                sugar = j * C;
                int size = water + sugar;
                int maxsugar = (water / 100 * E);
                if (size > F) break;
                if (maxsugar < sugar) continue;
                
                sugar += D * (min(maxsugar - sugar, (F - size)) / D);
                //cout << water << " " << sugar << " " << (water / 100 * E) << endl;
                if (maxsugar < sugar) continue;
                //cout << water << " " << sugar << endl;
                double rate1 = rate(water, sugar);
                double rate2 = rate(answater, anssugar);
                if (rate1 > rate2){
                    anssugar = sugar;
                    answater = water;
                }
            }
        }
    }
    cout << answater + anssugar << " " << anssugar << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] A = new int[N];
		double total = 0.0;

		for (int i = 0; i < A.length; i++) {
			A[i] = scan.nextInt();

		}


		for(int i = 0; i<N; i++) {
			total += (double)1/A[i];
		}

		System.out.println(1/total);

	}




}


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

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << a << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

int cnt[300];

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

    string s; cin >> s;
    ll ans = 0;
    forn(i,si(s)) {
        char c = s[i];
        ans += (i - cnt[c]++);
    }

    cout << 1+ans << endl;

    return 0;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;

int main(){
  ll h,n;
  cin >> h >> n;
  vector<ll> a(n);
  ll sum=0;
  rep(i,n){ cin>>a[i]; sum+=a[i]; }
  if(sum>=h){cout << "Yes"<< endl;}else{cout << "No"<< endl;}
  
  return 0;
}

Measured memory_bytes: 1024
//g++ -std=c++14 test.cpp -o test.out
//問題URL
//https://atcoder.jp/contests/agc047/tasks/agc047_a

//参考：https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2020-08-09agc047
//     https://www.hamayanhamayan.com/entry/2020/08/10/054247
//小数をdoubleで受け取った時点で誤差が発生する、ということが考えられる。
//   →string型で受け取ると良い
//Double型の変数で、例えば整数部4桁、小数部9桁の数を10倍してlongに変換する時、
//そのままx = y*10000000000などとやると誤差のせいでうまくいかないこともある
//Double型変数を一度文字列に変換、それをlongに直してやる必要がある
 
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

LL N;
LL A[200000];

LL ans = 0;

//xがdivisorを何個約数に持つかを返す
LL numof_divisor(LL x,LL divisor){
	if(x==0) return 0;
	for(LL i=0;;i++){
		if(x%divisor==0){
			x/=divisor;
		}else return i;
	}
}

void solve(){
	//集合Aのうち、約数として2をi個、5をj個持つような数の個数をdiv25[i][j]とする
	vector<vector<LL>> div25(19,vector<LL>(19,0));
	for(int i=0;i<N;i++){
		LL d2 = min(18LL,numof_divisor(A[i],2));
		LL d5 = min(18LL,numof_divisor(A[i],5));
		div25[d2][d5]++;
	}
	for(int i=0;i<N;i++){
		LL d2 = min(18LL,numof_divisor(A[i],2));
		LL d5 = min(18LL,numof_divisor(A[i],5));
		for(int i=18-d2;i<=18;i++){
			for(int j=18-d5;j<=18;j++){
				ans += div25[i][j];
				if(i==d2 && j==d5) ans--;
			}
		}
	}
	ans/=2;
}
 
int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		string s;cin >> s;
		A[i] = 0;
		bool rest_flag = false;
		int rest = 9;
		for(int j=0;j<s.size();j++){
			if(s[j]=='.') rest_flag = true;
			else{
				A[i] = A[i]*10LL + (s[j]-'0');
				if(rest_flag) rest--;
			}
		}
		for(int j=0;j<rest;j++) A[i]*=10LL;
	}
 
    solve();

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

Measured memory_bytes: 4728
# coding: utf-8
# Here your code !

def change(List,a,b):
    temp = List[a-1]
    List[a-1] = List[b-1]
    List[b-1] = temp

w = input()
n = input()

Lot = [i for i in xrange(1,w+1)]

for j in xrange(n):
    l = map(int, raw_input().split(","))
    change(Lot,l[0],l[1])

for k in xrange(len(Lot)):
    print Lot[k]

Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
int d,dp[100005][101][2];
string k;

int main(){
	cin >> k >> d;
	dp[0][0][1] = 1;
	for(int i = 1 ; i <= k.size() ; i += 1){
		for(int j = 0 ; j < d ; j += 1){
			for(int ii = 0 ; ii < k[i-1]-'0' ; ii += 1){
				dp[i][(j+ii)%d][0] += dp[i-1][j][1];
				if(dp[i][(j+ii)%d][0] >= 1000000007){
					dp[i][(j+ii)%d][0] -= 1000000007;
				}
			}
			dp[i][(j+(k[i-1]-'0'))%d][1] += dp[i-1][j][1];
			if(dp[i][(j+(k[i-1]-'0'))%d][1] >= 1000000007){
				dp[i][(j+(k[i-1]-'0'))%d][1] -= 1000000007;
			}
			for(int ii = 0 ; ii < 10 ; ii += 1){
				dp[i][(j+ii)%d][0] += dp[i-1][j][0];
				if(dp[i][(j+ii)%d][0] >= 1000000007){
					dp[i][(j+ii)%d][0] -= 1000000007;
				}
			}
		}
	}
	cout << (long long)(dp[k.size()][0][0]+dp[k.size()][0][1]+1000000006)%1000000007 << endl;
}

Measured memory_bytes: 8448
import statistics

n = int(input())
la = []
lb = []
for i in range(n):
  a, b = map(int, input().split())
  la.append(a)
  lb.append(b)
a = statistics.median(la)
b = statistics.median(lb)
if n % 2 == 1:
  print(b - a + 1)
else:
  print(int((b - a) * 2 + 1))

Measured memory_bytes: 28944
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cassert>
using namespace std;

long long N, MOD;

long long bipow(long long n, long long m, long long mod) {
    if (m == 0) return 1;
    if (m % 2 == 0) {
        n = (n * n) % mod;
        return bipow(n, m / 2, mod) % mod;
    } else
        return (n * bipow(n, m - 1, mod)) % mod;
}

// Combination
class Comb{
    vector<long long> fact_num, fact_den;
public:
    Comb(int N){
        fact_num.resize(N+1, 0);
        fact_den.resize(N+1, 0);
        vector<long long> fact_denpow(N+1, 0);

        fact_num[0] = 1;
        for(int i=1; i<=N; i++) fact_num[i] = (fact_num[i-1] * i) % MOD;

        for(int i=0; i<=N; i++) fact_denpow[i] = bipow(i, MOD-2, MOD);
        fact_den[0] = 1;
        for(int i=1; i<=N; i++) fact_den[i] = (fact_den[i-1] * fact_denpow[i]) % MOD;
    }
    long long calc(int m, int n){
        assert(m >= n);
        return ((fact_num[m] * fact_den[n]) % MOD * fact_den[m-n]) % MOD;
    }
};

long long dp[3333][3333];

int main(){
    cin >> N >> MOD;
    Comb comb(N);

    for(int i=0; i<=3000; i++)
        dp[i][0] = 1;

    for(int i=1; i<=3000; i++){
        for(int j=1; j<=i; j++){
            dp[i][j] = (dp[i-1][j-1] + ((j+1)*dp[i-1][j]) % MOD) % MOD;
        }
    }

    long long ans = 0;
    for(int i=0; i<=N; i++){
        long long tmp = 0;
        for(int j=0; j<=i; j++){
            tmp += (dp[i][j] * bipow(2, (N-i)*j, MOD)) % MOD;
            tmp %= MOD;
        }
        tmp = (tmp * bipow(2, bipow(2, N-i, MOD-1), MOD)) % MOD;
        tmp = (tmp * comb.calc(N, i)) % MOD;
        if(i % 2)
            tmp = (MOD - tmp) % MOD;
        ans = (ans + tmp) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 78464
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
using namespace std;

class Union_Find_Weight{
private:
    vector<int> par;
    vector<int> rank;
    vector<int> differ;
public:
    Union_Find_Weight(int n){
        rep(i,n){
            par.push_back(i);
            rank.push_back(0);
            differ.push_back(0);
        }
        
    }
    int find(int x){
        if(par.at(x)==x) return x;
        else{
            int f=find(par.at(x));
            differ.at(x)+=differ.at(par.at(x));
            return par.at(x)=f;
        }
    }
    int weight(int x){
        find(x);
        return differ.at(x);
    }
    int diff(int x, int y){
        return weight(y)-weight(x);
    }
    void unite(int x, int y, int w){
        w+=weight(x); w-=weight(y);
        x=find(x); y=find(y);
        if(x==y) return;
        if(rank.at(x)<rank.at(y)){
            swap(x, y); w=-w;
        }
        if(rank.at(x)==rank.at(y)) rank.at(x)++;
        par.at(y)=x;
        differ.at(y)=w;
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
};

signed main(){
    int n,m; cin>>n>>m;
    Union_Find_Weight uni(n);
    rep(i,m){
        int l,r,d; cin>>l>>r>>d;
        l--; r--;
        if(uni.same(l, r)){
            if(uni.diff(l, r)!=d){
                cout<<"No"<<endl;
                return 0;
            }
        }else{
            uni.unite(l, r, d);
        }
    }
    cout<<"Yes"<<endl;
}

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

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

//INSERT ABOVE HERE
signed main(){
  Int n,k;
  cin>>n>>k;
  vector<Int> v(n),w(n);
  for(Int i=0;i<n;i++) cin>>v[i]>>w[i];

  const Int INF = 1e18;
  vector<Int> dp(n*111+1,INF);
  dp[0]=0;
  for(Int i=0;i<n;i++)
    for(Int j=n*111-v[i];j>=0;j--)
      chmin(dp[j+v[i]],dp[j]+w[i]);
  
  Int ans=0;
  for(Int i=0;i<=n*111;i++)
    if(dp[i]<=k) ans=i;

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



Measured memory_bytes: 3180
#include <cstdio>
#include <map>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const ll maxn=1e18+5;
map <ll,ll> f;
ll Fc(ll x){
	if(f[x])return f[x];
	return f[x]=(Fc(x>>1)+Fc((x-1)>>1)+Fc((x-2)>>1))%mod;
}
int main(){
	ll n;
	scanf("%lld",&n);
	f[0]=1;f[1]=2;
	printf("%lld\n",Fc(n));
	return 0;
}

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

#define ll long long int
#define ull unsigned long long int
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


using namespace std;

const int INF = 1e9 + 7;
const int N = 1e5+5;


int main() {
	
	IO;
	
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	
	string ans, ur, ld, mdf="L", mof = "R";
	
	while (ty > sy) {
		ur += 'U';
		ld += 'D';
		sy++;
	}
	mdf += ur + 'U';
	mof += ld + 'D';
	while (tx > sx) {
		ur += 'R';
		ld += 'L';
		mdf += 'R';
		mof += 'L';
		sx++;
	}

	mdf += "RD";
	mof += "LU";
	ans += ur + ld + mdf + mof;
	
	cout << ans << endl;
		
		

}



Measured memory_bytes: 3640
#pragma GCC optimize ("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

//smaller names
#define int long long
#define double long double
#define Int signed
#define vi vector<int>
#define vvi vector<vi>
#define vd vector<double>
#define vvd vector<vd>
#define pii pair<int, int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define mii map<int, int>
#define unordered_map gp_hash_table

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

#define F first
#define S second

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(),v.end()

const int INF = 1e9;
const double EPS = 1e-9;
const double PI = acosl(-1);

//order_of_key(k) - number of elements e such that func(e, k) returns true, where func is less or less_equal
//find_by_order(k) - kth element in the set counting from 0

typedef tree <
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update
> 
ordered_set;

typedef tree <
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update
>
ordered_multiset;

const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const int maxa = 1e6 + 5;
const int logmax = 25;

//fast exponentiation

template <typename T>
T power (T a, int n = 1, T id = 1) {
    T ans = id;
    while(n) {
        if(n & 1) ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

//custom hash

struct custom_hash {
    // http://xorshift.di.unimi.it/splitmix64.c
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int sumdigs (int n) {
    int ans = 0;
    while (n) {
        ans += n % 10;
        n /= 10;
    }
    return ans;
}


void solve() {
    string s , t;
    cin >> s >> t;
    int n = s.size();
    int ans = 0;
    rep(i, n) ans += s[i] != t[i];
    cout << ans << endl;
}

signed main(){
    fastio;
    cout << setprecision(6) << fixed;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 3736
n = int(input())
s = input()

top_used = set()
used = set()
ans = 0
for i in range(n - 1):
    if int(s[i]) in top_used:
        continue
    top_used.add(int(s[i]))
    for j in range(i + 1, n):
        top = s[i] + s[j]
        if top not in used:
            ans += len(set(s[j + 1:]))
            used.add(top)


print(ans)


Measured memory_bytes: 82864
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void)
{
    int n, time, i;
    long int ans=0;
    vector<int> t(200000);
    
    cin >> n >> time;
    for(i=0;i<n;i++){
        cin >> t.at(i);
    }
    
    for(i=0;i<n-1;i++){
        ans=ans+min(t.at(i+1)-t.at(i), time);
       
    }
    ans=ans+time;
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

constexpr int cm = 1<<17;
char cn[cm], *ci = cn + cm, ct;

inline char readchar() {
	if (ci - cn == cm) {
    fread(cn, 1, cm, stdin); 
    ci = cn;
  }
	return *ci++;
}
inline int readint() {
	int ret = 0;
	if (ci - cn + 16 > cm) {
    while ((ct = readchar()) >= '0') {
      ret = (ret<<3) + (ret<<1) + ct - '0';
    }
  } else {
    while ((ct = *ci++) >= '0') {
      ret = (ret<<3) + (ret<<1) + ct - '0';
    }
  }
	return ret;
}

//int cnt[202020];
template<typename T> void fastout(T &n) {
  T N = n, rev, count = 0;
  rev = N;
  if (N == 0) {
    putchar_unlocked('0');
    putchar_unlocked('\n');
    return;
  }
  while ((rev % 10) == 0) { 
    ++count; rev /= 10;
  }
  rev = 0;
  while (N != 0) { 
    rev = (rev << 3) + (rev << 1) + N % 10;
    N /= 10;
  }
  while (rev != 0) { 
    putchar_unlocked(rev % 10 + '0');
    rev /= 10;
  }
  while (count--) putchar_unlocked('0');
  putchar_unlocked('\n');
}

int main(){
  int N = readint();
  vector<int> t(N), x(N), y(N);
  for (int i = 0; i < N; ++i) {
    t[i] = readint(); x[i] = readint(); y[i] = readint();
  }

  for (int i = 0; i < N; ++i) {
    if (t[i] % 2 == 0){
      if (abs(x[i]) + abs(y[i]) > t[i] || (abs(x[i]) + abs(y[i])) % 2 == 1){
        cout << "No" << '\n';
        return 0;
      }
    }
    else {
      if (abs(x[i]) + abs(y[i]) > t[i] || (abs(x[i]) + abs(y[i])) % 2 == 0){
        cout << "No" << '\n';
        return 0;
      }
    }
   }

  cout << "Yes" << '\n';

  return 0;
}




Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
#define rep(i,s,t) for(ll i=s ; i<t ; i++)
typedef pair<ll,ll> P;
const int max_n = 1e5;
const ll mod = 1e9+7;
int main(){
  ll n;  cin >> n;
  map<ll,ll> ma;
  vector<ll> v(n);
  rep(i,0,n){
    cin >> v[i];
    ma[v[i]]++;
  }
  map<ll,ll> ans;
  ll summ = 0;
  for(auto ite=begin(ma);ite!=end(ma);ite++){
    summ += ((ite->se)*((ite->se)-1))/2;
  }
  rep(i,0,n){
    ll x = ma[v[i]];
    cout << max(0LL,summ-(x*(x-1))/2 + ((x-1)*(x-2))/2) << " ";
  }
  return 0;
}


Measured memory_bytes: 11008
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define vi vector<int>
#define fi first
#define se second 
#define mp make_pair
#define show(x) cout<<#x<<" = "<<x<<endl;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define LL long long 
#define pi acos(-1)
#define fin freopen("in","r",stdin);
const int inf=0x3f3f3f3f;
const double eps=1e-8;
#define zero(x) (((x)>0?(x):-(x))<eps)
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
typedef long long ll;
const int maxn = 1000005, mod = 1e9+7;
#define fin freopen("in","r",stdin);
int a[maxn],n;
int main(){
	int mx=0,ans=0;
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>a[i];
		if(a[i]>=mx){
			mx=a[i];
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a) ((a).begin(),(a).end())
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
 
ll dp[330][330];
ll sum[330][330];
 
inline ll cost(ll x, ll y){
  ll res = 0, k = 1, c = 0;
  for(;;){
    if(x<k && y<k)break;
    ll xi = (x/k)%10LL, yi = (y/k)%10LL;
    res += xi*yi+c;
    if(xi+yi+c>=10LL)c = 1;
    else c = 0;
    k *= 10LL;
  }
  res += c;
  return res;
}
 
int main(){
  int n;
  ll a[330];
  cin >> n;
  rep(i,n)cin >> a[i];
   
  rep(i,n){
    sum[i][i] = 0;
    for(int j=i;j<n;j++){
      sum[i][j+1] += sum[i][j] + a[j];
    }
  }
 
  memset(dp,-1,sizeof(dp));
  rep(i,n)dp[i][i+1] = 0;
 
  for(int len=2;len<=n;len++){
    rep(l,n){
      int r = l+len;
      if(r>n)break;
 
      ll tmp = 1e18;
      for(int k=l+1;k<r;k++){
    tmp = min(tmp, dp[l][k] + dp[k][r] + cost(sum[l][k],sum[k][r]));
      }
      dp[l][r] = tmp;
    }
  }
 
  cout << dp[0][n] << endl;
}

Measured memory_bytes: 2800
#include <iostream>
        #include <vector>
        #include <algorithm>
        #include <numeric>
         
        using namespace std;
         
        int main() {
          long long n, k;
          cin >> n >> k;
          
          vector<long long> v(k);
          vector<long long> dv(k-1);
          for (int i=0;i<k;i++){
            cin >> v[i];
          }
          std::sort(v.begin(),v.end(),std::greater<int>());
          long long max = *std::max_element(v.begin(), v.end());
          long long min = *std::min_element(v.begin(), v.end());
          
          long long suml = max - min;
          long long suma=0;
           
          if(k==1 || k<=n){
            cout << 0 << endl;
          } else {
            for(int i=0;i<k-1;i++){
              dv[i]=v[i]-v[i+1];
            }
            std::sort(dv.begin(),dv.end(),std::greater<int>());
            if(n==1){
              cout << suml << endl;
            } else {
              for(int i=0;i<n-1;i++){
              	suma += dv[i];
              }
              cout << suml - suma << endl;
            }
          }
          return 0;
        }

Measured memory_bytes: 1792
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(char &c){
  int i;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
char S[102];
int N;
int main(){
  N = rd(S);
  wt_L(S[0]);
  wt_L(N-2);
  wt_L(S[N-1]);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190822-2

// --- original code ---
// char S[102];
// int N;
// {
//   rd(S@N);
//   wtN(S[0], N-2, S[N-1], '\n');
// }


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(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 mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

void merge(vector<ll>& a,const vector<ll>& b){
  assert(a.size()==3&&b.size()==3);
  ll a0=(a[0]*b[0]%mod)%mod;
  ll a1=(a[1]*b[0]%mod+a[0]*b[1]%mod)%mod;
  ll a2=(a[2]*b[0]%mod+a[2]*b[1]%mod+a[0]*b[2]%mod+a[1]*b[2]%mod+a[1]*b[1]%mod+a[2]*b[2]%mod)%mod;
  a[0]=a0; a[1]=a1; a[2]=a2;
}

int N;
vector<int> g[200010];
deque<vector<ll> > dp[200010];
int crtidx=0;
ll sz[200010];

int dfs(int v,int d){
  sz[d]++;
  vector<int> idxs;
  vector<ll> rootelem;
  rootelem.push_back(1); rootelem.push_back(1); rootelem.push_back(0);
  for(int nv : g[v]){
    int idx=dfs(nv,d+1);
    idxs.push_back(idx);
  }
  if(idxs.size()==0){ // leaf
    dp[crtidx].push_front(rootelem);
    return crtidx++;
  }
  sort(all(idxs),[=](const int& a,const int& b){ return dp[a].size() > dp[b].size(); });
  int base=idxs[0];

  repl(i,1,idxs.size()){
    rep(j,dp[idxs[i]].size()){
      merge(dp[base][j],dp[idxs[i]][j]);
    }
    if(i>1)dp[idxs[i]].clear();
  }
  if(idxs.size()>1){
    rep(j,dp[idxs[1]].size()){
      (dp[base][j][0]+=dp[base][j][2])%=mod;
      dp[base][j][2]=0;
    }
    dp[idxs[1]].clear();
  }

  dp[base].push_front(rootelem);
  return base;
}

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

int main(){
  cin>>N;
  rep(i,N){
    int P;
    cin>>P;
    g[P].push_back(i+1);
  }
  N++;
  int base=dfs(0,0);
  ll res=0;
  rep(i,dp[base].size()){
    (res+=(dp[base][i][1]*mod_pow(2,N-sz[i]))%mod)%=mod;
  }
  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 243956
#include<stdio.h>
int main(void){
	int H,W,i,j;
	while(1){
		scanf("%d %d",&H,&W);
		if(H==0 && W==0)
		break;
		
		for(i=1; i<=H; i++){
			for(j=1; j<=W; j++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 572
use itertools::{iproduct, izip, Itertools};
use proconio::input;

const WIDTH: usize = 41;

trait OrdTools: Ord + Clone + Sized {
    fn chmin(&mut self, x: Self) {
        *self = std::cmp::min(self.clone(), x);
    }
    fn chmax(&mut self, x: Self) {
        *self = std::cmp::max(self.clone(), x);
    }
}

impl<T: Ord + Clone + Sized> OrdTools for T {}

fn main() {
    input!(n: usize, orig: [u64; n]);
    let make_seq = |x| (0..WIDTH).map(|i| (x >> i & 1) as usize).collect_vec();
    let a = make_seq(orig[0]);
    let b = make_seq(orig[1]);
    let c = make_seq(orig.iter().skip(2).fold(0, |x, y| x ^ y));
    let dp = izip!(a, b, c).enumerate().fold(
        {
            let mut dp = vec![vec![[std::u64::MAX; 2]; 2]; WIDTH + 1];
            dp[0][0][0] = 0;
            dp
        },
        |mut dp, (i, (x, y, z))| {
            iproduct!((0..2), (0..2), (0..2))
                .filter(|&(j, k, _)| x ^ y ^ z ^ j ^ k == 0)
                .for_each(|(j, k, l)| {
                    let crr = dp[i][j][k];
                    if crr != std::u64::MAX {
                        let nj = (x < j + l) as usize;
                        let nk = (2 <= y + l + k) as usize;
                        dp[i + 1][nj][nk].chmin(crr + l as u64 * (1 << i));
                    }
                });
            dp
        },
    );
    let ans = *dp[WIDTH]
        .iter()
        .map(|v| v.iter().min().unwrap())
        .min()
        .unwrap();
    println!("{}", if orig[0] <= ans { -1 } else { ans as i64 });
}


Measured memory_bytes: 2192
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define endl        "\n"
#define P           pair<int, int>
#define dint        long double

const int mod = 998244353;

inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }

int modpow(int a, int b) {
    if(a == 0 || a == 1 || b == 1) return a;
    int ans = 1;
    while(b) {
        if(b%2) ans = mul(ans, a);    
        b /= 2; a = mul(a, a);
    }   return ans;
}

void solve() {
    int n; cin >> n;
    int m; cin >> m;
    int tot = 0;
    for(int i=0; i<m; i++) {
        int x; cin >> x;
        tot += x;
    }
    n -= tot;
    if(n < 0) {
        cout << -1 << endl;
    }
    else {
        cout << n << endl;
    }
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;

    while(T--) {
        solve();
    }
    return 0;

}



Measured memory_bytes: 3648
#define _USE_MATH_DEFINES
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>
#include<climits>
#include<numeric>
#include<cmath>
#include<cstring>
#include<deque>
#include<map>
#include<iomanip>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;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 VSORT(v) sort(v.begin(), v.end());
#define VE vector<int>
#define VEP vector<pair<int,int>>
#define llong long long
#define pb(a) push_back(a)
using namespace std;
const vector<VE> DIR{ {-1,0},{1,0},{0,-1},{0,1} };
const int MOD = 1000000007;
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}
template<class T>
int dp2csv(const vector<vector<T>>& dp, const string fname);

int main() {
	int n;
	cin >> n;
	vector<llong> len(n);
	llong all_len = 0;
	REP(i, n) {
		cin >> len[i];
		all_len += len[i];
	}
	llong now_len = 0;
	REP(i, n) {
		now_len += len[i];
		if (now_len > all_len / 2) {
			int ans = min(abs(now_len * 2 - all_len),abs((now_len - len[i]) * 2 - all_len));
			cout << ans << endl;
			break;
		}
	}
	return 0;
}
template<class T>
int dp2csv(const vector<vector<T>>& dp, const string fname) {
	ofstream ofs(fname);
	if (ofs.fail()) { cerr << "cannot open file. :" + fname << endl; return -1; }
	for (auto dp_row : dp) {
		for (auto dp_cell : dp_row) {
			ofs << dp_cell << ",";
		}
		ofs << endl;
	}
	ofs.close();
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_D 20

using namespace std;

int n,K;
bool vis[MAX_D];

bool check(int x)
{
	while(x)
	{
		if(vis[x%10]) return false;
		x/=10;
	}
	return true;
}

int main()
{
	scanf("%d%d",&n,&K);
	int x;
	for(int i=1;i<=K;i++)
	{
		scanf("%d",&x);
		vis[x]=true;
	}
	while(!check(n)) n++;
	printf("%d\n",n);
}


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

using namespace std;

#define ll           long long int 
#define endl         '\n'

static const int maxn = 2e5 + 5;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	int a, b;
	cin >> a >> b;
	string s, t;
	while (s.size() < b) {
		s.push_back(static_cast <char> (a + '0'));
	}
	while (t.size() < a) {
		t.push_back(static_cast <char> (b + '0'));
	}
	cout << min(s, t) << endl;
}

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

#define rep(x, n) for(int i = x; i < (n); ++i)

using namespace std;
using ll = long long;

int main(void)
{
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(0, n) cin >> a[i];

  for (int i = k; i < n; ++i) {
    if (a.at(i) > a.at(i - k)) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 4776
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <tuple>
#include <map>
using namespace std;
typedef long long ll;

int main() {
    string s, t;
    cin >> s >> t;

    int a[100010], b[100010];
    a[0] = b[0] = 0;
    for (int i = 0; i < s.size(); i++) {
        a[i + 1] = (a[i] + (s[i] - 'A' + 1)) % 3;
    }
    for (int i = 0; i < t.size(); i++) {
        b[i + 1] = (b[i] + (t[i] - 'A' + 1)) % 3;
    }

    int q;
    cin >> q;
    while (q--) {
        int sl, sr, tl, tr;
        cin >> sl >> sr >> tl >> tr;
        cout << ((a[sr] - a[sl - 1] + 3) % 3 == (b[tr] - b[tl - 1] + 3) % 3 ? "YES" : "NO") << endl;
    }

}

Measured memory_bytes: 1792
#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

int main() {
    ll n;   cin >> n;
    ll *a = new ll[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];

    ll cnt = (a[0] < 0) ? 1 : 0;

    ll ans = abs(a[0]), m = abs(a[0]);
    for (int i = 1; i < n; i++) {
        if (abs(a[i]) < m)
            m = abs(a[i]);
        ans += abs(a[i]);
        if (a[i] < 0)
            cnt++;
    }

    if (cnt%2)
        cout << ans - 2*m << endl;
    else 
        cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define long long long int
using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<vector<long>> d(n + 1, vector<long>(5, LLONG_MIN));
    d[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 5; j++) {
            int k = (i + 1) / 2 - j;
            if (k < 0) continue;
            {
                // don't take i-th
                int ii = i - 1;
                int jj = (ii + 1) / 2 - k;
                if (jj >= 0 && jj < 5) {
                    if (d[ii][jj] != LLONG_MIN) {
                        d[i][j] = max(d[i][j], d[ii][jj]);
                    }
                }
            }
            if (k > 0) {
                // take i-th, don't take i-1-th
                int ii = i == 1 ? 0 : i - 2;
                int jj = (ii + 1) / 2 - (k - 1);
                if (jj >= 0 && jj < 5) {
                    if (d[ii][jj] != LLONG_MIN) {
                        d[i][j] = max(d[i][j], d[ii][jj] + a[i - 1]);
                    }
                }
            }
        }
    }
    int k = n / 2;
    int j = (n + 1) / 2 - k;
    cout << d[n][j];

    return 0;
}

Measured memory_bytes: 18028
# キャンディーとN人の子供

mod = 10**9 + 7
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


def rev(X):
    return pow(X, mod-2, mod)


pow_sum = [[B[i]-A[i]+1 for j in range(C+1)] for i in range(N)]
pow_table = [[1 for j in range(401)] for i in range(401)]
for i in range(401):
    for j in range(401):
        pow_table[i][j] = pow(i, j, mod)

for cnt in range(C):
    for i in range(N):
        pow_sum[i][cnt+1] = 0
        for j in range(A[i], B[i]+1):
            pow_sum[i][cnt+1] += pow_table[j][cnt+1]
        pow_sum[i][cnt+1] %= mod

ans_dp = [[0 for i in range(C+1)] for j in range(N+1)]
# ans_dp[x][y] = 0<=x<=N,0<=y<=C の場合のdp
ans_dp[0][0] = 1
for n in range(1, N+1):
    # ans_dp[n]の更新
    for c in range(C+1):
        # ans_dp[n][c]の更新
        for k in range(c+1):
            ans_dp[n][c] += ans_dp[n-1][k]*pow_sum[n-1][c-k]
        ans_dp[n][c] %= mod
print(ans_dp[N][C] % mod)

Measured memory_bytes: 90876