akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
#define ll long long


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    const int mod = 1e9 + 7;
    int n, m;
    cin >> n >> m;
    ll x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        x += a * 1LL * i;
        x -= a * 1LL * (n - 1 - i);
        x = (x % mod + mod) % mod;
    }
    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        y += a * 1LL * i;
        y -= a * 1LL * (m - 1 - i);
        y = (y % mod + mod) % mod;
    }
    cout << (x * 1LL * y) % mod << endl;
    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to;
	ld cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
ll fact(ll x, ll k,ll p) {//最大値、個数
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
#define int long long
const long long inf = 4523372036854775807;
const int iinf = 1500000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
int n;
int a[1000];
bool b[10000000];
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	reverse(a, a + n);
	for (int i = 0; i < n; i++) {
		int k = 1;
		int sum = 0;
		for (int j = i; j < n; j++) {
			sum += k*a[j];
			if (sum > 10000000) break;
			b[sum] = 1;
			k *= 10;
		}
	}
	for (int i = 0; i < 10000000; i++) {
		if (!b[i]) {
			cout << i << endl;
			break;
		}
	}
	getchar(); getchar();
}


Measured memory_bytes: 7280
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
 
using namespace std;
using std::cout;
using ll =long long;
bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}
ll gcd11(ll x, ll y){
  long long a= max(x,y), b=min(x,y), c=a%b;
  while( c!=0){
    a =b;
    b =c;
    c = a%b;
  }
  return b;
}

int abs(int x, int y){
  if(x>=y){
    return x-y;
  }
  else if(y>x){
    return y-x;
  }
}
int main(){
  ll N,A,B,C,D,E;
  cin>> N>>A>>B>>C>>D>>E;
  ll aa =min(min(min(A,B),min(C,D)),E);
  cout << (N-1)/aa +5<<endl;


}



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

#define M 1000003
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key) {return key % M;}
int h2(int key) {return 1 + key % (M - 1);}

int find(char str[]){

  int i;
  long long a1,a2;
  a1 = getKey(str);
  for(i = 0; i < M; i++){
    a2 = (h1(a1) + i * h2(a1)) % M;
    if(H[a2][0] == '\0') return 0;
    if(strcmp(H[a2],str) == 0) return 1;

  }
  return 0;
}

int insert(char str[]){
  
  int i;
  long long a1,a2;
  a1 = getKey(str);
  for(i = 0; i < M; i++){
    
    a2 = (h1(a1) + i * h2(a1)) % M;
    
    if(H[a2][0] == '\0'){
      strcpy(H[a2],str);
      return 0;
    }
  }
}
int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}

Measured memory_bytes: 14280
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <numeric>
#include <queue>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <map>
#include <functional>
#include <limits>
#include <set>
#include <stack>
#define rep(i,a,b) for((i)=a;i<(int)(b);i++)
#define Max(a,b) ((a) < (b) ? (b) : (a))
#define Min(a,b) ((a) > (b) ? (b) : (a))
#define AAA (1000000007) 


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pairII;


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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll powD(ll a, ll b) {
	ll ans = 1;
	a %= AAA;
	for (int i= 0; i <b; i++)
	{
		ans *= a;
		ans %= AAA;
	}
	return ans;
}

int main() {
	int i, j, k;
	
	int N, M, K;

	string S;
	cin >> S;

	stack<char> A, B;
	reverse(S.begin(), S.end());
	for (auto x : S) {
		A.push(x);
	}
	
	while (!A.empty()) {
		B.push(A.top());
		A.pop();

		while (!A.empty() && !B.empty() && A.top() == 'T' && B.top() == 'S') {
			A.pop();
			B.pop();
		}
	}
	
	cout << B.size();
	
	return 0;
}

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

int main(){
	int a,b,n ;
	cin >> a >> b >> n ;
	bool ok = false ;
	for(int i=0;i<n;i++){
		int s,g ;
		cin >> s >> g ;
		if(s<b&&g>a) ok = true ;
	}
	cout << (int)ok << endl ;
}


Measured memory_bytes: 3104
local n = tonumber(io.read())
local p = {}
local maxp = 0
local sum = 0
for i=1,n,1 do
  p[i] = tonumber(io.read())
  sum = sum + p[i]
  if p[i]>maxp then
    maxp = p[i]
  end
