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

int main() {
	// your code goes here
	int h,n;
	cin>>h>>n;
	vector<int>a(n),b(n);
	std::vector<int>dp(h+1,INT_MAX);
	for(int i=0;i<n;i++)
	{
	    cin>>a[i]>>b[i];
	}
	dp[0]=0;
	for(int i=1;i<=h;i++)
	{
	    for(int j=0;j<n;j++)
	    {
	        dp[i]=min(dp[max(0,i-a[j])]+b[j],dp[i]);
	    }
	}
	cout<<dp[h]<<endl;
	
	return 0;
}


Measured memory_bytes: 384
import sys
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
x=read()
a=list(reads())
dic=[]
dic2=defaultdict(int)
for i in range(x):
  dic.append(i+a[i])
  dic2[i-a[i]]+=1
ans=0
#print(dic,dic2)
for i in dic:
  ans+=dic2[i]
print(ans)
  


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

ll H;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H;
	
	ll ret=0;
	ll num=1;
	while(H>0) {
		ret+=num;
		num=num*2;
		H/=2;
	}
	cout<<ret<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto S = readln.chomp.to!(char[]);
    int[] N;
    N.length = S.length;

    int x;
    foreach (i, c; S) {
        if (c == 'R') {
            ++x;
        } else {
            N[i-1] += (x+1)/2;
            N[i] += x/2;
            x = 0;
        }
    }
    x = 0;
    foreach_reverse (i, c; S) {
        if (c == 'L') {
            ++x;
        } else {
            N[i+1] += (x+1)/2;
            N[i] += x/2;
            x = 0;
        }
    }
    writeln(N.to!(string[]).join(" "));
}

Measured memory_bytes: 7704
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














string S;
ll cnt[2020];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> S;
	int N = S.length();

	ll ans = 0;
	cnt[0] = 1;
	int tot = 0;
	int p = 1;
	rrep(i, N - 1, 0) {
		tot = (tot + (S[i] - '0') * p) % 2019;
		
		ans += cnt[tot];

		p = (p * 10) % 2019;
		cnt[tot]++;
	}
	cout << ans << endl;
}







Measured memory_bytes: 3740
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)
typedef long long ll;
void solve(long long N, long long H, vector<long long> a, vector<long long> b){
	priority_queue< pair<ll,int> > Q;
	for(int i = 0 ; i < a.size() ; i++){
		Q.push({b[i], i});
	}
	long long ans = 0;
	while(H > 0){
		auto w = Q.top(); Q.pop();
		if( w.second >= 0 ){
			H -= w.first;
			ans++;
			Q.push({a[w.second], -1});
		}else{
			ans += (H+w.first-1) / w.first;
			break;
		}
	}
	cout << ans << endl;
}

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



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

using namespace std;

typedef long long ll;
typedef vector<int> pi;
typedef pair<int,int> vi;

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i <= b; i++)


int main() {
	int N;
	int M;
	int C;
	cin >> N >> M >> C;
	pi B;
	int b;
	for(int i = 0; i < M; i++){
		cin >> b;
		B.PB(b);
	}
	int solved = 0;
	for(int n = 0; n < N; n++){
		int sol = 0;
		for(int m=0; m < M; m++){
			cin >> b;
			sol += b*B[m];
		}
		if(sol + C > 0){
			++solved;
		}
	}
	cout << solved << "\n";
}


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

template <class T> using V = vector<T>;

using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;


#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;



int main() {
  ll n;
    ci(n);
  vll A(n);
  ll ans=0;
  FOR(i,0,n){
    ci(A[i]);
    ans=gcd(ans,A[i]);
  }
  co(ans)
}

Measured memory_bytes: 1024
n,m = gets.split.map(&:to_i)

if (n-m).abs > 1
  puts 0
  exit 0
end

M = 10**9+7

def fact(n)
   (1..n).inject{|memo,i| memo * i % M}
end

a = if n == m
  fact(n) * fact(m) * 2 % M
else
  fact(n) * fact(m) % M
end

puts a


Measured memory_bytes: 1788
import Text.Printf

getInts :: IO [Int]
getInts = map read . words <$> getLine

main :: IO()
main = do
  _ <- getLine
  a <- getInts
  printf "%f" $ slv a 

slv :: [Int] -> Double
slv a = 1.0 / val
  where val = sum $ map (\x -> 1.0 / (fromIntegral x)) a

Measured memory_bytes: 1020
n = int(input())
size = 1000001
# 1000001
# ar = [0] * 1000001
ar = [0] * size

br = list(map(int, input().split()))

for i in range(n):
	ar[br[i]] += 1


i = 1
cnt = 0
while i < size:
	if ar[i] is -1 or ar[i] is 0:
		i += 1
		continue
	
	if ar[i] == 1:
		# print(i)
		cnt += 1

	j = i
	while j < size:
		ar[j] = -1
		j += i

	i +=1

# print(ar)

print(cnt)

	

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

using namespace std;

typedef long long ll;
ll h1, m1, h2, m2, k;

int main() {
	cin >> h1 >> m1 >> h2 >> m2 >> k;

	ll t = (h2 * 60 + m2) - (h1 * 60 + m1);
	t -= k;
	if (t < 0) t = 0;
	cout << t << endl;

	return 0;
}

Measured memory_bytes: 3624
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
#define ll long long
int n;
ll k;
const int Maxn=5005;
int p[Maxn];
ll c[Maxn];

