akhauriyash/Code-Regression huggingface dataset:
i = int(input())

for j in range(1, i + 1) :
    tmpJ = int(j // 10)
    isFinish = False

    if j % 3 == 0 :
        print(' {}'.format(j), end = '')
    elif (j % 10 == 3) :
        print(' {}'.format(j), end = '')
    elif tmpJ % 10 == 3 :
        print(' {}'.format(j), end = '')
    elif tmpJ != 0 :
        tmpJ //= 10
        while tmpJ != 0 and (not isFinish) :
            if tmpJ % 10 == 3 :
                print(' {}'.format(j), end = '')
                isFinish = True
            tmpJ //= 10
print()

Measured memory_bytes: 7900
#include <iostream>
#include <algorithm>

int main()
{
	int n;
	long long int h;
	std::pair<long long int, long long int> a[200010];
	
	std::cin >> n >> h;
	
	for (int i = 0; i < n; ++i)
	{
		long long int x;
		std::cin >> x;
		
		a[i * 2].first = x;
		a[i * 2].second = 0;
		
		std::cin >> x;
		a[i * 2 + 1].first = x;
		a[i * 2 + 1].second = 1;
	}
	
	std::sort(a, a + (2 * n));
	int count = 0;
	
	for (int i = n * 2 - 1; i >= 0; --i)
	{
		if (h <= 0)
		{
			std::cout << count;
			return 0;
		}
		
		if (a[i].second == 1)
		{
			h -= a[i].first;
			++count;
		}
		else
		{
			count += h / a[i].first;
			if (h % a[i].first != 0)
				++count;
			
			std::cout << count;
			return 0;
		}
	}
}

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

typedef long long int ll;
typedef pair <ll, ll> pll;

const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const ll Inf = 1LL << 62;

int main() {
	int n;
	cin >> n;
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = i; j <= n; j+=i) {
			ans += j;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

const double pi = 3.141592653589793;
// -------------------------------------------------------
ll A, B;

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) {
    res[n]++;
  }
  return res;
}