end
print(sum-maxp//2)



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

struct Item {
    int value, weight;
};


int main() {
    int N, W;
    std::cin >> N >> W;

    std::vector<Item> items(N);
    for (int i = 0; i < N; i++) {
        std::cin >> items[i].value >> items[i].weight;
    }

    std::vector<int> max_value(W + 1, 0);

    for (auto&& item : items) {
        for (int j = W; j >= item.weight; j--) {
            max_value[j] = std::max(max_value[j], max_value[j - item.weight] + item.value);
        }
    }

    std::cout << max_value[W] << std::endl;
}



Measured memory_bytes: 3140
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,c,x,ans=0;
int main()
{
	scanf("%d%d%d%d",&a,&b,&c,&x);
	for(int i=0;i<=a;i++)
			for(int j=0;j<=b;j++)
					for(int k=0;k<=c;k++)
							if((i*500+j*100+k*50)==x) ans++;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
_ = $stdin.gets
S1 = $stdin.gets.chomp.gsub(/(.)\1/, '\1').split("")
S2 = $stdin.gets.chomp.gsub(/(.)\1/, '\1').split("")

D = S1.zip(S2).map{ |s1,s2|
  s1 == s2 ? :s : :d
}

#p D

st = nil
ans = 1
M = 1000000007

D.each { |t|
  case t
  when :s
    if st
      if st == :s
        ans = (ans * 2) % M
      else
        ans = ans
      end
    else
      ans = 3
    end
  when :d
    if st
      if st == :d
        ans = (ans * 3) % M
      else
        ans = (ans * 2) % M
      end
    else
      ans = 6
    end
  end
  st = t
}

p ans


Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n*3;i++) scanf("%d",&a[i]);
	sort(a+1,a+n*3+1);
	long long ans=0;
	for (int i=n*3-1;i>n;i-=2) ans+=a[i];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1408
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(k,v) emplace_back(k,v)
#define ct(res) cout << res << "\n";
#define vi vector<int>
#define vl vector<ll>
using namespace std;
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 int INF = 1e9;
const ll MOD = 1000000007;

using Graph = vector<vector<int>>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    map<char,int> mp;
    rep(i,s.size()) {
        mp[s[i]]++;
    }
    int ans = s.size()-abs(mp['0']-mp['1']);
    cout << ans << "\n";


}



Measured memory_bytes: 512
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=list(input())

point=dict()
point["p"]=s  #s wins p
point["s"]=r  #r wins s
point["r"]=p  #p wins r
point["checked"]=0

ans=0
for i in range(n):
  tmp=i-k
  if tmp>=0 and t[tmp]==t[i]:
    ans+=0
    t[i]="checked"
  else:
    ans+=point[t[i]]
print(ans)


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

