akhauriyash/Code-Regression huggingface dataset:
#include <math.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#include <climits>
#include <bitset>
using namespace std ;
#define ld long double
#define int long long
#define ii pair<int,int>
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL); clock_t beg = clock()
#define dbg(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
const int N = 2e3+7 ;
const int INF = 1e18 ;
const int MOD = 1e9 + 7 ;
string s ;
int cnt[N] ;
int dis[N] ;
bool vis[N] ;
vi g[N] ;
void bfs(int n){
	queue<ii> Q ;
	Q.push({n,0}) ;
	vis[n] = 1 ;
	while(!Q.empty()){
		int f = Q.front().ff ;
		int d = Q.front().ss ;
		//vis[f] = 1 ;
		dis[f] = d ;
		Q.pop() ;
		for(int x : g[f]){
			if(!vis[x]){
				Q.push({x,d+1}) ;
				vis[x]=1 ;
			}
		}
		//cout << "huh\n ";
	}

}

void solve(){
	int n , x , y ;
	cin >> n >> x >> y ;
	for(int i = 1 ; i < n ; i++){
		g[i].pb(i+1) ;
		g[i+1].pb(i) ;
	}
	g[x].pb(y) ;
	g[y].pb(x) ;
	//bfs(1) ;
	for(int i = 1 ; i <= n ; i++){
		ms(vis,0) ;
		ms(dis,0) ;
		bfs(i) ;
		for(int i = 1 ; i <= n ; i++){
			cnt[dis[i]]++ ;
		}
	}
	for(int i = 1 ; i < n ; i++){
		cout << cnt[i]/2 << endl ;
	}
}

int32_t main(){
	FAST_IO ;
	int t = 1 ;
//	cin >> t ;
	while(t--){
		solve() ;
	}
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
}


Measured memory_bytes: 512
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007
#define MOD 86400
#define RAN 10800

using namespace std;

long long N;
long long ans;


/*
 *範囲の和を取得
 */
//区間[l, r)
struct segtree {
	vector<long long> data;
	long long n;
	segtree(long long nin){
		n = pow( 2, ceil( log(nin) / log(2) ) );
		long long size = 2 * n - 1;
		this->data.resize(size, 0);
	}

	//API for update val
	void update(long long idx, long long val){
		update(idx, val, 0, 0, n);
	}

	long long update(long long idx, long long val, long long node_id, long long left, long long right){
		//if query idx is within range return val
		if( !( left <= idx && idx < right ) ){
			return data[node_id];
		}
		if( left + 1 < right ) {
			//when node range is not 1, get update children val and update node data
			long long mid = (left + right) / 2 ;
			long long L = update(idx, val, 2 * node_id + 1, left, mid);
			long long R = update(idx, val, 2 * node_id + 2, mid, right);
			data[node_id] = L + R;
		} else {
			//when node range is 1, update node data
			data[node_id] = data[node_id] + val;
		}
		return data[node_id];
	}
	
	//API for get value of [l, r)
	long long get(long long l, long long r){
		return get(l, r, 0, 0, n);
	}

	/*
	 *internaly used function
	 *query_l: query left range
	 *query_r: query right range
	 *node_id: node id of 
	 *node_l:  node left range 
	 *node_r:  node right range
	 */
	long long get(long long query_l, long long query_r, long long node_id, long long node_l, long long node_r){
		//query range is outside of node range: return INF
		if( query_r <= node_l || node_r <= query_l ){
			return 0;
		}
		//query range is within node range: return node val
		if( query_l <= node_l && node_r <= query_r ){
			return data[node_id];
		}
		long long mid = (node_l + node_r) / 2;
		long long L = get(query_l, query_r, 2 * node_id + 1, node_l, mid);
		long long R = get(query_l, query_r, 2 * node_id + 2, mid, node_r);
		return L + R;
	}
};




int main(){
	segtree sg(2*MOD + 10);
	cin >> N;
	long long cur = 0;
	for(int i = 0; i < N; i++){
		long long a, b;
		cin >> a >> b;
		cur += a;
		sg.update(cur%MOD, 1);
		sg.update(cur%MOD + MOD, 1);
		cur += b;
		cur %= MOD;
	}
	long long ans = 0;
	for(int s = 0; s + RAN <= 2*MOD; s++){
		ans = max(ans, sg.get(s, s + RAN + 1));
	}
	cout << ans << endl;
}


Measured memory_bytes: 4480
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanInit()

	n := nextInt()
	t := nextInt()
	tl := make([]int, n)

	sum := 0
	tl[0] = nextInt()
	for i := 1; i < n; i++ {
		tl[i] = nextInt()
		sum += min(t, tl[i]-tl[i-1])
	}
	sum += t
	fmt.Println(sum)
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// ---- readfunc
var sc = bufio.NewScanner(os.Stdin)

func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 6148
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
//#include<cstdio>
//#include<algorithm>
//#include<vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int N, M;
int K[100001];
int to[200001], ne[200001], he[100001], num[200001];
vector<int> S1[100001], S2[100001];
int dame[100001];