int main() {
  cin >> A >> B;
  auto a = prime_factor(A);
  auto b = prime_factor(B);

  ll ans = 1;
  for (auto e : a) {
    if (b[e.first] > 0) {
      ++ans;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int a, b, c;
	int total;
	int j;
	
	j = a, b, c;
	j<=13;
	j>=1;
	
	scanf("%d %d %d", &a, &b, &c);
	total = a + b +c;
	
	if(total>=22){
	printf("bust\n");
	}
	else{
	printf("win\n");
	}
	return 0;
}

Measured memory_bytes: 3164
#include <iostream>

using namespace std;

int main(){
    int cnt = 0;
    string s;
    cin >> s;
    if (s[0] == '1')    cnt++;
    if (s[1] == '1')    cnt++;
    if (s[2] == '1')    cnt++;
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
import itertools
results = []

def comb_gen(n):
    combs = []
    comb = []

    mb = 2 ** n
    for i in range(mb - 1):
        bi = bin(i + 1)[2:]
        con = "0" * (n - len(bi)) + str(bin(i + 1)[2:])
        #print(con)
        sum = 0
        for j in range(len(con)):
            if con[j] == "1" and sum < 3:
                comb.append(j + 1)
                sum += 1
        if len(comb) == 3 and comb not in combs:
            #print(comb)
            combs.append(comb)
        con = ""
        comb = []
    return combs

def combgen(n):
    nums = [i for i in range(1, n+1)]
    combs = []
    for i in itertools.combinations(nums, 3):
        combs.append(i)
    return combs

def sum_chk(combs, x):
    combs = combs
    res = 0
    for i in range(len(combs)):
        #print(combs[i])
        if sum(combs[i]) == x:
            #print(combs[i])
            res += 1
    return res

#print(comb_gen(5))


while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    combs = combgen(n)
    result = sum_chk(combs, x)
    results. append(result)

for i in range(len(results)):
    print(results[i])


Measured memory_bytes: 31268
#include <iostream>
#include <algorithm>

using namespace std;

int n, m, a[100], b[100];

main(){
  cin >> n >> m;
  for(int i=0;i<m;i++) cin >> a[i] >> b[i];
  int p = 1, ans = 0;
  while(p <= n){
    int valM = -1;
    for(int i=0;i<m;i++) if(a[i] <= p) valM = max(valM, b[i]);
    if(valM < p){
      cout << "Impossible" << endl;
      return 0;
    }else p = valM + 1;
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1164
while True:
    L=int(input())
    if L==0:
        break
    S=0
    B=0
    for i in range(1,13):
        M,N=map(int,input().split())
        A=M-N
        S+=A
        if S>=L and B==0:
            B=i
    if B>0:
        print(B)
    else:
        print("NA")
            


Measured memory_bytes: 5612
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define ll long long
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, n+1)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define rwhole(x) (x).rbegin(), (x).rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define P pair<int, int>
#define debug(var) cerr << "[" << #var << "] " << var << '\n'
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pr(s) cout << (s) << '\n'
ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;
const ll INFll = 1E+18;


ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin >> n;
    n *= 2;
    /*
    int z[10] = {1, 3, 2, 7, 4, 3, 6, 15, 8, 19};
    if (n<=10) {
        pr(z[n-1]);
        return 0;
    }
    */
    map<ll, ll> mp;
    ll now = n;
    for (ll i=2; i*i<=now; i++) {
        if (now%i==0) {
            while (now%i==0) {
                now /= i;
                mp[i]++;
            }
        }
    }
    if (now>1) mp[now]++;
    int fs = mp.size();
    vector<ll> factors(fs);
    int index = 0;
    for (auto m: mp) {
        factors[index] = m.first;
        index++;
    }
    ll k = INFll;
    
    //mp[2]++;
    
    rep(i, 1<<fs) {
        vector<bool> vb(fs);
        ll a = 1, b = 1;
        rep(j, fs) {
            if (i>>j&1) {
                rep(ii, mp[factors[j]]) a *= factors[j];
            }
            else {
                rep(ii, mp[factors[j]]) b *= factors[j];
            }
        }
        //const int mod = y;
        vector<ll> r, m;
        m.pb(a); m.pb(b);
        r.pb(0); r.pb(-1);
        auto c = crt(r, m);
        ll res = c.first;
        debug(c.first); debug(c.se);
        if (res<=0) res += c.se;
        chmin(k, res);
    }

    
    
    pr(k);
    return 0;
}


Measured memory_bytes: 3664
from collections import Counter

def solver():
    H, W, M = map(int, input().split())

    retu = Counter()
    gyo = Counter()

    ipt = [set() for _ in range(H)]

    for _ in range(M):
        a, b = map(int, input().split())
        retu[a-1] += 1
        gyo[b-1] += 1
        ipt[a-1].add(b-1)

    rm = retu.most_common()
    rmm = rm[0][1]
    gm = gyo.most_common()
    gmm = gm[0][1]

    for r in rm:
        if r[1] < rmm:
            break
        for g in gm:
            if g[1] < gmm:
                break

            if g[0] not in ipt[r[0]]:
                return rmm+gmm
    
    return rmm+gmm-1

print(solver())


Measured memory_bytes: 237872
function Main(input){
  var X = parseInt(input);
  var keta = Math.floor(Math.log10(X)) + 1;

  var fX = 0;
  var x = X;
  for(var i = 0; i < keta; i++){
    fX += x % 10;
    x = Math.floor(x / 10);
  }

  if(X % fX === 0){
    console.log('Yes');
  } else {
    console.log('No');
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7752
input_num = input().split()
input_str = input()

str_len = int(input_num[0])
change_num = int(input_num[1])

change_char = input_str[change_num -1]

change_char.lower()
print(input_str[:change_num -1] + change_char.lower() + input_str[change_num :]) 

Measured memory_bytes: 2940
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    ll ans = 0;
    REP(i, 1, N + 1) {
        if (i % 3 != 0 && i % 5 != 0) ans += ll(i);
    }

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

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

int main(){
    int sum = 0;
    int n; cin >> n;

    for(int i = n; i > 0; i /= 10){
        sum += i % 10;
    }

    put((n % sum == 0 ? "Yes":"No"));
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define ll int
#define bits_count __builtin_popcountll
#define endl '\n'
#define double long double
#define ld double
#define FOR(i,a,n) for (ll i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define MINUS(a) memset((a),-1,sizeof((a)))
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
#define sz(x) (ll)x.size()
#define pr pair<int,int>
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }
    
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash { int operator()(int x) const { return x ^ RANDOM; }};
// cc_hash_table<int, int, hash<int>> cnt;

const int MAXN = 2e5 + 10;
const int MAXA = 1e6 + 10;
int a[MAXN];
int freq[MAXA];
int cnt[MAXA];

void solve(){
    int n; cin>>n;
    FOR(i,1,n){
        cin>>a[i];
        freq[a[i]]++;
    }

    FOR(i,1,MAXA-1){
        for(int j=i;j<MAXA;j+=i){
            cnt[j] += freq[i];
        }
    }

    int ans = 0;
    FOR(i,1,n){
        if(cnt[a[i]] == 1) ans++; 
    }

    cout<<ans<<endl;
}
    
signed main(){
    
    FastRead;     

    
    int t = 1; 
    // cin>>t;
    FOR(i,1,t){
        // cout<<"Case #"<<i<<": ";
        solve();
    }
}
    




Measured memory_bytes: 20784
N = int(input())
ps = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 }
bs = []
for n in range(1, N+1):
  a = n
  while a > 1:
    prime = True
    for p in ps:
      if a%p == 0:
        prime = False
        bs.append(p)
        a = a//p
    if prime:
      bs.append(a)
      a = 1
#print(bs)
ps2 = set(bs)
r = 1
for p in ps2:
  c = bs.count(p)
  r = r*(c+1)%1000000007
print(r)


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	bool S[13] = {false}, H[13] = {false}, C[13] = {false}, D[13] = {false};
	char c;
	int x;

	for (int i = 0; i < n; ++i)
	{
		cin >> c >> x;
		if(c == 'S') S[x-1] = true;
		else if (c == 'H') H[x-1] = true;
		else if (c == 'C') C[x-1] = true;
		else D[x-1] = true;
	}
		
	for (int i = 0; i < 13; i++)
		if(!S[i])
			cout << "S " << i+1 << endl;

	for (int i = 0; i < 13; i++)
		if(!H[i])
			cout << "H " << i+1 << endl;

	for (int i = 0; i < 13; i++)
		if(!C[i])
			cout << "C " << i+1 << endl;

	for (int i = 0; i < 13; i++)
		if(!D[i])
			cout << "D " << i+1 << endl;
	return 0;
}

Measured memory_bytes: 3064
#include<stdio.h>

 int main(){
   int n,k;
   scanf("%d %d",&n,&k);
   int p[n+1];
   for(int i=1;i<=n;i++)scanf("%d",&p[i]);
   
   for(int i=1;i<=n-1;i++){
     for(int j=i+1;j<=n;j++){
       if(p[i]>=p[j]){
         int s=p[i];
         p[i]=p[j];
         p[j]=s;
       }
     }
   }
   int ans=0;
   for(int i=1;i<=k;i++){
     ans+=p[i];
   }
   printf("%d",ans);
   return 0;
 }


Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n,m,x;
  cin >> n >> m >> x;
  int k[n][m];
  int c[n];
  rep(i,n){
    cin >> c[i];
    rep(j,m)cin >> k[i][j]; 
  }
  int ans=1000000000;
  int u=(1<<n);
  rep(i,u){
    int an=0;
    int y[m];
    rep(o,m)y[o]=0;
    rep(j,n){
      if(i&(1<<j)){
        an+=c[j];
        rep(q,m)y[q]+=k[j][q];
      }
    }
    int l=0;
    rep(z,m){
      if(y[z]<x)l++;
    }
    if(l==0){
      ans=min(ans,an);
    }
  }
  if(ans>=1000000000)cout << -1 << endl;
  else cout << ans << endl;
}

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

int main() {
    int H, W;
    string a;
    cin >> H >> W;
    rep(i, W + 2){
        cout << "#";
    }
    cout << endl;
    rep(i, H){
        cin >> a;
        cout << "#";
        rep(j, W){
            cout << a[j];
            }
        cout << "#" << endl;
        }
    rep(i, W + 2){
        cout << "#";
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <unordered_map>
#include <queue>
#include <set>
using namespace std;

int main(){
    int h, w;
    cin >> h >> w;
    string s;
    int a[h][w], b[h][w], c[h][w];
    for (int i = 0; i < h; i++){
        cin >> s;
        for (int j = 0; j < w; j++){
            if (s[j] == '#') a[i][j] = 0;
            else a[i][j] = 1;
        }
    }
    for (int i = 0; i < h; i++){
        int count = 0;
        for (int j = 0; j < w; j++){
            if (a[i][j] == 1) {
                count++;
            }
            else {
                b[i][j] = 0;
                for (int k = j - 1; k >= max(j - count, 0); k--){
                    b[i][k] = count;
                }
                count = 0;
            }
        }
        if (count){
            for (int k = w - 1; k >= max(w - count, 0); k--){
                b[i][k] = count;
            }
        }
    }
    for (int j = 0; j < w; j++){
        int count = 0;
        for (int i = 0; i < h; i++){
            if (a[i][j]) {
                count++;
            }
            else {
                c[i][j] = 0;
                for (int k = i - 1; k >= max(i - count, 0); k--){
                    c[k][j] = count;
                }
                count = 0;
            }
        }
        if (count){
            for (int k = h - 1; k >= max(h - count, 0); k--){
                c[k][j] = count;
            }
        }
    }
    int result = 0;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            result = max(result, b[i][j] + c[i][j] - 1);
        }
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 47104
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, K = read_ints()
R, S, P = read_ints()
T = read()[:-1]

points = {
    'r': P,
    's': R,
    'p': S
}

# hands = {
#     'r': 'p',
#     's': 'r',
#     'p': 's'
# }

handsls = []

ans = 0
for i in range(N):
    now = T[i]
    if i < K:
        ans += points[now]
        handsls.append(now)
    else:
        if now == handsls[i - K]:
            handsls.append('n')
            continue
        ans += points[now]
        handsls.append(now)
        # print(T[i], points[now])
# print(handsls)
print(ans)


Measured memory_bytes: 47472
# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
N,A = map(int,input().split())
X = [0] + list(map(int,input().split()))

# dp[n][k][d] : n枚からk枚選んで合計dにする選び方
dp = [[[0 for _ in range(50*N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for n in range(N+1):
    for k in range(n+1):
        for d in range(50*k+1):
            # 選んだ数がn枚目のカードより小さい場合, そのカードは使えない
            if d < X[n]:
                dp[n][k][d] = dp[n-1][k][d]
            # そうでない場合
            else:
                # k==0のときはカードを選べないことに注意
                if k >= 1:
                    dp[n][k][d] = dp[n-1][k][d] + dp[n-1][k-1][d-X[n]]

ans = 0
for i in range(1,N+1):
    # N枚からi枚選んで平均がA,つまり合計がA*i
    ans += dp[N][i][A*i]

print(ans)

Measured memory_bytes: 65504
#include <bits/stdc++.h>
using namespace std;
const int mod =  1000000007;
const int LIM = 100005;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) a.begin() , a.end()
#define vvi vector<vector<int>>
//#define double long double
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define endl '\n'
#define pb push_back
#define sp <<" "<<
#define ss second
#define ff first
int power(int x, int n){
    int res = 1;
    while(n){
          if(n&1){
                res = res * x % mod;
          }
          x = x * x % mod;
          n>>=1;
    }
    return res;
}
int numLen(int K)
{
    if (K % 2 == 0 || K % 5 == 0)
        return -1;
    int num = 0;
    int len = 1;
    for (len = 1; len <= K; len++) {
        num = (num * 10 + 1) % K;
        if (num == 0)
            return len;
    }

    return -1;
}

int32_t main()
{     //IOS;
      int tt=1,n,k,x,y,z,i,j;
      //cin>>tt;
      while(tt--)
      { cin>>n;
        if(n%7==0)n=n/7;
        cout<<numLen(n);

      }
}


Measured memory_bytes: 3588
#include <cstdio>
#include <vector>
#include <algorithm>
const int xn = 131073;
std::vector < std::pair < int, int > > V[xn];
int N, q[xn];
std::vector < std::pair < long long, long long > > ans[xn];
void merge(auto &O, const auto &V0, const auto &V1, long long E0, long long E1, long long LIM)
{
	O.clear();
	std::vector < std::pair < long long, long long > > TMP;
	for (auto &i : V0)
	{
		auto it = std::upper_bound(V1.begin(), V1.end(), std::make_pair(LIM - E0 - E1 - i.second, 1LL << 60));
		if (it != V1.begin())
		{
			std::pair < long long, long long > To_Push_back = { i.first + E0, (it - 1) -> second + E1 };
			TMP.push_back(To_Push_back);
			std::swap(To_Push_back.first, To_Push_back.second);
			TMP.push_back(To_Push_back);
		}
	}
	std::sort(TMP.begin(), TMP.end());
	for (auto i : TMP)
		if (O.empty() || i.second < O.back().second)
			O.push_back(i);
}
bool check(long long mid)
{
	for (int i = N; i; i--)
	{
		int u = q[i];
		if (V[u].empty())
			ans[u] = { { 0, 0 } };
		else
			merge(ans[u], ans[V[u][0].first], ans[V[u][1].first], V[u][0].second, V[u][1].second, mid);
		if (ans[u].empty())
			return false;
	}
	return true;
}
int main()
{
	scanf("%d", &N);
	for (int i = 2, f, l; i <= N; i++)
	{
		scanf("%d%d", &f, &l);
		V[f].push_back({ i, l });
	}
	int H = 0, T = 1;
	q[1] = 1;
	while (H < T)
	{
		int u = q[++H];
		for (auto v : V[u])
			q[++T] = v.first;
	}
	long long l = 0, r = 1LL << 40;
	while (l < r)
	{
		long long m = l + r >> 1;
		if (check(m))
			r = m;
		else
			l = m + 1;
	}
	printf("%lld\n", l);
	return 0;
}


Measured memory_bytes: 31364
#include<iostream>
#include<cstdio>
#include<time.h>
using namespace std;
#define N 314159
int a[N],t[N];
long long ans=0;
void marge_count(int s,int g){
  if(s+1==g)return;
  int m= (s+g)/2;
  marge_count(s,m);
  marge_count(m,g);
  int p=s,q=m,r=s;
  while(p<m&&q<g){
    if(a[p]<=a[q]){
      t[r++]=a[p++];
    }else{
      t[r++]=a[q++];
      ans+=m-p;
    }
  }
  if(p<m){
    while(p<m)t[r++]=a[p++];
  }else{
    while(q<g){
      t[r++]=a[q++];
    }
  }
  for(int i=s;i<g;i++){
    a[i]=t[i];
  }
}
int n;
int main(){
    while(cin>>n&&n){ans=0;
  for(int i=0;i<n;i++)cin>>a[i];
  marge_count(0,n);
   cout<<ans<<endl;}
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

const ll MOD = 1'000'000'007;

int main(){
    int N, K;
    cin >> N >> K;
    int a[101];
    for(int i=1;i<=N;i++) cin >> a[i];

    static ll dp[101][100002], sum[101][100003];
    for(int i=0;i<=K;i++) dp[0][i] = 0;
    for(int i=0;i<=N;i++) dp[i][0] = 1;

    sum[0][0] = 0;
    for(int i=1;i<=K+1;i++) sum[0][i] = (sum[0][i-1] + dp[0][i-1]) % MOD;

    for(int i=1;i<=N;i++){
        for(int j=1;j<=K;j++){
            dp[i][j] = (sum[i-1][j+1] - sum[i-1][max(-1, j-a[i]-1)+1] + MOD) % MOD;
        }
        sum[i][0] = 0;
        for(int j=1;j<=K+1;j++) sum[i][j] = (sum[i][j-1] + dp[i][j-1]) % MOD;
    }

    cout << dp[N][K] << endl;

    return 0;
}

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

int main(){

  int a[3];
  for(int i=0; i<3; i++){
	cin >> a[i];
  }
  cout << max(a[0],max(a[1],a[2]))-min(a[0],min(a[1],a[2])) << endl;
}

Measured memory_bytes: 3680
//https://atcoder.jp/contests/abc075/tasks/abc075_b

#include <iostream>
using namespace std;

int main(void){
    int H,W;
    int counter = 0;
    // string S[51][51];
    string S[50];

    cin >> H >> W;
    for (int i = 0; i < H; i++){
        cin >> S[i];
    }
    // for (int i = 0; i < H; i++){
    //         cout << S[i] << endl;
    // }

    // string num[H][W];
    // int num[H][W];
    // for (int i = 0; i < H; i++){
    //     for (int j = 0; j < W; j++){
    //         num[H][W] = 0;
    //     }
    // }
    int dx[8] = {1,0,-1,0,1,-1,-1,1};
    int dy[8] = {0,1,0,-1,1,1,-1,-1};
    int ii = 0;
    int jj = 0;

    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            counter = 0;
            // if (S[i][j] == '.') printf("S[%d][%d]=clear\r\n",i,j);
            if (S[i][j] == '.'){
                for (int p = i-1; p <= i+1; p++){
                    for (int q = j-1; q <= j+1; q++){
                        if(p >= 0 && q >= 0 && p < H && q < W && S[p][q] == '#') counter ++;
                    }
                }
                
                S[i][j] = '0' + counter;
                // printf("num[%d][%d] = %d\r\n",i,j,num[i][j]);

                // for (int k = 0; k < 8; k++){
                //     ii = i + dx[k];
                //     jj = j + dy[k];
                //     if(ii >= 0 && jj >= 0 && ii < H && jj < W && S[ii][jj] == '#') counter ++;
                // }
                // S[i][j] = '0' + counter;
            }
        }
    }
    // for (int i = 0; i < H; i++){
    //     for (int j = 0; j < W; j++){
    //         if (S[i][j] == '.'){
    //             S[i][j] = char('0' + num[i][j]);
    //         }
    //     }
    // }
    for (int i = 0; i < H; i++) {
        cout << S[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 256
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0

using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/


int main() {
	
	int a, b;
	scanf("%d%d", &a, &b);
	printf("%d\n", a - 1 + (a <= b));
	
	Please AC;
}


Measured memory_bytes: 888
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
 
  int n, m;
  rd(n, m);
  auto a=readln.split.to!(int[]);
  auto b=readln.split.to!(int[]);
 
  int mx=0;
  foreach(i; 0..m){
    int j=i;
    foreach(e; a){
      if(j>=m) break;
      if(e==b[j]) j++;
    }
    mx=max(mx, j-i);
  }
 
  writeln(mx);
}
 
void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}

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

int	sqrt(int num)
{
	int	r = 1;
	while (r * r <= num) 
		++r;
	return r - 1;
}

int	main()
{
	int	Q;
	cin >> Q;
	vector<int>	l_vec(Q), r_vec(Q);
	int	max_r = -1;
	for (int i = 0; i < Q; ++i) {
		cin >> l_vec.at(i) >> r_vec.at(i);
		if (max_r < r_vec.at(i))
			max_r = r_vec.at(i);
	}
	vector<bool>	is_prime(max_r + 1, true);
	is_prime.at(0) = false;
	is_prime.at(1) = false;
	int	sqrt_max_r = sqrt(max_r);
	for (int i = 2; i <= sqrt_max_r; ++i) {
		if (!is_prime.at(i))
			continue;
		for (int j = 2 * i; j <= max_r; j += i)
			is_prime.at(j) = false;
	}
	vector<int>	cnt_vec(max_r + 1, 0);
	for (int i = 1; i <= max_r; ++i) {
		cnt_vec.at(i) = cnt_vec.at(i - 1);
		if (is_prime.at(i) && is_prime.at((i + 1) / 2))
			++cnt_vec.at(i);
	}
	for (int i = 0; i < Q; ++i) 
		cout << cnt_vec.at(r_vec.at(i)) - cnt_vec.at(l_vec.at(i) - 1) << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

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

    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    int num_negative = 0;
    for (int i = 0; i < N; ++i) {
        if (A[i] < 0) {
            ++num_negative;
        }
    }

    ll sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += abs(A[i]);
    }

    if (num_negative % 2 == 0) {
        cout << sum << endl;
    } else {
        auto it = min_element(begin(A), end(A), [](ll a, ll b){
            return abs(a) < abs(b);
        });

        cout << sum - 2 * abs(*it) << endl;
    }

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) {
    cin >> s.at(i);
  }
  
  
  map<string, int> smap;
  rep(i, n) {
    if (smap.count(s.at(i))) {
      smap[s.at(i)]++;
    }
    else {
      smap[s.at(i)] = 1;
    }
  }
  int max = 0;
  for (string x : s) {
    if (max <= smap.at(x)) {
      max = smap.at(x);
    }
  }
  for (pair<string, int> p : smap) {
    string key = p.first;
    int val = p.second;
    if (max  == val) {
      cout << key << endl;
    }
  }
}



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

using namespace std;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vmi;

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

    vmi a(n, vi(3));
    for (int i = 0; i < n; ++i)
        cin >> a[i][0] >> a[i][1] >> a[i][2];

    vmi dp(n, vi(3));
    dp[0] = a[0];

    for (int i = 1; i < n; ++i)
        for (int j = 0; j < 3; ++j)
            dp[i][j] = a[i][j] + max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]);

    cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));
    return 0;
}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
struct wjmzbmr
{
    int x,y;
    void input()
    {
        scanf("%d%d",&x,&y);
    }
}a[maxn+5];
int mod[maxn+5];
int n;
vector<int> ans;
int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;++i) a[i].input(),mod[i]=abs(a[i].x+a[i].y)%2;
    int cnt[2]={0,0};
    for(int i=1;i<=n;++i) ++cnt[mod[i]];
    if(cnt[0]&&cnt[1]) return 0*printf("-1");
    bool flag=0;
    if(mod[1]==0)
    {
        ans.push_back(1);
        flag=1;
        for(int i=1;i<=n;++i) a[i].x--;
    }
    for(int i=0;i<31;++i) ans.push_back(1<<i);
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();++i)
    {
        printf("%d",ans[i]);
        if(i<int(ans.size())-1) printf(" ");else printf("\n");
    }
    for(int i=1;i<=n;++i)
    {
        int x=a[i].x,y=a[i].y;
        if(flag) printf("R");
        for(int j=0;j<30;++j)
        {
            if(x&1)
            {
                if((x+1+y)&2) printf("L"),x=(x+1)/2,y=y/2;
                else printf("R"),x=(x-1)/2,y=y/2;
            }
            else
            {
                if((x+y+1)&2) printf("D"),x/=2,y=(y+1)/2;
                else printf("U"),x/=2,y=(y-1)/2;
            }
        }
        if(x==-1) printf("L\n");
        if(x==1) printf("R\n");
        if(y==-1) printf("D\n");
        if(y==1) printf("U\n");
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		Scanner scan = new Scanner(System.in);
		int x = 0;
		
		while(true) {
	        int a = scan.nextInt();
	        String op = scan.next();
	        int b = scan.nextInt();
	        
			if (op.equals ("?")){
				break;
			}
			else if(op.equals ("+")) {
				x = a+b;
				System.out.println(x);
			}
			else if(op.equals ("-")) {
				x = a-b;
				System.out.println(x);
			}
			else if(op.equals ("*")) {
				x = a*b;
				System.out.println(x);
			}
			else if(op.equals ("/")) {
				double A = a;
				double y = A/b;
				System.out.println((int) y);
			}
		}
		
	}

}