typedef long long lint;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main () {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    char in;
    cin >> H >> W;
    vector<vector<bool>> vv(H, vector<bool>(W));
    vector<bool> vvv(W, true);
    rep(i, H) {
        rep(j, W) {
            cin >> in;
            if(in == '#') {
                vv[i][j] = true;
            }
        }
    }
    bool b = false;
    for(int i = vv.size()-1; i >= 0; i--) {
        rep(j, vv[0].size()) {
            if(vv[i][j]) b = true;
        }
        if(!b)vv.erase(vv.begin() + i);
        b = false;
    }
    for(int i = vv[0].size()-1; i>= 0; i--) {
        rep(j, vv.size()) {
            if(vv[j][i]) b = true;
        }
        if(!b)vvv[i] = false;
        b = false;
    }
    rep(i, vv.size()) {
        rep(j, vv[0].size()) {
            if(!vvv[j]) continue;
            if(vv[i][j]) cout << '#';
            else cout << ".";
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>

template<class T> inline T Abs(const T x){return x>=0?x:-x;}
template<class T> inline T Min(const T a,const T b){return a<b?a:b;}
template<class T> inline T Max(const T a,const T b){return a>b?a:b;}

int n,d,q,a[500005],p,x[500005],y[500005];

int main()
{
    scanf("%d%d",&n,&d),x[0]=d;
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)x[i]=Min(x[i-1],Abs(x[i-1]-a[i]));
    for(int i=n;i>=1;--i)y[i]=y[i+1]+((y[i+1]<<1|1)>=a[i]?a[i]:0);
    for(scanf("%d",&q);q--;)scanf("%d",&p),puts(x[p-1]>y[p+1]?"YES":"NO");
    return 0;
}

Measured memory_bytes: 7680
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int M=1e9;
int n,k,s;

int main(){
	cin>>n>>k>>s;
	vi a(n);
	for(int i=0;i<k;i++) a[i]=s;
	for(int i=k;i<n;i++) a[i]=(s==M?M-1:M);
	for(int i=0;i<n;i++) cout<<a[i]<<" \n"[i==n-1];
}

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

#define MAXINF 1000000005
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define repc(it, x) for(auto it = (x).begin(); it != (x).end(); ++it)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rrepc(it, x) for(auto it = (x).rbegin(); it != (x).rend(); ++it)
#define all(x) (x).begin(), (x).end()
#define P pair<int, int>

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a = {
        1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
    };
    int k;
    cin >> k;
    cout << a[k-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

G = (
    None,
    0, 2, 0, 1, 0,
    1, 0, 0, 1, 0,
    1, 0,
)

def main():
    X, Y = map(int, input().split())
    ok = G[X] == G[Y]
    print("Yes" if ok else "No")

if __name__ == "__main__": main()


Measured memory_bytes: 2940
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int Amax(int *p,int size){
   int _max = 0;
   for(int i = 0;i < size;i++)
      if(p[i] > _max)_max = p[i];
   return _max;
}

int com_asc_str(const void *n1,const void *n2){
   return strcmp((const char *)n1, (const char *)n2);

}

int main(){
   unsigned int n;scanf("%d",&n);
   char paper[200000][11];for(int i = 0;i < n;i++)scanf("%s",paper[i]);
   char tmp[11];
   unsigned int count[200000] ={0};
   int pointer;
   qsort(paper,n,sizeof (char)*11,com_asc_str);
   pointer = 0;
   for(int i = 0;i < n-1;i++){
      if (!(strcmp(paper[i],paper[i+1]))){
         count[pointer]++;
      }else {
         pointer = i+1;
      }
   }
   /*for(int i = 0;i < n;i++){
      printf("%d\n",count[i]);
      printf("%s\n",paper[i]);
   }*/

   unsigned int x = Amax(count,n);
   unsigned int p = 0;
   for(int i = 0;i < n ;i++)
      if(count[i] == x)printf("%s\n",paper[i]);
   return 0;
}


Measured memory_bytes: 5244
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory>
#include<cmath>
#include<algorithm>
#include<vector>
#include<unordered_map>
double min_double(double a,double  b){
    if(a<b) return a;
    else return b;
}
void swap(int *x,int *y){
    int tmp;
    tmp=*x;
    *x=*y;  
    *y=tmp;
}
int gcd(int a,int b){
    if(a<b) swap(&a,&b);
    if(b<1) return -1;

    if(a%b==0) return b;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a * b / gcd(a,b);
}

int main(){
    std::unordered_map<std::string,long> map;
    int N;
    long ans=0;
    std::cin>>N;
    std::string str;
    for(int i=0;i<N;i++){
        std::cin>>str;
        std::sort(str.begin(),str.end());
        //std::cout<<str<<std::endl;
        auto itr=map.find(str);
        if(itr!=map.end()){
            ans+=map[str];
            map[str]++;
        }
        else map[str]=1;
    }

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

Measured memory_bytes: 10372
N = int(input())
a = list(map(int, input().split()))

t = [0] * (N + 1)
for i in range(N, 0, -1):
    t[i] = (sum(t[2 * i::i]) % 2) ^ a[i - 1]

print(sum(t))
print(*[i for i in range(1, N + 1) if t[i] == 1])


Measured memory_bytes: 13116
S=input()
N=len(S)
S1 = S[:int((N-1)/2)]
S2 = S[int((N+1)/2):]
#print(S1,S2)
if S == S[::-1] and S1 == S1[::-1] and S2 == S2[::-1]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38384
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, A, B;
    cin >> N >> A >> B;
    vector<int> P(N);

    int a, b, c;
    a = b = c = 0;
    REP(i, N) {
        int p;
        cin >> p;
        if (p <= A) {
            a++;
        }
        else if (p <= B) {
            b++;
        }
        else {
            c++;
        }
    }
    cout << min({a, b, c}) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;
typedef vector<char> vech;

int main() {
    str s; cin>>s;
    vel data(s.size()); rep0(i,s.size()){data[i]=(ll)(s[i]-'a');}
    set<ll> S;
    rep0(i,s.size()){
        S.insert(data[i]);
    }
    ll ans=-1;
    rep0(i,26){
        if(1-S.count(i)){ans=i;break;}
    }
    if(ans>=0){
        cout<<(char)(ans+'a')<<endl;
    }
    else{cout<<"None"<<endl;}
}


Measured memory_bytes: 1280
import java.util.*;
import java.io.BufferedInputStream;

public class Main {
    private static int res;
    private static int[][] num;
    private static int[][] sum;
    private static int K;
    public static void main(String[] args){
        Scanner sc = new Scanner (new BufferedInputStream(System.in));
        int m = sc.nextInt();
        int n = sc.nextInt();
        K = sc.nextInt();
        res = m + n;
        num = new int[m][n];
        sum = new int[m + 1][n + 1];
        for(int i = 1; i <= m; ++i) {
          String now = sc.next();
            for(int j = 1; j <= n; ++j) {
                num[i - 1][j - 1] = now.charAt(j - 1) - '0';
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num[i - 1][j - 1];
            }
        }

        rowDfs(0, new boolean[m - 1], 0);
        System.out.println(res);
    }
    
    private static void rowDfs(int step, boolean[] rcut, int used) {
        if(step == rcut.length) {
            greedy(rcut, used, 0);
            return;
        }
        rcut[step] = true;
        rowDfs(step + 1, rcut, used + 1);
        rcut[step] = false;
        rowDfs(step + 1, rcut, used);        
    }
    private static void greedy(boolean[] rcut, int used, int start) {
        if(used >= res) return;
        List<Integer> index = new LinkedList<>();
        int i = 0;
        for(i = 0; i < rcut.length; ++i) {
            if(rcut[i]) index.add(i + 1);
        }
        index.add(num.length);
        boolean check = false;
        for(i = start + 1; i <= num[0].length; i++) {
            int j = 0;
            for(int ind : index) {
             // System.out.println(start + " " + i + " " + j + " " + ind + " " + used);
             // System.out.println(sum[ind][i] - sum[ind][start] - sum[j][i] + sum[j][start]);
                if(sum[ind][i] - sum[ind][start] - sum[j][i] + sum[j][start] > K) {
                    if(i != start + 1) greedy(rcut, used + 1, i - 1);
                    check = true;
                    break;
                }
                j = ind;
            }
            if(check) break;
        }
        if(!check) res = Math.min(used, res);
    }
}

Measured memory_bytes: 24844
while ((n,x = gets.split(" ").map(&:to_i)).inject(:+) != 0) do
  max = 3*(n-1)
  if !((6..max).include?(x))
    puts 0
    next
  end
  count = 0
  n.downto(1) do |n1|
    (n1-1).downto(1) do |n2|
      (n2-1).downto(1) do |n3|
        if ((n1 + n2 + n3) == x)
          count += 1
          break
        end
      end
    end
  end
  puts count
end

Measured memory_bytes: 8664
fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let s: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .take_while(|c| !c.is_whitespace())
        .collect();
    s.parse::<T>().ok().unwrap()
}

fn ki_su(mut vec: Vec<u64>) {
    vec.sort();
    let ans = vec[1] * vec[0];
    println!("{}", ans);
}
fn is_ki_su(vec: &std::vec::Vec<u64>) -> bool {
    vec.iter().fold(1, |sum, &x| sum * x) % 2 == 1
}
#[test]
fn ki_su_test() {
    assert!(is_ki_su(vec![3]));
    assert!(is_ki_su(vec![3, 5]));
    assert!(!is_ki_su(vec![2]));
    assert!(!is_ki_su(vec![2, 3]));
    assert!(is_ki_su(vec![3, 3]));
}

fn main() {
    let a: u64 = read();
    let b: u64 = read();
    let c: u64 = read();
    let vec = vec![a, b, c];

    if is_ki_su(&vec) {
        ki_su(vec);
    } else {
        println!("0");
    }
}


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

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

    if ((N * 10000) < Y) {
        cout << "-1 -1 -1" << endl;
        return 0;
    }

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= (N - i); j++) {
            if ((Y - ((i * 10000) + (j * 5000))) / 1000 == N - (i + j)) {
                cout << i << ' ' << j << ' ' << (N - (i + j)) << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N,D,X;
    cin >> N >> D >> X;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < D; j += A[i]){
            X++;
        }
    }
    cout << X << endl;
}


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

int main()
{
  string S;
  char c;
  int Q, t, f, tsum = 0;
  list<char> L;
  cin >> S >> Q;
  for (int i = 0; i < S.size(); i++)
  {
    L.push_back(S.at(i));
  }
  for (int i = 0; i < Q; i++)
  {
    cin >> t;
    if (t == 1)
    {
      tsum++;
    }
    else
    {
      cin >> f >> c;
      if ((f == 1 && tsum % 2 == 0) || (f == 2 && tsum % 2 == 1))
      {
        L.push_front(c);
      }
      else
      {
        L.push_back(c);
      }
    }
  }
  if (tsum % 2 == 1)
  {
    reverse(L.begin(), L.end());
  }
  for (list<char>::iterator it = L.begin(); it != L.end(); it++)
  {
    cout << *it;
  }
  cout << endl;
}


Measured memory_bytes: 9984
ans = 0
n = int(input())
blue = [input() for i in range(n)]
m = int(input())
red = [input() for i in range(m)]
for i in range(m):
    if red[i] in blue:
        blue.remove(red[i])
for j in list(set(blue)):
    if blue.count(j) > ans:
        ans = blue.count(j)
print(ans)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine()+"           ";
		//char[] s = ss.toCharArray();
		for(int i = 0;i<s.length()-5;i++){
			if(s.substring(i,i+5).equals("peach")){
				String tmp="";
				tmp+=s.substring(0,i);
				tmp+="apple";
				tmp+=s.substring(i+5,s.length());
				s=tmp;
			}
			else if(s.substring(i,i+5).equals("apple")){
				String tmp="";
				tmp+=s.substring(0,i);
				tmp+="peach";
				tmp+=s.substring(i+5,s.length());
				s=tmp;
				
			}
		}
		System.out.println(s.trim());

	}

}

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