int dfs(int v, int prev) {
	if (dame[v]) {
		if (dame[v] >= 2) {
			ll tmp = dfs(to[dame[v]], dame[v] ^ 1);
			int k = K[v] - num[dame[v]];
			for (int i = k - 1; i < K[v]; i++) {
				S1[v][i] = S1[v][i] * tmp % M;
			}
			S2[v][k - 1] = tmp;
			tmp = S2[v][K[v] - 1];
			for (int i = K[v] - 2; i >= 0; i--) {
				tmp = tmp * S2[v][i] % M;
				S2[v][i] = tmp;
			}
			dame[v] = -1;
		}

		ll ret = 1;
		if (prev >= 2) {
			int k = K[v] - num[prev];
			if (k >= 2) ret *= S1[v][k - 2];
			if (k < K[v]) ret *= S2[v][k];
			ret %= M;
		}
		else ret = S1[v].back();

		return ret + 1;
	}
	dame[v] = prev;
	ll ret = 1;
	int k = 0;
	for (int i = he[v]; i; i = ne[i]) {
		int tmp = 1;
		if (i != prev) {
			tmp = dfs(to[i], i ^ 1);
			ret = ret * tmp % M;
		}
		S1[v][k] = ret;
		S2[v][k++] = tmp;
	}
	if (prev == -1) {
		for (int i = k - 2; i >= 0; i--) {
			S2[v][i] = ((ll)S2[v][i] * S2[v][i + 1]) % M;
		}
	}
	return ret + 1;
}

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


	cin >> N >> M;

	int k = 2;
	rep1(i, N - 1) {
		int x, y;
		cin >> x >> y;

		num[k] = K[x]++;
		to[k] = y;
		ne[k] = he[x];
		he[x] = k++;
		num[k] = K[y]++;
		to[k] = x;
		ne[k] = he[y];
		he[y] = k++;
	}
	rep1(i, N) {
		S1[i].resize(K[i]);
		S2[i].resize(K[i]);
	}

	rep1(j, N) {
		co(dfs(j, -1) - 1);
	}


	Would you please return 0;
}

Measured memory_bytes: 21248
#line 1 "/workspaces/compro/lib/template.hpp"


#line 1 "/workspaces/compro/lib/io/vector.hpp"
#include <iostream>
#include <vector>

#ifndef IO_VECTOR
#define IO_VECTOR

template <class T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  int size = v.size();
  for (int i = 0; i < size; i++) {
    std::cout << v[i];
    if (i != size - 1)
      std::cout << " ";
  }
  return out;
}

template <class T> std::istream &operator>>(std::istream &in, std::vector<T> &v) {
  for (auto &el : v) {
    std::cin >> el;
  }
  return in;
}

#endif
#line 4 "/workspaces/compro/lib/template.hpp"
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 2 "main.cpp"

const std::string YES = "Yes";
const std::string NO = "No";

// generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator)
int main() {
  // failed to analyze input format
  // TODO: edit here
  int n;
  std::cin >> n;
  std::vector<pair<ll, ll>> a(n);
  for (int i = 0; i < n; ++i) {
    int d1, d2;
    cin >> d1 >> d2;
    a[i] = {d1, d2};
  }

  REP(i, n) {
    if (a[i].first == a[i].second) {
      bool ok = true;
      REP(j, 3) {
        if (a[i + j].first != a[i + j].second) {
          ok = false;
          break;
        }
      }
      if (ok) {
        cout << YES << endl;
        return 0;
      }
    }
  }
  std::cout << NO << std::endl;
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L

bool isPrime(long long x) {
    if (x == 1) return true;
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

long long gcd(long long a, long long b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

vector<long long> common_divisors(long long a, long long b) {
    long long n = gcd(a, b);
    vector<long long> ans;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (n / i == i) {
                ans.push_back(i);
            }
            else {
                ans.push_back(n / i);
                ans.push_back(i);
            }
        }
    }
    return ans;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    if (n == 1) {
        cout << (int)(a[0] / pow(2, k));
        return 0;
    }
    sort(a.rbegin(), a.rend());
    while (k) {
        while (k && a[0] >= a[1]) {
            a[0] /= 2;
            k--;
        }
        int temp = a[0];
        a.erase(a.begin(), a.begin() + 1);
        int l  = 0, h = n - 2;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (a[m] > temp) {
                l = m+1;
            }
            else {
                h = m-1;
            }
        }
        a.insert(a.begin() + l, temp);
    }
    
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    cout << sum;
    return 0;
}

Measured memory_bytes: 3884
#include <iostream>
#include <string>
#define rep(i, n) for (int i = 0; (i) < (int)(n); i++)
using namespace std;

int p(string s) {
  int n = s.length();
  int m;
  if (n % 2 == 0) {
    m = n / 2;
  } else {
    m = (n - 1) / 2;
  }
  for (int i = 0; i < m; i++) {
    if (s[i] != s[n - 1 - i]) {
      return 0;
    }
  }
  return 1;
}