Measured memory_bytes: 26268
#include<vector>
#include<iostream>
 
using namespace std;
int main(void)
{
  int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int i = 0;
  
  cin >> i ;
  
  cout << a[i - 1];
  
  return 0;
  
 
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <cmath>
 
using namespace std;
 
// typedef
typedef long long ll;
typedef long double ldbl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
 
// container util
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for (typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
// repetition
#define FOR(i,m,n) for (ll (i) = ((ll) m); (i) < ((ll) n); ++(i))
#define RFOR(i,m,n) for (ll (i) = ((ll) (m)-1); (i) >= ((ll) n); --(i))
#define REP(i,n) FOR(i,0,n)
 
// i/o
#define TFOUT(b,t,f) cout << ((b)? (t) : (f)) << endl
 
//constant
const double    EPS        = 1e-10;
const double    PI         = acos(-1.0);
const int       INFTY_INT  = (1<<21);
const ll        INFTY_LL   = (1LL<<60);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

int main() {
    int n; cin >> n;
    ll ans = 0;
    REP(i, n) {
        ll a; cin >> a;
        ans += a - 1;
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N;
  cin>>N;
  vector<int> x(N);
  
  for (int i=0;i<N;i++) {
    cin>>x.at(i);}
  
  sort(x.begin(),x.end());
  
  int answer=0;
  
  for (int i=0;i<N;i++){
    if(i%2==0) answer += x.at(N-1-i);
    else answer -= x.at(N-1-i);
  }
  
  cout<<answer<<endl;
}


Measured memory_bytes: 256
x,y = gets.chomp.split(' ').map(&:to_i)

def hoge(n)
  if (n == 3)
    return 100000
  elsif (n == 2)
    return 200000
  elsif (n == 1)
    return 300000
  else
    return 0
  end
end

if (x == 1 && y == 1)
  puts 1000000
else
  puts hoge(x) + hoge(y)
end

Measured memory_bytes: 14276
#include <stdio.h>

int main() {
    int n, m, l, tmp;
    
    scanf("%d", &n);
    
    int M[n][n];
    for (int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            M[i][j] = 0;
        }
    }
    
    for (int i=0; i<n; i++) {
        scanf("%d %d", &m, &l);
        for (int j=0; j<l; j++) {
            scanf("%d", &tmp);
            M[m-1][tmp-1] = 1;
        }
    }
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(j) printf(" ");
            printf("%d", M[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}


Measured memory_bytes: 2732
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int flag=0;
    if(a==b&&b!=c)flag=1;
    if(a==c&&b!=c)flag=1;
    if(c==b&&b!=a)flag=1;
    if(flag)cout<<"Yes";
    else cout<<"No";
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int a = (int)Integer.parseInt(sc.next());
    	int b = (int)Integer.parseInt(sc.next());
    	int c = (int)Integer.parseInt(sc.next());
    	if(a<b && b<c){
    		System.out.println("Yes");
    	}else {
    		System.out.println("No");
		}
    }
}



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

int main()
{
	int a, b;

	cin >> a >> b;

	if (a > b)
	{
		for(int i=0;i < a;i++)
		{
			cout << b;
		}
	}

	else
	{
		for (int i = 0;i < b; i++)
		{
			cout << a;
		}
	}

}

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

int main() {
  int N;
  cin >> N;
  vector<int> L(N);
  for (int i = 0; i < N; i++) cin >> L.at(i);
  sort(L.begin(), L.end());
  int x = L.at(N-1);
  int y = 0;
  for (int i = 0; i < N-1; i++) {
    y += L.at(i);
  }
  if (x < y){
    cout << "Yes" << endl;
    return 0;
  }
  else {
    cout << "No" << endl;
    return 0;
  }
}
 

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
int main(){
  typedef long long int ll;
int A, B, C;
cin >> A >> B >> C;
bool ans = false;
if((A * 100 + B * 10 + C) % 4 == 0)ans = true;
if(ans)cout << "YES" << endl;
else cout << "NO" << endl;
        return 0;
}

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

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, long long x, std::vector<long long> a){
  ll ans = 0;
  a.push_back(0);
  N+=1;
  for(ll i = 1; i<N; i++) {
    if(a[i-1]+a[i]>x) {
      if(a[i]+a[i-1]-x>a[i]) {
	ans+=a[i]+a[i-1]-x;
	a[i-1] = x;
	a[i] = 0;
      } else {
	ans += a[i]+a[i-1]-x;
	a[i]-= a[i]+a[i-1]-x;
      }
    }
  }
  std::cout << ans << std::endl;
  //std::cout << a << std::endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long x;
    scanf("%lld",&x);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, x, std::move(a));
    return 0;
}


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