#define vec(v) vector<int>(v)
#define be(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define mapci(mp) map<char*,int>(mp)
#define mapcc(mp) map<char*,char*>(mp)
typedef long long ll;
using namespace std;

int main() {
    int n,ans=0,sum=0;
    cin>>n;
    int a[2][n];
    for(int i=0;i<n;i++){
        cin>>a[0][i];
    }
    for(int i=0;i<n;i++){
        cin>>a[1][i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            sum+=a[0][j];
        }
        for(int j=i;j<n;j++){
            sum+=a[1][j];
        }
        ans=max(sum,ans);
        sum=0;
    }
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()


int main(){
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    REP(i, n + 1){
        cin >> a.at(i);
    }

    const ll asum = accumulate(ALL(a), 0LL);

    vector<ll> lb(n + 1, 0), ub(n + 1, (n + 1) * asum);
    REP(i, n + 1){
        if(i == n){
            lb.at(i) = a.at(i);
            ub.at(i) = min(ub.at(i), a.at(i));
        }else{
            lb.at(i) = a.at(i) + 1;
        }
        if(i <= 60){
            ub.at(i) = min(ub.at(i), 1LL << i);
        }
    }

    REP(_, 5){
        for(ll i = n - 1; i >= 0; --i){
            lb.at(i) = max(lb.at(i), a.at(i) + lb.at(i + 1) / 2);
            ub.at(i) = min(ub.at(i), a.at(i) + ub.at(i + 1));
        }
        for(ll i = 1; i <= n; ++i){
            lb.at(i) = max(lb.at(i), lb.at(i - 1) - a.at(i - 1));
            ub.at(i) = min(ub.at(i), 2 * (ub.at(i - 1) - a.at(i - 1)));
        }
    }

    ll ans = 0;
    REP(i, n + 1){
        // cerr << i << " " << lb.at(i) << " " << ub.at(i) << endl;
        if(lb.at(i) > ub.at(i)){
            cout << -1 << endl;
            return 0;
        }
        ans += ub.at(i);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5572
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  int n;
  cin >> n;
  ll count[5] = {};
  rep(i, n) {
    string s;
    cin >> s;
    if (s[0] == 'M') count[0]++;
    if (s[0] == 'A') count[1]++;
    if (s[0] == 'R') count[2]++;
    if (s[0] == 'C') count[3]++;
    if (s[0] == 'H') count[4]++;
  }
  ll ans = 0;
  //10通りのパターンを記述。
  int p[10] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 2};
  int q[10] = {1, 1, 1, 2, 2, 3, 2, 2, 3, 3};
  int r[10] = {2, 3, 4, 3, 4, 4, 3, 4, 4, 4};
  rep(i, 10) ans += count[p[i]] * count[q[i]] * count[r[i]];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		int days = scan.nextInt();
		int remain = scan.nextInt();

		int eatdays = 0;
		int[] day = new int[num];

		for (int n=0; n<num; n++) {
			day[n] = scan.nextInt();

		}

		for (int n=0; n<num; n++) {
			int amari = days % day[n];
			if (amari == 0) {
				eatdays += days/day[n];
			} else {
				eatdays += days/day[n] + 1;
			}

		}

		System.out.println(eatdays + remain);

		scan.close();

	}

}


