akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;
const int MOD = 1000000007;

int main() {
	int N;
	cin >> N;
	vi a(N);
	REP(i, N) {
		cin >> a[i];
	}

	int ans = -1;
	string cond = "123456789";
	REP(i, N - 1) {
		FOR(j, i + 1, N - 1) {
			int p = a[i] * a[j];
			if (cond.find(toStr(p)) != string::npos) {
				ans = max(ans, p);
			}
		}
	}

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

Measured memory_bytes: 3224
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
const int mod = 1e9+7;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
char s[N];
int n,m,mx;
int f[N],f2[N],ans;

int main()
{
	cin >> n >> m;
	scanf("%s",s+1);
	int p;
	for(p=1;p<=m;p++){
		if(s[p]!=s[1])break;
	}
	mx=p-1;
	if(mx==m){
		f[0] = f2[0] = ans = 1;
		for(int i=0;i<=n;i++){
			if(i>=2)f[i] = f2[i-2];
			f2[i] = add((i-1>=0?f2[i-1]:0),f[i]);
			if(n-i>=2)ans = add(ans, 1ll*f[i]*(n-i)%mod);
		}
		cout << ans << endl;
		return 0;
	}
	if(n&1){
		puts("0");
		return 0;
	}
	if(mx%2==0)++mx;
	for(int t=0;p<=m;p++){
		if(s[p]==s[1])++t;
		else{
			if(t&1)mx = min(mx, t);
			t=0;
		}
	}
	n/=2,mx=(mx+1)/2;
	f[0]=f2[0]=1;
	for(int i=0;i<=n;i++)
	{
		if(i)
		{
			f[i]=(mod+f2[i-1]-(i-mx-1>=0?f2[i-mx-1]:0))%mod;
			f2[i]=(f2[i-1]+f[i])%mod;
		}
		if(n-i<=mx) ans = add(ans,(mod+1ll*(n-i)*f[i]*2%mod)%mod);
	}
	cout<<ans;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll A, B;
  cin >> A >> B;
  cout << A*B << endl;
}

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

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int mod_) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod_;
		}
		x = x * x % mod_;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
/*--------Library Zone!--------*/

int n, a[114], sum[114];
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
		sum[i] += a[i];
		sum[i + 1] += sum[i];
	}
	int ans = sum[n - 1];
	rep(i, n) {
		ans = min(ans, abs(sum[i] - (sum[n - 1] - sum[i])));
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);
        int d = sc.nextInt();
        // 満足度低下係数
        int[] c = new int[26];
        Arrays.setAll(c, i -> sc.nextInt());
        // 満足度増加度
        int[][] s = new int[d][26];
        for (int i = 0; i < d; i++) {
            Arrays.setAll(s[i], i1 -> sc.nextInt());
        }
        // 最終開催履歴
        int[] ans = new int[d];
        long grandScore = 0;
        // 何日目まで先を見るか
        for (int k = 0; k < 26; k++) {
            long score = 0;
            int[] array = new int[d];
            int[] last = new int[26];
            // 何日目の開催コンテストを決定するか
            for (int i = 0; i < d; i++) {
                int index = 0;
                long v = 0;
                // コンテストのk日後のスコアを見て開催コンテストを決める
                for (int j = 0; j < 26; j++) {
                    int ruiseki = 0;
                    for (int l = 1; l <= k; l++) {
                        ruiseki += l;
                    }
                    long childV = s[i][j] - ruiseki * c[j];
                    if (j == 0) {
                        v = childV;
                    } else if (childV > v) {
                        v = childV;
                        index = j;
                    }
                }
                array[i] = index;
                for (int j = 0; j < 26; j++) {
                    if (j == index) {
                        score += s[i][j];
                        last[j] = i + 1;
                    } else {
                        score -= c[j] * (i + 1 - last[j]);
                    }
                }
            }
            if (k == 0) {
                grandScore = score;
                ans = array;
            } else if (score > grandScore) {
                grandScore = score;
                ans = array;
            }
        }
        for (int i = 0; i < d; i++) {
            System.out.println(ans[i] + 1);
        }
    }
}

Measured memory_bytes: 46724
import java.util.Arrays;
import java.util.Scanner;

//0631
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), l[] = new int[m], a = 0;
        for (int i = 0; i < m; i++) {
            l[i] = sc.nextInt();
            sc.nextInt();
        }
        Arrays.sort(l);
        for (int i = m - 1; i > 0; i--) {
            a += l[i] < n ? n - l[i] : 0;
        }
        System.out.println(a);
    }
}



Measured memory_bytes: 31456
#include<bits/stdc++.h>
using namespace std;
// URDL
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
long long mod = 1e9+7;
//

int main(){
  int x, a; cin >> x >> a;
  cout << (x >= a ? 10 : 0) << endl;

  return 0;
}



// EOF


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, K;
int V[100];