int main() {
    string S;
    cin >> S;
    int N = S.length();
    if (p(S) == 0) {
      cout << "No" << endl;
      return 0;
    }
    if (p(S.substr(0, (N - 1) / 2)) == 0) {
      cout << "No" << endl;
      return 0;
    }
    if (p(S.substr((N + 3) / 2 - 1, (N - 1) / 2)) == 0) {
      cout << "No" << endl;
      return 0;
    }
    cout << "Yes" << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

struct SegTree {
  int size;
  vector<ll> pos;
  SegTree(ll N) { size = 1; while(size<N) size<<=1; pos.resize(2*size,0); }
  ll operator[](const ll &x) const { return pos[x+size]; }

  void build() { per(i,size) operate(i); }
  void set(ll x, const ll v) { pos[x+size] = v; }
  void update(ll x, const ll v) { set(x,v); x+=size; while (x>>=1) operate(x); }
  ll query(ll a, ll b) {
    ll L = LLINF, R = LLINF;
    for (a+=size, b+=size; a<b; a>>=1, b>>=1) {
      if (a&1) { L = q(L,pos[a]); a++; }
      if (b&1) { b--; R = q(pos[b],R); }
    }
    return q(L,R);
  }
  void operate(ll i) { pos[i] = min(pos[i*2], pos[i*2+1]); }
  ll q(ll x, ll y) { return min(x, y); }
};

// ----------------------------------------------------------------------
// ----------------------------------------------------------------------

int main() {
  ll H, W; cin >> H >> W;
  ll A[H], B[H]; rep(i,H) { cin >> A[i] >> B[i]; A[i]--; B[i]--; }

  set<ll> num; rep(i,W) num.insert(i);
  SegTree st(W);
  rep(i,H) {
    auto titr = num.upper_bound(B[i]);
    if (titr!=num.begin()) { 
      ll from = *(--titr);
      if (B[i]!=W-1 && st[B[i]+1]==LLINF) { 
        num.insert(B[i]+1);
        st.update(B[i]+1, st[from]+(B[i]+1-from));
      }
      auto itl = num.lower_bound(A[i]), itr = num.upper_bound(B[i]);
      for (auto it = itl; it != itr;) {
        st.update(*it,LLINF);
        it = num.erase(it);
      }
    }
    // for (auto x: num) cout << x << " "; cout << endl;
    // rep(i,W) cout << st[i] << " "; cout << endl;

    ll result = st.query(0,W);
    if (result==LLINF) result = -1;
    else result += i+1;
    cout << result << endl;
  }

  return 0;
}

Measured memory_bytes: 19864
import math

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

x = a * 100 / 8
y = (a+1) * 100 / 8
z = b * 100 / 10
w = (b+1) * 100 / 10
    
if z <= x and x < w and w <= y:
    print(math.ceil(x))
elif x <= z and z < y and y <= w:
    print(math.ceil(z))
else:
    print(-1)


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

int main() {
    int n;
    cin >> n;
    vector<int> v;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x % 10 != 0) {
            v.push_back(x);
        }
        sum += x;
    }

    sort(v.begin(), v.end());
    int ans = sum;
    if (sum % 10 != 0) {
        ans = sum;
    } else {
        if (v.size()) {
            sum -= v[0];
            if (sum % 10 != 0) {
                ans = sum;
            } else{
                ans = 0;
            }
        } else {
            ans = 0;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;
typedef tuple<int, int, int> T;

int n, m, q;
int a[51], b[51], c[51], d[51];
vector<int> res;
int ans = 0;

void dfs(int s) {
	if (res.size() == n) {
		int sum = 0;
		rep(i, q) {
			if (res[b[i]] - res[a[i]] == c[i]) {
				sum += d[i];
			}
		}
		ans = max(ans, sum);
		return;
	}
	for (int i = s; i <= m; ++i) {
		res.push_back(i);
		dfs(i);
		res.pop_back();
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	rep(i, q) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--; b[i]--;
	}
	dfs(1);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3648
#include<iostream>
using namespace std;
const int MOD = 1000000007;
int N,M,A,ans[100001];
bool a[100001]={0};

int solve(int n){
	if(n<0||a[n])return 0;
	if(ans[n]==-1)ans[n]=(solve(n-1)+solve(n-2))%MOD;
	return ans[n];
}
int main(){
	cin>>N>>M;
	for(int i=0;i<M;i++){cin>>A;a[A]=true;}
	fill(ans,ans+N+1,-1);
	ans[0]=1;
	cout<<solve(N);
	return 0;
}

Measured memory_bytes: 3840
package main

import (
	"fmt"
	"sort"
)

type point struct{ x, y int }
type points []point
type byX struct{ points }
type byY struct{ points }

func (p points) Len() int        { return len(p) }
func (p points) Swap(i, j int)   { p[i], p[j] = p[j], p[i] }
func (b byX) Less(i, j int) bool { return b.points[i].x < b.points[j].x }
func (b byY) Less(i, j int) bool { return b.points[i].y < b.points[j].y }

var n int
var redPoints, bluePoints []point

func nextInt() int {
	var x int
	fmt.Scan(&x)
	return x
}

func reverse(s []point) []point {
	j := len(s)
	for i := 0; i < j; i++ {
		j--
		s[i], s[j] = s[j], s[i]
	}
	return s
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	n = nextInt()

	redPoints = make([]point, n)
	bluePoints = make([]point, n)

	for i := range redPoints {
		redPoints[i] = point{nextInt(), nextInt()}
	}
	for i := range bluePoints {
		bluePoints[i] = point{nextInt(), nextInt()}
	}

	ans := 0
	for i := range make([]struct{}, 2) {
		sort.Sort(byX{redPoints})
		sort.Sort(byY{redPoints})
		if i == 0 {
			sort.Sort(byX{redPoints})
		}
		for j := range make([]struct{}, 2) {
			sort.Sort(byX{bluePoints})
			sort.Sort(byY{bluePoints})
			if j == 0 {
				sort.Sort(byX{bluePoints})
			}
			bluePoints = reverse(bluePoints)

			rPs := make([]point, n)
			bPs := make([]point, n)
			copy(rPs, redPoints)
			copy(bPs, bluePoints)

			cnt := 0
			for len(rPs) > 0 {
				for k := len(bPs) - 1; k >= 0; k-- {
					rPsh := rPs[len(rPs)-1]
					bPsk := bPs[k]
					if rPsh.x < bPsk.x && rPsh.y < bPsk.y {
						rPs = rPs[:len(rPs)-1]
						bPs = append(bPs[:k], bPs[k+1:]...)
						cnt++
						break
					}
					if k == 0 {
						rPs = rPs[:len(rPs)-1]
					}
				}
				ans = max(ans, cnt)
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+10;

template<int char_size>
struct Trie{
    struct TrieNode{
        char c; int dep,sub=0;
        vector<int> nxt,idxs;
        TrieNode(char c,int dep):c(c),dep(dep),nxt(char_size,-1){}
    };
    vector<TrieNode> Nodes;
    function<int(char)> ctoi;
    Trie(function<int(char)> ctoi):ctoi(ctoi){
        Nodes.emplace_back('$',0);
    }
    inline int &next(int node,int c){
        return Nodes[node].nxt[c];
    }
    inline int &next(int node,char c){
        return next(node,ctoi(c));
    }
    void add(const string &s,int x){
        int node=0;
        for (int i=0;i<s.size();++i){
            int k=ctoi(s[i]);
            if (next(node,k)<0){
                next(node,k)=Nodes.size();
                Nodes.emplace_back(s[i],i+1);
            }
            node=next(node,k);
            ++Nodes[node].sub;
        }
        Nodes[node].idxs.emplace_back(x);
    }
    int find(const string &s){
        int node=0;
        for (int i=0;i<s.size();++i){
            int k=ctoi(s[i]);
            if (next(node,k)<0) return -1;
            node=next(node,k);
        }
        return node;
    }
    int sub(int node){return ~node?Nodes[node].sub:0;}
    vector<int> idxs(int node){return Nodes[node].idxs;}
    template<typename F>
    void query(const string &s,const F &f,int l){
        int node=0;
        for (int i=l;i<s.size();++i){
            node=next(node,s[i]);
            if (node<0) return;
            for (auto &idx:Nodes[node].idxs) f(idx);
        }
    }
    template<typename F,typename G>
    void dfs(const string &s,const F &f,const G &g){
        int node=0;
        for (int i=0;i<s.size();++i){
            g(idxs(node).size());
            for (int j=0;j<char_size;++j) if (ctoi(s[i])!=j){
                f(j,ctoi(s[i]),sub(next(node,j)));
            }
            node=next(node,s[i]);
        }
    }
    int size(){return Nodes.size();};
};

int dp0[MAX_N][26][26];
int dp1[MAX_N];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<string> S(N);
    for (int i=0;i<N;++i) cin >> S[i];
    Trie<26> trie([](char c){return c-'a';});
    for (int i=0;i<N;++i) trie.add(S[i],i);
    for (int i=0;i<N;++i){
        auto f=[&](int j,int k,int x){dp0[i][j][k]+=x;};
        auto g=[&](int x){dp1[i]+=x;};
        trie.dfs(S[i],f,g);
    }
    int Q; cin >> Q;
    for (;Q--;){
        int k; cin >> k; --k;
        string p; cin >> p;
        int ans=1+dp1[k];
        for (int i=0;i<26;++i){
            for (int j=i+1;j<26;++j){
                ans+=dp0[k][p[i]-'a'][p[j]-'a'];
            }
        }
        cout << ans << '\n';
    }
}

Measured memory_bytes: 294504
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAX 10000
#define INF (1<<30)

using namespace std;
enum state{
  BLACK,
  WHITE
};

int main(){
  vector<pair<int,int>> a[MAX];
  int n; cin>>n;
  int d[MAX];
  state s[MAX];

  for(int i=0;i<n;i++){
    int u,k; cin>>u>>k;
    for(int j=0;j<k;j++){
      int v,c; cin>>v>>c;
      a[u].push_back(make_pair(v,c));
    }
  }

  for(int i=0;i<n;i++){
    s[i]=WHITE;
    d[i]=INF;
  }
  d[0]=0;

  priority_queue<pair<int,int>> q;
  q.push(make_pair(0,0));

  while(!q.empty()){
    pair<int,int> p;
    p = q.top(); q.pop();
    if(s[p.second]==BLACK) continue;
    d[p.second]=p.first*-1;
    s[p.second]=BLACK;
    
    for(auto it = a[p.second].begin(); it!=a[p.second].end(); it++){
      int i = it->first;
      int cost = it->second;
      if(s[i]==WHITE && d[i] > d[p.second] + cost ){
        d[i]=d[p.second]+cost;
        q.push(make_pair(d[i]*-1,i));
      }
    }
  }
  
  for(int i=0;i<n;i++){
    printf("%d %d\n",i,d[i]);
  }


}

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


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 2e6 + 5;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);


int n , m;

int spf[N];
bool prime[N];

void seive() {

    prime[0] = prime[1] = 1;

    for(ll i = 2 ; i < N ; i ++) {
            if(!prime[i]) {
                    spf[i] = i;
                    for(ll j = i*i ; j < N ; j += i) {
                            spf[j] = i;
                            prime[j] = 1;
                    }
            }
    }
}

map < int , int > freq;

void work(int x) {

    if(x == 1) return;

    while(x > 1) {
            int curr = spf[x];

            freq[curr] ++;

            while(x%curr == 0) x /= curr;
    }

    if(x > 1) {
            freq[x] ++;
    }
}

bool check(int x) {

    if(x == 1) return false;

    while(x > 1) {
            int curr = spf[x];

            if(freq[curr] > 1) return true;
            while(x%curr == 0) x /= curr;
    }

    if(x > 1) {
            if(freq[x] > 1) return true;
            freq[x] ++;
    }

    return false;
}


void solve(int testCase){

    scanf("%d" , &n);

    seive();

    vector < int > a(n);

    int g = 0;
    for(int i = 0 ; i < n ; i ++) {
            scanf("%d" , &a[i]);
            work(a[i]);

            g = __gcd(g , a[i]);
    }

    if(g > 1) {
            printf("not coprime\n");
            return;
    }

    for(int i = 0 ; i < n ; i ++) {
            if(check(a[i])) {
                    printf("setwise coprime\n");
                    return;
            }
    }

    printf("pairwise coprime\n");


}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}


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

#define ll long long int

void solve(){
    ll h,n;
    cin >> h >> n;
    vector<ll> v(n);
    for(auto &it:v)
        cin >> it;
    if(accumulate(v.begin(),v.end(),0LL) >= h){
        cout << "Yes\n";
    } 
    else {
        cout << "No\n";
    }
}

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

    int test=1;
    // cin >> test;
    while(test--)
        solve();
    
    return 0;
}

Measured memory_bytes: 1024
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    res = [[0] * W for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            if grid[y][x] == "#":
                visited[y][x] = True
                que = deque([[y, x]])
                cnt = 1
                tmp = []
                while que:
                    h, w = que.popleft()
                    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if grid[h][w] == "#" and grid[next_h][next_w] == ".":
                            if not visited[next_h][next_w]:
                                que.append([next_h, next_w])
                                tmp.append([next_h, next_w])
                                visited[next_h][next_w] = True
                        elif grid[h][w] == "." and grid[next_h][next_w] == "#":
                            if not visited[next_h][next_w]:
                                cnt += 1
                                que.append([next_h, next_w])
                                visited[next_h][next_w] = True
                for h, w in tmp:
                    res[h][w] = cnt
    ans = 0
    for h in range(H):
        ans += sum(res[h])
    print(ans)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 93704
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int sigma(int n){
    int sum=0;
    for (int i=1; i<=(n); i++){
        sum+=i;
    }
    return sum;
}
int distance(int yo,int xo,int yi,int xi){
    return (yo-yi)*(yo-yi)+(xo-xi)*(xo-xi);
}
signed main(){
    int A,B;
    cin >> A >> B;
    cout << lcm(A,B) << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
//		// get a integer
//		int a = sc.nextInt();
//		// get a string
//		String s = sc.next();
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0; i<n; i++){
			a[i] = sc.nextInt();
		}
		int cnt = 1;
		for(int i=0; i<n-1; i++){
			if(a[i]==a[i+1])	continue;
			if(a[i]<a[i+1]){
				while(i<n-1 && a[i]<=a[i+1])	i++;
				cnt++;
			}
			else{
				while(i<n-1 && a[i]>=a[i+1])	i++;
				cnt++;
			}
			if(i==n-1)	cnt--;
		}
		System.out.println(cnt);
	}
}


Measured memory_bytes: 62044
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
#![macro_use]

use std::cmp::*;
use std::collections::*;
use std::io::*;
use std::mem::*;
use std::num::*;
use std::slice::*;

fn main() {
    let (r, w, e) = (stdin(), stdout(), stderr());
    let mut io = IO::new(r.lock(), w.lock(), e.lock());
    // =============================================== //
    let (n, k): (usize, usize) = (io.read(), io.read());
    let h = io.readn::<isize>(n);

    let inf = 3 << 29;
    let mut dp: Vec<isize> = vec![inf; n + k];
    dp[0] = 0;
    for i in 0..n {
        for k in 1..(k + 1) {
            if i + k < n {
                dp[i + k] = min(dp[i + k], dp[i] + (h[i] - h[i + k]).abs());
            }
        }
    }
    io.writeln(dp[n - 1]);
}

// IO
struct IO<R: Read, W: Write, E: Write> {
    Read: R,
    Write: BufWriter<W>,
    Error: BufWriter<E>,
}
impl<R: Read, W: Write, E: Write> IO<R, W, E> {
    fn new(r: R, w: W, e: E) -> IO<R, W, E> {
        IO {
            Read: r,
            Write: BufWriter::new(w),
            Error: BufWriter::new(e),
        }
    }
    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let next: String = self
            .Read
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
        next.parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    fn readn<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect::<Vec<_>>()
    }
    fn readmat<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n).map(|_| self.readn(m)).collect()
    }
    fn write<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
    }
    fn writeln<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
        self.Write.write(b"\n");
    }
    fn debug<S: std::fmt::Debug>(&mut self, val: S) {
        writeln!(self.Error, "(debug ) {:?}", &val);
    }
    fn debug2<S: std::fmt::Debug>(&mut self, val1: S, val2: S) {
        writeln!(self.Error, "(debug2) {:?} -> {:?}", val1, val2);
    }
}