Measured memory_bytes: 21972
#include<iostream>
using namespace std;
int main(){
  int W,H,x,y,r;

  cin >> W >> H >> x >> y >> r;
  if(x < r || x >W-r || y <r || y> H-r){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;}

	
  return 0;
  }

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int a, b, c,d; cin >> a >> b >> c >> d;
    cout << max(a*b, c*d) << endl;
}

Measured memory_bytes: 256
#AGC033-A-Darker and Darker
from collections import deque

h,w = map(int,input().split())
grid = [input() for i in range(h)]

#初期の黒('#')の位置からの距離
dist = [[-1]*w for _ in range(h)]

p = deque()
d = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            p.append((i,j))
            dist[i][j] = 0

while p:
    y,x = p.popleft()
    d = dist[y][x]
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<= x+dx < w and 0<= y+dy < h and dist[y+dy][x+dx] == -1:
            dist[y+dy][x+dx] = d+1
            p.append((y+dy,x+dx))

    
print(d)

Measured memory_bytes: 88028
n,l=map(int,input().split())
ans1=0
for i in range(n):
    ans1=ans1+l+i
if l==0:
    ans2=ans1
elif l<0 and abs(l)<n:
    ans2=ans1
elif l<0 and abs(l)>=n:
    ans2=ans1-l-n+1
else:
    ans2=ans1-l
print(ans2)


Measured memory_bytes: 38256
import itertools
import math

n = int(input())
xy = []
for _ in range(n):
    xxyy = list(map(int, input().split()))
    xy.append(xxyy)

l = [i for i in range(n)]
p = list(itertools.permutations(l))
dist = 0
for pp in p:
    preppi = pp[0]
    for ppi in pp[1:]:
        dist += math.sqrt((xy[ppi][0] - xy[preppi][0])**2 + (xy[ppi][1] - xy[preppi][1])**2)
        preppi = ppi
print(dist/len(p))


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

using namespace std;

const int INF = 2e9 + 3;
const int N = 1e5 + 3;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;

const double PI = acos(-1);


void solve() {
    string s;
    cin >> s;
    auto sum = 0ll;
    while (!s.empty()) {
        sum += (s.back() - '0');
        s.pop_back();
    }
    if (sum % 9 == 0)
        cout << "Yes";
    else
        cout << "No";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    t = 1;
    while (t--) {
        solve();
    }
}

Measured memory_bytes: 3780
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

long long c[3000][3000];

int main(){
  int n,k;
  cin >> n >> k;
  for(int i=0;i<n+1;i++){
    c[i][0] = 1;
    c[i][i] = 1;
  }

  for(int i=2;i<n+1;i++){
    for(int j=1;j<i;j++){
      c[i][j] = c[i-1][j-1]+c[i-1][j];
      c[i][j] %= 1000000007;
    }
  }

  long long ans;
  for(int i=1;i<k+1;i++){
    ans = c[n-k+1][i]*c[k-1][i-1];
    ans %= 1000000007;
    cout << ans << endl;
  }

  return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);


using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powmod(ll b, ll e){ll r=1;while(e>0){if(e&1)r=(r%MOD)*(b%MOD)%MOD;b=(b%MOD)*(b%MOD)%MOD;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

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; }
template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);
    };
}fastio;

int main(){


    int n;
    cin >> n;
    int cnt = 0;
    rep(i, n){
        int a;
        cin >> a;
        if(a != i+1) ++cnt;
    }
    JUDGE(cnt == 0 or cnt == 2);
    return 0;
}


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

using namespace std;

long long memo[100010];