signed main(){
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> V[i];
    }
    int ans = 0;
    for(int i = 0; i <= N; i++){
        for(int j = i; j <= N; j++){
            if(N - j + i > K)continue;
            vector<int> w;
            int sum = 0;
            for(int a = 0; a < i; a++){
                w.push_back(V[a]);
                sum += V[a];
            }
            for(int b = j; b < N; b++){
                w.push_back(V[b]);
                sum += V[b];
            }
            sort(w.begin(), w.end());
            for(int c = 0; c < K - (N - j + i) && c < (int)w.size(); c++){
                if(w[c] < 0)sum -= w[c];
            }
            //printf("a:%lld b:%lld %lld sum:%lld\n", i, j, N - j + 1, sum);
            ans = max(ans, sum);
        }
    }
    cout << ans << endl;

    return 0;
}
/*


*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define fr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include<string>
#include<algorithm>
#include<vector>
const long long int maxn = 1e3+2;
const long long int mod = 1e3+2;

int main()
{
	fr
	ll n,k;
	cin>>n;
	int fp[4][n+1],dp[3][n+1];
	for(int i=1;i<=n;i++)
	{
		cin>>dp[0][i];
		cin>>dp[1][i];
		cin>>dp[2][i];
	}
	fp[0][0]=0;
	fp[1][0]=0;
	fp[2][0]=0;
	
	for(int i=1;i<=n;i++)
	{
		fp[0][i]=max(dp[0][i]+fp[1][i-1],dp[0][i]+fp[2][i-1]);
	//	cout<<fp[0][i]<<" ";
		fp[1][i]=max(dp[1][i]+fp[0][i-1],dp[1][i]+fp[2][i-1]);
	//	cout<<fp[1][i]<<" ";
		fp[2][i]=max(dp[2][i]+fp[0][i-1],dp[2][i]+fp[1][i-1]);
	//	cout<<fp[2][i]<<endl;
	}
	cout<<max(fp[0][n],max(fp[1][n],fp[2][n]));
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for(int i = 0; i < s.size(); i++) {
        s[i] = al[((s[i] - 'A') + n) % 26];
    }
    cout << s << endl;
}

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

using namespace std;

const int64_t INF = 1LL << 60;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  int64_t T;
  cin >> N >> T;
  vector<int64_t> A, B, C;
  for (int i = 0; i < N; i++) {
    int64_t a, b;
    cin >> a >> b;
    if (a == 0) {
      C.emplace_back(b + 1);
    } else {
      A.emplace_back(a);
      B.emplace_back(b);
    }
  }
  vector<int> idx(A.size());
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(),
       [&](int a, int b) { return A[b] * (B[a] + 1) < A[a] * (B[b] + 1); });
  vector<int64_t> NA, NB;
  for (int i : idx) {
    NA.emplace_back(A[i]), NB.emplace_back(B[i]);
  }
  A = NA, B = NB;
  vector<int64_t> dp(31, T + 1);
  dp[0] = 0;
  for (int i = 0; i < (int)A.size(); i++) {
    for (int j = (int)dp.size() - 2; j > -1; j--) {
      if (dp[j] > T) continue;
      chmin(dp[j + 1], (A[i] + 1) * (dp[j] + 1) + B[i]);
    }
  }
  sort(C.begin(), C.end());
  for (int i = 0; i < (int)C.size() - 1; i++) {
    C[i + 1] += C[i];
  }
  int res = 0;
  for (int i = 0; i < (int)dp.size(); i++) {
    if (dp[i] > T) continue;
    int p = upper_bound(C.begin(), C.end(), T - dp[i]) - C.begin();
    res = max(res, i + p);
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 9188
import math
p = int(input())
p_size = int(math.log10(p) + 1)
q = str(p)
sum_p = 0
for a in range(p_size):
    sum_p = sum_p + int(q[a])
if p % sum_p == 0:
    print("Yes")
else:
    print("No")


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

#ifndef M_PI
#define M_PI 3.14159265358979
#endif
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef pair<int, int> pi;
typedef long double ld;
typedef pair<long double, long double> pld;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll i, j, k, l;

    string S, T;
    cin >> S >> T;
    ll ans = T.length();
    for(i = 0; i < S.length() - T.length() + 1; i++) {
        ll s = 0;
        for(j = 0; j < T.length(); j++) {
            if(S[i + j] != T[j]) {
                s++;
            }
        }
        ans = min(ans, s);
    }
    cout << ans << endl;

    return 0;
}


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

const int V = 100000;
const ll INF = 1e15;

int main() {
  int N, W;
  cin >> N >> W;
  vector<int> w(N), v(N);
  rep(i, N) cin >> w[i] >> v[i];

  vector<vector<ll>> dp(N+1, vector<ll>(V+1, INF));
  dp[0][0] = 0;
  rep(i, N) rep(j, V+1) {
    dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
    if (j + v[i] < V+1) dp[i+1][j + v[i]] = min(dp[i+1][j + v[i]], dp[i][j] + w[i]);
  }
  int ans = 0;
  for (int j = V; j >= 0; --j) {
    if (dp[N][j] <= W) {
      ans = j;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 83228
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
var n,x=[],y=[];

console.log(main());
function main(){
  n = o.a();
  for(var i = 0; i < n; i++){
    var a = o.a(), b = o.a();
    if(a === 0 && b === 0)continue;
    x.push(a);
    y.push(b);
  }
  n = x.length;
  var ans = 0;
  for(var i = -1000000; i <= 1000000; i+=20){
    var z = solve(-1000000,i);
    if(ans < z)ans = z;
    var z = solve(1000000,i);
    if(ans < z)ans = z;
    var z = solve(i,1000000);
    if(ans < z)ans = z;
    var z = solve(i,-1000000);
    if(ans < z)ans = z;
  }
  return Math.sqrt(ans);
}
function solve(h,w){
  var tx = 0, ty = 0;
  for(var i = 0; i < n; i++){
    if(x[i]*w+y[i]*h>0)tx += x[i], ty += y[i];
  }
  return tx*tx+ty*ty;
}

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

using namespace std;

int main(void){
  int N[3];
  cin >> N[0] >> N[1] >> N[2];
  if(N[0]==N[1]){
    cout << N[2] << endl;
  }
  else if(N[0]==N[2]){
    cout << N[1] << endl;
  }
  else{
     cout << N[0] << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
main(){
    int h,w;
    int i,j;
    scanf("%d %d",&h,&w);
    while(h||w){
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                printf((!i||!j||i==h-1||j==w-1) ? "#" : ".");
            }
            printf("\n");
        }
        printf("\n");
        scanf("%d %d",&h,&w);
    }
}

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

using namespace std;

int main()
{
    long long int N, M;
    scanf("%lld %lld",&N, &M);

    if(N==1 && M==1) printf("%d",1);
    else if(N==1){
        printf("%lld",M-2);
    }
    else if(M==1){
        printf("%lld",N-2);
    }
    else{
        printf("%lld",N*M-2*(N+M)+4);
    }

    return 0;
}


Measured memory_bytes: 256
import math
def nor(x,y,p):
    sum = 0
    for i in range(len(x)):
        sum += (abs(x[i]-y[i]))**p
    return sum**(1/p)
def nor_inf(x,y):
    tmp = []
    for i in range(len(x)):
        tmp.append(abs(x[i]-y[i]))
    return max(tmp)
                 
n = int(input())
x = list(map(float,input().split()))
y = list(map(float,input().split()))

print(nor(x,y,1))
print(nor(x,y,2))
print(nor(x,y,3))
print(nor_inf(x,y))

Measured memory_bytes: 7900
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        

fast();
//ll t;cin>>t;while(t--)

    ll n;
    cin>>n;
    //ll a[100005]={0};
    map<ll,ll>a;
    //for(int i=0;i<10;i++)cout<<a[i]<<" ";
    for(int i=0;i<n;i++)
    {
      ll x;
      cin>>x;
      a[x]++;
    }
    vi v,vv;
    for(auto t:a)
    {
      if(t.se>=4)
      {
        v.pb(t.fi);
      }
      else if(t.se>=2)
      {
        vv.pb(t.fi);
      }


    }

    /*for(auto t:v)cerr<<t<<" ";
      cerr<<endl;
    for(auto t:vv)cerr<<t<<" ";
      cerr<<endl;*/
    sort(v.begin(),v.end(),greater<ll>());
    sort(vv.begin(),vv.end(),greater<ll>());
    if(v.size()==0&&vv.size()<2)
    {
      cout<<0<<endl;
    }
    else
    {
      ll f=0,s=0,th=0;
      if(v.size()>0)
      {
            f=1ll*v[0]*v[0];
      }
      if(vv.size()>1)
      {
        s=1ll*vv[0]*vv[1];
      }
      if(v.size()>0&&vv.size()>0)
      {
        th=1ll*v[0]*vv[0];
      }
      ll ans=max(f,max(s,th));
      cout<<ans<<endl;

    }


