akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;

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

const ll mod = 1000000007;

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

  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &x: a) cin >> x;

  unordered_map<int, int> count;
  for (auto &x: a) count[x]++;

  for (auto &x: count) {
    if (x.second >= 2) {
      cout << "NO" << endl;
      return 0;
    }
  }

  cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 9288
#![allow(unused_imports)]
#![allow(dead_code)]

use std::collections::*;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let ma: usize = sc.read();
    let mb: usize = sc.read();
    let abc: Vec<(usize, usize, i32)> = (0..n).map(|_| (sc.read(), sc.read(), sc.read())).collect();
    let inf = 10000000;
    let mut init = vec![vec![inf; 401]; 401];
    init[0][0] = 0;
    let dp = abc.iter().fold(init, |acc, &v| {
        let (a, b, c) = v;
        (0..401)
            .map(|i| {
                (0..401)
                    .map(|j| {
                        let mut res = acc[i][j];
                        if i >= a && j >= b {
                            res = std::cmp::min(res, acc[i - a][j - b] + c);
                        }
                        res
                    })
                    .collect()
            })
            .collect()
    });
    let mut mul = 1;
    let mut ans = inf;
    while mul * ma <= 400 && mul * mb <= 400 {
        ans = std::cmp::min(ans, dp[mul * ma][mul * mb]);
        mul += 1;
    }
    if ans == inf {
        ans = -1;
    }
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
using namespace std;

int main()
{
	long long N, M;
	cin >> N >> M;
	long long ans = 0;
	if (2 * N > M) {
		ans = M / 2;
	} else {
		ans += N;
		M -= 2 * N;
		ans += M / 4;
	}
	cout << ans << endl;
	return 0;
}

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

#define endl '\n'

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

    int n;
    cin >> n;
    while(n >= 1) {
        int sq = sqrt(n);
        if(sq * sq == n) {
            cout << n;
            return 0;
        }
        n--;
    }

    return 0;
}

Measured memory_bytes: 256
# 長さ1の配列ならば反転数は0
# 2つの配列をソートしながらマージするときについでに反転数が求まるのが鍵で、これを実装に組み込む

INF = 10**9 + 1
def merge(A: list, left: int, mid: int, right: int) -> int:
    '''
    2つの配列をmergeする関数

    Aはこのプログラムで処理する配列。
    left, mid, rightはAのindex。
    '''
    cnt = 0  # mergeするときに何回反転するか
    n1 = mid-left  # 右の方の配列のlen (反転数を計算するときにこいつを使う)
    # n2 = right-mid  # 左の方の配列のlen ぶっちゃけいらない

    L = A[left:mid]  # python sliceはshallow copyらしい
    L.append(INF)  # 番兵
    R = A[mid:right]
    R.append(INF)  # 番兵

    i_l, i_r = 0, 0  # LとRのコントロール用idx
    for k in range(left, right):
        # L,Rの先頭を比較していって小さい方をAに打ち込む
        if L[i_l] <= R[i_r]:
            A[k] = L[i_l]
            i_l += 1
        else:
            A[k] = R[i_r]
            i_r += 1
            cnt += n1-i_l  # ここが重要 反転したときだけ反点数を足し込んでいく
    return cnt


def merge_sort(A: list, left: int, right: int):
    '''
    マージソートをしつつ、反転数を再帰的に計算する。

    ここではマージを再帰的に適応し反転数をどんどん上に伝播させていく仕組み
    '''
    if left + 1 >= right:  # 終了条件
        return 0

    mid = (left+right)//2
    v1 = merge_sort(A, left, mid)  # 右左にも再帰的にmerge_sortを適応
    v2 = merge_sort(A, mid, right)
    v3 = merge(A, left, mid, right)  # 右左整ったらmerge

    return v1+v2+v3


n = int(input())
A = list(map(int, input().split()))
print(merge_sort(A, 0, n))


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

ll N;
ll *L;
ll Max = -1;
ll total = 0;


void input(){
    cin >> N;
    L = (ll *)malloc(sizeof(ll)*N);
    for(ll i=0;i<N;i++){
        cin >> L[i];
        if(Max < L[i]){
            Max = L[i];
        }
        total += L[i];
    }
}

void solve(){
    
}