long long sum(int x) {
  if (memo[x] != -1) return memo[x];
  return memo[x] = x + sum(x - 1);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 0; i < 100010; i++) memo[i] = -1;
  memo[0] = 0;
  memo[1] = 1;
  int n, m;
  cin >> n >> m;
  vector<int> a(n + 1, 0);
  for (int i = 1; i <= n; i++) cin >> a[i];
  unordered_map<int, int> mp;
  for (int i = 1; i <= n; i++) {
    a[i] = (a[i] + a[i - 1]) % m;
  }
  for (int i = 1; i <= n; i++) {
    mp[a[i]]++;
  }
  long long ans = 0;
  for (auto kv: mp) {
    if (kv.first == 0) {
      ans += sum(kv.second);
    } else {
      ans += sum(kv.second - 1);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4876
/**
 *    created by : PawPaw       
**/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  

using namespace __gnu_pbds;  
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,  
        tree_order_statistics_node_update>  
        ordered_set;  

#define F(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define LL long long
#define PHI acos(-1)
#define EPS 0.000000001
#define N 1000001
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define FbO find_by_order
#define OoK order_of_key

int solve(){
  int a, b;
  cin >> a >> b;
  if(a != 1 && b != 1) cout << "1\n";
  else if(a != 2 && b != 2) cout << "2\n";
  else cout << "3\n";
  return 0;
}

void fun(){
  int t = 1;
  // cin >> t;
  while(t--) solve();
} 

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

  fun();

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;
string s[55];
int ans[55][55];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>s[i],s[i]=' '+s[i];
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int ans1=0;
			if(s[i][j]!='#')
			{
				if(s[i-1][j]=='#') ans1++;
				if(s[i-1][j-1]=='#') ans1++;
				if(s[i-1][j+1]=='#') ans1++;
				if(s[i][j-1]=='#') ans1++;
				if(s[i][j+1]=='#') ans1++;
				if(s[i+1][j]=='#') ans1++;
				if(s[i+1][j-1]=='#') ans1++;
				if(s[i+1][j+1]=='#') ans1++;
			}
			ans[i][j]=ans1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]!='#')
			s[i][j]=ans[i][j]+48;
			cout<<s[i][j];
		}
		cout<<endl;
	}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define maxn 610
#define ll long long
#define db double
#define vi vector<int>
#define pb push_back
#define mod 998244353
#define fi first
#define pi pair<int, int>
#define se second
#define mp make_pair
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
// head
vector<pi> r;
int id[maxn][maxn], fl[maxn][maxn];
pi s[maxn * maxn];
int n;
void bfs(int tp) {
	memset(fl, 0, sizeof(fl));
	int fr = 0, ed = 0;
	for (int i = 0; i < 2 * n; i++)
		for (int j = 0; j < 2 * n; j++) {
			if (fl[i][j]) continue;
			s[ed++] = (mp(i, j));
			fl[i][j] = 1;
			while (fr < ed) {
				pi f = s[fr];
				for (auto v : r) {
					pi kk = mp(f.fi + v.fi, f.se + v.se);
					if (kk.fi < 0 || kk.se < 0 || kk.fi >= 2 * n || kk.se >= 2 * n) continue;
					if (fl[kk.fi][kk.se]) continue;
					fl[kk.fi][kk.se] = 3 - fl[f.fi][f.se];
					s[ed++] = kk;
				}
				fr++;
			}
	}
	for (int i = 0; i < 2 * n; i++)
		for (int j = 0; j < 2 * n; j++)
			if (fl[i][j] == 2)
				id[i][j] |= tp;
}
void cal(int d) {
	r.clear();
	for (int i = 0; i < 2 * n; i++) {
		int ns = d - i * i;
		if (ns >= 0) {
			int ed = sqrt(ns + 0.5);
			if (ed * ed == ns)
				r.pb(mp(i, ed)), 
				r.pb(mp(i, -ed)), 
				r.pb(mp(-i, ed)), 
				r.pb(mp(-i, -ed));
		}
	}
}
int main() {
	cin >> n;
	int d1, d2;
	cin >> d1 >> d2;
	cal(d1), bfs(1);
	cal(d2), bfs(2);
	int cnt[4] = {0};
	for (int i = 0; i < 2 * n; i++)
		for (int j = 0; j < 2 * n; j++)
			cnt[id[i][j]]++;
	for (int i = 0; i < 4; i++) {
		if (cnt[i] >= n * n) {
			int tot = 0;
			for (int j = 0; j < 2 * n; j++)
				for (int k = 0; k < 2 * n; k++) {
					if (id[j][k] == i && tot < n * n) {
						tot++;
						printf("%d %d\n", j, k);
					}
				}
			break;
		}
	}
	return 0;
}


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

int main(){
	int n;
  	cin >> n;
  	queue<int> a;
	rep(i, n){
      int res;
      cin >> res; 
      a.push(res);
    }
  
	vector<int> ans;
 
  	int k = 1;
	while(!a.empty()){
    	if(a.front() == k){
          	ans.push_back(a.front());
        	k++;
        }
        a.pop();
    }
  
  	bool res = false;
  	for(int i = 1; i < k; i++){
    	if(ans[i-1] == i){
          res = true;
          continue;
        } else res = false;
    }
  
	cout << (res ? n-(k-1) : -1) << endl;
}

Measured memory_bytes: 2300
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f80 = __float80;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define pb push_back
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define sz(x) (i64)(x).size()
#define bit(n) (1LL<<(n))
typedef vector<i64> vi;
typedef vector<vi> vvi;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

i64 pow_mod(i64 n, i64 k, i64 m){
  i64 r = 1;
  for(;k;k>>=1){
    if(k&1) r=(r*n)%m;
    n=(n*n)%m;
  }
  return r;
}