return 0;
}

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

using namespace std;

#define int long long
#define pii pair<int, int>
#define pb push_back
int n, k, c;
string s;
int const N = 2e5 + 10;
int dp[N];
int solve(int i){ 
    if(i >= n){
        return 0;
    }
    if(dp[i] != -1) return dp[i];
    if(s[i] == 'x') return dp[i] = solve(i + 1);
    return dp[i] = max(solve(i + 1), 1 + solve(i + c));
}
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k >> c; c++;
    cin >> s;
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < n; i++) {
        solve(i);
    }
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'x') continue;
        if(dp[i] == dp[i + 1]) {
            i += c - 1;
            continue;
        }
        if(dp[i] != dp[i + 1]) {
            ans.pb(i + 1);
            i += c - 1;
        }
    }
    if(dp[0] > k) ans.clear();
    for(auto x: ans) cout << x << endl;

    return 0;
}



Measured memory_bytes: 11272
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int N, a, b; cin >> N;
	vector<int> costs(N);
	vector<vector<int>> G(N, vector<int>());
	rep(i,N-1){
		cin >> a >> b;
		--a; --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	ll max_score = 0;
	rep(i,N){
		cin >> costs[i];
		max_score += costs[i];
	}
	sort(all(costs), greater<int>());
	max_score -= costs[0];
	int use = 0;
	vector<int> ans(N, inf);
	queue<int> Q;
	Q.push(0);
	ans[0] = costs[use++];
	while(!Q.empty()){
		int f = Q.front();
		Q.pop();
		for(auto x:G[f]){
			if(ans[x] == inf){
				ans[x] = costs[use++];
				Q.push(x);
			}
		}
	}
	cout << max_score << endl;
	show(ans);
		return 0;
}


Measured memory_bytes: 4016
n=int(input())
hoge=[]
for i in range(n):
  x,y=map(int,input().split())
  hoge.append([x,y])
ans=0
for i in range(n):
  for j in range(n):
    if(i!=j):
      ans+=((hoge[i][0]-hoge[j][0])**2+(hoge[i][1]-hoge[j][1])**2)**0.5
ans=(ans/n)
print(ans)