Measured memory_bytes: 6396
def solve(N, A):
    if len(list(filter(lambda x: x < 0, A))) % 2 == 0:
        return sum(map(abs, A))
    else:
        min_abs = min(map(abs, A))
        return sum(map(abs, A)) - 2 * min_abs


N = int(input())
A = list(map(int, input().split()))
print(solve(N, A))

Measured memory_bytes: 14412
import heapq
import collections


class Graph:

    def __init__(self, size):
        self.size = size
        self.graph = [[] for i in range(size)]

    def add_edge(self, source, target, cost):
        self.graph[source].append(self.Edge(target, cost))

    def add_bidirectional_edge(self, source, target, cost):
        self.add_edge(source, target, cost)
        self.add_edge(target, source, cost)

    def min_dist_dijkstra(self, s):
        dist = [float('inf')] * self.size
        dist[s] = 0
        q = [(0, s)]
        while q:
            node = self.Node(*heapq.heappop(q))
            v = node.id
            if dist[v] < node.dist:
                continue
            for e in self.graph[v]:
                if dist[e.target] > dist[v] + e.cost:
                    dist[e.target] = dist[v] + e.cost
                    heapq.heappush(q, (dist[e.target], e.target))
        return dist

    def min_path_dijkstra(self, s, t):
        dist = [float('inf')] * self.size
        prev = [-1] * self.size
        dist[s] = 0
        q = [(0, s)]
        while q:
            node = self.Node(*heapq.heappop(q))
            v = node.id
            if dist[v] < node.dist:
                continue
            for e in self.graph[v]:
                if dist[e.target] > dist[v] + e.cost:
                    dist[e.target] = dist[v] + e.cost
                    heapq.heappush(q, (dist[e.target], e.target))
                    prev[e.target] = v
            if v == t:
                break

        path = [t]
        while path[-1] > -1:
            path.append(prev[path[-1]])
        return path[1:]

    def min_dist_queue(self, s):
        dist = [float('inf')] * self.size
        dist[s] = 0
        q = collections.deque()
        q.append(s)
        while q:
            v = q.popleft()
            for e in self.graph[v]:
                if dist[e.target] > dist[v] + e.cost:
                    dist[e.target] = dist[v] + e.cost
                    if e.cost == 0:
                        q.appendleft(e.target)
                    else:
                        q.append(e.target)
        return dist

    def __str__(self):
        res = ''
        for i in range(self.size):
            res += str(i)
            for e in self.graph[i]:
                res += ' ' + str(e.target)
            res += '\n'
        return res

    class Edge:

        def __init__(self, target, cost):
            self.target = target
            self.cost = cost

    class Node:

        def __init__(self, dist, i):
            self.dist = dist
            self.id = i

        def __cmp__(self, other):
            if self.dist < other.dist:
                return -1
            elif self.dist == other.dist:
                return 0
            else:
                return 1