void Main()
{
  i64 n;
  cin >> n;

  vvi g(n);
  vi e(n,0);
  i64 a,b;
  rep(i,n-1){
    cin >> a >> b;
    a--;
    b--;
    g[a].pb(b);
    g[b].pb(a);
    e[a]++;
    e[b]++;
  }

  vi c(n);
  rep(i,n) cin >> c[i];
  sort(rng(c));

  queue<int> que;
  rep(i,n)
    if(e[i]==1) que.push(i);

  i64 ans = 0;
  vi ans_l(n);
  i64 x=0;
  vector<bool> reach(n,true);
  while(!que.empty()){
    i64 a = que.front();
    que.pop();
    for(auto itr=g[a].begin();itr!=g[a].end();itr++){
      if(--e[*itr]==1){
        que.push(*itr);
      }
      if(reach[*itr]) ans += c[x];
    }
    ans_l[a]=c[x++];
    reach[a] = false;
  }

  cout << ans << endl;
  rep(i,n){
    cout << ans_l[i];
    if(i==n-1) cout << endl;
    else cout << " ";
  }
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}


Measured memory_bytes: 1280
#include<cstdio>
#include<vector>
#include<algorithm>
#include<complex>
#include<cmath>
using namespace std;
typedef long long ll;
typedef complex<double> C;
#define cx real()
#define cy imag()
const C I = C(0, 1);
const double EPS = 1e-10;
const double INF = 1e10;

bool isEqual(double a, double b) { return abs(a - b) < EPS; }
double dot(C a, C b) { return a.cx * b.cx + a.cy * b.cy; }
double det(C a, C b) { return a.cx * b.cy - a.cy * b.cx; }
bool isPointOnSegment(C a, C b, C c) { return isEqual(abs(a-b) - abs(a-c) - abs(b-c), 0.0); }
bool isLineParallel(C a1, C a2, C b1, C b2) { return isEqual(det(a1-a2, b1-b2), 0.0); }
C intersectionLine(C a1, C a2, C b1, C b2) { 
  C a = a2 - a1, b  = b2 - b1;
  return a1 + a * det(b, b1 - a1) / det(b, a);
}

ll n, x[100], y[100], r[100];
C c[100], p[2][101];
double d[2][101];

int main() {
  while (scanf("%lld", &n), n) {
    for (ll i = 0; i < n; i++) scanf("%lld%lld%lld", &x[i], &y[i], &r[i]), c[i] = C(x[i], y[i]);
    p[0][0] = p[1][0] = c[0];
    p[0][n] = p[1][n] = c[n-1];
    for (ll i = 0; i < n-1; i++) {
      double len = abs(c[i] - c[i+1]);
      double t1 = (len * len + r[i] * r[i] - r[i+1] * r[i+1]) / (2 * len);
      C temp = t1 / len * (c[i+1] - c[i]) + c[i];
      C dir = sqrt(r[i] * r[i] - t1 * t1) * (c[i+1] - c[i]) / abs(c[i+1] - c[i]) * I;
      p[0][i+1] = temp + dir;
      p[1][i+1] = temp - dir;
    }
    for (ll i = 1; i <= n; i++) d[0][i] = d[1][i] = INF;
    d[0][0] = d[1][0] = 0;
    for (ll i = 1; i <= n; i++) {
      for (ll j = 0; j < i; j++) {
        for (ll k = 0; k < 4; k++) {
          ll s = (k&2) ? 1 : 0, t = k&1;
          C c1 = p[s][j], c2 = p[t][i];
          bool flag = true;
          for (ll r = j+1; r < i; r++) {
            if (isLineParallel(c1, c2, p[0][r], p[1][r])) { flag = false; break; }
            C temp = intersectionLine(c1, c2, p[0][r], p[1][r]);
            if (!isPointOnSegment(c1, c2, temp) || !isPointOnSegment(p[0][r], p[1][r], temp)) { flag = false; break; }
          }
          if (flag) d[t][i] = min(d[t][i], d[s][j] + abs(p[s][j]-p[t][i]));
        }
      }
    }
    printf("%.9lf\n", d[0][n]);
  }
}



Measured memory_bytes: 2660
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl 
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl 
#define no cout<<"no"<<endl
#define vec(a,y,x)  vector<vector<char>> a (y,vector<char>(x))
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
const vector<int> dx={1,0,-1,0};
const vector<int> dy={0,1,0,-1};

int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  int sum=0;
  rep(i,m){
    cin>>a.at(i);
    sum+=a.at(i);
  }
  if(sum>n){
    cout<<-1<<endl;
    return 0;
  }
  cout<<n-sum<<endl;
  
}

Measured memory_bytes: 3648
#include<stdio.h>

int main(void)
{
	double r, a, b;
	scanf("%lf", &r);
	a = r * r * 3.14159265358979323846256433832;
	b = 2 * r * 3.14159265358979323846256433832;
	printf("%f %f\n", a, b);
	return 0;
}

Measured memory_bytes: 648
N = int(input())
array = tuple(map(int, input().split()))

from collections import Counter
cnt = Counter(array)
total = 0
for key in cnt:
  if cnt[key] >= 2:
  	total += int(cnt[key] * (cnt[key] - 1) / 2)
    
for key in cnt:
  if cnt[key] == 1:
    cnt[key] = total
  else:
    temp = total - int(cnt[key] * (cnt[key] - 1) / 2)
    cnt[key] = temp + int((cnt[key]-1) * (cnt[key] - 2) / 2)

for num in array:
    print(cnt[num])

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

int main()
{
	string a;
	cin>>a;
	ll n = a.length();
	ll sum=0;
	for(ll i=0;i<n/2;i++)
	{
		if(a[i]!=a[n-i-1])
		{
			sum ++;
		}
	}
	cout<<sum;
}