int main() {
  int N,M; cin >> N >> M;
  vector<int> x(M),y(M);
  for (int i = 0; i < M; i++) cin >> x[i] >> y[i];
  vector<int> a(N,1);
  vector<bool> c(N,false);
  c[0] = true;
  for (int i = 0; i < M; i++) {
    a[x[i]-1]--;
    a[y[i]-1]++;
    if (c[x[i]-1]) c[y[i]-1] = true;
    if (a[x[i]-1] == 0) c[x[i]-1] = false;
  }
  int count = 0;
  for (int i = 0; i < N; i++) if (c[i]) count++;
  
  cout << count << endl;
}

Measured memory_bytes: 1408
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n, k = f()
    pii = [[0,0] for i in range(n)]
    
    for i in range(n):
        x, y = f()
        pii[i][0] = x
        pii[i][1] = y

    pii = sorted(pii, key = lambda x: x[0])

    cnt = 0
    for i in range(n):
        if cnt + pii[i][1] >= k:
            print(pii[i][0])
            return
        
        cnt += pii[i][1]


solve()


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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin (),(x).end()
#define sqrt(x) sqrt(abs(x))
#define re return
#define sz(x) ((int)(x).size ())
#define prev PREV
#define next NEXT

using ll = long long;
using ii = pair<int, int>;
using ld = long double;
using D = double;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vs = vector<string>;