void calc(int now,vector<ll>&vv){
	ll sum=0;
	int at=now;
	for(int i=1;i<=n;i++){
		sum+=c[p[at]];
		vv.push_back(sum);
		at=p[at];
		if(at==now)return;
	}
}
int main(){
	scanf("%d%lld",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&p[i]);
		p[i]--;
	}
	for(int i=0;i<n;i++)scanf("%lld",&c[i]);
	ll ans=-1e17;
	for(int i=0;i<n;i++){
		vector<ll>vv;
		calc(i,vv);
//		for(int i=0;i<vv.size();i++)cout<<vv[i]<<' ';cout<<endl;
		int q=k/vv.size();
		if(q>=1){
			ll mx=-1e17;
			for(int j=0;j<(k-q*vv.size());j++){
				mx=max(mx,vv[j]);
			}
			if(vv.back()>0)mx+=q*vv.back();
			ans=max(ans,mx);
			
			mx=-1e17;
			for(int j=0;j<vv.size();j++)mx=max(mx,vv[j]);
			if(vv.back()>0)mx+=(q-1)*vv.back();
			ans=max(ans,mx);
		}else{
			ll mx=-1e17;
			for(int j=0;j<k;j++){
				mx=max(mx,vv[j]);
			}
			ans=max(ans,mx);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3948
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define REP(i,n) for(int i = 0 ; i < n ; i ++) 
#define ms(a,c) memset(a,c,sizeof a)
#define INF 1e15
int N , W , *wt , *val ;
int dp[102][100005] ;
int f(int i , int v ) {
	if(v==0) return 0;
	if(v<0) return INF;
	if(i==N) {
		return INF;
	}
	int &ret = dp[i][v] ;
	if(ret!=-1) return ret;
	return ret = min({f(i+1,v),wt[i] + f(i+1, v-val[i])}) ;
}
int driver() {
	int sv = 0 ;
	REP(i,N){
		sv+=val[i] ;
	}
	ms(dp,-1);
	for(int v = sv ; v >= 1 ;v-- ) {
		if(f(0,v) <= W) {
			return v;
		}
	}
	return 0;	
}
int32_t main() {
	cin >> N >> W;
	wt = new int[N] ;
	val = new int[N];
	REP(i,N) {
		cin >> wt[i] >> val[i] ;
	}
	int ans = driver();
	printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 80000
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

ll h, w;
ll p[100005];
ll q[100005];

int main() {
    cin >> w >> h;

    for (int i = 0; i < w; i++) {
        cin >> p[i];
    }

    for (int i = 0; i < h; i++) {
        cin >> q[i];
    }

    sort(p, p + w);
    sort(q, q + h);
    p[w] = 1ll << 60ll;
    q[h] = 1ll << 60ll;

    ll ans = 0;
    ll k, j;
    k = j = 0;
    for (ll i = 0; i < (h + 1) * (w + 1) - 1;) {
        if (p[k] < q[j]) {
            ans += p[k] * (h + 1 - j);
            k++;
            i += h + 1 - j;
        }
        else {
            ans += q[j] * (w + 1 - k);
            j++;
            i += w + 1 - k;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e16+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int mod_pow(int x,int y) {
    int res = 1;
    while(y > 0) {
        if(y%2) {
            res = res*x%mod;
        }
        x = x*x%mod;
        y/=2;
    }
    return res;
}
int fac[100005], finv[100005], inv[100005];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 100005; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}
int COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
signed main() {
    int N,K;
    cin >> N >> K;
    vector<int>A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    COMinit();
    sort(A.begin(),A.end());
    int ans = 0;
    for(int i = 0; i <= N-K; i++) {
        ans = (ans+mod-COM(N-i-1,K-1)*A[i]%mod);
    }
    for(int i = K-1; i < N; i++) {
        ans += COM(i,K-1)*A[i];
        ans %= mod;
    }
    cout << ans << endl;
}


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

nn = [1 for i in range(n)]
mm = [2 for i in range(m)]

nn.extend(mm)

res = 0
for i in range(n+m):
    for j in range(i+1, n+m):
        if (nn[i] + nn[j]) % 2 ==0:
            res = res + 1
        
print(res)



Measured memory_bytes: 3060
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"

using namespace std;

int main()
{
  string s;
  cin >> s;
  long long k;
  cin >> k;
  bool check = true;
  for (long long i = 0; i < k; i++)
  {
    if (s[i] > '1')
    {
      cout << s[i] << endl;
      check = false;
      break;
    }
  }
  if (check)
  {
    cout << 1 << endl;
  }
}


Measured memory_bytes: 256
(* O(1) *)
let f0 n =
  let last = if n mod 2 = 0 then n else 0 in
  last lxor ((n + 1) / 2 mod 2)

(* O(1) *)
let solve a b = f0 (a - 1) lxor f0 b

let read_ints () = read_line () |> Str.split (Str.regexp " ") |> List.map int_of_string

let _ =
  match read_ints () with
  | [a; b] -> solve a b |> string_of_int |> print_endline
  | _ -> ()

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

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

int main()
{
    ll i,j;
    ll n;
    string s;
    cin >> n >> s;
    ll q;
    cin >> q;
    vector<ll> k(q);
    rep(i,q) cin >> k[i];
    rep(i,q){
        ll now = 0;
        ll d = 0, m = 0, dm = 0;
        ll ans = 0;
        while(now < n){
            if(s[now] == 'D') ++d;
            else if(s[now] == 'M'){
                ++m;
                dm += d;
            }else if(s[now] == 'C'){
                ans += dm;
            }
            if(now - k[i] + 1 >= 0){
                j = now - k[i] + 1;
                if(s[j] == 'D'){
                    dm -= m;
                    --d;
                }
                else if(s[j] == 'M') --m;
            }
            ++now;
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 5244
#include<iostream>
using namespace std;
int main(){
  int N,a,b,c;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>a>>b>>c;
    if((a*a)==(b*b)+(c*c))
      cout<<"YES"<<endl;
    else if((b*b)==(a*a)+(c*c))
      cout<<"YES"<<endl;
    else if((c*c)==(a*a)+(b*b))
      cout<<"YES"<<endl;
    else
      cout<<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    string s, t, u;
    cin >> s >> t >> u;
    cout << (char)toupper(s[0]) << (char)toupper(t[0]) << (char)toupper(u[0]) << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main()
{
  int a[5];
  for(int i=0; i<5; i++)
    	cin>>a[i];
  for(int i=0; i<5; i++)
  {	
    if(a[i]==0)
    {
      cout<<i+1<<endl;
      break;
    }
  }
  return(0);
}

Measured memory_bytes: 3584
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;
char a[55];

int main()
{
	scanf("%s",&a);
	int len = strlen(a);
	for(int i = len - 1; i >= len - 8; i--){
		a[i] = 0;
	}
	a[len - 8] = '\0';
	printf("%s\n",a);
}
 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, b, n) for (int i = b; i <= n; ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;
const string YES = "Yes";
const string NO = "No";

void solve(long N, long M, vector<long> A, vector<long> B) {

  vector<vector<long>> roads(N + 1);
  REP(i, M) {
    roads[A[i]].emplace_back(B[i]);
    roads[B[i]].emplace_back(A[i]);
  }
  vector<long> mark(N + 1);
  queue<long> q;
  q.emplace(1);

  while (!q.empty()) {
    long n = q.front();		// interested node
    q.pop();
    long nn = roads[n].size();	// num neighbors
    REP(i, nn) {
      long neighbor = roads[n][i];
      if (!mark[neighbor]) {
	mark[neighbor] = n;
	q.emplace(neighbor);
      }
    }
  }
  if (find(mark.cbegin() + 2, mark.cend(), 0) != mark.cend()) {
    cout << NO << endl;
    return;
  } else {
    cout << YES << endl;
    FOR(i, 2, N)
      cout << mark[i] << endl;
  }
}

int main(){
  // int 3E4  long 2E9  ll 9E18
  cin.tie(0);
  ios::sync_with_stdio(false);

  long N, M;
  cin >> N >> M;
  vector<long> A(M);
  vector<long> B(M);
  REP(i, M)
    cin >> A[i] >> B[i];

  solve(N, M, move(A), move(B));

  return 0;
}


Measured memory_bytes: 15968
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


const long long INF = 1LL << 60;
vector<ll> a(100010), dp(100010);

int main(){
  int N;
  cin >> N;
  int sum = 0;
  vector<int> T(N);
  for(int i = 0; i < N; i++){
    cin >> T.at(i);
    sum += T.at(i);
  }
  int M;
  cin >> M;
  vector<int> P(M), X(M);
  for(int i = 0; i < M; i++){
    cin >> P.at(i) >> X.at(i);
    P.at(i)--;
  }

  for(int i = 0; i < M; i++){
    cout << sum - T.at(P.at(i)) + X.at(i) << endl;
  }

}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Text;

namespace contest
{
    class Program
    {       
        static int Main(string[] args)
        {
                string read = Console.ReadLine();
                int dataset_num = int.Parse(read);

                for (int i = 0; i < dataset_num; i++)
                {
                    //空白で分割する
                    var line = Console.ReadLine().Split();

                    //配列の要素、すべてに処理を行う
                    var num_array =  Array.ConvertAll(line, len => int.Parse(len));

                    //ソート
                    Array.Sort(num_array);

                    if (num_array[2] * num_array[2] == (num_array[0] * num_array[0] + num_array[1] * num_array[1]))
                    {
                        Console.WriteLine("YES");
                    }
                    else
                    {
                        Console.WriteLine("NO");
                    }

                }


                return 0;

        }

    }
}

Measured memory_bytes: 5600
n = int(input())
x = {}
for i in range(1,n+1):
  si,pi = map(str,input().split())
  if si not in x.keys():
    x[si] = [(int(pi),i)]
  else:
    x[si].append((int(pi),i))
y = sorted(x.keys())
for k in y:
  xk = x[k]
  xk.sort(key=lambda xx:xx[0],reverse=True)
  for i in xk:
    print(i[1])

Measured memory_bytes: 3064
//------------------------------------------------------------------------------MANAS UNIYAL---------------------------------------------------------
//                                                                              NEVER GIVE UP
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);	cin.tie(NULL);	cout.tie(NULL);
#define ll long long
#define pb push_back
#define fi first 
#define se second
#define pii pair<ll,ll>
#define INF 0x3f3f3f3f
#define LINF 98765432123456789
#define testcases() ll t; cin>>t; while(t--)
#define debug1(x) cout<<#x<<" "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<"\n";
#define debug4(w,x,y,z) cout<<#w<<" "<<w<<" "<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<"\n";
#define rep(i,start,end) for(ll i=start;i<end;i++)
 
//----------------------------------------------------------------------------------------------------------------------------------------------------

int main()
{
	fast;
    int n;
	cin>>n;
	ll sum = 0;
	for(ll i=1;i<=n;i++)
	{
		if((i%3==0 && i%5==0) || i%3==0 || i%5==0)
			continue;
		sum += i;
	}
	cout<<sum;
}


Measured memory_bytes: 3648
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

double entropy(vector<int> I, int S, int A, int C) {
	vector<int> a(256);
	int N = I.size(), R = S;
	for (int i = 0; i < N; i++) {
		R = (A * R + C) % 256;
		I[i] = (I[i] + R) % 256;
		a[I[i]]++;
	}
	double x = 0;
	for (int j = 0; j < 256; j++)
		if (a[j]) {
			double r = (double)a[j] / N;
			x -= r * log(r);
		}
	return x;
}

int main() {
	for (;;) {
		int N; cin >> N;
		if (N == 0) break;
		vector<int> I(N);
		for (int i = 0; i < N; i++) cin >> I[i];
		int s, a, c; double mini = DBL_MAX;
		for (int S = 0; S < 16; S++)
			for (int A = 0; A < 16; A++)
				for (int C = 0; C < 16; C++) {
					double x = entropy(I, S, A, C);
					if (x < mini - EPS) {
						s = S; a = A; c = C; mini = x;
					}
				}
		cout << s << ' ' << a << ' ' << c << endl;
	}
}

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

#define rep(i, n) REP(i, 0, n)
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(x) cout << x << endl;

int main() {
    int a[9];
    rep(i, 9) cin >> a[i];
    int n;
    cin >> n;
    rep(i, n){
        int b;
        cin >> b;
        rep(i, 9){
            if(a[i] == b){
                a[i] = 0;
            }
        }
    }

    string ans = "No";
    if(a[0] == 0 && a[1] == 0 && a[2] == 0) ans = "Yes";
    if(a[3] == 0 && a[4] == 0 && a[5] == 0) ans = "Yes";
    if(a[6] == 0 && a[7] == 0 && a[8] == 0) ans = "Yes";
    if(a[0] == 0 && a[3] == 0 && a[6] == 0) ans = "Yes";
    if(a[1] == 0 && a[4] == 0 && a[7] == 0) ans = "Yes";
    if(a[2] == 0 && a[5] == 0 && a[8] == 0) ans = "Yes";
    if(a[0] == 0 && a[4] == 0 && a[8] == 0) ans = "Yes";
    if(a[2] == 0 && a[4] == 0 && a[6] == 0) ans = "Yes";
    OP(ans);
}


Measured memory_bytes: 256
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    ans = 10**15
    from itertools import accumulate
    S = list(accumulate([0] + A))
    idx = [1, 2, 3]
    for center in range(2, N-1):
        idx[1] = center
        P_sum = S[idx[0]] - S[0]
        Q_sum = S[idx[1]] - S[idx[0]]
        mae_diff = abs(P_sum - Q_sum)
        while idx[0] < center - 1 and \
                abs((P_sum + A[idx[0]]) - (Q_sum - A[idx[0]])) < mae_diff:
            idx[0] += 1
            P_sum = S[idx[0]] - S[0]
            Q_sum = S[idx[1]] - S[idx[0]]
            mae_diff = abs(P_sum - Q_sum)

        R_sum = S[idx[2]] - S[idx[1]]
        S_sum = S[N] - S[idx[2]]
        usi_diff = abs(R_sum - S_sum)
        while idx[2] < N and \
                abs((R_sum + A[idx[2]]) - (S_sum - A[idx[2]])) < usi_diff:
            idx[2] += 1
            R_sum = S[idx[2]] - S[idx[1]]
            S_sum = S[N] - S[idx[2]]
            usi_diff = abs(R_sum - S_sum)

        ans = min(ans, abs(max(P_sum, Q_sum, R_sum, S_sum) -
                           min(P_sum, Q_sum, R_sum, S_sum)))
        if idx[1] + 1 == idx[2]:
            idx[2] += 1
    print(ans)


if __name__ == '__main__':
    main()


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

typedef long long int ll;
typedef pair<int,int> pi;
priority_queue<pi, vector<pi>, greater<pi> > pq; //min heap

ll mini(ll a,ll b){	return a<b?a:b;}
ll maxi(ll a,ll b){	return a>b?a:b;}
ll gcd(ll a,ll b){	if(b == 0)	return a;return gcd(b,a%b);}
ll binpow(ll n,ll x){	ll ans = 1;while(x){if(x & 1)	ans *= n;n *= n;x >>= 1;}return ans;}

vector<int> edge[int(1e5+1)];
vector<int> indegree(1e5+1,0);

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

    int n,m;
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;++i){
        cin>>u>>v;
        edge[u].push_back(v);
        indegree[v]++;
    }

    for(int i=1;i<=n;++i)   pq.push(make_pair(indegree[i], i));

    vector<int> dp(1e5+3,0);//dp array that keeps track of maximum length of path till that point
    queue<int> q;
    while(pq.top().first == 0){
        // cout<<pq.top().second<<"\n";
        q.push(pq.top().second);
        pq.pop();
    }
   
    int ind;
    // cout<<"start\n";
    while(q.size()){
        // cout<<ind<<"\n";
        ind = q.front();
        q.pop();
        for(auto i:edge[ind]){
            dp[i] = max(dp[i], dp[ind] + 1);
            indegree[i]--;
            if(!indegree[i])    q.push(i);
        }
    }
    // cout<<"end\n";

    int ans = 0;
    // for(int i=1;i<=n;++i)   cout<<dp[i]<<" ";
    // cout<<"\n";
    for(int i=1;i<=n;++i)   ans = max(ans, dp[i]);

    cout<<ans<<"\n";

    return 0;
}

Measured memory_bytes: 10388
using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var str = Console.ReadLine();
            var strs = str.Split(' ');
            var N = int.Parse(strs[0]);
            var Q = int.Parse(strs[1]);

            var S = Console.ReadLine();

            var ls = new int[Q];
            var rs = new int[Q];
            for (int i = 0; i < Q; i++)
            {
                str = Console.ReadLine();
                strs = str.Split(' ');
                ls[i] = int.Parse(strs[0]);
                rs[i] = int.Parse(strs[1]);
            }

            var AC = new int[N + 1];
            for (int i = 0; i < N - 1; i++)
            {
                if (S[i] == 'A')
                {
                    if (S[i + 1] == 'C')
                    {
                        AC[i + 1] = AC[i] + 1;
                        i++;
                        AC[i + 1] = AC[i];
                    }
                    else
                    {
                        AC[i + 1] = AC[i];
                    }
                }
                else
                {
                    AC[i + 1] = AC[i];
                }
            }
            AC[N] = AC[N - 1];
            
            for (int i = 0; i < Q; i++)
            {
                Console.WriteLine(AC[rs[i] - 1] - AC[ls[i] - 1]);
            }
        }
    }
}


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

#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 300300;
const long long mod = 1e9 + 7;

using namespace std;

int q;
int a[N];
int b[N];
string s, t;

void solve()
{
        cin >> s >> t;
        for(int i = 0; i < s.size(); i++) a[i + 1] = a[i] + s[i] - 'A' + 1;
        for(int i = 0; i < t.size(); i++) b[i + 1] = b[i] + t[i] - 'A' + 1;
        cin >> q;
        for(int i = 0; i < q; i++){
                int l1, r1, l2, r2;
                cin >> l1 >> r1 >> l2 >> r2;
                if((a[r1] - a[l1 - 1]) % 3 == (b[r2] - b[l2 - 1]) % 3) cout << "YES\n";
                else cout << "NO\n";
        }
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("landscape.in");
        //fout("landscape.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}


Measured memory_bytes: 1744
#include <stdio.h>
#include <math.h>
int main(){
	double c,d;
	scanf("%lf",&d);
	int di=d;
	c=sqrt(2)*d;
	if(d<sqrt(di*di+1)&&c<di+1)c=di+1;
	printf("%.9f\n",c);
	return 0;
}

Measured memory_bytes: 652
var N;
function c753(s) {
    if ((s - 0) > N) return 0;

    var f = new Array(8).fill(false);
    for (var n = 0; n < s.length; n++) { f[s.charAt(n) - 0] = true; }
    var count = (f[7] && f[5] && f[3]) ? 1 : 0;
    for (var c of ['7', '5', '3']) { count += c753(s + c); }
    return count;
}

function Main(input) {
    N = input.split("\n")[0] - 0;
    var count = c753("");
    console.log(count);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21448
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,N) for(int i = 0; i < N; i++)
#define INF 1 << 28
typedef pair<int,int> Pi;
#define F first
#define S second
#define pb push_back

inline void chmax(int &a, int b) { a = max(a,b); }
inline void chmin(int &a, int b) { a = min(a,b); }

int main()
{
  int N;
  while(cin >> N,N) {
    stack<Pi>st;
    int A;
    int sum = 0;
    Rep(i,N) {
      cin >> A;
      if(!A)sum++;
      if(!(i & 1) || st.top().F == A) {
	if(st.empty() || st.top().F != A)st.push(Pi(A,i));
	continue;
      }
      int p = st.top().S;
      st.pop();
      if(A)sum -= (i - p);
      else sum += (i - p);
      if(st.empty())st.push(Pi(A,0));
    }
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
const ll INF =1001001001;

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}

//素数判定
ll isprime(ll n){
  bool prime=true;
  for(int i=2;i<n;i++){
    if(n%i==0){
      prime=false; break;
    }
  }
if(prime){cout<<n<<" is prime"<<endl;
         }else{cout<<n<<" is not prime"<<endl;}

}
//階乗　20くらいが限界
ll factorial(ll n){
  ll a=1;ll b=n;
  for(int i=0;i<n;i++){
    a*=b;
    b--;
  }
  return a;
}

//組み合わせ　nCr
ll comb(ll a,ll b){
  ll c;
  c=factorial(a)/(factorial(a-b)*factorial(b));
  return c; 
}




/*10億7。　　　100000007
2*2行列 H*W
vector<vector<int>> vec(H,vector<int>(W));
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
cin>>vec[i][j];
  }
}

文字列→数列
string S;int A=atoi(S.c_str());
数列→文字列
int A;string S=to_string(A);
数字判定　isdigit(a)
pair宣言　pair<int,int> p(5,7);
ソート　sort(vec.begin(),vec.end());
*/

int main(){
cout<<fixed<<setprecision(10);
//cin.tie(0); ios::sync_with_stdio(false);

string S;cin>>S;
  for(int i=0;i<S.size();i+=2){
    cout<<S[i];
  }
  cout<<endl;
  
  
  
  
  
}




Measured memory_bytes: 512
#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <queue>

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

using namespace std;

#define MAX_V 10000
int V;

typedef int Weight;
const Weight INF = 1000000000;

struct Edge{
  int src, dest;
  int cap, rev;
  Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

Weight h[MAX_V];                // potential
Weight dist[MAX_V];             // minimum distance
int prevv[MAX_V], preve[MAX_V]; // previous vertex and edge

void add_edge(Graph &g, int src, int dest, int cap, int weight) {
  g[src].push_back((Edge){src, dest, cap, (int)g[dest].size(), weight});
  g[dest].push_back((Edge){dest, src, 0, (int)g[src].size() - 1, -weight});
}

Weight min_cost_flow(Graph &g, int s, int t, int f) {
  Weight res = 0; V = g.size();
  memset(h, 0, sizeof(h));
  typedef pair<Weight, int> P;
  while (f > 0) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist, dist + V, INF);
    dist[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
      P p = que.top(); que.pop();
      int v = p.second; 
      if (dist[v] < p.first) continue;
      REP(i, g[v].size()) {
        Edge &e = g[v][i];
        if (e.cap > 0 && dist[e.dest] > dist[v] + e.weight + h[v] - h[e.dest]) {
          dist[e.dest] = dist[v] + e.weight + h[v] - h[e.dest];
          prevv[e.dest] = v;
          preve[e.dest] = i;
          que.push(P(dist[e.dest], e.dest));
        }
      }
    }
    if (dist[t] == INF) return -1;
    REP(v, V) h[v] += dist[v];

    int d = f;
    for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
    f -= d;
    res += d * h[t];
    for (int v = t; v != s; v = prevv[v]) {
      Edge &e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return res;
}

int main() {
  while(1){
    int n;
    cin>>n;
    if(!n)break;
    vector<int> s(n+1);
    vector<int> e(n+1);
    vector<int> w(n);
    Graph g(2*n+3);
    REP(i,n){
      cin>>s[i]>>e[i+1]>>w[i];
      add_edge(g, i*2+1, i*2+2, 1, -w[i]);
    }
    s[n]=366;
    REP(i,n+1){
      REP(j,n+1){
        if(e[i] < s[j]){
          add_edge(g, i*2, j*2+1, 1, 0);
        }
      }
    }
    add_edge(g, 2*n+2, 0, 2, 0);
    int v = min_cost_flow(g, 2*n+2, 2*n+1, 2);
    cout<<-v<<endl;
  }
  return 0;
}

Measured memory_bytes: 27028
n, k = map(int, input().split())
a = list(map(int, input().split()))

# prob1
"""
ans = 0
for i in range(1, len(a)):
    ans += max(a[i-1]-a[i]+1, 0)
    a[i] += max(a[i-1]-a[i]+1, 0)
print(ans)
"""

ans = float("inf")
for i in range(1 << (n - 1)):
    a_copied = a.copy()
    comb = [0]
    cost = 0
    for j in range(n-1):
        if (i >> j) & 1 == 1:
            comb.append(1)
        else:
            comb.append(0)
    if sum(comb) < k - 1:
        continue
    
    for j in range(1, len(comb)):
        if comb[j] == 0:
            continue
        else:
            height = max(0, max(a_copied[:j])-a_copied[j]+1)   
            cost += height
            a_copied[j] += height 
    ans = min(cost, ans)
print(ans)

            



    





Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    string s,t;
    cin>>s>>t;
    int cnt=0;
    rep(i,0,N){
        bool u=true;
        rep(j,0,N-i){
            if(s[i+j]!=t[j]) u=false;
        }
        if(u){
            cout <<N+i<<"\n";
            return 0;
        }
    }
    cout <<2*N<<"\n";
}

Measured memory_bytes: 256
n, m = map(int, input().split())
hList = list(map(int, input().split()))
hAns = [1] * n
for i in range(m):
    a, b = map(int, input().split())
    if hList[a - 1] > hList[b - 1]:
        hAns[b - 1] = 0
        continue
    if hList[a - 1] < hList[b - 1]:
        hAns[a - 1] = 0
        continue
    if hList[a - 1] == hList[b - 1]:
        hAns[a - 1] = 0
        hAns[b - 1] = 0
print(sum(hAns))


Measured memory_bytes: 19988
public class Main {
    private static java.util.Scanner scanner = new java.util.Scanner(System.in);

    public static void main(String[] args) {
        int n = scanner.nextInt();
        long fd = 0, min = -1, temp;
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            fd += a[i] = scanner.nextInt();
        for (int i = 0; i < n - 1; i++) {
            min = Math.min(temp = Math.abs(fd -= a[i] * 2), min == -1 ? temp : min);
        }

        System.out.println(min);
    }
}

Measured memory_bytes: 80328
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int target = n;
		int sum = 0;
		while (target > 0) {
			sum += target % 10;
			target /= 10;
		}
		System.out.println(n % sum == 0 ? "Yes" : "No");

	}

}


Measured memory_bytes: 23764
// In the name of God

#include <bits/stdc++.h>

using namespace std;

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

	int k;
	cin >> k;
	
	string s;
	cin >> s;

	cout << s.substr(0, min(k, (int)s.length()));

	if(s.length() > k) cout << "...";

	return 0;
}


Measured memory_bytes: 3568
k,a,b = map(int,input().split())
if a+2>=b:
  print(1+k)
else:
  #bisできるセット
  q = (k-a+1)//2
  if q ==0:
    print(1+k)
  else:
    print(1+(k-2*q)+q*(b-a))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <string.h>
#define rep(i, n) for(int i = 0; i<(n); i++)
using namespace std;
typedef long long ll;
static const int MAX = 200000; 
//pi = 3.14159265358979323846

int main() {

    int x, a;
    cin >> x >> a;

    if(x < a){
        cout << "0";
    }else{
        cout << "10";
    }

}




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

const int MAX_Q = 55;
int n, m, q;
int a[MAX_Q], b[MAX_Q], c[MAX_Q], d[MAX_Q];

int ans = 0;
 
void all_search(vector <int> &v, int dep) {
	if ( dep > n ) {
		int sum = 0;
		for ( int k = 0; k < q; k++ ) {
      if ( v[b[k]] - v[a[k]] == c[k] ) { sum += d[k]; }
    }
		ans = ( sum > ans ) ? sum : ans;
		return;
	}

	for(int k = v[dep - 1]; k <= m; k++) {
		v[dep] = k;
		all_search(v, dep+1);
	}
}
 
int main() {
	cin >> n >> m >> q;
	for ( int i = 0; i < q; i++ ) {
	  cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
	
	vector <int> v(n+1, 1);
	all_search(v, 1);

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

Measured memory_bytes: 3648
from collections import deque

n, m = map(int, input().split())
l = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)
ans = [0] * (n + 1)
f = [0] * (n + 1)
d = deque()
d.append(1)
while len(d) > 0:
    k = d.popleft()
    f[k] = 1
    for i in l[k]:
        if f[i] == 1:
            continue
        ans[i] = k
        d.append(i)
        f[i] = 1
for i in range(2, n + 1):
    if ans[i] == 0:
        print("No")
        exit()
print("Yes")
for i in range(2, n + 1):
    print(ans[i])

Measured memory_bytes: 34992
from sys import exit

A, B, C, K = map(int, input().split())


if A == B:
    print(0)
    exit()

if abs(A - B) > 10 ** 18:
    print("Unfair")
    exit()

sign = (A - B) // abs(A - B)


if K % 2 == 0:
    print(abs(A - B) * sign)
else:
    print(abs(A - B) * sign * (-1))


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> p2;
ll c[200005],sz[200005],tin[200005],ans[200005],timer=1;
vector<vector<ll>> res(200005);
ll func(ll n){
	return n*(n+1)/2;
}
void dfs(ll i,ll p,vector<vector<ll>> &v){
	sz[i]=1;
	tin[i]=timer++;
	for(ll j=0;j<ll(v[i].size());j++)
	if(v[i][j]!=p){
		dfs(v[i][j],i,v);
		sz[i]+=sz[v[i][j]];
		ll val=sz[v[i][j]];
		while(!res[c[i]].empty()&&tin[res[c[i]].back()]>=tin[i]){
			val-=sz[res[c[i]].back()];
			res[c[i]].pop_back();
		}
		ans[c[i]]+=func(val);
	}
	res[c[i]].push_back(i);
}
void solve(){
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)
	cin>>c[i];
	vector<vector<ll>> v(n+1);
	for(ll i=0;i<n-1;i++){
		ll a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1,1,v);
	for(ll i=1;i<=n;i++){
		ll sum=n;
		for(ll j=0;j<ll(res[i].size());j++)
		sum-=sz[res[i][j]];
		ans[i]+=func(sum);
	}
	for(ll i=1;i<=n;i++){
		ans[i]=func(n)-ans[i];
		cout<<ans[i]<<"\n";
	}
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll qc=1;
    for(ll i=1;i<=qc;i++)
    solve();
}


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

int main() {
  int A,B,C,D ;
  cin >> A >> B >> C >>D;
   if (A+B > C+D) {
     cout << "Left" << endl;
   }
  else if (A+B < C+D) {
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}


Measured memory_bytes: 3668
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sc(x) scanf("%d", &x)
#define sc2(x, y) scanf("%d%d", &x, &y)
#define sc3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sc4(x, y, z, t) scanf("%d%d%d%d", &x, &y, &z, &t)
#define print(x) printf("%d ", x)
#define println(x) printf("%d\n", x)
#define println2(x, y) printf("%d %d\n", x, y)
#define println3(x, y, z) printf("%d %d %d\n", x, y, z)
#define println4(x, y, z, t) printf("%d %d %d %d\n", x, y, z, t)
#define mp make_pair
#define pb push_back
#define ft first
#define sd second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define endl '\n'                           // CommentInInteractive
#define DB(x) cerr << #x << " = " << x << endl

const ld eps = 1e-6;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;

void solve() {
    int x;
    cin >> x;
    cout << 1000*(x/500) + 5*(x%500/5) << endl;
}

//#define FILES
//#define TIME

int main() {
    // Comment if use stdio
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

#ifdef FILES
    freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    auto start = chrono::high_resolution_clock::now();
    solve();
    auto stop = chrono::high_resolution_clock::now();

#ifdef TIME
    cerr << chrono::duration_cast <chrono::milliseconds> (stop - start).count() << " ms\n";
#endif
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int N, M; 
vector<vector<int> > G(100005);
bool visited[100005];
deque<int> ans;
void dfs(int x, int f) {
  if(f) ans.push_front(x);
  else ans.push_back(x);
  visited[x] = true;
  for(int to : G[x]) {
    if(visited[to]) continue;
    dfs(to, f);
    break;
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  FOR(i,0,M) {
    int a, b; cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  dfs(1, 1);
  dfs(1, 0);
  cout << ans.size() - 1 << endl;
  FOR(i,0,ans.size()) {
    cout << ans[i] << " ";
    if(ans[i] == 1) i++;
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 6784
use proconio::input;
use std::collections::VecDeque;
use proconio::marker::Usize1;

fn push(dist: &mut Vec<usize>, queue: &mut VecDeque<usize>, v: usize, d: usize) {
  if dist[v] != usize::max_value() {
    return
  }
  dist[v] = d;
  queue.push_back(v);
}

fn main() {
  input! {
    K: usize,
    X: Usize1,
    Y: Usize1,
  }
  
  let mut answer: Vec<usize> = vec![0;K];
  for i in 0..K {
    let mut dist = vec![usize::max_value();K];
    let mut queue = VecDeque::new();
    push(&mut dist, &mut queue, i, 0);
    while queue.len() > 0 {
      let v = queue.pop_front().unwrap();
      let d = dist[v];
      if 0 != v { push(&mut dist, &mut queue, v-1, d+1); }
      if v+1 < K { push(&mut dist, &mut queue, v+1, d+1); }
      if v == X { push(&mut dist, &mut queue, Y, d+1); }
      if v == Y { push(&mut dist, &mut queue, X, d+1); }
    }
    
    for ii in dist {
      answer[ii] += 1;
    }
  }

  for i in 1..K {
    println!("{}", answer[i]/2);
  }
}


Measured memory_bytes: 2132
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#pragma warning(disable : 4996)

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

int n, r, d; int p[401][401];

int main()
{
	while (true)
	{
		scanf("%d", &n);

		if (n == 0) break;

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

		p[200][200] = 0;

		for (int i = 0; i < n - 1; i++)
		{
			scanf("%d", &r);
			scanf("%d", &d);

			for (int j = 0; j < 401; j++)
			{
				for (int k = 0; k < 401; k++)
				{
					if (p[j][k] == r)
					{
						p[j + dy[d]][k + dx[d]] = i + 1;
					}
				}
			}
		}

		int minx = 999, maxx = -1, miny = 999, maxy = -1;

		for (int j = 0; j < 401; j++)
		{
			for (int k = 0; k < 401; k++)
			{
				if (p[j][k] != -1)
				{
					minx = min(minx, k);
					maxx = max(maxx, k);
					miny = min(miny, j);
					maxy = max(maxy, j);
				}
			}
		}

		printf("%d %d\n", maxx - minx + 1, maxy - miny + 1);
	}

	return 0;
}

Measured memory_bytes: 3316
#include <stdio.h>
#include <string.h>
int equal(char *t,char *p,int i,int plen){
  int j;
  for(j=0;j<plen;j++){
    if(t[i+j]!=p[j]) return 0;
  }
  
  return 1;
}
int main(){
  char t[1000];
  char p[1000];
  int i,j;
  int tlen;
  int plen;
  scanf("%s",t);
  scanf("%s",p);
  tlen=strlen(t);
  plen=strlen(p);
  for(i=0;i<tlen;i++){
    if(equal(t,p,i,plen))printf("%d\n",i);
    
  }
  return 0;
}

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

using namespace std;
int freq[100010];
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        int x;
        scanf("%d",&x);
        freq[x]++;
    }
    int t = 0;
    for(int i = 0;i < 100010;i++)
    {
        if(freq[i] > 1)
        {
            n -= (freq[i]-1);
            if(freq[i]%2 == 0)
            {
                t++;
            }
        }
    }
    if(t % 2)
    {
        n--;
    }
    cout << n;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 100000
void inarray(int a[], int n){
    for(int i = 0; i < n; i++) cin >> a[i];
}

int main(){
    int a; cin >> a;
    cout << a + a*a + a*a*a << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long int LL;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const LL inf = 1e15;
LL n, a[maxn], sum[maxn];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + a[i];
    LL ans = inf;
    int st = lower_bound(sum+1, sum+1+n, sum[n]/2) - sum;
    st = max(st-100, 2);
    for(int i=2; i<n-1; i++){
        st = lower_bound(sum+1, sum+1+i, sum[i]/2) - sum;
        st = max(st-4, 1);
        LL mi = abs(sum[i]-sum[st]*2);
        for(;st<i;st++){
            LL val = abs(sum[i]-sum[st+1]*2);
            if(val > mi) break;
            mi = val;
            if(st == i-1) break;
        }
        a[0] = sum[st]; a[1] = sum[i] - sum[st];
        st = lower_bound(sum+1+i+1, sum+1+n, (sum[n]-sum[i])/2+sum[i]) - sum;
        st = max(st-4, i+1);
        mi = abs(sum[n]-sum[st]-sum[st]+sum[i]);
        for(;st<n;st++){
            LL val = abs(sum[n]-sum[st+1]-sum[st+1]+sum[i]);
            if(val > mi) break;
            mi = val;
            if(st == n-1) break;
        }
        a[2] = sum[st] - sum[i]; a[3] = sum[n] - sum[st];
        sort(a, a+4);
        ans = min(ans, a[3] - a[0]);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 5888