Measured memory_bytes: 3064
use proconio::{input, fastout};

const MOD: usize = 1_000_000_007;

#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
    }

    let mut ans = 0;

    for i in k..=n+1 {
        let min = i * (i - 1) / 2;
        let max = i * (n + n - i + 1) / 2;
        ans = (ans + max - min + 1) % MOD;
    }
    println!("{}", ans);
}

Measured memory_bytes: 2164
#include <stdio.h>
#include <string.h>

int main(void)
{
	int n, m;
	int s;	
	int card_hanako[101], card_taro[101];
	int sum_hanako, sum_taro;
	int i, j;
	int diff;
	
	while (1){
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0){
			break;
		}
		
		memset(card_hanako, 0, sizeof(card_hanako));
		memset(card_taro, 0, sizeof(card_taro));
		sum_taro =sum_hanako = 0;
		
		for (i = 0; i < n; i++){
			scanf("%d", &s);
			sum_taro += s;
			card_taro[s]++;
		}
		
		for (i = 0; i < m; i++){
			scanf("%d", &s);
			sum_hanako += s;
			card_hanako[s]++;
		}
		
		diff = sum_taro - sum_hanako;
		
		if (diff % 2 != 0){
			printf("-1\n");
			continue;
		}
		
		diff /= 2;
		
		for (i = 0; i <= 100; i++){
			if (card_taro[i] != 0){
				if (0 <= i - diff && i - diff <= 100){
					if (card_hanako[i - diff] != 0){
						printf("%d %d\n", i, i - diff);
						break;
					}
				}
			}
		}
		if (i > 100){
			printf("-1\n");
		}
	}
	return (0);
}

Measured memory_bytes: 612
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;
vector<int> G[10001];
int used[10001] = {0};
int p = 0;
int n;
int ans[10001];
int c[10001];
void dfs(int d){
    ans[d] = c[n-p-1];
    p++;

    used[d] = 1;
    for(auto x:G[d]){
        if(used[x] == 0)dfs(x);
    }
}
signed main(){
    
    cin >> n;
    int s = 0;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        G[a-1].pb(b-1);
        G[b-1].pb(a-1);
    }
    
    rep(i,n){
        cin >> c[i];
        s += c[i];
    }
    sort(c,c+n);
    dfs(0);


    cout << s-c[n-1] << endl;
    rep(i,n)cout << ans[i] << " ";
    cout << endl;

    

    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc128.contest.atcoder.jp/tasks/abc128_a

Measured memory_bytes: 1408
#include <iostream>
#include <cmath>
//#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define EPS (1e-10)
using namespace std;
static const int COUNTER_CLOCKWISE=1;
static const int CLOCKWISE=-1;
static const int ONLINE_BACK=2;
static const int ONLINE_FRONT=-2;
static const int ON_SEGMENT=0;
class Point{
public:
    double x,y;
    Point(double x=0, double y=0):x(x),y(y){}
    Point operator +(const Point &p){
        return Point(x+p.x,y+p.y);
    }
    Point operator -(const Point &p){
        return Point(x-p.x,y-p.y);
    }
    Point operator *(double k){
        return Point(k*x,k*y);
    }
    Point operator /(double k){
        return Point(x/k,y/k);
    }

    double norm(){
        return x*x+y*y;
    }
    double abs(){
        return sqrt(norm());
    }
};



class segment{
public:
    Point p1,p2;
};
typedef Point Vector;
double dot(const Vector &v1,const Vector &v2){
    return v1.x*v2.x+v1.y*v2.y;
}
double cross(const Vector &v1,const Vector &v2){
    return v1.x*v2.y-v1.y*v2.x;
}
bool isParallel(const Vector &v1,const Vector &v2){
    if(fabs(cross(v1,v2)-0.0)<EPS)return true;
    return false;
}
bool isOrthogonal(const Vector &v1,const Vector &v2){
    if(fabs(dot(v1,v2)-0.0)<EPS)return true;
    return false;
}
Point projection( Point &p, Point &p1, Point &p2){
    Vector a=p-p1;
    Vector b=p2-p1;
    double r=dot(a,b);
    double pro_abs=r/b.norm();
    Vector res=b*pro_abs;
    return Point(res.x+p1.x,res.y+p1.y);
}
Point reflection(Point &p, Point &p1, Point &p2){
    Point pro=projection(p,p1,p2);
    Vector v=pro-p;
    v=v*2;
    return Point(v.x+p.x,v.y+p.y);
}
int ccw(Point &p, Point &p1, Point &p2){
    Vector a=p-p1;
    Vector b=p2-p1;
    if(cross(a,b)>0)return COUNTER_CLOCKWISE;
    if(cross(a,b)<0)return CLOCKWISE;
    if(dot(a,b)<0)return ONLINE_BACK;
    if(a.norm()>b.norm())return ONLINE_FRONT;
    return ON_SEGMENT;
}
bool intersect(segment &s1,segment &s2){
    if(ccw(s1.p1,s2.p1,s2.p2)*ccw(s1.p2,s2.p1,s2.p2)<=0 && ccw(s2.p1,s1.p1,s1.p2)*ccw(s2.p2,s1.p1,s1.p2)<=0)
        return true;
    return false;
}
double getDistanceSP(Point &p,segment &s){
    if(dot(p-s.p1,s.p2-s.p1)<0)return (p-s.p1).abs();
    if(dot(p-s.p2,s.p1-s.p2)<0)return (p-s.p2).abs();
    return fabs(cross(p-s.p1,s.p2-s.p1)/(s.p2-s.p1).abs());
}
double Distance(segment &s1,segment &s2){
    if(intersect(s1,s2))return 0;
    double min1=min(getDistanceSP(s1.p1,s2),getDistanceSP(s1.p2,s2));
    double min2=min(getDistanceSP(s2.p1,s1),getDistanceSP(s2.p2,s1));
    return min(min1,min2);
}
int main()
{
    int q,p0x,p0y,p1x,p1y,p2x,p2y,p3x,p3y;
    segment s1;
    segment s2;
    cin>>q;
    while(q>0){
        cin>>p0x>>p0y>>p1x>>p1y>>p2x>>p2y>>p3x>>p3y;
        s1.p1=Point(p0x,p0y);
        s1.p2=Point(p1x,p1y);
        s2.p1=Point(p2x,p2y);
        s2.p2=Point(p3x,p3y);
        printf("%.8f\n",Distance(s1,s2));
        q--;
    }
    return 0;
}