template<typename T> T abs (T x) { re x < 0 ? -x : x; }
template<typename T> T sgn (T x) { re x < 0 ? -1 : (x > 0 ? 1 : 0); }
template<typename T> T sqr (T x) { re x * x; }
template<typename T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }

const int mod = 1000*1000*1000+7;

int n;
int m;
int res[51][51][51][51];
int f[51];
int rf[51];

int power (int a, int b) {
	int c = 1;
	while (b) {
		if (b & 1) c = ((ll)c * a) % mod;
		a = ((ll)a * a) % mod;
		b /= 2;
	}
	re c;
}

int go (int lev, int now, int pos, int neg) {
	if (res[lev][now][pos][neg]) re res[lev][now][pos][neg];
	if (now == n) {
		int cur = ((ll)rf[pos] * rf[neg]) % mod;
//		printf ("%d %d %d %d = %d\n", lev, now, pos, neg, (int)((ll)cur * f[n - now + pos + neg] % mod));
		re cur;
	}	
	if (pos + neg == 0 || lev == n) re 0;
	int cur = 0;
	set<pair<ii, ii> > was;
	for (int apos = 0; apos <= pos && now + apos <= n; apos++)
		for (int aneg = 0; aneg <= neg && now + apos + aneg <= n; aneg++)
			for (int both = 0; now + apos + aneg + 2 * both <= n; both++) {
				int cpos = pos - apos + aneg;
				int cneg = neg - aneg + apos;
				int npos = apos + both;
				int nneg = aneg + both;
				if (was.count (mp (mp (cpos, cneg), mp (npos, nneg)))) continue;
				was.insert (mp (mp (cpos, cneg), mp (npos, nneg)));
				cur = (cur + (ll)go (lev + 1, now + apos + aneg + 2 * both, npos, nneg) * rf[cpos] % mod * rf[cneg]) % mod;
			}
//	printf ("%d %d %d %d = %d\n", lev, now, pos, neg, (int)((ll)cur * f[n - now + pos + neg] % mod));
	re res[lev][now][pos][neg] = cur;
}

