akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

struct edge { int to, cost; };

vector<edge> g[101010];
int color[101010];

void dfs(int u, int pre, ll dist) {
    for (auto e : g[u]) {
        if (e.to == pre) continue;
        dfs(e.to, u, dist + e.cost);
    }
    color[u] = dist % 2;
}

int main() {
    fill(color, color + 101010, -1);
    ll n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    dfs(0, -1, 0);
    for (int i = 0; i < n; i++) {
        cout << color[i] << endl;
    }
}

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

#define pb(x) push_back(x);
#define all(v) v.begin(),v.end()

using ll = long long int;
using ul = unsigned long long int;
using vi = vector<int>;
ll max(ll x,ll y){
    if(x>y)
        return x;
    else
        return y;
}
ll min(ll x,ll y){
    if(x>y)
        return y;
    else
        return x;
}

int main(){
    ul ans =0;
    vi v(3);
    cin>>v[0];
    cin>>v[1];
    cin>>v[2];
    sort(all(v));
    if(v[2]-v[1] == 0){
        if((v[2]-v[0])%2==0){
            ans = (v[2]-v[0])/2;
        }else{
            ans = (v[2]-v[0])/2;
            ans += 2;
        }
    }else{
        ans = (v[2]-v[1]);
        v[0] += ans;
        if((v[2]-v[0])%2==0){
            ans += (v[2]-v[0])/2;
        }else{
            ans += (v[2]-v[0])/2;
            ans += 2;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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


int main(void) {
  int n;
  cin >> n;
  vector<int> s(n);
  int point = 0;
  rep(i, n) {
    cin >> s[i];
    point += s[i];
  }

  if (point % 10 != 0) {
    cout << point << endl;
    return 0;
  }

  sort(s.begin(), s.end());

  int target = 0;
  while (target < n) {
    if (s[target] % 10 != 0) break;
    target++;
  }

  if (target >= n) {
    cout << 0 << endl;
  } else {
    cout << point - s[target] << endl;
  }

  return 0;
}

Measured memory_bytes: 3612
use std::io;
fn main() {
    let mut buf = String::new();

    std::io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let N: u32 = iter.next().unwrap().parse().unwrap();

    let ans = if  N%10 == 9 || (N/10)%10 == 9 { "Yes" } else { "No" };
    println!("{}",ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

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

	int X;
	cin >> X;
	cout << lcm(X, 360) / X << endl;

	return 0;
}


Measured memory_bytes: 3608
import numpy as np
N, K = map(int,input().split())
S = input()
L = np.zeros(N+1, int)
flag = '1'
i = 0
for char in S:
    if char == flag:
        L[i] += 1
    else:
        i += 1
        flag = char
        L[i] += 1

W = min(2 * K + 1, N + 1)

ans = L[:W].sum()

cnt = L[:W].sum()

for i in range((N+1-W) // 2):
    cnt = cnt - L[i*2] - L[i*2+1] + L[i*2+W] + L[i*2+W+1]
    ans = max(ans, cnt)
print(ans)

Measured memory_bytes: 13412
#include<bits/stdc++.h>
#define REPI(i, n) for(int i = 0; i < n; i++)
using namespace std;
int main(){
    int n, ans = 0; cin >> n;
    int a[n]; REPI(i, n) cin >> a[i];
    sort(a, a + n, greater<int>());
    REPI(i, n) ans += i%2 ? -a[i] : a[i];
    cout << ans;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import numpy as np
N = int(input())
# スペース区切りの整数の入力
line = list(map(int, input().split()))
a = b = 0

for i in range(N):
    n = max(line)
    line.remove(n)
    if i % 2:
        b += n
    else:
        a += n
        
print(a-b)

Measured memory_bytes: 12396
X = int(input())
if X <= 599:
    print("8")
else:
    if X <= 799:
        print("7")
    else:
        if X <= 999:
            print("6")
        else:
            if X <= 1199:
                print("5")
            else:
                if X <= 1399:
                    print("4")
                else:
                    if X <= 1599:
                        print("3")
                    else:
                        if X <= 1799:
                            print("2")
                        else:
                            print("1")


Measured memory_bytes: 9176
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

    # 数列を度数分布とみたときに、x番目がどのインデックスにあるかを返す
    def rank(self, x):
        idx = 0
        for lv in range((self.n - 1).bit_length() - 1, -1, -1):
            mid = idx + (1 << lv)
            if mid >= self.n: continue
            if self.table[mid] < x:
                x -= self.table[mid]
                idx += 1 << lv
        return idx

def solve():
    bit = BitSum(w + 1)
    for j in range(w): bit.add(j + 1, 1)
    cost = [0] * (w + 1)
    hp = [0] * w
    heapify(hp)
    rem = []

    for i in range(h):
        l, r = MI()
        r += 1
        # cost[r]の更新
        if r <= w:
            cnt = bit.sum(r)
            if cnt:
                j = bit.rank(cnt)
                if l <= j < r:
                    bit.add(r, 1)
                    cost[r] = cost[j] + r - j
                    heappush(hp, cost[r])
        # 区間[l,r)を無効にする
        cnt = bit.sum(l - 1)
        while 1:
            j = bit.rank(cnt + 1)
            if j >= r: break
            heappush(rem, cost[j])
            bit.add(j, -1)
        # ヒープからの削除
        while hp and rem and hp[0] == rem[0]:
            heappop(hp)
            heappop(rem)
        # 出力
        if hp: print(hp[0] + i + 1)
        else: print(-1)

h,w=MI()
solve()


Measured memory_bytes: 94640
from typing import List


def count_sort(array: List[int]) -> List[int]:
    max_num = max(array)
    min_num = min(array)

    count_element = [0] * (max_num - min_num + 1)
    for element in array:
        count_element[element - min_num] += 1

    result = []
    for index, cnt in enumerate(count_element, start=min_num):
        result.extend([index] * cnt)

    return result


def main() -> None:
    N, K = map(int, input().split(' '))
    array = [int(_) for _ in input().split(' ')]

    print(sum(count_sort(array)[:K]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 75148
#include <iostream>
#include <array>

using namespace std;

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

  array<int, 100000> A;
  for (int i=0; i<N; i++) {
    cin >> A[i];
  }

  bool result = false;
  for (int i=0; i<N; i++) {
    H = H - A[i];
    if (H <= 0) {
      result = true;
      break;
    }
  }

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



Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	int *line;
	while(cin>>n&&n!=0){
		line=new int[n];
		for(int i=0;i<n;++i){
			cin>>line[i];
		}
		sort(line,line+n);
		--n;
		int ans=(1<<31)-1;
		for(int i=0;i<n;++i){
			ans=min(ans,line[i+1]-line[i]);
		}
		cout<<ans<<endl;
		delete[] line;
	}
	return 0;
}

Measured memory_bytes: 3084
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);
        String[] s = sc.next().split("");
        long ans = 0;
        int[] l = new int[s.length + 1];
        int[] r = new int[s.length + 1];
        for (int i = 0; i < s.length; i++) {
            if (s[i].equals("<")) {
                l[i + 1] = l[i] + 1;
            }
        }
        for (int i = s.length - 1; i >= 0; i--) {
            if (s[i].equals(">")) {
                r[i] = r[i + 1] + 1;
            }
        }
        for (int i = 0; i <= s.length; i++) {
            ans += Math.max(l[i], r[i]);
        }
        
        System.out.println(ans);
    }
}

Measured memory_bytes: 68596
if ARGV[0]=="LOCAL_DEV"
  define_method("debug") do |var|
    p var
  end
else
  define_method("debug") do |var|
  end
end

A,B,C,X,Y=STDIN.gets.strip.split.map(&:to_i)
ans=[]
ans<<A*X+B*Y
ans<<[X,Y].max*C*2
if X>Y
  ans<<2*Y*C+(X-Y)*A
else
  ans<<2*X*C+(Y-X)*B
end

puts ans.min



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

using namespace std;

int solve(int N, int P) {
	int p = P;
	vector<int> have(N, 0);
	int turn = 0;
	while (1) {
		if (p > 0) {
			--p;
			if (++have[turn] == P) return turn;
		}
		else {
			swap(p, have[turn]);
		}
		turn = (turn + 1) % N;
	}
}

int main() {
	int N, P;
	while (cin >> N >> P, N || P) {
		cout << solve(N, P) << endl;
	}
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;

int main(){
    string s; cin >> s;
    int blue = 0, red = 0;
    rep(i, s.size()){
        if(s[i] == '0')red++;
        else blue++;
    }
    cout << min(red, blue) * 2 << endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<double> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  double S = 0;
  for (int i = 0; i < N; i++) {
    S += 1 / A.at(i);
  }
  cout << 1 / S << endl;
}

Measured memory_bytes: 256
n=int(input())
for i in range(int((2*n)**0.5-3),n+2):
  if i*(i+1)//2==n:
    for j in range(1,i+1):
      print(j)
    break
  elif i*(i+1)//2>n:
    k=i*(i+1)//2-n
    for j in range(1,i+1):
      if j!=k:
        print(j)
    break


Measured memory_bytes: 42200
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

ll N;
ll H;
ll A[101010], B[101010];

int main() {
    cin >> N >> H;
    for (int j = 0; j < N; ++j) cin >> A[j] >> B[j];

    int a_idx = 0;
    for (int j = 0; j < N; ++j) {
        if (A[a_idx] < A[j]) a_idx = j;
    }
    vector<ll> v;
    for (int j = 0; j < N; ++j) {
        if (j != a_idx && B[j] >= A[a_idx]) v.push_back(B[j]);
    }
    sort(begin(v), end(v));
    reverse(begin(v), end(v));

    ll count = 0;
    ll damage = 0;
    for (ll w : v) {
        ++count;
        damage += w;
        if (damage+B[a_idx] >= H) {
            break;
        }
    }

    if (damage >= H) {
        cout << count << endl;
        return 0;
    }

    ll ans = count + 1 + max(0LL, (H - damage - B[a_idx] + A[a_idx] - 1) / A[a_idx]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

int main(){
  vector<int> a(5);
  int minsec = 10;
  for(int i = 0; i < 5; i++){
    cin >> a.at(i);
    if(minsec > a.at(i) % 10 && a.at(i) % 10 != 0)
      minsec = a.at(i) % 10;
  }

  int sum = 0;
  for(int i = 0; i < 5; i++){
    if(a.at(i) % 10 == 0)
      sum += a.at(i);
    else
      sum += (a.at(i) / 10 + 1) * 10;
  }
 
  cout << sum - 10 + minsec << endl;

}




Measured memory_bytes: 256
from fractions import gcd

V = 1003
G = []
visited = []
match = []

def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)

def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True

def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res

while True:
    m,n = map(int,raw_input().split())
    if m|n == 0:
        break
    V = m+n+2
    G = [[] for _ in xrange(V)]
    visited = [True] * V
    data = []
    while len(data) < n+m:
        data += map(int,raw_input().split())
    for i,b in enumerate(data[:m]):
        for j,r in enumerate(data[m:],m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()

Measured memory_bytes: 11504
import java.util.Scanner;
public class Main {

    private static int[] button;
    private static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        button = new int[n+1];
        for(int i=1; i<n+1; i++){
            button[i] = sc.nextInt();
        }

        int recent = 1, cnt = 0;
        while (recent != 2){
            recent = button[recent];
            cnt++;
            if(cnt > n){
                System.out.println(-1);
                System.exit(0);
            }
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 51456
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int mochi_num;
	cin >> mochi_num;
	vector<int> mochi_radius;
	int radius_input;
	for (int i = 0; i < mochi_num; i++) {
		cin >> radius_input;
		mochi_radius.push_back(radius_input);
	}
	sort(mochi_radius.begin(), mochi_radius.end());
	int kagami_level = 0;
	int temp_count=0;
	for (int i = 0; i < mochi_num; i++) {
		if (temp_count == mochi_radius[i]) {
		}
		else {
			kagami_level++;
			temp_count = mochi_radius[i];
		}
	
	}
	cout << kagami_level;


    return 0;
}



Measured memory_bytes: 256
/*

Parallelism(https://onlinejudge.u-aizu.ac.jp/problems/0021)
前

*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <complex>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define putsp(x) cout << x << ' ';
#define putln(x) cout << x << endl;
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef complex<double> comp;
typedef vector <int> vec;
typedef vector <ll> vecll;
typedef vector <double> vecd;
typedef vector <vec> mat;
typedef vector <vecll> matll;
typedef vector <vecd> matd;

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 200000;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const ll INFL = 1e18;
const int MOD = 1000000007;

int dx4[4]={1,0,-1,0};
int dy4[4]={0,1,0,-1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

//********************************template END****************************************//

//外積を計算する関数
double gaiseki(comp a, comp b)
{
	return (conj(a)*b).imag();
}

void solve(void){

	int N;
	cin >> N;
	while(N--)
	{

		double xs[4], ys[4];
		rep(4, i)
		{
			cin >> xs[i] >> ys[i];
		}

		vector <comp> ps(4);
		rep(4, i)
		{
			ps[i] = comp(xs[i], ys[i]);
		}

		//直線AB,CDに対応するベクトルl,m
		comp l = ps[1]-ps[0], m = ps[3]-ps[2];

		cout << (abs(gaiseki(l, m)) < EPS ? "YES" : "NO") << endl;

	}

}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}



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

int main() {
    int N;
    cin >> N;
    vi A(N);
    rep(i, N) {
        cin >> A[i];
    }

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if ((i + 1) % 2 == 0) continue;

        if (A[i] % 2 != 0) {
            cnt++;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3620
#define _USE_MATH_DEFINES
#include<iostream>
#include<sstream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<math.h>
#include<iterator>

using namespace std;


int main(){
  string s;
  cin >> s;
  int score=0;
  for (int i = 0; i < s.length(); i++) {
    if(i%2==0){
      if(s[i]=='p')score--;
    }else{
      if(s[i]=='g')score++;
    }
  }
  cout <<score<<endl;
  return 0;
}


Measured memory_bytes: 640
n = int(input()) - 2
L = list(map(int, input().split()))
a = 0

for i in range(n):
  if L[i] < L[i+1] and L[i+1] < L[i+2]:
    a = a+1
  elif L[i+2] < L[i+1] and L[i+1] < L[i]:
    a = a+1
    
print(a)

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


int main() {
    int N; cin>>N;
    vector<int>p(N);
    vector<int>q(N);
    rep(i,N)cin>>p[i];
    rep(i,N)cin>>q[i];
    vector<int>b(N);
    rep(i,N)b[i]=i+1;
    int g,h;
    int cnt =0;
    do{
        if(b==p)g=cnt;
        if(b==q)h=cnt;
        cnt++;
    }while(next_permutation(b.begin(),b.end()));
    cout<<abs(g-h)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
const int INF = 1<<30;
const ll MOD = 1000000007;

int main(void) {

    int n; cin >> n;
    rep(i, n) {
        cout << "ACL";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define BIT_COUNT 70

int add(int x,int y) {
    int ret = x+y;
    if(ret>=mod) {
        ret -= mod;
    }
    if(ret<0) {
        ret += mod;
    }
    return ret;
}

int dp[BIT_COUNT][2][2][2];

ll L,R;
int solveDp(int pos,int mbit,int LeqX,int ReqY) {
    if(pos<0) {
        return mbit==1;
    }
    int &ret = dp[pos][mbit][LeqX][ReqY];
    if(ret!=-1) {
        return ret;
    }
    ret = 0;
    for(int a=0;a<2;++a) {
        for(int b=0;b<2;++b) {
            if(a==1 && b==0) continue;
            if(LeqX && a==0 && (L&(1LL<<pos))>0 ) continue;
            if(ReqY && b==1 && (R&(1LL<<pos) )==0)continue;
            if(mbit==0 && (a!=b)) continue;
            int nmbit = mbit | (a==1 && b==1);
            int nLeqX = LeqX && ( ((L>>pos)&1) == a);
            int nReqY = ReqY && ( ((R>>pos)&1) ==b);
            ret = add(ret, solveDp(pos-1,nmbit,nLeqX,nReqY));
        }
    }
    return ret;
}
void solve() {
    scanf("%lld %lld",&L,&R);
    memset(dp,-1,sizeof(dp));
    cout<<solveDp(62,0,1,1)<<endl;
}
int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
import math

def main():
  A, B, H, M = map(int, input().split())
  Ax = A * math.sin((H + M / 60) * 30 / 180 * math.pi)
  Ay = A * math.cos((H + M / 60) * 30 / 180 * math.pi)
  Bx = B * math.sin(M * 6 / 180 * math.pi)
  By = B * math.cos(M * 6 / 180 * math.pi)
  dist = math.sqrt((Ax - Bx) ** 2 + (Ay - By) ** 2)
  print(dist)

if __name__ == '__main__':
  main()


Measured memory_bytes: 9504
#include<cstdio>
#include<iostream>
#include<cstring>
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i))
int n,m,K,maxbit,ans;
const int N=25,B=1050010,mod=1e9+7; 
int dp[2][N][B],lim[N][N],nex[B][N],ban[B][N];
int cmin(int x,int y){return x<y?x:y;}
int ADD(int x,int y){return (x+=y)>=mod?x-mod:x;}
void init()
{
	int x;
	f(S,0,maxbit)
	{
		x=-1;
		rf(i,n-1,0)
		{
			if(S&(1<<i))x=i;
			nex[S][i]=x;
		}
	}
}
int main()
{
	int now=0,pre,x,y,z;
	scanf("%d%d%d",&n,&m,&K),--n,maxbit=(1<<n)-1;
	f(i,1,m)
	 f(j,0,n-1)
	  lim[i][j]=-1;
	f(i,1,K)
	{
		scanf("%d%d%d",&x,&y,&z);	
		lim[x][y-1]=z;
	}
	dp[0][n][0]=1;
	init();
	f(i,1,m)
	{
		pre=now,now^=1;
		f(S,0,maxbit)dp[now][0][S]=dp[pre][n][S];
		f(j,0,n)
		 f(S,0,maxbit)
		  dp[pre][j][S]=0;
		f(j,0,n-1)
	     f(S,0,maxbit)if(dp[now][j][S])
		 {
			x=(S&(1<<j))?1:0;
			f(k,0,1)
			{
				if((lim[i][j]^-1)&&(lim[i][j]^k))continue;
				if((!k)&&x)continue;
				if(k==x)dp[now][j+1][S]=ADD(dp[now][j+1][S],dp[now][j][S]);
				else
				{
					y=nex[S][j];
					if(y!=-1)dp[now][j+1][(S|(1<<j))^(1<<y)]=ADD(dp[now][j+1][(S|1<<j)^(1<<y)],dp[now][j][S]);
					else dp[now][j+1][S|1<<j]=ADD(dp[now][j+1][S|1<<j],dp[now][j][S]);
				}
			}
		 }
	}f(S,0,maxbit)ans=ADD(ans,dp[now][n][S]);
	//std::cerr<<clock()*1.0/CLOCKS_PER_SEC<<std::endl;
	return printf("%d\n",ADD(ans,mod)),0;
}

Measured memory_bytes: 217344
#include<stdio.h>

int main(void){

  int x,y;
  int turu;

    scanf("%d %d",&x,&y);

  if((1<=x)&&(x<=100)){
    if((1<=y)&&(y<=100)){

      turu=4*x-y;

      if(y<=4*x){

      if((turu<=2*x)&&(turu%2==0)){
        printf("Yes\n");
      }else{printf("No\n");
    }

}else{printf("No\n");
}


    }
  }

  return 0;
}


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

#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define int long long

signed main(){
    int n; cin >> n;
    //奇数なら約数に2がないので0
    if(n%2==1){
        cout<<0<<endl;
        return 0;
    }
    //偶数なら明らかに約数は5の数が少ないので5の数を調べれば良い
    int res=0;
    int divide=10;
    while(divide<=n){
        res+=n/divide;
        divide*=5;
    }


    cout<<res<<endl;


}


Measured memory_bytes: 256
<?php
  $k = intval(fgets(STDIN));

  $total = 0;
  for($a=1; $a<=$k; $a++){
    for($b=1; $b<=$k; $b++){
      $tmp = gmp_gcd($a, $b);
      for($c=1; $c<=$k; $c++){
        $total += gmp_gcd($tmp, $c);
      }
    }
  }

  echo $total."\n";

Measured memory_bytes: 16292
/*
*
* author: ian macleod
*
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef vector<long long int> vll;

#define IO                 \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
 
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fo(i,a,b) for(ll i = a; i<=b;i+=1)
#define rf(i,a,b) for(ll i=a;i>=b;i--)

ll power(ll x, ll y) {
    ll res = 1;     // Initialize result
    x = x ;
    if (y==0)return 1;
    if(x==0)return 0;
    while (y > 0) {
        if (y & 1)
            res = (res*x);
        y = y>>1; // y = y/2
        x = (x*x);  // Change x to x^2
    }
    return res;
}


void solve() {
    
    ll x, v, count;
    cin >> x;
    v = 100;
    count = 0;
    while (v < x) {
        v += v / 100;
        count++;
    }
    cout << count << endl;
    return ;
}



int main() {
    solve();
}



Measured memory_bytes: 3680
n = int(input())
w_list = input().split()

sum1 = 0
for i in range(n):
   sum1 += int(w_list[i])

diff = 0
sum2 = 0
for i in range(n):
    sum2 += int(w_list[i])
    sum1 -= int(w_list[i])
    diff = abs(sum2-sum1)
    if i==0:
        diff_old = diff
    else:
        if diff_old < diff:
            print(diff_old)
            exit()
        else:
            diff_old = diff
print(diff)


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

int main(){
  int a,b,h,m;
  cin >> a >> b >> h >> m;

  double ang_m = 6 * m;
  double ang_h = 30 * h + 0.5 * m;
  ang_m *= M_PI / 180;
  ang_h *= M_PI / 180;
  double xh = a * cos(ang_h);
  double xm = b * cos(ang_m);
  double yh = a * sin(ang_h);
  double ym = b * sin(ang_m);
  double ans = sqrt((xh-xm) * (xh-xm) + (yh-ym) * (yh-ym));

  printf("%.12lf",ans);

  return 0;
}

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

void solve() {
  int N;
  cin >> N;
  vector<int> a(N), v(1e6 + 1, 0);

  for (auto &e : a) { cin >> e; }
  sort(a.begin(), a.end());

  for (auto &e : a) {
    if (v[e] != 0) {
      v[e] = 2;
      continue;
    }
    for (int i = e; i <= a.back(); i += e) v[i]++;
  }

  int ans = 0;
  for (auto &e : a)
    if (v[e] == 1) ans++;
  cout << ans << endl;
}

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

Measured memory_bytes: 7916
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	long long n, m;
	cin >> n >> m;
	long long A[1000][3];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) cin >> A[i][j];
	}
	vector<long long> Ba(n, 0);
	vector<long long> Bb(n, 0);
	vector<long long> Bc(n, 0);
	vector<long long> Bd(n, 0);
	vector<long long> Be(n, 0);
	vector<long long> Bf(n, 0);
	vector<long long> Bg(n, 0);
	vector<long long> Bh(n, 0);
	for (int j = 0; j < n; j++) {
		Ba[j] = Ba[j]+A[j][0] + A[j][1] + A[j][2];
		Bb[j] = Bb[j]+A[j][0] + A[j][1] - A[j][2];
		Bc[j] = Bc[j]+A[j][0] - A[j][1] + A[j][2];
		Bd[j] = Bd[j]+A[j][0] - A[j][1] - A[j][2];
		Be[j] = Be[j]- A[j][0] + A[j][1] + A[j][2];
		Bf[j] = Bf[j]- A[j][0] + A[j][1] - A[j][2];
		Bg[j] = Bg[j]- A[j][0] - A[j][1] + A[j][2];
		Bh[j] = Bh[j]- A[j][0] - A[j][1] - A[j][2];
	}
	sort(Ba.begin(), Ba.end());
	sort(Bb.begin(), Bb.end());
	sort(Bc.begin(), Bc.end());
	sort(Bd.begin(), Bd.end());
	sort(Be.begin(), Be.end());
	sort(Bf.begin(), Bf.end());
	sort(Bg.begin(), Bg.end());
	sort(Bh.begin(), Bh.end());
	vector<long long> ans(8,0);
	for (int i = n - 1; i >= n-m; i--) {
		ans[0] = ans[0] + Ba[i];
		ans[1] = ans[1] + Bb[i];
		ans[2] = ans[2] + Bc[i];
		ans[3] = ans[3] + Bd[i];
		ans[4] = ans[4] + Be[i];
		ans[5] = ans[5] + Bf[i];
		ans[6] = ans[6] + Bg[i];
		ans[7] = ans[7] + Bh[i];
	}
	long long answer=0;
	for (int i = 0; i < 8; i++) if (answer < ans[i]) answer = ans[i];
	cout << answer;
}


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

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

int main(){
    string s;
    cin >> s;
    int N = (int)s.size();
    int ans = 0;
    rep(i, N/2){
        if(s[0+i] != s[N-1-i]) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3612
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

/**
   ceil(0, 2) == 0
   ceil(1, 2) == 1
   ceil(2, 2) == 1
   ceil(3, 2) == 2
   ceil(4, 2) == 2
*/
template<class T>
T ceil(T dividend, T divisor)
{
    return (dividend + (divisor - 1)) / divisor;
}


int main()
{
    int64_t D, G;
    std::cin >> D >> G;

    struct Pr {
        int64_t p;
        int64_t c;
    };
    std::vector<Pr> pr;
    for (decltype(D) i = 0; i < D; ++i) {
        Pr t;
        std::cin >> t.p >> t.c;
        pr.push_back(t);
    }

    std::vector<int64_t> ord(D);
    std::iota(ord.begin(), ord.end(), 0);

    int64_t ans = INT64_MAX;
    do {
        int64_t n = 0;
        int64_t remain_score = G;
        for (auto& i: ord) {
            if (remain_score <= pr[i].p * 100 * (i+1)) {
                n += ceil(remain_score, 100 * (i+1));
                goto nxt;
            }
            else {
                remain_score -= pr[i].p * 100 * (i+1);
                n += pr[i].p;
            }
            #if 0
            for (int64_t j = 0; j < pr[i].p; ++j) {
                remain_score -= 100 * (i+1);
                n++;
                if (remain_score <= 0) {
                    goto nxt;
                }
            }
            #endif
            remain_score -= pr[i].c;
            if (remain_score <= 0) {
                goto nxt;
            }
        }
    nxt:
        ans = std::min(ans, n);
    } while (std::next_permutation(ord.begin(), ord.end()));

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 256
#pragma region
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define ALL(x) (x).begin(), (x).end()
constexpr int INF=1<<30; constexpr ll LINF=1LL<<60; constexpr ll mod=1e9+7; constexpr int NIL = -1;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
#pragma endregion
//-------------------

int main(){
    cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15);
    int x; cin >> x;
    x -= 400;
    cout << 8 - x/200 << endl;
    return 0;
}


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

#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 EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORTASC(c) sort((c).begin(), (c).end())
#define SORTDESC(c, t) sort((c).begin(), (c).end(), std::greater<t>());
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define VMAX(a) *max_element(ALL(a))
#define VMIN(a) *min_element(ALL(a))
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

const double PI = acos(-1.0);

using ll = long long;
using namespace std;

int main()
{
    ll n;
    vector<ll> v;

    cin >> n;

    REP(i, n){
        ll tmp;
        cin >> tmp;
        v.PB(tmp);
    }

    ll mn = 9999999999;
    REP(i, 100){
        ll tmp = 0;
        REP(j, n){
            tmp += (i+1 - v[j]) * (i+1 - v[j]);
        }
        mn = min(mn, tmp);
    }

    cout << setprecision(20) << mn << endl;

    return 0;
}

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007
#define PI 3.1415926535897932384626433

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s1, s2;
    cin >> s1 >> s2;
    string sum = s1 + s2;
    //cout << sum << endl;
    int num = stoi(sum);
    //cout << num << endl;
    int sqr = sqrt(num);
    if(sqr*sqr == num){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}


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

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

	vector<int> A(N);

	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
	}

	vector<int> B(N);
	B = A;

	sort(B.begin(), B.end());
	reverse(B.begin(), B.end());

	for (int i = 0; i < N; i++) {
		if (A.at(i) == B.at(0)) {
			cout << B.at(1) << endl;
		}else{
			cout << B.at(0) << endl;
		}
	}
}

Measured memory_bytes: 3200
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;

int main() {

	unsigned long long N;
	cin >> N;

	vector<string> S;
	string str;

	for (int i = 0; i < N; i++) {
		cin >> str;
		S.push_back(str);
	}

	sort(S.begin(), S.end());
	S.push_back("0");

	string str1 = S[0];
	string str2;
	unsigned long long cnt = 1;
	unsigned long long maxcnt = 1;
	vector<string> ans;
	
	for (int i = 1; i <= N; i++) {
		str2 = S[i];
		if (str1 == str2) {
			cnt += 1;
		}
		else if (str1 != str2) {
			if (cnt == maxcnt) {
				ans.push_back(str1);
			}
			else if (cnt > maxcnt) {
				maxcnt = cnt;
				ans.clear();
				ans.push_back(str1);
			}
			cnt = 1;
		}
		str1 = str2;
	}

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 15984
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

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

const int MAX_H = 100;

vector<int> hs;
vector<vector<int>> table;

int solve(const int N) {
    int ans = 0;

    for (int h = 0; h < MAX_H; h++) {
        int pos = 0;
        while (true) {
            while (table[h][pos] == 0 && pos < N) pos++;
            if (pos >= N) break;
            while (table[h][pos] == 1 && pos < N) pos++;
            ans++;
            if (pos >= N) break;
        }
    }

    return ans;
}

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

    hs.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> hs[i];
    }

    table.resize(MAX_H);
    for (int i = 0; i < MAX_H; i++) {
        table[i].resize(N, 0);
        for (int j = 0; j < N; j++) {
            if (hs[j] > i) {
                table[i][j] = 1;
            }
        }
    }

    // for (int i = 0; i < MAX_H; i++) {
    //     for (int j = 0; j < N; j++) {
    //         cout << table[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    cout << solve(N) << endl;

    return 0;
}


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

int main(){
  int n;
  cin >> n;
  map<string, int> mp;
  for(int i=0; i<n; ++i){
    string s;
    cin >> s;
    ++mp[s];
  }
  cout << mp.size() << endl;
}

Measured memory_bytes: 19120
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

/*--------Library Zone!--------*/

int n,m,x[114514];
int sum[114514];
int pa[114514];
int cnt[114514];
signed main(){
	cin>>n>>m;
	rep(i,n){
		cin>>x[i];
		sum[x[i]]++;
	}
	REP(i,100001){
		pa[i%m]+=sum[i]/2;
		cnt[i%m]+=sum[i];
	}
	int ans=0;
	rep(i,m/2+1){
		if(!i||i*2==m){
			ans+=cnt[i]/2;
		}else {
			if(cnt[i]<cnt[m-i]){
				int ma=min(pa[m-i],(cnt[m-i]-cnt[i])/2);
				ans+=ma;
				ans+=cnt[i];
			}else {
				int ma=min(pa[i],(cnt[i]-cnt[m-i])/2);
				ans+=ma;
				ans+=cnt[m-i];
			}
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3328
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int D = sc.nextInt();
		System.out.print("Christmas");
		while(D < 25) {
			System.out.print(" Eve");
			D++;
		}
		System.out.println();
	}
}


Measured memory_bytes: 21844
import sys

# sys.stdin = open('a1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


a, b = read_int_list()
if (a + b) % 3 == 0 or a % 3 == 0 or b % 3 == 0:
    print('Possible')
else:
    print('Impossible')


Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#define MAXN 100003

int array_a[MAXN][3];
int array_d[MAXN][3];

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

int main(){
	memset(array_a,-1,sizeof(int)*MAXN*3);
	memset(array_d,-1,sizeof(int)*MAXN*3);
	int N;
	scanf("%d",&N);

	for(int i=0;i<N;i++){
		scanf("%d %d %d",&array_a[i][0],&array_a[i][1],&array_a[i][2]);
	}

	array_d[0][0]=array_a[0][0];
	array_d[0][1]=array_a[0][1];
	array_d[0][2]=array_a[0][2];
	for(int i=1;i<N;i++){
		array_d[i][0]=array_a[i][0]+max(array_d[i-1][1],array_d[i-1][2]);
		array_d[i][1]=array_a[i][1]+max(array_d[i-1][0],array_d[i-1][2]);
		array_d[i][2]=array_a[i][2]+max(array_d[i-1][0],array_d[i-1][1]);
	}
	printf("%d",max(array_d[N-1][0],max(array_d[N-1][1],array_d[N-1][2])));
	return 0;

}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

int main() {
  in(string, s, t);
  int ans = 0;
  rep(i, 3) ans += s[i] == t[i];
  out(ans);
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
long long gcd(long long a, long long b) {
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
int main() {
	long long n, k, sum = 0; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> k;
		if (h == 0) {
			sum = k;
		}
		else if (sum != k) {
			sum = k / gcd(sum, k) * sum;
		}
	}
	cout << sum << endl;
	cin >> n;
}

Measured memory_bytes: 256
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

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

const int N = 1e4 + 10;

vector<int> g[N];
int u[N], v[N], deg[N], val[N], c[N];

int main() {
	fast_cin();
	int n; cin >> n;
	for (int i = 2; i <= n; ++i) {
		cin >> u[i] >> v[i];
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
		++deg[u[i]];
		++deg[v[i]];
	}
	priority_queue<pii, vector<pii>, greater<pii>> q;
	for (int i = 1; i <= n; ++i) {
		q.push({deg[i], i});
	}
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
	}
	sort(c + 1, c + 1 + n);
	for (int i = 1; i <= n; ++i) {
		while (!q.empty()) {
			auto cur = q.top();
			q.pop();
			int x = cur.second;
			if (val[x]) {
				continue;
			}
			val[x] = c[i];
			for (auto &y : g[x]) {
				--deg[y];
				q.push({deg[y], y});
			}
			break;
		}
	}
	ll ans = 0;
	for (int i = 2; i <= n; ++i) {
		ans += min(val[u[i]], val[v[i]]);
	}
	cout << ans << endl;
	for (int i = 1; i <= n; ++i) {
		cout << val[i] << ' ';
	}
	cout << endl;
}

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

using namespace std;

typedef long long ll;

ll get(ll x) {
  ll sum = 0;
  while(x > 0) {
    sum += x % 10;
    x /= 10;
  }
  return sum;
}

ll get_next(ll x) {
  ll possible = x, pw = 1, extra = 0;
  while(x > 0) {
    extra += pw * 9ll;
    pw *= 10ll;
    x /= 10ll;
    if(possible * get(x * pw + extra) > get(possible) * (x * pw + extra)) {
      possible = x * pw + extra;
    }
  }
  return possible;
}

int main() {
  int n; cin >> n;
  ll cur = 1;
  while(n--) {
    cout << cur << '\n';
    cur = get_next(cur + 1);
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> x(n, vector<int>(n)), y(n, vector<int>(n));
    rep(i, n){
        cin >> a.at(i);
        rep(j, a.at(i)){
            cin >> x[i][j] >> y[i][j];
            x[i][j]--;
        }
    } 
    ll bin[(1<<n)][n];
    for(int bit = 0; bit < (1<<n); bit++){
        for(int i = 0; i < n; i++){
            if(bit & (1<<i))bin[bit][i] = 1;
            else bin[bit][i] = 0;
        }
    }
    int ans = 0;
    for(int bit = 0; bit < (1<<n); bit++){
        bool ok = true;
        int now = 0;
        rep(i, n){
            if(bin[bit][i] == 1){
                now++;
                rep(j, a.at(i)){
                    if(bin[bit][x[i][j]] != y[i][j])ok = false;
                }
            }
        }
        if(ok)ans = max(ans, now);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4096
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	DoublyLinkedList first;
	DoublyLinkedList last;
	public static void main(String args[]) {
		new Main().run();
	}
	public void run() {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		first = new DoublyLinkedList();
		last = first;
		try {
			int n = Integer.parseInt(br.readLine());
			for (int i = 0; i < n; i++) {
				String line = br.readLine();
				int num;
				if (line.charAt(0) == 'i') {
					num = Integer.parseInt(line.substring(7));
					insertHead(num);
				} else {
					switch(line.charAt(6)) {
					case ' ':
						num = Integer.parseInt(line.substring(7));
						deleteKey(num);
						break;
					case 'F':
						deleteFirst();
						break;
					case 'L':
						deleteLast();
						break;
					}
				}
			}
			printList();
		} catch (Exception e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
			System.out.println(e);
		}
	}
	public void insertHead(int n) {
		DoublyLinkedList dll = new DoublyLinkedList(n);
		if (first.isGenerated()) {
			// 要素がゼロ個の場合
			first = dll;
			last = first;
		} else
		if (first == last) {
			// 要素が一つしかない場合
			dll.setNext(last);
			last.setBack(dll);
			first = dll;
		} else {
			// 要素が複数個ある場合
			dll.setNext(first);
			first.setBack(dll);
			first = dll;
		}
	}

	public void deleteKey(int n) {
		DoublyLinkedList dll = first;
		while (true) {
			if (dll.num == n) {
				if (dll == first) {
					// 先頭要素の場合
					deleteFirst();
				} else
				if (dll == last) {
					// 終端要素の場合
					deleteLast();
				} else {
					// 先頭でも最後でもない要素の場合
					dll.next.setBack(dll.back);
					dll.back.setNext(dll.next);
				}
				return;
			}
			if (dll  == last) {
				return;
			}
			dll = dll.next;
		}
	}
	public void deleteFirst() {
		if (first.next != null) {
			first.next.setBack(null);
			first = first.next;
		} else {
			// 要素が一つしかない場合
			first = new DoublyLinkedList();
			last = first;
		}

	}
	public void deleteLast() {
		if (last.back != null) {
			last.back.setNext(null);
			last = last.back;
		} else {
			// 要素が一つしかない場合
			last = new DoublyLinkedList();
			first = last;
		}
	}
	public void printList() {
		DoublyLinkedList dll = first;
		boolean flag = true;
		while (dll != null) {
			System.out.print((flag?"":" ") + dll.num);
			dll = dll.next;
			flag = false;
		}
		System.out.println();
	}
}

class DoublyLinkedList {
	int num;
	boolean exist;
	DoublyLinkedList next,back;
	DoublyLinkedList() {
		exist = false;
	}
	DoublyLinkedList(int n) {
		num = n;
		exist = true;
	}
	public boolean isGenerated() {
		return !exist;
	}
	public void setNext(DoublyLinkedList dll) {
		next = dll;
	}
	public void setBack(DoublyLinkedList dll) {
		back = dll;
	}
}


Measured memory_bytes: 133764
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

"""
pairwise coprime 1,3,7,10
setwise coprime 2,3,4,10


coprimeかどうかで全部やる
"""

def primes(n): #試し割り法で各素因数とその指数を求める
    cnt=collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            while n%i==0:
                cnt[i]+=1
                n//=i
    if n!=1:
        cnt[n]+=1
    return cnt


def solve():
    gcd = A[0]
    for a in A:
        gcd = math.gcd(gcd, a)
    if gcd != 1:
        return "not coprime"

    history = {}
    for i in range(10**6):
        history[i] = 0

    for a in A:
        d = primes(a)
        for key in d.keys():
            history[key] += 1
            if history[key] > 1:
                return "setwise coprime"
    return "pairwise coprime"
 
    
print(solve())

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

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
    
int main(){
    LL N,W;
    cin>>N>>W;
    LL w1,v1;
    cin>>w1>>v1;
    vector<vector<LL>> v(4);
    v[0].pb(v1);
    FOR(i,1,N){
        int w,val;
        cin>>w>>val;
        v[w-w1].pb(val);
    }
    REP(i,4){
        sort(ALL(v[i]));
        v[i].pb(0);
        reverse(ALL(v[i]));
        FOR(j,1,v[i].size())v[i][j]+=v[i][j-1];
    }
    LL res=0;

    REP(a,v[0].size())
        REP(b,v[1].size())
        REP(c,v[2].size())
        REP(d,v[3].size())
        if(a*w1+b*(w1+1)+c*(w1+2)+d*(w1+3)<=W)
            chmax(res,v[0][a]+v[1][b]+v[2][c]+v[3][d]);
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 256