Measured memory_bytes: 3224
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
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; }

#define MOD 998244353

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

class mint{
    typedef long long ll;
public:
    mint(ll a){
        _val = a%_mod;
    }
    mint(){
        _val=0;
    }
    explicit operator ll() {return _val;}
    ll _val;
    static const ll _mod = MOD;
};

mint operator*(mint mi, mint i){
    return mint(mi._val * i._val);
}
mint operator+(mint mi, mint i){
    return mint(mi._val + i._val);
}
mint operator/(mint mi, mint i){
    ll div = modpow(i._val,mi._mod-2,mi._mod);
    return mint(mi._val*div);
}



int main(){
    /*
    mint a(8960);
    mint b = a+3;
    cout << b._val << endl;
    b=a+6;
    cout << b._val << endl;
    b=a*5;
    cout << b._val <<endl;
    b=7*a;
    cout << b._val <<endl;
    b=a/2/1;
    cout << (ll)b<<endl;
    */
    
    ll n,m,k;
    cin >> n >> m >> k;
    vector<mint> kj(n), MM(n);
    kj[0] = mint(1);
    MM[0] = mint(1);
    rep(i,n-1){
        kj[i+1] = kj[i] * (i+1);
        MM[i+1] = MM[i] * (m-1);
        //cout << i+1 << " kj[i+1]: "<< kj[i+1]._val <<" MM[i+1]: "<< MM[i+1]._val<<endl;
    }

    mint sum(0);
    rep(i,k+1){
        mint tmp;
        tmp= tmp+kj[n-1]*m*MM[n-1-i];
        tmp= tmp/kj[n-1-i]/kj[i];
        sum = sum+tmp;
    }
    cout<<sum._val<<endl;

    return 0;
}


Measured memory_bytes: 6336
#include <stdio.h>

int gcd(int a, int b);

int main(){
    int x, y, d;
    scanf("%d%d", &x, &y);
    
    d = gcd(x, y);

    printf("%d\n", d);
}

int gcd(int a, int b)
{
    int c;
    while (b > 0)
    {
        c = a%b;
        a = b;
        b = c;
}
    return a;
}



Measured memory_bytes: 2044
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct data{
    int team, solve, tim;
    int pena[11] = {};
    data() {}
    data(int t) : team(t) {solve = 0, tim = 0;}
    void add(int p, int r){
        solve++;
        tim += r + pena[p]*20;
    }

    bool operator <(const data other) const{
        if(solve != other.solve){
            return solve > other.solve;
        }else if(tim != other.tim){
            return tim < other.tim;
        }else{
            return team > other.team;
        }
    }

    bool operator ==(const data other){
        return solve == other.solve && tim == other.tim;
    }
};