int main(void){
    // Your code here!
    input();
    solve();
    cout << (((total - Max * 2) > 0)?"Yes":"No") << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int p[5000];
long long dp[5001][5001];

int main() {
    int n, a, b, i, j;
    long long ans = 1e18;
    
    scanf("%d %d %d", &n, &a, &b);
    
    for (i = 0; i < n; i++) scanf("%d", &p[i]);
    
    for (i = 0; i < n; i++) {
        int x = p[i];
        
        for (j = 0; j < x; j++) dp[i + 1][j] = dp[i][j] + a;
        for (j = x + 1; j <= n; j++) dp[i + 1][j] = dp[i][j] + b;
        
        dp[i + 1][x] = 1e18;
        for (j = 0; j < x; j++) dp[i + 1][x] = min(dp[i + 1][x], dp[i][j]);
    }
    
    for (i = 0; i <= n; i++) ans = min(ans, dp[n][i]);
    
    printf("%lld\n", ans);
    
    return 0;
}


Measured memory_bytes: 195584
C0=0
C1=0
C2=0
C3=0
N=int(input())
S=list(range(N))
for i in range(N):
  S[i] = input()
for i in range(N):
  if S[i]=="AC":
    C0 += 1
  elif S[i]=="WA":
    C1 += 1
  elif S[i]=="TLE":
    C2 += 1
  else:
    C3 += 1
print("AC","x",C0)
print("WA","x",C1)
print("TLE","x",C2)
print("RE","x",C3)

Measured memory_bytes: 16048
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

ll n,a[100001];
const int mod=1000000007;
ll inv[100001],si[100002];
int inv_init(ll n,ll p){
    inv[1]=1;
    FOR(i,2,n+1) inv[i]=p-(p/i)*inv[p%i]%p;
    return 0;
}
int main(){
    cin>>n;
    rep(i,n) cin>>a[i];
    inv_init(n,mod);
    ll fac=1;
    FOR(i,1,n+1){
        si[i]=(inv[i]+si[i-1])%mod;
        fac*=i;
        fac%=mod;
    }
    ll ans=0;
    rep(i,n){
        ans+=a[i]*(si[i+1]-1+si[n-i])%mod;
        ans%=mod;
    }
    ans=ans*fac%mod;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2560
#define _USE_MATH_DEFINES // for C++
#include <cmath>
#include <stdio.h>

int main(){
	
	double r, s, l;


	scanf("%lf", &r);

	l = 2 * M_PI * r;
	s = M_PI * r * r;

	printf("%.6lf %.6lf\n", s, l);

	return 0;
}

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

struct tramp{
    char suit;
    int value;
};

void bsort(struct tramp a[],int n ){
    for(int i=0;i<n;i++){
        for(int j=n-1;j>=i;j--){
            if(a[j].value<a[j-1].value){
                tramp t=a[j-1]; a[j-1]=a[j]; a[j]=t;
            }
        }
    }
    
}

void ssort(struct tramp a[],int n){
    int min;
    for (int i=0;i<n-1;i++){
        min=i;
        for(int j=i;j<n;j++){
            if(a[min].value>a[j].value) min=j;
        }
        tramp t=a[i]; a[i]=a[min]; a[min]=t;
    }
}

void print(struct tramp a[],int n){
    for(int k=0;k<n;k++){
        if(k) cout<<" ";
        cout<<a[k].suit<<a[k].value;
    }
    cout<<endl;
}

bool isstable(struct tramp a[],struct tramp b[],int n){
    for(int i=0;i<n;i++)
        if(a[i].suit!=b[i].suit)return false;
    return true;
}

int main(){
    tramp a[100],b[100];
    int n;
    
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].suit>>a[i].value;
    }
    for(int j=0;j<n;j++)b[j]=a[j];
    
    ssort(a,n);
    bsort(b,n);
    
    print(b,n);
    cout<<"Stable"<<endl;
    
    print(a,n);
    if(isstable(a, b, n))
        cout<<"Stable"<<endl;
    else
        cout<<"Not stable"<<endl;
    
    return 0;
    
}



Measured memory_bytes: 3104
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#define ld long double 
#define ll long long 
using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	ll a[n];
	ll i=0;
	ll p=1;
	ld m=1;
	for(i=0;i<n;i++)
	{
		
		cin>>a[i];	
	
	}
	
	for(i=0;i<n;i++)
	{
		
	    p=p*a[i];
	    m=m*a[i];
			
    
	}
	 
	ll k= pow(10,18);
	if(m>k) 
	{
		
		cout<<"-1"<<endl;
		
	}
	
	
	else 
	{
		
		cout<<p<<endl;
		
	}
	

	

	return 0;
	
}

Measured memory_bytes: 4388
#include <iostream>
using namespace std;
int n, q, w, f, l[399], r[399], p[399], s[399], dp[399];
int main() {
	cin >> n;
	for(int i = 0; i < n; i++) cin >> l[i] >> r[i] >> p[i];
	for(int i = 1; i <= 393; i++) {
		dp[i] = -999999999;
		for(int j = 0; j < n; j++) {
			for(int k = l[j]; k <= r[j] && i - k >= 0; k++) dp[i] = max(dp[i], dp[i - k] + p[j]);
		}
	}
	cin >> q;
	for(int i = 0; i < q; i++) cin >> w, s[i] = dp[w], f = f | (dp[w] < 0 ? 1 : 0);
	if(f) cout << -1 << endl;
	else for(int i = 0; i < q; i++) cout << s[i] << endl;
}

Measured memory_bytes: 3112
#include<iostream>

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

long long dp[100100][3];
long long a[100100][3];


int main(void){
    int n;
    std::cin >> n;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < 3; j++){
            std::cin >> a[i][j];
        }
    }

    for(int i = 0; i < n; i++){
            chmax(dp[i+1][0], dp[i][1]+a[i][1]);
            chmax(dp[i+1][0], dp[i][2]+a[i][2]);

            chmax(dp[i+1][1], dp[i][0]+a[i][0]);
            chmax(dp[i+1][1], dp[i][2]+a[i][2]);

            chmax(dp[i+1][2], dp[i][0]+a[i][0]);
            chmax(dp[i+1][2], dp[i][1]+a[i][1]);

    }

    long long ans = 0;

    chmax(ans, dp[n][0]);
    chmax(ans, dp[n][1]);
    chmax(ans, dp[n][2]);

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

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  for(int i = 0; i < N; i++){
    cin >> H.at(i);
  }
  int left = 0; int right = 0;
  int result = 0;
  while(left < N){
    //rightをいけるところまで右に進める
    while(right < N - 1 && H.at(right) >= H.at(right + 1)){
      right++;
    }
    if(right - left > result) result = right - left;
    if(right == left) right++;
    left++;
  }
  cout << result << endl;
}

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