V, E, root = map(int, input().split())
g=Graph(V)
for i in range(E):
    s, t, d = map(int, input().split())
    g.add_edge(s,t,d)
dist = g.min_dist_dijkstra(root)
for i in range(V):
    if dist[i] == float('inf'):
        print('INF')
    else:
        print(dist[i])

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

using namespace std;
#define sz(a) int(a.size())
#define ll  long long
#define ull unsigned long long
#define mod (ll)(1000000007)
#define endl '\n'
#define ENGZ ios::sync_with_stdio(0);ios_base::sync_with_stdio(0);cin.tie(0) , cout.tie(0) ;
#define pi double(acos(-1))
#define S second
#define F first
#define mem(arr,a) memset(arr,a,sizeof arr)
//  freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ll fp(ll n , ll p )
{
    if(p==0)
        return 1 ;
    if(p==1)
        return n%mod ;
    ll res ;
    res = fp(n,p/2)%mod;
    res = (res*res)%mod ;
    if(p%2)
        res = (res*n)%mod ;
    return res;
}


int main()
{
    ENGZ;
    pair<ll,ll> arr[200005] ;
    ll n , a = 0 , b;
    cin>>n ;
    for(int i=0 ; i <n ; i++)
    {
        cin>>arr[i].S >>arr[i].F ;
    }
    sort(arr,arr+n);
    bool f = 1 ;
    for(int i=0 ; i<n; i ++)
    {
        a+=arr[i].S ;
        if(a>arr[i].F)
            f=0 ;
    }
    if(f)cout<<"Yes"<<endl;
    else cout<<"No" <<endl ;
}