int main () {
	scanf ("%d", &n);
	f[0] = rf[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = ((ll)f[i - 1] * i) % mod;
		rf[i] = power (f[i], mod - 2);
	}
	cout << ((ll)go (0, 1, 1, 0) * f[n]) % mod << endl;
//	cerr << clock () << endl;
	return 0;
}

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

#define M_PI 3.14159265358979323846

using namespace std;

//typedef
//-------------------------#include <bits/stdc++.h>

#define M_PI 3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s)
{
    int v;
    istringstream sin(s);
    sin >> v;
    return v;
}
template <class T>
inline string toString(T x)
{
    ostringstream sout;
    sout << x;
    return sout.str();
}
inline int readInt()
{
    int x;
    scanf("%d", &x);
    return x;
}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a) * (a))
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

//repetition
//------------------------------------------
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define MOD 1000000007

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double EPS = 1E-8;

#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const int INF = 2147483647;

const int dxy[5] = {-1, 0, 1, 0, -1};
const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

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;
}

vector<vector<int>> G(100010);
int c[10010];
int ans[10010];
int idx = 0;
int sum = 0;
void dfs(int v, int prev = -1)
{

    ans[v] = c[idx];
    idx++;
    if (prev != -1)
        sum += ans[v];
    for (int i = 0; i < G[v].size(); i++)
    {
        int u = G[v][i];
        if (u == prev)
            continue;

        dfs(u, v);
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int N;
    cin >> N;
    REP(i, N - 1)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    REP(i, N)
    {
        cin >> c[i];
    }

    sort(c, c + N);
    reverse(c, c + N);

    dfs(0);

    cout << sum << endl;
    for (int i = 0; i < N; i++)
    {
        if (i)
            cout << " ";

        cout << ans[i];
    }
    cout << endl;
}


Measured memory_bytes: 3584
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

div = make_divisors(n)
ans = 0
for i in div:
    res = n//i-1
    if res <= 0:continue
    if n%res==i:
        ans += res

print(ans)

Measured memory_bytes: 39024
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll ans; // :))
int n, m, k, u, v, x, y, t, a, b, X, Y;
int par[MAXN], h[MAXN], sz[MAXN][2];
pii val[MAXN];
vector<int> G[MAXN];

inline pii operator +(pii i, pii j){ return {i.first+j.first, i.second+j.second};}

void dfs1(int node, int p){
	h[node]=h[par[node]=p]+1;
	for (int v:G[node]) if (v!=par[node]){
		if (!h[v]) dfs1(v, node);
		else{
			X=v;
			Y=node;
		}
	}
}
void dfs2(int node){
	sz[node][h[node]&1]++;
	for (int v:G[node]) if (v!=par[node]){
		dfs2(v);
		sz[node][0]+=sz[v][0];
		sz[node][1]+=sz[v][1];
	}
}
void dfs3(int node){
	if (h[node]&1) val[node].first=1;
	else val[node].first=-1;
	for (int v:G[node]) if (v!=par[node]){
		dfs3(v);
		val[node]=val[node]+val[v];
	}
}
int Solve1(){
	dfs2(1);
	if (sz[1][0]!=sz[1][1]) kill(-1)
	for (int i=2; i<=n; i++) ans+=abs(sz[i][0]-sz[i][1]);
	kill(ans)
}
int Solve2(){
	int diff=sz[1][1]-sz[1][0];
	if (diff&1) kill(-1)
	diff>>=1;
	if (h[X]&1) diff*=-1;
	memset(sz, 0, sizeof(sz));
	sz[X][h[X]&1]+=diff;
	sz[Y][h[Y]&1]+=diff;
	dfs2(1);
	for (int i=2; i<=n; i++) ans+=abs(sz[i][0]-sz[i][1]);
	ans+=abs(diff);
	kill(ans)
}
int Lca(int x, int y){
	while (x^y){
		if (h[x]<h[y]) swap(x, y);
		x=par[x];
	}
	return x;
}
int Solve3(){
	if (sz[1][0]!=sz[1][1]) kill(-1)
	val[X].second--;
	val[Y].second--;
	val[Lca(X, Y)].second+=2;
	dfs3(1);
	vector<int> vec={0};
	for (int i=1; i<=n; i++) if (val[i].second){
		int tmp=val[i].first;
		vec.pb(tmp);
	}
	sort(all(vec));
	int diff=vec[(vec.size())/2];
	ans+=abs(diff);
	for (int i=1; i<=n; i++) ans+=abs(val[i].first + val[i].second*diff);
	kill(ans)
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=0; i<m; i++){
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs1(1, 0);
	if (m==n-1) Solve1();
	else{
		for (int &x:G[Y]) if (x==X) swap(G[Y].back(), x);
		for (int &y:G[X]) if (y==Y) swap(G[X].back(), y);
		G[X].pop_back();
		G[Y].pop_back();
		dfs2(1);
		if (h[X]%2==h[Y]%2) Solve2();
		else Solve3();
	}
	
	return 0;
}

Measured memory_bytes: 19516
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {

  string S;
  cin >> S;

  long long sum = 0;
  for(int i = 0;i < S.size();i++) {
    sum += S[i]-'0';
  }

  if(sum%9 == 0) cout << "Yes" << endl;
  else cout << "No" << endl;

}


Measured memory_bytes: 3752