int main() {
  string a;
  cin >> a;
  if (a[0] == a[1] && a[1] == a[2]) {
    cout << "Yes" << endl;
  }  
  else if (a[1] == a[2] && a[2] == a[3]) {
    cout << "Yes" << endl;
  }  
  else {
    cout << "No" << endl;
  }  
}


Measured memory_bytes: 3620
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <climits>
#include <cfloat>
#include <algorithm>
using namespace std;

int main()
{
    int n, m, l;
    cin >> n >> m >> l;

    vector<int> k(n);
    for(int i=0; i<n; ++i){
        cin >> k[i];
        -- k[i];
    }
    sort(k.begin(), k.end());

    vector<long long> sum(m+1, 0);
    for(int i=1; i<=m; ++i){
        cin >> sum[i];
        sum[i] += sum[i-1];
    }

    vector<long long> dp(1);
    dp[0] = (sum[k[1]+1] - sum[k[0]]) / l;
    for(int i=2; i<n; ++i){
        vector<long long> nextDp(i, LLONG_MAX);
        for(int j=0; j<i-1; ++j){
            nextDp[i-1] = min(nextDp[i-1], dp[j] + (sum[k[i]+1] - sum[k[j]]) / l);
            nextDp[j] = min(nextDp[j], dp[j] + (sum[k[i]+1] - sum[k[i-1]]) / l);
        }
        dp.swap(nextDp);
    }

    long long ret = LLONG_MAX;
    for(int i=0; i<n-1; ++i)
        ret = min(ret, dp[i] + (sum[k[n-1]+1] - sum[k[i]]) / l);
    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 1720
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,a,sum=0,i,count1=0;
    float sum2;
    vector<int>ar;
    cin>>n>>m;
    for(i=0;i<n;i++)
    {
        cin>>a;
        ar.push_back(a);
        sum=sum+a;
    }
    sum2=float(float(sum)/float(4*m));
    //cout<<sum2<<endl;
    for(i=0;i<n;i++)
    {
        if((ar[i])>=sum2)
            count1++;
    }
        if(count1<m)
            cout<<"No"<<endl;
        else
                cout<<"Yes"<<endl;
        return 0;
}


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

#pragma warning(disable:4996)
using namespace std;


struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main() {
	int N,M;cin>>N>>M;
	vector<int>v(N);
	for (int i = 0; i < M; ++i) {
		int a,b;cin>>a>>b;
		for (int x = a; x < a + b; ++x) {
			v[x%N]=true;
		}
	}
	UnionFind uf(N);
	for (int i = 0; i < N; ++i) {
		int l=i;
		int r=(i+1)%N;
		if (v[l] && v[r]) {
			uf.unionSet(l,r);
		}
	}
	set<int>used;
	map<int,int,greater<int>>mp;
	for (int i = 0; i < N; ++i) {
		if (v[i]) {
			int r=uf.root(i);
			if (used.find(r) == used.end()) {
				used.emplace(r);
				mp[uf.size(i)]++;
			}
		}
	}
	for (auto m : mp) {
		cout<<m.first<<" "<<m.second<<endl;
	}
	return 0;
}


Measured memory_bytes: 3104
#include<stdio.h>
int f(int n)
{
    int i=1;
    while(i*i<n)i++;
    return (i*i==n);
}
int main()
{
    int a,b,m,k=0,n;
    scanf("%d%d",&a,&b);
    n=b;
    while(n>0){n/=10;a*=10;}
    m=a+b;
    if(f(m))printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define llu unsigned long long int
#define Endl endl
#define mod  998244353
#define mkp make_pair
#define pb push_back
#define cin(n) scanf("%d",&n)
#define cout(n) printf("%d ",n)
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d ",n)
#define bitget(n) __builtin_popcountll(n)
ll dx[] = {1,1,0,-1,-1,-1,0,1};
ll dy[] = {0,-1,-1,-1,0,1,1,1};
ll dxx[] = {1,-1,0,0};
ll dyy[] = {0,0,-1,1};
ll modexpo(ll x,ll y){if(y==0)return 1;if(y%2){ll viky=modexpo(x,y/2);
return (((x*viky)%mod)*viky)%mod;}else{ll viky=modexpo(x,y/2);return (viky*viky)%mod;
}}
bool isvalid(ll x,ll y,ll n, ll m) { return (x>=0&&x<n&&y>=0&&y<m); }
vector<ll>v[100011];

int main() {
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;

    cin>>n;

    string ans = "";

    while(n>0){

        n--;
        ans += ('a' + (n%26));
        n = n/26;
    }
    reverse(ans.begin(), ans.end());
    cout<<ans;

    return 0;
}

Measured memory_bytes: 6020
# coding: utf-8


def solve(*args: str) -> str:
    n, y = map(int, args[0].split())

    for man in range(n+1):
        for gosen in range(n-man+1):
            sen = n-man-gosen
            if y//1000 == (10*man)+(5*gosen)+sen:
                return '{} {} {}'.format(man, gosen, sen)

    return '-1 -1 -1'


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 2940
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC098_B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var S = Console.ReadLine().ToCharArray();
            var alpha = "abcdefghijklmnopqrstuvwxyz";

            var m = 0;
            for (int i = 0; i < N; i++)
            {
                var fS = S.Take(i);
                var ls = S.Skip(i);
                var c = 0;

                foreach (var a in alpha)
                {
                    if (fS.Contains(a))
                        if (ls.Contains(a))
                            c++;
                }
                if (m < c) m = c;
            }
            Console.WriteLine(m);
        }
    }
}