Measured memory_bytes: 3328
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            #経路圧縮
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.find_root(x)
        y = self.find_root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSame(self, x, y):
        return self.find_root(x) == self.find_root(y)

    # ノードxが属する木のサイズを返す
    def size(self, x):
        return -self.root[self.find_root(x)]

n,m,k=map(int,input().split())
fre=[list(map(int,input().split()))for _ in range(m)]
bro=[list(map(int,input().split()))for _ in range(k)]
f_cnt=[0]*(n+1)
b_cnt=[0]*(n+1)
u=UnionFind(n)

for i in range(m):
    u.unite(fre[i][0],fre[i][1])
    f_cnt[fre[i][0]]+=1
    f_cnt[fre[i][1]]+=1
for i in range(k):
    if u.isSame(bro[i][0],bro[i][1])==True:
        b_cnt[bro[i][0]]+=1
        b_cnt[bro[i][1]]+=1

for i in range(1,n+1):
    print(u.size(i)-f_cnt[i]-b_cnt[i]-1 ,end=" ")
    
    

Measured memory_bytes: 55820
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <stdint.h>
#include <queue>
#include <bitset>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

#define PI (3.14159265358979323846)
#define INF (2147483647)
#define INF_LL (9223372036854775807)
#define DIV_NUM (1000000007)
typedef long long ll;