int main(){
    int M, T, P, R;

    while(cin >> M >> T >> P >> R, M+T+P+R){
        vector<data> v(T);
        for(int i = 0; i < T; i++)  v[i] = data(i+1);

        int m, t, p, j;
        for(int i = 0; i < R; i++){
            cin >> m >> t >> p >> j;
            if(j == 0){
                v[t-1].add(p, m);
            }else{
                v[t-1].pena[p]++;
            }
        }

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

        cout << v[0].team;
        for(int i = 1; i < T; i++){
            if(v[i] == v[i-1])  cout << "=";
            else                cout << ",";
            cout << v[i].team;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3108
#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int n;
int a[100010];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	int mid=n/2;
	if(a[mid]==a[mid+1])
		cout<<"0"<<endl;
	else
		cout<<a[mid+1]-a[mid]<<endl;
	return 0;
}

Measured memory_bytes: 640
n, m = map(int,input().rstrip().split())

food_list = [list(map(int, input().rstrip().split())) for _ in range(n)]
answer = [0]*m

for food in food_list:
    food.pop(0)
    for tmp in food:
        answer[tmp-1] += 1

print(answer.count(n))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define irp(i,s,e) for(int i=(s);i>(e);--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;}
// #define NMAX 1000000000
ll N,a,b,c;
vi V,U;

ll solve(){

	ll ans = 0;
	rp(i,1,N+1){
		if(i%15==0){
			// ans += i;
		}
		else if(i%3==0){
			// ans += i;
		}
		else if(i%5==0){
			// ans += i;
		}
		else{
			ans += i;
		}

	}
	return ans;
}

int main(){
	cin>>N;
	cout<< solve() <<endl;
}


Measured memory_bytes: 3632
/*
n个球的情况移动一个球后变成n-1个球的情况，且问题形式完全相同
计算出这次移动对答案的贡献
考虑计算新情况中每条边的期望长度，即可正确统计答案，把问题转化成子问题！！！
原图中边是等差数列-->新图中边也是等差数列
递归至n=1即可
*/
#include<cstdio>
#include<cstring>
#define ld long double
using namespace std;
int n, d, x;
ld ans;
inline void solve(int n, ld d, ld x){
	ans+=d+(2*n-1)*x/2; if(n==1)return;
	solve(n-1, (ld)(n+1)/n*d+(ld)5/(2*n)*x, (ld)(n+2)/n*x);
}
int main(){
	scanf("%d%d%d", &n, &d, &x);
	ans=0; solve(n, d, x); printf("%.15Lf", ans);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main()
{
    long N;
    int K, ans = 0;
    cin >> N >> K;
    int h;
    for (long i = 0; i < N; i++)
    {
        cin >> h;
        if (h >= K)
        {
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define R register
using namespace std;
const int N = 2e6+200;
template <class Ruby> inline void read(Ruby &x)
{
	x=0;
	char ch=getchar(), w=0;
	while(!isdigit(ch))w=(ch=='-'), ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
	x=w?-x:x;
}

int main()
{
	int a, b;
	read(a), read(b);
	if(a*500>=b)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;

#define rep(i, n) \
for(int i = 0; i <n; i++)
#define REP(i, a, b) \
for(int i = int(a); i <= int(b); i++)
#define TRvi(c, it) \
for(vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for(vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for(msi::iterator it = (c).begin(); it != (c).end(); it++)

#define INF 2000000000

#define MEMSET_INF 127
#define MEMSET_HALF_INF 63

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	string s;
    cin >> s;
    int N = s.size();
     vector<char> v(N);
    for(int i=0; i<N; i++){
    v.at(i) = s.at(i);
    }
    vector<char> vodd(N);
    for(int i=0; i<N; i++){
    vodd.at(i/2) = v.at(i);
    i++;
    }
  if(N%2 == 0){
    for(int i=0; i<N/2; i++){
    cout << vodd.at(i);
    }
  }
  if(N%2 == 1){
    for(int i=0; i<(N+1)/2; i++){
      cout << vodd.at(i);
    }
  
  }
 

  }  

Measured memory_bytes: 640
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back 
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<10)
#define LLINF (1<<30)
#define MOD 1000000007
using ll = long long;
using namespace std;


int main() {
    ll n, a[200000], sum[200000] = {};
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        if (i != 0) {
            sum[i] = sum[i - 1] + a[i];
        }
        else {
            sum[i] = a[i];
        }
    }
    ll ans = abs(sum[0] - (sum[n - 1] - sum[0]));
    for (int i = 1; i < n-1; i++) {
        ans = min(ans, abs(sum[i] - (sum[n - 1] - sum[i])));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3328
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#define mid ((l + r) >> 1)
#define lson (x << 1)
#define rson ((x << 1) | 1)
using namespace std;
typedef long long LL;
const LL N = 998244353;

LL val[800005];

void pushup(LL x){
	val[x] = max(val[lson],val[rson]);
}

void modify(LL x,LL l,LL r,LL L,LL R,LL v){
	if(L > R) return;
	if(L <= l && r <= R){
		val[x] = v;
		return;
	}
	if(L <= mid) modify(lson,l,mid,L,R,v);
	if(R > mid) modify(rson,mid + 1,r,L,R,v);
	pushup(x);
}

LL query(LL x,LL l,LL r,LL L,LL R){
	if(L > R) return -1;
	if(L <= l && r <= R) return val[x];
	LL ret = 0;
	if(L <= mid) ret = max(ret,query(lson,l,mid,L,R));
	if(R > mid) ret = max(ret,query(rson,mid + 1,r,L,R));
	pushup(x); return ret;
}

struct node{
	LL x,d;
}s[400005];
bool cmp(node x,node y){
	return x.x < y.x;
}

LL n,ans = 0;
LL mr[400005],suf[400005] = {0},dp[400005] = {0};

LL kpw(LL x,LL y){
	LL ans = 1,tmp = x % N;
	while(y){
		if(y & 1) ans = (ans * tmp) % N;
		tmp = (tmp * tmp) % N;
		y >>= 1;
	}
	return ans;
}

int main(){
	cin >> n;
	for(LL i = 1;i <= n;i ++) cin >> s[i].x >> s[i].d;
	sort(s + 1,s + 1 + n,cmp);
	
	suf[n + 1] = 0;
	for(LL i = n;i >= 1;i --){
		mr[i] = i;
		LL L = i,R = n,MID,tmp = i;
		while(L <= R){
			MID = (L + R) >> 1;
			if(s[i].x + s[i].d > s[MID].x){
				tmp = MID;
				L = MID + 1;
			}
			else R = MID - 1;
		}
		mr[i] = max(i,query(1,1,n,i + 1,tmp)); modify(1,1,n,i,i,mr[i]);
		if(mr[i] == n) dp[i] = 1;
		else dp[i] = (suf[mr[i] + 1] + 1) % N;
		suf[i] = (suf[i + 1] + dp[i]) % N;
		ans = (ans + dp[i]) % N;
	}
	ans = (ans + 1LL) % N;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 20224
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int W,N,w[1000],v[1000],dp[1001][1001];

int main() {
	int Case=1;
	while(scanf("%d",&W),W) {
		scanf("%d",&N);
		for(int i=0;i<N;i++) {
			scanf("%d,%d",&v[i],&w[i]);
		}
		for(int i=0;i<=N;i++) {
			for(int j=0;j<=W;j++) dp[i][j]=0;
		}
		for(int i=1;i<=N;i++) {
			for(int j=0;j<=W;j++) {
				if(j>=w[i-1]) {
					dp[i][j]=max(dp[i-1][j-w[i-1]]+v[i-1],dp[i-1][j]);
				}else {
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		int max_t=0,ans;
		for(int i=0;i<=W;i++) {
			if(max_t<dp[N][i]) max_t=dp[N][i],ans=i;
		}
		printf("Case %d:\n",Case++);
		printf("%d\n%d\n",max_t,ans);
	}
}

Measured memory_bytes: 4948
al=[[x]|x<-['a'..'z']]
main=do
 s<-getLine;k<-readLn
 putStrLn(f s k al (length s))
  where f s k (q:t) n =if(substr s n q (length q))then(if k==1 then q else(f s (k-1) (add q t) n))else(f s k t n)
        substr s n q m =if n<m then False else(if(take m s)==q then True else(substr(tail s)(n-1)q m))
        add q t =((map (\x->q++x))al)++t

Measured memory_bytes: 1148
using System;
using System.Linq;
using System.Collections.Generic;

public class Prime{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
         
        var primeFactors = PrimeFactors(n);
         
        string output = primeFactors.Count() == 0 
                        ? n.ToString() 
                        : string.Join(" ", primeFactors.Select (f => f.ToString()).ToArray()); //AOJ??¨
                        //:string.Join(" ", primeFactors);
        Console.WriteLine("{0}: {1}", n, output);
    }
     
    public static IEnumerable<int> PrimeFactors(int n)
    {
        int i = 2;
        int tmp = n;
         
        while (i <= tmp)
        {
            if(tmp % i == 0){
                tmp /= i;
                yield return i;
            }else if(i > Math.Sqrt(n)){
                i = int.MaxValue; //???????????????
                yield return tmp;
	    }else{
                i++;
            }
             
            //if(i > Math.Sqrt(n)){
            //}
        }
    }
}

Measured memory_bytes: 8028
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[]) {
  ll N;
  cin >> N;
  ll ans = N;
  for (ll i = 0; i <= N; i++) {
    int cc = 0;
    int t = i;
    while (t > 0) {
      cc += t % 6;
      t = t / 6;
    }
    t = N - i;
    while (t > 0) {
      cc += t % 9;
      t = t / 9;
    }
    if (ans > cc) ans = cc;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
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 (a > b) {a = b; return 1;} return 0; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }

// gcc拡張マクロ
#define gcd __gcd
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll h, w, n; cin >> h >> w >> n;
    ll sr, sc; cin >> sr >> sc;
    string s, t; cin >> s >> t;
    sr--; sc--; // 0-indexed

    ll i0 =   0, j0 =   0;
    ll i1 = h-1, j1 = w-1;

    DSRNG(i, n-1, 0) {
        switch (t[i]) {
            case 'U': if (i1 < h-1) i1++; break;
            case 'D': if (i0 > 0) i0--; break;
            case 'L': if (j1 < w-1) j1++; break;
            case 'R': if (j0 > 0) j0--; break;
        }
        switch (s[i]) {
            case 'U': i0++; break;
            case 'D': i1--; break;
            case 'L': j0++; break;
            case 'R': j1--; break;
        }
        if (i0 > i1 || j0 > j1) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << YES(i0 <= sr && sr <= i1 && j0 <= sc && sc <= j1) << endl;
    
}

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

int main(){
	int n;
	cin >> n;
	vector<int> t(n+1);
	vector<int> x(n+1);
	vector<int> y(n+1);
	rep(i,n) cin >> t[i+1] >> x[i+1] >> y[i+1];
	int prex = 0;
	int prey = 0;
	bool ok = false;
	rep(i,n){
		int dist = abs(x[i+1] -x[i]) + abs(y[i+1] - y[i]);
		int deltat = abs(t[i+1] - t[i]);
		if(dist > deltat){
			cout << "No" << endl;
			return 0;
		} 
		else{
			if(dist%2 ==deltat%2) ok = true;
			// if(dist%2 == 0 && deltat%2 == 0) ok = true;
		}
	}
	if(ok) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 4212
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int x, y;
	cin >> x >> y;
	
	if( (x * y) % 2 != 0 ) {
		cout << "No" << endl;
		return 0;
	}
	
	int a = 4 * x - y;
	int b = y - 2 * x;
	
	a /= 2; b /= 2;
	
	if( a >= 0 && b >= 0 && a + b == x && 2 * a + 4 * b == y ) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3632
import heapq
import sys
sys.setrecursionlimit(10000000)
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))

Measured memory_bytes: 68312
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>

using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;


int n,m;
ll z;
vector<int> G[101];
int id[101][101];
pair<int,int> ids[1001];

// A*B
mat mulm(mat &A,mat &B){
	mat C(A.size(),vec(B[0].size()));
	for(int i = 0; i < (int)A.size(); i++){
		for(int k = 0; k < (int)B.size(); k++){
			for(int j = 0; j < (int)B[0].size(); j++){
				C[i][j]=(C[i][j]+A[i][k]*B[k][j]);
				if(C[i][j]>=1)C[i][j]=1;
			}
		}
	}
	return C;
}

// A^NÌvZ
mat pow(mat A,ll n){
	mat B(A.size(),vec(A.size()));
	for(int i = 0; i < (int)A.size(); i++)B[i][i]=1;
	while(n>0){
		if(n&1)B=mulm(B,A);
		A=mulm(A,A);
		n>>=1;
	}
	return B;
}

void ans(bool a){
	if(a)cout<<"yes"<<endl;
	else cout<<"no"<<endl;
}

int main(){

	while(cin>>n>>m>>z&&(n|m|z)){
		for(int i=0;i<101;i++)G[i].clear();
		for(int i=0;i<m;i++){
			int s,d;
			cin>>s>>d;
			s--;d--;
			G[s].push_back(d);
			G[d].push_back(s);
		}
		int cnt=0;
		for(int i=0;i<n;i++){
			if(i==0){
				// X^[gn_Ìo^
				id[i][n]=cnt;
				ids[cnt]=make_pair(i,n);
				cnt++;
			}
			for(int j=0;j<(int)G[i].size();j++){
				id[i][G[i][j]]=cnt;
				ids[cnt]=make_pair(i,G[i][j]);
				cnt++;
			}
		}
		// úsñÌì¬©ÂidÌo^
		mat init(cnt,vec(cnt));
		for(int i=0;i<cnt;i++)for(int j=0;j<cnt;j++)init[i][j]=0;
		// startn_©çÌJÚ
		for(int j=0;j<(int)G[0].size();j++){
			// ÌÓ
			int to=G[0][j];
			// Ìid
			int cid=id[to][0];
			init[cid][0]=1;
		}
		// »êÈOÌJÚ
		for(int i=0;i<n;i++){
			for(int j=0;j<(int)G[i].size();j++){
				int to=G[i][j];
				int cid=id[to][i];
				for(int k=0;k<(int)G[i].size();k++){
					int prv=G[i][k];
					if(to==prv)continue;
					int pid=id[i][prv];
					init[cid][pid]=1;
				}
			}
		}
		mat mx=pow(init,z);
		// resÆÊuvecÅZ
		vec inipos(cnt);
		vec res(cnt);
		for(int i=0;i<cnt;i++)inipos[i]=res[i]=0;
		inipos[0]=1;
		for(int i=0;i<cnt;i++){
			for(int j=0;j<cnt;j++){
				res[i]+=mx[i][j]*inipos[j];
				if(res[i]>=1)res[i]=1;
			}
		}
		bool ok=false;
		// êÂÅàn-1ªtoÅ ém[hÉ1ÈãÌª¶ÝµÄ¢éÈçÎ
		for(int i=0;i<(int)G[n-1].size();i++){
			int cid=id[n-1][G[n-1][i]];
			if(res[cid]>=1)ok=true;
		}
		ans(ok);
	}
	return 0;
}

Measured memory_bytes: 1108
#include <stdio.h>

int main(void)
{
	int a,b,c[7],d;
	for(d=0;d<7;d++){
		scanf ("%d %d",&a,&b);
		c[d]=a-b;
	}
	for(d=0;d<7;d++){
		printf("%d\n",c[d]);
	}
	return 0;
}


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;


int main() {
    string S; cin >> S;
    vector<int> alpha(26,0);
    REP(i,S.size()){
        alpha[S[i]-'a']++;
    }
    for (char a='a'; a<='z';a++){
        if(alpha[a-'a']==0){
            cout << a << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

Measured memory_bytes: 3744
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

K = int(input())
i = 1
v = 7 % K
V = {v}
while v != 0:
	i += 1
	v = (10 * v + 7) % K
	if v in V:
		print(-1)
		break
	V.add(v)
else:
	print(i)


Measured memory_bytes: 156716
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val a = sc.nextInt()
    val b = sc.nextInt()
    if ((b - a) % 2 == 0) {
        println("Alice")
    } else {
        println("Borys")
    }
}

Measured memory_bytes: 29464
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
cheby = []
for i in range(n):
    l = [xy[i][0]-xy[i][1],xy[i][0]+xy[i][1]]
    cheby.append(l)

xmax = -10**10
xmin = 10**10
ymax = -10**10
ymin = 10**10
for i in range(n):
    if cheby[i][0] > xmax :
        xmax = cheby[i][0]
        xa = i
    if cheby[i][0] < xmin :
        xmin = cheby[i][0]
        xi = i
    if cheby[i][1] > ymax :
        ymax = cheby[i][1]
        ya = i
    if cheby[i][1] < ymin :
        ymin = cheby[i][1]
        yi = i

if abs(xmax-xmin) > abs(ymax-ymin):
    print(abs(xy[xa][0]-xy[xi][0])+abs(xy[xa][1]-xy[xi][1]))
else :
    print(abs(xy[ya][0]-xy[yi][0])+abs(xy[ya][1]-xy[yi][1]))


Measured memory_bytes: 75784