Measured memory_bytes: 13276
#include <iostream>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
int dy[] = {1, 0, 0, -1};
int dx[] = {0, 1, -1, 0};
bool used[110][110];
string s[110];
int h, w;
void dfs(int y, int x, char c){
	rep(i, 4){
		int ny = y + dy[i], nx = x + dx[i];
		if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
		if(used[ny][nx]) continue;
		if(s[ny][nx] != c) continue;
		used[ny][nx] = true;
		dfs(ny, nx, c);
	}
	return;
}
int main(void){
	while(1){
		cin >> h >> w;
		if(h == 0 && w == 0) return 0;
		rep(i, 110)rep(j, 110) used[i][j] = false;
		int cnt = 0;
		rep(i, h){
			cin >> s[i];
		}
		rep(i, h)rep(j, w){
			if(!used[i][j]){
				cnt++;
				used[i][j] = true;
				dfs(i, j, s[i][j]);
			}
		}
		cout << cnt << endl;
	}
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DECIMAL(n)  std::cout << std::fixed;std::cout << std::setprecision(n);
#define hell 1000000007
#define M hell
#define PI 3.14159265358979323844
#define sz(a) (int)a.size()
#define pb push_back
#define fi first 
#define se second
#define fr first 
#define sc second
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>  
#define vi vector<int>   
using namespace std;
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};

#define point complex<ll>
ll dot(point a,point b){
	return (conj(a)*b).real();
}
ll f(point a,ll x){
	return dot(a,{x,1});
}
struct node{
	point p;
	node* left;
	node* right;
};
node* create(){
	node* wen = new node;
	wen->left=NULL;
	wen->right=NULL;
	wen->p={0,(ll)hell*hell};
	return wen;
}
const int maxn=hell;
class LiChao{
public:
	node* root;
	LiChao(){
		root=create();		
	}
	void add_line(point nw,node* v,int tl=0,int tr=maxn){
		int tm=tl+(tr-tl)/2;
		bool left= f(nw,tl) < f(v->p,tl);
		bool mid= f(nw,tm) < f(v->p,tm);
		if(mid){
			swap(v->p,nw);
		}
		if(tr-tl==1){
			return;
		}else if(left!=mid){
			if(!(v->left))v->left=create();
			add_line(nw,v->left,tl,tm);
		}else{
			if(!(v->right))v->right=create();
			add_line(nw,v->right,tm,tr);
		}
	}
	void add_line(ll a,ll b){
		add_line({a,b},root);
	}
	ll get_min(ll x,node* v,int tl=0,int tr=maxn){
		int tm=tl+(tr-tl)/2;
		if(tr-tl==1){
			return f(v->p,x);
		}else if(x<tm){
			if(!(v->left))return f(v->p,x);
			return min(f(v->p,x),get_min(x,v->left,tl,tm));
		}else{
			if(!(v->right))return f(v->p,x);
			return min(f(v->p,x),get_min(x,v->right,tm,tr));
		}
	}
	ll get_min(ll x){
		return get_min(x,root);
	}
};


const int N=200005;
ll h[N],dp[N];

void FermatsLittlePP()
{
		LiChao cht;
    ll n,c; cin>>n>>c;
    for(int i=0;i<n;i++)cin>>h[i];
    cht.add_line(-h[0],h[0]*h[0]);
    for(int i=1;i<n;i++){
        dp[i]=cht.get_min(2*h[i])+h[i]*h[i]+c;
        cht.add_line(-h[i],dp[i]+h[i]*h[i]);
    }
   cout<<dp[n-1];   
}
int main()
{
    FAST;
    int testcases=1;
    //cin>>testcases;
    for(int i=0;i<testcases;++i)
    {
        FermatsLittlePP();
    }
    return 0;
}

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