// 配列初期化テンプレ
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T& val) {
	std::fill((T*)array, (T*)(array + N), val);
}



int main() {

	ll A, B, N;
	cin >> A >> B >> N;

	ll ans = 0;
	if (N >= B) {
		ans = (double)(A) * ((double)(B)-1.0) / (double)(B);
	}
	else {
		ans = (double)(A) * (double)(N) / (double)(B);
	}

	cout << (ll)(ans) << endl;

	return 0;

}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll inf = 1e14;

class min_cost_flow{
private:
    int N;
    struct edge{int to; ll cap,cost; int rev;};
    vector<vector<edge>> G;
    vector<ll> h,dist,prevv,preve;
public:
    min_cost_flow(int n){
        N = n;
        G = vector<vector<edge>>(N);
        h = dist = prevv = preve = vector<ll>(N,0);
    }
    void add_edge(int from,int to,ll cap,ll cost){
        G[from].push_back((edge){to,cap,cost,(int) G[to].size()});
        G[to].push_back((edge){from,0,-cost,(int) G[from].size()-1});
    }
    ll answer(int s,int t,ll f){
        ll res = 0;
        fill(h.begin(),h.end(),0);
        while(f>0){
            priority_queue<P,vector<P>,greater<P>> Q;
            fill(dist.begin(),dist.end(),inf);
            dist[s] = 0;
            Q.push(P(0,s));
            while(!Q.empty()){
                P p = Q.top(); Q.pop();
                int v = p.second;
                if(dist[v]<p.first) continue;
                for(int i=0;i<G[v].size();i++){
                    edge &e = G[v][i];
                    if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
                        dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        Q.push(P(dist[e.to],e.to));
                    }
                }
            }
            if(dist[t]==inf) return -1;
            for(int v=0;v<N;v++) h[v] += dist[v];
            ll d = f;
            for(int v=t;v!=s; v=prevv[v]){
                d = min(d,G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d*h[t];
            for(int v=t;v!=s;v=prevv[v]){
                edge &e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

struct edge{
    ll s,t,d;
};

int main(){
    int N,M;
    cin >> N >> M;
    vector<vector<edge>> g(N);
    vector<edge> edges(M);
    for(int i=0;i<M;i++){
        int a,b,c;
        cin >> a >> b >> c;
        edges[i] = {a,b,c};
        g[a].push_back({a,b,c});
    }
    vector<ll> dp(N,0);
    for(int i=N-1;i>=0;i--){
        for(auto& e:g[i]) dp[i] = max(dp[i],dp[e.t]+e.d);
    }
    ll D = dp[0];
    min_cost_flow flow(N+2);
    vector<ll> b(N,0);
    flow.add_edge(0,N-1,inf,D);
    ll ans = 0;
    ll tinf = 10000;
    for(auto& e:edges){
        b[e.t] -= tinf;
        b[e.s] += tinf;
        ans += -e.d*tinf;
        flow.add_edge(e.s,e.t,tinf-1,e.d);
    }
    ll sum = 0;
    for(int i=0;i<N;i++){
        if(b[i]>0) flow.add_edge(N,i,b[i],0);
        if(b[i]<0) flow.add_edge(i,N+1,-b[i],0);
        sum += max(b[i],0LL);
    }
    cout << ans+flow.answer(N,N+1,sum) << endl;
}


Measured memory_bytes: 3328
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> >G(252),R(252);
int n,m;
int d[552];
bool u[252];
void f(int v)
{
	u[v]=1;
	for(int i=0;i<R[v].size();i++)
	{
		if(!u[R[v][i]])f(R[v][i]);
	}
}
bool vi[252];
bool ok(int v)
{
    bool ans=u[v];
    vi[v]=1;
    for(int i=0;i<G[v].size();i++)
    {
        if(!vi[G[v][i]])ans&=ok(G[v][i]);
    }
    return ans;
}
main()
{
	while(cin>>m,m)
	{
		cin>>n;
		for(int i=0;i<=n+1;i++)G[i].clear(),R[i].clear(),d[i]=vi[i]=u[i]=0;
		for(int i=1;i<=n;i++)cin>>d[i];
		for(int i=0;i<=n;i++)
		{
			for(int j=1;j<=m&&i+j<=n+1;j++)
			{
				int k=i+j+d[i+j];
				if(k>n+1)k=n+1;
				if(k<0)k=0;
				G[i].push_back(k);
				R[k].push_back(i);
			}
		}
		f(n+1);
		cout<<(ok(0)?"OK":"NG")<<endl;
	}
}



Measured memory_bytes: 3188
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
using qll = queue<ll>;
using vb = vector<bool>;
using sll = stack<ll>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)
#define REP(i,n) for(long long i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define elnd endl //* missspell check
ll INF = 1LL << 60;
long long N;
vll res;
priority_queue<ll> que;
void dfs(vector<vll> &G, vb &checked, ll u){
    checked[u] = true;
    res[u] = que.top(); que.pop();
    for(auto v: G[u]){
        if(!checked[v])
            dfs(G, checked, v);
    }
}

void solve(long long N, std::vector<long long> a, std::vector<long long> b, std::vector<long long> c){
    vector<vll> G(N);
    REP(i, N-1){
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    REP(i, N){
        que.push(c[i]);
    }
    res.assign(N, 0);
    vb checked(N, false);
    dfs(G, checked, 0);
    ll cnt = 0;
    REP(i, N-1){
        cnt += min(res[a[i]], res[b[i]]);
    }
    cout << cnt << endl;
    REP(i, N){
        cout << res[i]<<" ";
    }
    cout << endl;


}

int main(){

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


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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int a, b, c;
  cin >> a >> b >> c;
  set<int> s;
  s.insert(a);
  s.insert(b);
  s.insert(c);
  if (s.size() == 2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long int
#define pb push_back

int main() {
  ll N, M, ans;
  cin >> N >> M;

  ll a = M/N;

  for(int i = a; i > 0; i--){
    if(M % i == 0) {
      ans = i;
      break;
    }
  }
  print(ans);
}


Measured memory_bytes: 256
import copy
N=int(input())

L=[]
for i in range(N):
    n=int(input())
    L.append(n)
A=copy.deepcopy(L)
A.sort(reverse=True)
#print(L)
#print(A)
for i in range(N):
    if L[i]==A[0]:
        print(A[1])
    else:
        print(A[0])

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

int main() {

    string a;
    cin >> a;

    int fr = (a[0]-'0')*10+(a[1]-'0');
    int se = (a[2]-'0')*10+(a[3]-'0');
    
    if (fr > 0 && fr <= 12 && se > 0 && se <= 12) {
        cout << "AMBIGUOUS";
    }
    else if (fr > 0 && fr <= 12) {
        cout << "MMYY";
    }
    else if (se > 0 && se <= 12) {
        cout << "YYMM";
    }
    else {
        cout << "NA";
    }

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String N;
    int ans = 999;
    int sa;
    
    String S = sc.next();
    for(int i=0; i<S.length()-2; i++) {
      N = S.substring(i, i+3);
      if(753<=Integer.parseInt(N)) {
        sa = Integer.parseInt(N) - 753;
      } else {
        sa = 753 - Integer.parseInt(N);
      }
      
      if(ans >=sa){
        ans = sa;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 23508
def main():
    n = int(input())
    s = str(input())

    str_list = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    ans_list = []
    for i in range(len(s)):
        tmp = str_list.find(str(s[i]))
        index_tmp = tmp+n
        if index_tmp >= len(str_list):
            index_tmp -= len(str_list)

        ans_list.append(str_list[index_tmp])

    mojiretsu = ''.join(ans_list)
    print(mojiretsu)



if __name__ == '__main__':
    main()



Measured memory_bytes: 3060
from collections import deque

n,m = map(int,input().split())

res = {}
for i in range(m):
    a,b = map(int,input().split())
    res.setdefault(a,[]).append(b)
    res.setdefault(b,[]).append(a)

dist =[0] * (n+1)
sirusi = [0] * (n+1)
dist[1] = -1

que = deque([])
ique = deque([])
x = res.pop(1)
#print(x)
que.append(x)
ique.append(1)

d = 1
#print(len(que))

while(len(que)>0):
    data = que.popleft()
    index = ique.popleft()
    #print(data)
    ind = 0
    for i in data:
        #print(int(i))

        if dist[int(i)] == 0 :
            # print("d")
            # print(index)
            dist[i] = d
            sirusi[i] = index
            que.append(res.pop(i))
            ique.append(int(i))
        ind += 1
    d = d + 1
#
# while(len(next) > 0):
#     data = next.pop()
#     print("data = ",end="")
#     print(data)
#     if(not(type(data) is int)):
#         print("not int")
#         for i in range(len(data)):
#             if dist[i]  != 0:
#                 dist[data[i]] = d
#                 print("res[data[i]] = ")
#                 #print(res[data[i]])
#                 next.append(res.pop(data[i]))
#     else:
#         print("int")
#         if dist[data] == 0:
#             dist[data] = d
#             print("res = ",end="")
#             print(res[data])
#             next.append(res[data])
#
#     d = d +1



#print(dist)
#print(sirusi)
print("Yes")
for i in range(2,len(sirusi)):
    print(sirusi[i])

Measured memory_bytes: 39072
#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <iostream>
#include <algorithm>


using namespace std;



int main() {
	int n = 0, t = 0;
	cin >> n >> t;
	int val = t / 2;
	int ans = n + val;
	cout << ans << endl;

  	return 0;
}

Measured memory_bytes: 256
n = int(input())
X = [0] * n
Y = [0] * n
cx = []
cy = []

for i in range(n):
    X[i], Y[i] = map(int, input().split())
    cx.append(X[i] - Y[i])
    cy.append(X[i] + Y[i])

#print(X, Y)
#print(cx, cy)

ans = max(max(cx) - min(cx), max(cy) - min(cy))
print(ans)

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


int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout<<setprecision(30)<<fixed;

	
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int t=max(b*d,a*c);
	t=max(a*d,t);
	t=max(b*c,t);
	if(a<=0 && 0<=b && t<0)
		t=0;
	if(c<=0 && 0<=d && t<0)
		t=0;
	cout<<t<<endl;
	return 0;
}

Measured memory_bytes: 3644