Measured memory_bytes: 256
// Bitter Alchemy

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int N, X;
	cin >> N >> X;
	int m[N];
	for (int i = 0; i < N; ++i)
		cin >> m[i];

	sort(m, m+N);

	int minv = 1000, res = 0;

	for (int i = 0; i < N; ++i){
		if (X >= m[i]){
			res++;
			X -= m[i];
			minv = min(minv, m[i]);
		}else{
			break;
		}
	}

	if (X >= 0)
		res += X / minv;

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 764
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>

using namespace std;

struct TFenwickTree {
  vector<int> t;
  int n;
  
  void init(int nn)
  {
    n = nn;
    t.assign (n, 0);
  }
  
  int sum(int r)
  {
    int result = 0;
    for (; r >= 0; r = (r & (r+1)) - 1)
      result += t[r];
    return result;
  }
  
  void inc(int i, int delta)
  {
    for (; i < n; i = (i | (i+1)))
      t[i] += delta;
  }
  
  int sum (int l, int r)
  {
    if (l > r) return 0;
    return sum(r) - sum(l-1);
  }
};

typedef long long ll;

const int maxn = 5000;

ll cnt[maxn][maxn];
ll ans[maxn][maxn];

ll Solve(int k, int n, int a, int b, const vector<int>& pos) {
  if (k <= 0 || n == 0) return 0;
  ll& res = ans[k][n];
  if (res != -1) return res;

  if (pos[n] > k) {
    res = Solve(k, n - 1, a, b, pos);
    return res;
  }

  res = min(a + Solve(k, n - 1, a, b, pos), cnt[k][n] * b + Solve(pos[n] - 1, n, a, b, pos));
  return res;
}

int main()
{
  int n;
  ll a, b;
  cin >> n >> a >> b;
  vector<int> p(n), pos(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    p[i]--;
    pos[p[i]] = i;
  }

  for (int k = 0; k < n; ++k) {
    TFenwickTree tree;
    tree.init(k + 1);
    for (int r = 0; r < n; ++r) {
      if (pos[r] > k) continue;
      cnt[k][r] = tree.sum(pos[r], k);
      tree.inc(pos[r], 1);
    }
  }


  memset(ans, -1, sizeof(ans));

  cout << Solve(n - 1, n - 1, a, b, pos) << endl;

  return 0;
}


Measured memory_bytes: 391680
N, K = map(int, input().split())
a = tuple(map(int, input().split()))

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [0] * (K+1)
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())


Measured memory_bytes: 37144
import numpy as np
num = np.array(map(int,raw_input().split()))

num = np.sort(num)

if (num[1] - num[0]) % 2 == 0:
    print (num[1] - num[0]) / 2 + num[2] - num[1]

else:
    print (num[1] - num[0]) / 2 + num[2] - num[1] + 2

Measured memory_bytes: 12288
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

//AtCoder Beginner Contest 155
//C	Poll
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		String[] S = new String[N];
		Map<String, Integer> count = new HashMap<>();
		for (int i = 0; i < N; i++) {
			S[i] = sc.next();
			if (count.containsKey(S[i])) {
				count.put(S[i], count.get(S[i]).intValue() + 1);
			} else {
				count.put(S[i], 1);
			}
		}
		sc.close();

		int max = Collections.max(count.values());
		Set<String> set = new HashSet<>();
		for (Map.Entry<String, Integer> s : count.entrySet()) {
			if (s.getValue() == max) {
				set.add(s.getKey());
			}
		}
		List<String> l = new ArrayList<>(set);
		Collections.sort(l);
		for (String s : l) {
			System.out.println(s);
		}
	}
}


Measured memory_bytes: 92344
#include <iostream>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < n;i++)
int main() {
	int n, h, x, y, sum = 0,ans =0;cin >> n >> h;
	vector<pair<int, bool>> a(2 * n);
	rep(i, n) {
		cin >> x >> y;
		a[i * 2].first = x;a[i * 2].second = true;
		a[i * 2 + 1].first = y;a[i * 2 + 1].second = false;
	}
	sort(a.rbegin(), a.rend());
	int k = 0;
	rep(i, 2 * n) {
		if (a[i].second) {
			k = a[i].first;
			if ((h - sum) % k != 0) ans += (h - sum) / k + 1;
			else ans += (h - sum) / k;
			break;
		}
		sum += a[i].first;ans++;
		if (sum >= h) break;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <stdio.h>

#define MAX_N 246912

int isPrime[ MAX_N + 1 ];

int main( void ) {
	int i, j, n, num;

	isPrime[ 0 ] = isPrime[ 1 ] = 0;
	for ( i = 2; i <= MAX_N; i++ )
		isPrime[ i ] = 1;

	for ( i = 4; i <= MAX_N; i += 2 )
		isPrime[ i ] = 0;

	for ( i = 3; i * i <= MAX_N; i += 2 )
		if ( isPrime[ i ] )
			for ( j = i * 2; j <= MAX_N; j += i )
				isPrime[ j ] = 0;

	for ( ; scanf( "%d", &n ), n; printf( "%d\n", num ) ) {
		num = n == 1;
		for ( i = ( n + 1 ) / 2 * 2 + 1; i <= n * 2; i += 2 )
			num += isPrime[ i ];
	}

	return 0;
}

Measured memory_bytes: 1564