bool isprime(int n){
    double rootn = sqrt(n);
    if (n < 2){
        return false;
    }
    else if (n == 2){
        return true;
    }
    else if (n % 2 == 0){
        return false;
    }
    else{
        for(int i = 3; i <= rootn; i += 2){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

// 空のベクトルを二つ渡す。N (>=2) 以下の素数を primes に順番に入れる。
void prime_vectors(int N, vector<int>& primes, vector<bool>& is_prime){
    primes = {};
    is_prime = {};
    for(int i=0; i<=N; i++){
        is_prime.push_back(true);
    }

    primes.push_back(2);
    for(int j=4; j<=N; j+=2){
        is_prime[j] = false;
    }

    int i;
    for(i=3; i*i<=N; i+=2){
        if(!is_prime[i]) continue;
        primes.push_back(i);
        for(int j=2*i; j<=N; j+=i){
            is_prime[j] = false;
        }
    }

    for(; i<=N; i+=2){
        if(is_prime[i]){
            primes.push_back(i);
        }
    }
}

signed main(){
    // cout << fixed << setprecision(10) << flush;

    int n;
    cin >> n;
    string s;
    cin >> s;

    int cnt = 0;
    for(int i=0; i<1000; i++){
        int tempi = i;
        string p;
        for(int k=0; k<3; k++){
            p[k] = tempi % 10 + '0';
            tempi /= 10;
        }
        int k = 0;
        for(int j=0; j<n; j++){
            if(s[j] == p[k]){
                k++;
                if(k == 3){
                    cnt++;
                    break;
                }
            }
        }
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3724
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

import static java.lang.Integer.parseInt;

/**
 * Princess's Marriage - Accepted
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int N, M;
			N = parseInt(line.substring(0, line.indexOf(' ')));
			M = parseInt(line.substring(line.indexOf(' ') + 1));
			if ((N | M) == 0) break;

			int[] ps = new int[11];

			for (int i = 0; i < N; i++) {
				line = br.readLine();
				int D, P;
				D = parseInt(line.substring(0, line.indexOf(' ')));
				P = parseInt(line.substring(line.indexOf(' ') + 1));
				ps[P] += D;
			}

			for (int i = ps.length - 1; i >= 0; i--) {
				if (ps[i] > 0) {
					if (ps[i] <= M) {
						M -= ps[i];
						ps[i] = 0;
					} else {
						ps[i] -= M;
						M = 0;
					}
				}
			}

			int expected = 0;
			for (int i = 0; i < ps.length; i++) {
				if (ps[i] > 0) expected += i * ps[i];
			}
			System.out.println(expected);

		} //end while
	} //end main
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin() x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin() x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a, b, c; cin>>a>>b>>c;

	cout << ((b-a == c-b) ? "YES" : "NO") << "\n";

	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
print(N-K+1)


Measured memory_bytes: 4460
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  int h,w;
  cin >> h >> w;
  vector<vector<char>> vec(h,vector<char>(w,'0'));
  rep(i,h){
    rep(j,w){
      cin >> vec[i][j];
    }
  }
  rep(i,h){
    rep(j,w){
      if(vec[i][j]!='#'){
        ll a=0;
        FOR(x,-1,2){
          FOR(y,-1,2){
            ll ni=x+i;
            ll nj=y+j;
            if(ni>=0&&nj>=0&&ni<h&&nj<w&&vec[ni][nj]=='#'){
              a++;
            }
          }
        }
        vec[i][j]=a+'0';
      }
    }
  }
  rep(i,h){
    rep(j,w){
      cout << vec[i][j];
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i = (ll)(a); i < (ll)(b); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1LL << 60;
int main(){
    int n;
    cin >> n;
    vector<pair<int,int>> xy[15];
    rep(i,n){
        int a; cin >> a;
        rep(j,a){
            int a,b;
            cin >> a>> b;
            xy[i].push_back(make_pair(a-1,b));
        }
    }
    int mx = 0;
    for(int bit=0; bit< (1<<n); ++bit){
        vector<int> v(n);
        bool ok=true;
        int tmp=0;
        rep(i,n){
            if (bit & (1<<i)) v[i]=1;
            else v[i]=0;
        }
        rep(i,n){
            if (v[i]==0) continue;
            for(auto spk: xy[i]){
                if (spk.second != v[spk.first]){
                    ok =false;
                    break;
                }
            }
            if(!ok) break;
            tmp++;
        }
        // rep(i,n) cout <<v[i];
        // cout << " "<< tmp << endl;
        if(ok && tmp>mx) mx=tmp;
    }
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <utility>
#include <numeric>
#include <iomanip>

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

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    int r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;

    int ans = 0;
    string tt;

    for (int i = 0; i < n; i++)
    {
        if (i+1 <= k)
        {
            if (t.at(i)== 'r')
            {
                ans += p;
                tt.append("p");
            }
            else if (t.at(i)== 's')
            {
                ans += r;
                tt.append("r");
            }
            else
            {
                ans += s;
                tt.append("s");
            }
        }
        else
        {
            if (t.at(i)== 'r')
            {
                if (tt.at(i-k) == 'p')
                {
                    tt.append("x");
                }
                else
                {
                    ans += p;
                    tt.append("p");
                }
            }
            else if (t.at(i)== 's')
            {
                if (tt.at(i-k) == 'r')
                {
                    tt.append("x");
                }
                else
                {
                    ans += r;
                    tt.append("r");
                }
            }
            else if(t.at(i)== 'p')
            {
                if (tt.at(i-k) == 's')
                {
                    tt.append("x");
                }
                else
                {
                    ans += s;
                    tt.append("s");
                }
            }
        }
    }
    
    cout << ans << endl;


}


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

using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset

typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'

char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
bool isect (int l1, int r1, int l2, int r2){
    pii p1,p2;
    p1 = mp(l1,r1); p2 = mp(l2,r2);
    if(p1>p2)swap(p1,p2);
    if(p2.fi <= p1.se)return true;
    else return false;
}
ll fexp (ll num1, ll num2, ll MOD){
    if(num2==0)return 1;
    else if(num2==1)return num1;
    else{
        ll temp = fexp (num1,num2/2,MOD); ll res = ((temp%MOD) * (temp%MOD))%MOD;
        if(num2%2==1) res = ((res%MOD)*(num1%MOD))%MOD; return res;
    }
}
ll invmod (ll num, ll MOD){return fexp (num,MOD-2,MOD);}
ll gcd (ll num1, ll num2){
    if(num1 < num2) swap(num1,num2); ll num3 = num1 % num2 ;
    while(num3 > 0){ num1 = num2; num2 = num3; num3 = num1 % num2;}
    return num2;
}
ll lcm (ll num1 , ll num2){return (ll) (num1/gcd(num1,num2))*num2;}

// end of Template

int n;
map <str,int> m;
map <str,int> :: iterator itr;
ll ans;
int main(){

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;
    for(int i=1;i<=n;i++){
        str temp; cin>>temp;
        sort(temp.begin(),temp.end());
        m[temp]++;
    }

    for(itr = m.begin(); itr!= m.end(); ++itr){
        ll tmp = itr->se;
        ans += (tmp*(tmp-1))/2;
    }
    cout<<ans<<newl;
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
long long int saisyou(long long int C, long long int D) {
    long long int LCM=(C*D)/__gcd(C,D);
    return LCM;
}
int main(){
    long long int A,B;
    long long int C,D;
    cin>>A>>B>>C>>D;
    long long int saisyo1= B/saisyou(C, D);
    long long int c1=B/C;//Cで割り切れる
    long long int d1=B/D;//Dで割り切れる
    long long int ansm=B-(c1+d1-saisyo1);//CでもDでも割り切れない

    long long int saisyo2=(A-1)/saisyou(C,D);
    long long int c2=(A-1)/C;
    long long int d2=(A-1)/D;
    long long int ansn=(A-1)-(c2+d2-saisyo2);

    long long int ans=ansm-ansn;
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define END '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define trace(x) cerr<<x<<END;
#define loop(i, a, b) for(int i = (a); i < (b); i++)
#define loopb(i, b, a) for(int i = (b); i > (a); --i) 
const int mod = 1e9+7;
const int mod1 = 998244353;
const int inf = 1e18;
int n,x,y,d,cnt;
void solve()
 {
  cin>>n>>d;
  cnt = 0;
  loop(i,0,n)
   {
		 cin>>x>>y;
		 double dis = hypot(x,y);
		 if(dis<=1.0*d)
		  cnt++;
		}
 cout<<cnt;
  
 }  
signed main()
 {   
  ios_base::sync_with_stdio(false);
  cin.tie(0); 
  cout.tie(0); 
   /*int t;
   cin>>t;
   loop(i,1,t+1)*/
      solve();
      
  //cerr<<END<<1.0*clock();
  return 0;
} 


Measured memory_bytes: 3664
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string>
#include <iostream>
#include <vector>
#include <iomanip>
#define lsb(x) ((x) & -(x))
using namespace std;

#define mod 1000000007

int d;

void add(int & a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}

void pass(int * vechi, int * nou)
{
    /// adauga o cifra in plus
    fill(nou, nou + d, 0);
    for (int i = 0; i < d; i++) {
        if (!vechi[i])
            continue;
        for (int c = 0, q = i; c <= 9; c++) {
            add(nou[q], vechi[i]);
            q++;
            if (q == d)
                q = 0;
        }
    }
}

int spcif[100010]; /// suma ultimelor i cifre
int cifr[100010];
int dp[2][100];

int main()
{
    string s;
    cin >> s >> d;

    int n = s.size();

    for (int i = 0; i < s.size(); i++)
        cifr[i + 1] = s[i] - '0', spcif[i + 1] = (spcif[i] + cifr[i + 1]) % d;

    dp[0][0] = 1;
    int nr = (spcif[n] == 0);

    for (int lback = 0; lback < n; lback++) {
        int * act = dp[lback & 1];
        int * oth = dp[(lback & 1) ^ 1];

        int c_poz = cifr[n - lback], sback = spcif[n - lback - 1];
        for (int c = 0; c < c_poz; c++) {
            int sact = (sback + c) % d;
            sact = d - sact;
            if (sact == d)
                sact = 0;
            add(nr, act[sact]);
        }

        if (lback + 1 < n)
            pass(act, oth);
    }

    cout << (nr - 1 + mod) % mod << '\n';
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) { return std::vector<T>(n, std::forward<T>(val)); }
template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}
template<class Cond> struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  template<class T> bool operator()(T& a, const T& b) const { if(cond(a, b)) { a = b; return true; } return false; }
};
template<class Cond> chain<Cond> make_chain(Cond cond) { return chain<Cond>(cond); }

vector<vector<pair<i64, i64>>> G;
i64 N, M;
vector<i64> used;
vector<i64> cnt;
vector<pair<i64, i64>> ans;

namespace dfs1 {
  void dfs(int v) {
    cnt[v] = 1;
    for(auto e: G[v]) {
      int t = e.first;
      int i = e.second;
      if(cnt[t]) continue;
      used[i] = 1;
      dfs(t);
    }
  }
}

namespace dfs2 {
  void dfs(int v, int f) {
    for(auto e: G[v]) {
      int t = e.first;
      int i = e.second;
      if(t == f) continue;
      if(!used[i]) continue;
      dfs(t, v);
    }
    if(cnt[v]) { 
      ans.emplace_back(v, f);
      cnt[v] ^= 1;
    }
    else if(f != -1) {
      ans.emplace_back(f, v);
      cnt[f] ^= 1;
    }
  }
}

int main() {
  cin >> N >> M;
  G.resize(N);
  used.resize(M);
  cnt.resize(N);
  vector<i64> A(M), B(M);
  rep(i,0,M) {
    cin >> A[i] >> B[i];
    A[i]--;
    B[i]--;
    G[A[i]].emplace_back(B[i], i);
    G[B[i]].emplace_back(A[i], i);
  }
  if(M % 2 == 1) {
    cout << -1 << endl;
    return 0;
  }

  dfs1::dfs(0);
  cnt.assign(N, 0);
  rep(i,0,M) {
    if(!used[i]) {
      cnt[A[i]] ^= 1;
      ans.emplace_back(A[i], B[i]);
    }
  }

  dfs2::dfs(0, -1);
  rep(i,0,M) {
    cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
  }
}



Measured memory_bytes: 17904
def get_input_data():
    input_data = int(input())
    return input_data

def get_two_data():
    two_data = input().split()
    for i in range(2):
        two_data[i] = int(two_data[i])
    return two_data

def make_gem_map(gem_num):
    gem_map = set()
    for i in range(gem_num):
        gem_map.add(tuple(get_two_data()))
    return gem_map

def make_order(order_num):
    order = [None] * order_num
    for i in range(order_num):
        order[i] = input().split()
        order[i][1] = int(order[i][1])
    return order

class Robot:

    def __init__(self, gem_map, order):
        self.x, self.y = (10, 10)
        self.gem_map = gem_map
        self.order = order

    def move_and_catch_gems(self):
        self.gem_map.discard((self.x, self.y))
        for i in range(len(order)):
            direction, vector = order[i]
            for j in range(vector):
                if direction == "N":
                    self.y += 1
                elif direction == "S":
                    self.y -= 1
                elif direction == "E":
                    self.x += 1
                else:
                    self.x -= 1
                self.gem_map.discard((self.x, self.y))

if __name__ == "__main__":
    while True:
        gem_num = get_input_data()
        if gem_num == 0:
            break
        gem_map = make_gem_map(gem_num)
        order_num = get_input_data()
        order = make_order(order_num)
        robot = Robot(gem_map, order)
        robot.move_and_catch_gems()
        if robot.gem_map:
            print("No")
        else:
            print("Yes")



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

typedef long long ll;
const int mod = 1e9 + 7;

ll N, K;

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

    if (K == 0) {
        cout << N * N << endl;
        return 0;
    }

    ll ans = 0;
    for (ll b = 1; b <= N; b++) {
        // mod を足す
        // ans += (N % b);
        ll r = N % b;
        ans += max(0LL, r - K + 1);

        ll q = N / b;
        ans += q * (max(0LL, b - K));
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;
// }}}

void init()
{
}

void solve()
{
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    N--; K--;
    cout << (N / K + (N%K != 0 ? 1 : 0)) << endl;
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    int sum=a+b+c;
    int ma=max(max(a,b),c);
    sum-=ma;
    for(int i=0;i<k;i++){
        ma*=2;
    }
    int ans=ma+sum;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
main(){int m,d,s[]={0,31,60,91,121,152,182,213,244,274,305,335};char a[7][9]={"Thurs","Fri","Satur","Sun","Mon","Tues","Wednes"};
  while(1)
    {
      scanf("%d%d",&m,&d);
      if(!m)exit(0);
      d+=s[m-1];
      printf("%sday\n",&a[(d%7==0)?6:(d%7-1)][0]);
    }
}

Measured memory_bytes: 0
((stdin) => {
	let [l1, l2] = stdin.split('\n');
	let [n, k] = l1.split(' ');
	[n, k] = [+n, +k];
	let a = l2.split(' ');

	for (let i = 0; i < n; i++) {
		a[i] = +a[i];
	}

	for (let j = 0; j < k && j < 41; j++) {
		let b = new Array(n).fill(0);
		for (let i = 0; i < n; i++) {
			let l = Math.max(0, i - a[i]);
			let r = Math.min(n - 1, i + a[i]);
			b[l]++;
			if (r + 1 < n) { b[r + 1]--; }
		}
		for (let i = 1; i < n; i++) { b[i] += b[i - 1]; }
		a = b.slice();
	}
	console.log(a.join(' '));

})(require("fs").readFileSync("/dev/stdin", "UTF-8"));

Measured memory_bytes: 75516
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
/*-------------------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<vector<int> > edge(n);
  REP(i, n - 1) {
    int a, b; cin >> a >> b; --a; --b;
    edge[a].emplace_back(b);
    edge[b].emplace_back(a);
  }
  vector<int> c(n); REP(i, n) cin >> c[i];
  sort(ALL(c), greater<int>());
  int ans = 0;
  vector<int> ver(n, -1);
  queue<int> que;
  que.emplace(0);
  ver[0] = c.front();
  int cnt = 1;
  while (!que.empty()) {
    int now = que.front(); que.pop();
    for (int e : edge[now]) if (ver[e] == -1) {
      ver[e] = c[cnt];
      ans += ver[e];
      ++cnt;
      que.emplace(e);
    }
  }
  cout << ans << '\n';
  REP(i, n) cout << ver[i] << (i == n - 1 ? '\n' : ' ');
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 13;

string s[MAX_N];
vector<int> vec[MAX_N];
vector<char> c;
int dame[26];
int mp[26];
int cnt;
int n;

int main()
{
    while(1){
        scanf("%d",&n);
        if(n == 0){
            break;
        }
        cnt = 0;
        rep(i,n){
            vec[i].clear();
        }
        c.clear();
        rep(i,26){
            dame[i] = 0;
        }
    	rep(i,n){
    		cin >> s[i];
    	}
        rep(i,n){
            rep(j,s[i].length()){
                if(j == 0 && s[i].length() > 1){
                    dame[(int)(s[i][j]-'A')] = 1;
                }
                c.push_back(s[i][j]);
                vec[i].push_back((int)(s[i][j] - 'A'));
            }
        }
        sort(c.begin(),c.end());
        c.erase(unique(c.begin(),c.end()),c.end());
        rep(i,c.size()){
            mp[(int)(c[i]-'A')] = i;
        }
        vector<bool> v(10);
        fill(v.end() - c.size(), v.end(), true);
        do {
            vector<int> pm;
            for (int i = 0; i < 10; ++i) {
                if (v[i]) {
                    pm.push_back(i);
                }
            }
            do{
                bool flag = false;
                rep(i,26){
                    if(dame[i] > 0){
                        if(pm[mp[i]] == 0){
                            flag = true;
                            break;
                        }
                    }
                }
                if(flag){
                    continue;
                }
                int a[MAX_N];
                rep(i,n){
                    ll hoge = 0;
                    ll dig = 1;
                    for(int j = vec[i].size()-1;j>=0;j--){
                        hoge += pm[mp[vec[i][j]]] * dig;
                        dig *= 10LL;
                    }
                    a[i] = hoge;
                }
                ll sm = 0;
                rep(i,n-1){
                    sm += a[i];
                }
                if(a[n-1] == sm){
                    cnt++;
                }
            }while(next_permutation(pm.begin(), pm.end()));
        } while (next_permutation(v.begin(), v.end()));
        printf("%d\n",cnt);
    }
	return 0;
}

Measured memory_bytes: 3252
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define ll long long
#define faltu ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define binary(x) std::string binary = std::bitset<25>(x).to_string(); //to binary
#define inf 1000000007
#define mod 1000000007
#define pi pair<int,int>
#define lpi pair<int,int>
#define mp make_pair
#define pb push_back
#define vi vector<int>
#define lvi vector<long long int>
#define pie 3.14159265358979323846
using namespace std;
int main()
{
	faltu;
	int a,b,c;
	cin>>a>>b>>c;
	for(int i=0;i<10;i++)
	{
		int x=(a*c)-b;
		cout<<x<<endl;
		c=x;
	}

}





Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(o) {cerr<<#o<<" "<<o<<endl;}
#define DUMPC(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

//?§? ??? hh:mm:ss ???
string timeToStr(int s) {
	int hh = s / 3600;
	int mm = (s % 3600) / 60;
	int ss = s % 60;
	ostringstream stream;
	stream << setfill('0') << setw(2) << hh;
	stream << ":";
	stream << setfill('0') << setw(2) << mm;
	stream << ":";
	stream << setfill('0') << setw(2) << ss;
	return stream.str();
}

signed main() {
	for (int T, H, S; cin >> T >> H >> S&&T != -1;) {
		int a, b;
		a = 2 * 3600 - (T * 3600 + H * 60 + S);
		b = a * 3;
		cout << timeToStr(a) << endl;
		cout << timeToStr(b) << endl;
	}
	return 0;
}

Measured memory_bytes: 3108
import numpy as np
n,k=map(int, input().split())
exp=list(map(lambda x:(int(x)+1)/2,input().split())) # 入力と同時に期待値計算

l=np.cumsum(exp) # 累積和の計算

ans=l[k-1]
for i in range(n-k):
    ans=max(ans,l[i+k]-l[i])
    
print(ans)

Measured memory_bytes: 32348
import copy
from itertools import groupby
h,w,K = map(int,input().split())
l0 = [[int(i) for i in list(input())] for _ in range(h)]


def check(time,l):
    global K
    t = 0
    for i in range(h):
        gr = groupby(l[i])
        lst = []
        p = 0
        for key,g in gr:
            j = len(list(g))
            lst.append([p,key,j])
            p += j
        for j in range(len(lst)):
            if lst[j][1] == 0:
                continue
            if lst[j][2] >= K:
                t += (2**time)*lst[j][1]*lst[j][2]
                for k in range(lst[j][0],lst[j][0]+lst[j][2]):
                    l[i][k] = 0
    return t


def drop(l):
    for j in range(w):
        lst = []
        for i in range(h-1,-1,-1):
            if l[i][j] > 0:
                lst.append(l[i][j])
        lst += [0]*(h-len(lst))
        for i in range(h-1,-1,-1):
            l[i][j] = lst[h-i-1]

ans = 0
for i in range(h):
    for j in range(w):
        l = copy.deepcopy(l0)
        s = 0
        l[i][j] = 0
        drop(l)
        time = 0
        while True:
            temp = check(time, l)
            if temp == 0:
                break
            s += temp
            drop(l)
            time += 1
        ans = max(ans,s)
print(ans)

Measured memory_bytes: 79444
#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>

typedef long long ll;

const int MAXN = 1e5+7;

using namespace std;
int main()
{
    
    ll t,a,b;
    cin>>t>>a>>b;
    cout<<min(t*a,b)<<endl;
    return 0;
}


Measured memory_bytes: 256