akhauriyash/Code-Regression huggingface dataset:
// https://atcoder.jp/contests/dp/tasks/dp_a
#include <bits/stdc++.h>
using namespace std;

const int NAX = int(1e5) + 5;

int arr[NAX];
int dp[NAX];

int N;

int solve(int i) {
	if (i >= N) return 0;
	if (dp[i] != -1) return dp[i];
		
	int a = abs(arr[i]-arr[i+1]) + solve(i+1);
	int b = N-i >= 2 ? abs(arr[i]-arr[i+2]) + solve(i+2) : INT_MAX;
	
	return dp[i] = min(a, b);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(dp, -1, sizeof(dp));
	
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> arr[i];
	
	cout << solve(1) << endl;
	
	return 0;
}


Measured memory_bytes: 4224
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split -- START --
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l
# Factoring by trial split --- END ---

# Summarize count of factor within list -- START --
def summarizeList(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

def main():
  n=I()
  ans=0

  for k in range(1,n+1):
    ans+=int((k/2)*(n//k)*(1+n//k))

  # for i in range(1,n+1):
  #   x=1
  #   if i==1:
  #     pass
  #   else:
  #     pl=getPrimeList(i)
  #     pl=summarizeList(pl)
  #     for a,c in pl:
  #       x*=(c+1)

  #   ans+=i*x

  return ans

# main()
print(main())


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

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

  int n, k;
  cin >> n >> k;
  vector<bool> a(10);
  while (k--) {
    int x;
    cin >> x;
    a[x] = true;
  }
  auto is_bad = [&](int x) {
    while (x) {
      if (a[x % 10]) return true;
      x /= 10;
    }
    return false;
  };
  while (is_bad(n)) n++;
  cout << n;
}

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

//template
#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 ALL(v) (v).begin(),(v).end()
typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x3fffffffffffffff;
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; }
//template end

typedef tuple<int,int,int> T;
ll calc(int a){return 1LL*a*(a+1)/2;}

int main(){
    int n,k; scanf("%d%d",&n,&k);
    T ans[100010];
    if(calc(k+2*n-1)-calc(k-1)>calc(k+3*n-1)-calc(k+2*n-1)){
        printf("-1\n"); return 0;
    }
    rep(i,0,n)get<2>(ans[i])=k+2*n+i;
    rep(i,0,n/2+1)get<0>(ans[2*i])=k+i,get<0>(ans[2*i+1])=k+n/2+(n&1)+i;
    rep(i,0,n/2+1)get<1>(ans[2*i+1])=k+n+i,get<1>(ans[2*i])=k+n+n/2+i;
    rep(i,0,n)if(get<0>(ans[i])+get<1>(ans[i])>get<2>(ans[i])){
        printf("-1\n"); return 0;
    }
    rep(i,0,n)printf("%d %d %d\n",get<0>(ans[i]),get<1>(ans[i]),get<2>(ans[i]));
    return 0;
}

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

int main() {
    string S;
    cin >> S;
    string result = "consonant";
    
    if(S == "a" || S == "e" || S == "i" || S == "o" || S == "u")
    {
        result = "vowel";
    }
    
    cout << result << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <map>
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
using namespace std;
int A[2][100];
int search(const int n, int itl, int itr,int sum) {
	int under = 0, right = 0;
	sum += A[itl][itr];
	if (itr == n - 1 && itl) {
		return sum;
	}
	if (itr < n - 1) {
		right = search(n, itl, itr + 1 , sum);
	}
	if (!itl) {
		under = search(n, itl + 1 , itr, sum);
	}
	return max(under, right);
}
int main() {
	int N;
	cin >> N;
	FOR(i, 0, N) cin >> A[0][i];
	FOR(i, 0, N) cin >> A[1][i];
	cout << search(N, 0, 0, 0);
	return 0;
}

Measured memory_bytes: 256
N, L = map(int, input().split())


def taste(i):
    return L + i - 1


all_taste = 0
for i in range(1, N + 1):
    all_taste += taste(i)
# print(all_taste)

ans = 1000000
final_taste = all_taste
for i in range(1, N + 1):
    sub_taste = 0
    for j in range(1, N + 1):
        if not i == j:
            sub_taste += taste(j)
    if abs(all_taste - sub_taste) < ans:
        ans = abs(all_taste - sub_taste)
        final_taste = sub_taste

print(final_taste)


Measured memory_bytes: 3064
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, initial=1)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()

def digit_sum(i):
    sm = 0
    for s in str(i):
        sm += int(s)
    return sm

suff = '9999999999999'
ans = 0 
# 後ろに付ける9の数を減らして、10^16-1から10099までを作る
for i in range(12):
    # 999～100までループ
    for j in range(999, 99, -1):
        j = int(str(j) + suff)
        if j > N:
            continue
        ans = max(digit_sum(j), ans)
    suff = suff[:-1]
# 9999以下は普通に全部やる(大した大きさじゃないので)
for i in range(9999, 0, -1):
        if i > N:
            continue
        ans = max(digit_sum(i), ans)
print(ans)


Measured memory_bytes: 5280
import numpy as np

N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

A = np.array(A).cumsum()
B = np.array(B).cumsum()

ans = 0
j = M
for i in range(N+1):
    if A[i] > K:
        break
    while B[j] > K - A[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)


Measured memory_bytes: 59756
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<iomanip>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1e9+7
#define LINF (long long)4e18


int main(){
   int X;
   cin >> X;
   vector<int> P = {1,4,8,16,32,64,128,256,512,9,27,81,243,729,25,125,625,36,216,49,343,100,1000};
   repr(i,11,32){
       P.push_back(i*i);
   }
   sort(P.begin(),P.end(),greater<int>());
   int ans = 0;
   rep(i,P.size()){
       if(P[i] <= X){
           ans = P[i];
           break;
       }
       
   }
   cout << ans << endl;
} 

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp make_pair
typedef long long Int;
#define INF (1<<28)

int n, a[4096];
int dp[4096][4096], fr[4096][4096];
Int s[4096];

int main() {
    scanf("%d", &n);
    rep (i, n) scanf("%d", a+i);
    rep (i, n) s[i+1] = s[i] + a[i];
    rep (i, n) dp[0][i+1] = 1;
    rep (i, n) {
        vector<pair<Int, int> > v;
        rep (j, i) if (dp[j][i]) v.push_back(mp(s[i]-s[j], j));
        for (int j = i+1; j <= n; j++) v.push_back(mp(s[j]-s[i], -j));
        sort(v.begin(), v.end());
        int mx = 0, mi = -1;
        rep (k, v.size()) {
            const int j = v[k].second;
            if (j < 0) {
                if (mi != -1) {
                    dp[i][-j] = mx + 1;
                    fr[i][-j] = mi;
                }
            }
            else {
                if (mx < dp[j][i]) {
                    mx = dp[j][i];
                    mi = j;
                }
            }
        }
    }
    int ans = -1, pre = -1;
    rep (i, n) {
        if (ans < dp[i][n]) {
            ans = dp[i][n];
            pre = i;
        }
    }
    printf("%d\n", ans);
    vector<int> ax;
    int cur = n;
    while (pre != 0) {
        ax.push_back(pre);
        const int npre = fr[pre][cur];
        cur = pre;
        pre = npre;
    }
    rep (i, ax.size()) {
        if (i) putchar(' ');
        printf("%d", ax[ax.size()-1-i]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 132264
#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(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

constexpr ll lim = 2510;

struct Edge {
    ll to, time, money;
    Edge(){}
    Edge(ll to, ll money, ll time):to(to), money(money), time(time){}
};

typedef pair<ll, P> PP;

int main(int argc, char const *argv[]) {
    ll n,m,s; cin>>n>>m>>s;
    s = min(lim-1, s);
    vector<vector<Edge>> g(n);
    rep(i,m) {
        ll u,v,a,b; cin>>u>>v>>a>>b;
        --u, --v;
        g[u].emplace_back(v,a,b);
        g[v].emplace_back(u,a,b);
    }
    vector<ll> c(n), d(n);
    rep(i,n) cin>>c[i]>>d[i];

    vector<vector<ll>> dp(n, vector<ll>(lim, LINF));
    auto dijkstra = [&]() {
        priority_queue<PP, vector<PP>, greater<PP>> pq;
        dp[0][s] = 0;
        // time, node, money
        pq.emplace(0, P(0, s));
        
        while (!pq.empty()) {
            PP cur = pq.top(); pq.pop();
            ll v = cur.second.first;
            ll c_m = cur.second.second;
            ll c_time = cur.first;
            if (dp[v][c_m] < c_time) continue;

            for (auto &&e: g[v]) {
                ll n_m = c_m-e.money;
                if (n_m < 0) continue;
                if (chmin(dp[e.to][n_m], dp[v][c_m]+e.time)) {
                    pq.emplace(dp[e.to][n_m], P(e.to ,n_m));
                }
            }

            if (c_m == lim) continue;
            ll n_m = min(c_m+c[v], 2500ll);
            if (chmin(dp[v][n_m], dp[v][c_m]+d[v])) {
                pq.emplace(dp[v][n_m], P(v, n_m));
            }
        }
    };

    dijkstra();

    for (int i = 1; i < n; ++i) {
        ll ans = LINF;
        rep(j, lim) {
            chmin(ans, dp[i][j]);
        }
        cout << ans << '\n';
    }

    return 0;
}

Measured memory_bytes: 7272
#include<stdio.h>
int X, A, B;
int main(){
  scanf("%d%d%d", &X, &A, &B);
  if(B<=A){
    printf("delicious\n");
  }else if(B<=A+X){
    printf("safe\n");
  }else{
    printf("dangerous\n");
  }
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int INF = 1 << 30;

int main() {
	int A[5];
	int sum = 0;
	for (int i = 0; i < 5; i++) {
		cin >> A[i];
		sum += ((A[i] + 9) / 10) * 10;
	}
	int ans = sum;
	for (int i = 0; i < 5; i++) {
		ans = min(ans, sum - ((A[i] + 9) / 10) * 10 + A[i]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <string>
#include <iostream>
#include <stack>

using namespace std;

long n;
long ans = 0;

void check(long m){
    if(m > 1 && n / m == n % m){
        ans += m;
    }
}

int main(){
    scanf("%ld", &n);
    for(long i = 1; i*i <= n; ++i){
        if(i * i == n){
            check(i-1);
        }else if(n % i == 0){
            // check(i-1);
            check(n/i-1);
        }
    }
    printf("%ld\n", ans);
    return 0;
}

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

using namespace std;

int main() {
    string s;
    cin >> s;
    if (s == "Sunny") {
        cout << "Cloudy" << endl;
    } else if (s == "Cloudy") {
        cout << "Rainy" << endl;
    } else {
        cout << "Sunny" << endl;
    }
}

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

using namespace std;


#define fr(i,a,b) for (long long int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (long long i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (long long i = (n) - 1; i >= 0; i--)
#define foreach(it,ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define debug(x) cout<<#x<<": "<<x<<endl
#define ull unsigned long long
#define ll long long int
#define ld double
#define ui unsigned int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second


#define PI 3.1415926535897932385
#define INF 1000111222
#define EPS 1e-7
#define MAXN 1000001
#define MOD 1000000007
                                           /*ASHWINI SHARMA*/
int main() {
    
    cin.sync_with_stdio(false);
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    int ans = h*W+w*H-w*h;
    ans = H*W - ans;
    cout << ans;
   
    return 0;
}

Measured memory_bytes: 256
n,c,k = map(int,input().split())
t = list(int(input()) for i in range(n))
t.sort()
ans = 0
i = 0
while i < n:
    a = t[i]
    j = i + 1
    z = 1
    for j in range(i+1,min(i+c,n)):
        if a+k >= t[j]:
            z += 1
        else:
            break
    i += z
    ans += 1
print(ans)

Measured memory_bytes: 13068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const ll INF = 1e18;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n, m;
    ll l;
    cin >> n >> m >> l;
    vector<vector<ll>> d(n, vector<ll>(n, INF));
    rep(i, 0, n) d[i][i] = 0;
    rep(i, 0, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        d[a][b] = d[b][a] = c;
    }

    rep(k, 0, n) {
        rep(i, 0, n) {
            rep(j, 0, n) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    vector<vector<ll>> d2(n, vector<ll>(n, INF));
    rep(i, 0, n) d2[i][i] = 0;
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (d[i][j] <= l) {
                d2[i][j] = 1;
            }
        }
    }
    rep(k, 0, n) {
        rep(i, 0, n) {
            rep(j, 0, n) {
                d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);
            }
        }
    }

    int q;
    cin >> q;
    rep(i, 0, q) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        if (d2[s][t] == INF) cout << -1 << endl;
        else cout << d2[s][t] - 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 1920
import java.util.Scanner;

public class Main {
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		scan.useDelimiter("\\n");
		String str = scan.next();
		char[] ans = str.toCharArray();
		
		for(int i = 0;i < ans.length;i++)
		{
			if(Character.isLowerCase(ans[i]))
			{
				ans[i] = Character.toUpperCase(ans[i]);
			}else if(Character.isUpperCase(ans[i])){
				ans[i] = Character.toLowerCase(ans[i]);
			}
		}
		
		for(int i = 0;i < ans.length;i++)
		{
			System.out.print(ans[i]);
		}
		System.out.println("");
	}
}

Measured memory_bytes: 17284
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (const string& e_) { return "\"" + e_ + "\""; }
string to_string (char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string (bool e_) { return e_ ? "true" : "false"; }
template <typename T> string to_string (T e_) {
	string s_ = "[ ";
	for (const auto& x_ : e_) s_ += to_string(x_) + " ";
	return s_ + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e_) {
	return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	int n;
	cin >> n;
	string s, t;
	map <string, int> m;
	ll a[26], ans = 0;
	memset(a, 0, sizeof a);

	for(int i = 0; i < n; i++){
		t = "";

		cin >> s;
		for(int j = 0; j < 10; j++) a[s[j] - 'a']++;
		for(int j = 0; j < 26; j++){
			while(a[j]){
				t.push_back('a'+j);
				a[j]--;
			}
		}
		m[t]++;
	}
	map<string , int> :: iterator it;
	for(it = m.begin(); it != m.end(); it++){
		ll x = (it->second);
		ans += (x * (x - 1))/2;
	}
	cout << ans;
}

Measured memory_bytes: 12800
# include<stdio.h>

int main(void){
	int N, K ,X ,Y;
	scanf("%d" ,&N);
	scanf("%d" ,&K);
	scanf("%d" ,&X);
	scanf("%d" ,&Y);
	if(N<K+1){
		printf("%d\n",X*N);
	}
	else{
		printf("%d\n",X*K+Y*(N-K));
	}
	return 0;
}


Measured memory_bytes: 128
N = int(input())

c = [[0 for _ in range(10)] for __ in range(10)]
for x in range(1, N+1):
    check = str(x)
    it = int(check[0])
    jt = int(check[-1])
    c[it][jt] += 1

ans = 0
for i in range(0,10):
    for j in range(0,10):
        ans += c[i][j] * c[j][i]

print(ans)


Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

# バイナリインデックス木
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):
        s = 0
        while 0 < i:
            s += self.tree[i]
            s %= MOD
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# エントリーポイント
def main():
    N, T = input(int, int)
    A = input([int, N])

    ans = 0
    for n in range(N - 1):
        ans += min(T, A[n + 1] - A[n])
    print(ans + T)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


Measured memory_bytes: 26044
// Problem : A - Air Conditioner
// Contest : AtCoder - AtCoder Beginner Contest 174
// URL : https://atcoder.jp/contests/abc174/tasks/abc174_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// Delete the dynamically allocated memory

#include<bits/stdc++.h>
using namespace std;
 
#define ff              first
#define ss              second
#define pb              push_back
#define pr              pair<long long,long long>
#define mp(a,b)         make_pair(a,b)
#define vr              vector<long long>
#define mod1            1000000007
#define mod2            998244353
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define fill(a,b)       memset(a, b, sizeof(a))
#define mk(arr,n,type)  type *arr=new type[n];
#define ll              long long
#define ld	            long double
#define w(x)            int x; cin>>x; while(x--)
ll power(ll base, ll exp) {
    ll res=1;
    while(exp>0) {
       if(exp%2==1) res=(res*base);
       base=(base*base);
       exp/=2;
    }
    return res;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll x;
	cin>>x;
	if(x>=30){
		cout<<"Yes"<<"\n";
	}else{
		cout<<"No"<<"\n";
	}
	return 0;
	}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
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;
            break;
        }
    }
}

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) for(int i = 0 ; i < n ; ++i)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int n, ans = 0;

void solve(lint now, bool shichi, bool go, bool san){
    if(now > n){
        return;
    }
    if(shichi && go && san){
        ++ans;
    }
    solve(now * 10LL + 7LL, true, go, san);
    solve(now * 10LL + 5LL, shichi, true, san);
    solve(now * 10LL + 3LL, shichi, go, true);
    return;
}

int main(){
    cin >> n;
    solve(0, false, false, false);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <stdio.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 998244353
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 
string S;
int dp[202020][2][3][3]; 

set<string> se;

void dfs(string ss) {
  se.insert(ss);
  REP(i,ss.length()-1) if (ss[i] != ss[i+1]) {
    string t = ss;
    if ((ss[i] == 'b' && ss[i+1] == 'c') || (ss[i] == 'c' && ss[i+1] == 'b')) t[i] = t[i+1] = 'a';
    else if ((ss[i] == 'a' && ss[i+1] == 'c') || (ss[i] == 'c' && ss[i+1] == 'a')) t[i] = t[i+1] = 'b';
    else if ((ss[i] == 'a' && ss[i+1] == 'b') || (ss[i] == 'b' && ss[i+1] == 'a')) t[i] = t[i+1] = 'c';
    if (se.find(t) == se.end()) {
      dfs(t);
    }
  }
}

int brute(string ss) {
  dfs(ss);
  return se.size();
}

signed main() {
  cin >> S;
  int N = S.length();

  // if (N <= 7) assert(false);

  if (N <= 7) {
    cout << brute(S) % MOD << endl;
    return 0;
  }

  bool same = true;
  REP(i,N-1) if (S[i] != S[i+1]) {
    same = false;
    break;
  }
  if (same) {
    cout << 1 << endl;
    return 0;
  }

  dp[1][0][0][0] = 1;
  dp[1][0][1][1] = 1;
  dp[1][0][2][2] = 1;
  for (int i=1; i<=N-1; i++) {
    REP(C,2) {
      REP(last,3) {
        REP(mod,3) {
          // if (dp[i][C][last][mod] != 0) {
          //   REP(j,3) {
          //     dp[i+1][C|(last==j)][j][(mod+j)%3] += dp[i][C][last][mod];
          //     dp[i+1][C|(last==j)][j][(mod+j)%3] %= MOD;
          //   }
          // }
          REP(j,3) {
            dp[i+1][C|(last==j)][j][(mod+j)%3] += dp[i][C][last][mod];
            dp[i+1][C|(last==j)][j][(mod+j)%3] %= MOD;
          }
        }
      }
    }
  }

  int mod = 0;
  REP(i,N) mod += S[i] - 'a';
  mod %= 3;

  int ans = 1;
  ans += dp[N][1][0][mod] + dp[N][1][1][mod] + dp[N][1][2][mod];
  REP(i,N-1) if (S[i] == S[i+1]) {
    ans--;
    break;
  }
  cout << ans % MOD << endl;
}

Measured memory_bytes: 28676
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
    int a,b,c;
    string res="Yes";
    cin >> a >> b >> c;
    if(c>a+b) res="No";
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;typedef vector<ll> vll;
#define fill(a) memset(a, 0, sizeof (a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define each(it,s) for(auto it = s.begin(); it != s.end(); ++it)
#define unq(v) sort(all(v)),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define getpos(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const int INF = 1e9 + 10;
const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int maxn = 2000100;

int main(){
        _ios;

        int k, s; cin >> k >> s;
        int cnt = 0;
        for(int i = 0; i<=k; i++){
            for(int j = 0; j<=k; j++){
                //if(i==j)continue;
                if((s-i-j)<=k and (s-i-j)>=0)cnt++;
            }
        }
        cout<<cnt<<endl;



return 0;
}








Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int a, b, c, d, e, k;

  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d;
  cin >> e;
  cin >> k;

  if (e - a > k) {
    cout << ":(" << '\n';
  } else {
    cout << "Yay!" << '\n';
  }

  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	void doIt(){
		Scanner sc = new Scanner(System.in);
		Player[] p = new Player[8];
		Player[] pp = new Player[6];

		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 8; j++) {
				p[j] = new Player(sc.nextInt(), sc.next());
			}
			Arrays.sort(p);
			for(int j = 0; j < 2; j++) {
				System.out.println(p[j].num + " " + p[j].time);
				pp[i * 2 + j] = p[j + 2];
			}
		}
		Arrays.sort(pp);
		for(int i = 0; i < 2; i++){
			System.out.println(pp[i].num + " " + pp[i].time);
		}
	}

	class Player implements Comparable<Player>{
		int num;
		String time;
		Player(int num, String time){
			this.num = num;
			this.time = time;
		}
		@Override
		public int compareTo(Player p) {
			return time.compareTo(p.time);
		}
	}

	public static void main(String[] args){
		new Main().doIt();
	}

}

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

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
using ll = long long;
using ull = unsigned long long;
constexpr int MOD = 1000000007;

int mod(int x){
	return x % MOD;
}

int main(void)
{
    IOS
    int n,k; cin >> n >> k;
    int ml = (n-1)*(n-2) / 2;
    if (ml < k) {
        cout << -1 << endl;
        return 0;
    } else {
        int l = ml-k;
        cout << n-1 + l << endl;
        REP(i,n-1) cout << 1 <<" "<< i+2 << endl;

        int i = 2;
        int j = 3;
        while(l > 0) {
            cout << i <<" "<< j << endl;
            j++;
            if (j > n) {
                i++;
                j = i+1;
            } 
            l--;
        }
    }


    return 0;
}


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

int main(void){

  char S[100],T[100];

  scanf("%s", S);
  scanf("%s", T);

  int len = strlen(S);
  char top;
  int j=0,flag=0;

  for(int i=0; i<len; i++){
    j = 0;
    flag = 0;
    while(j<len && flag==0){
      if(S[(j+i)%len]!=T[j]){
        flag++;
      }
      j++;
    }
    if(flag==0){
      printf("Yes\n");
      return 0;
    }
  }

  printf("No\n");
  return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int
main(void) 
{
  int a[10000];
  int i;
  for (i = 1; i <= 10000; i++) {
    scanf("%d", &a[i]);
    if (a[i] == 0) {
      exit(1);
    }
    printf("Case %d: %d\n", i, a[i]);
  }
  
  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
long long n,k;
long long w[109],s[109];
long long dp[109][100009];
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>w[i]>>s[i];
	}
	for(int i=0;i<n;i++){
		for(int j=1;j<=100009;j++){
			dp[i][j]=10000000000009;
		}
	}
	dp[0][s[0]]=w[0];
	for(int i=1;i<n;i++){
		for(int j=0;j<=100009;j++){
			if(j-s[i]<0){
				dp[i][j]=dp[i-1][j];
				continue;
			}
			dp[i][j]=min(dp[i-1][j],dp[i-1][j-s[i]]+w[i]);
		}
	}
	int mx=0;
/*	for(int i=0;i<n;i++){
		for(int j=0;j<=21;j++){
			if(dp[i][j]>1000) cout<<-1<<" ";
			else cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	for(int i=0;i<=100008;i++){
		if(dp[n-1][i]>k) continue;
		mx=max(mx,i);
	}
	cout<<mx<<endl;
}


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

int main() {
  long long N,a,b;
  cin >>N;
  vector<pair<long long,long long>>f(N);
 for(int i=0;i<N;i++){
   cin>>a>>b;
   f[i]=make_pair(b,a);
 }
  sort(f.begin(),f.end());
  a=0;
  b=0;
  for(int i=0;i<N;i++){
    a+=f[i].second;
    b=f[i].first;
    if(a>b){
      cout<<"No"<<endl;
    return 0;
    }
  }
  cout<<"Yes"<<endl;
}

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

int main() {
  int n;

  cin >> n;

  int d1 = n % 10;
  n /= 10;
  
  int d2 = n % 10;
  n /= 10;
   
  int d3 = n % 10;
  n /= 10;
  
  int d4 = n % 10;
  n /= 10;
  
  bool match = (d1 == d2 && d2 == d3)  
    || (d2 == d3 && d3 == d4);

  if (match) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
#include <assert.h>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    ll n, k;
    cin >> n >> k;
    int a = n/2, b = 2*n - 1, c = 3*n - 1;
    vector<array<ll, 3>> t(n);
    for (int i = 0; i < n; ++i) {
        if (a + k + b + k > c + k) {
            puts("-1");
            return 0;
        }
        t[i] = {a + k, b + k, c + k};
        --c;
        if (a < b-3) {
            ++a; b -= 2;
        } else {
            a = 0;
            b = 2*n-2;
        }
    }
    for (auto &&j : t) {
        printf("%lld %lld %lld\n", j[0], j[1], j[2]);
    }
    return 0;
}

Measured memory_bytes: 4608
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		FastScanner fs = new FastScanner();
		int ans = 15;
		for (int i = 0; i < 5; i++) {
			ans -= fs.nextInt();
		}
		System.out.println(ans);
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 32436
#include <stdio.h>
#include <vector>
#include <utility>

int t1,t2,t3;

int n;
std::vector<int> g[100005];
std::vector<std::pair<int,int> > gw[100005];
bool vis[100005];
int sz[100005];
int prefer[100005];

void unvis(int u)
{
    vis[u]=0;
    for (int v:g[u]) {
        if (vis[v]) unvis(v);
    }
}

void getprefer(int u)
{
    vis[u]=sz[u]=1;
    prefer[u]=0;
    for (int v:g[u]) {
        if (vis[v]) continue;
        getprefer(v);
        sz[u]+=sz[v];
        if (sz[prefer[u]]<sz[v]) {
            prefer[u]=v;
        }
    }
}

long long getans(int u)
{
    vis[u]=sz[u]=1;
    long long out=0;
    for (std::pair<int,int> p:gw[u]) {
        if (vis[p.first]) continue;
        out+=getans(p.first);
        out+=p.second*2LL*sz[p.first];
        sz[u]+=sz[p.first];
    }
    return out;
}

int c1,c2;

long long ans=0x3f3f3f3f3f3f3f3f;

int main()
{
    #ifdef NOT_DMOJ
    freopen("data.txt","r",stdin);
    #endif // NOT_DMOJ
    scanf("%d",&n);
    for (int i=1; i<n; i++) {
        scanf("%d%d%d",&t1,&t2,&t3);
        g[t1].push_back(t2);
        g[t2].push_back(t1);
        gw[t1].push_back({t2,t3});
        gw[t2].push_back({t1,t3});
    }
    // get centroids
    getprefer(1);
    c1=1;
    c2=-1;
    while (sz[prefer[c1]]*2>=n) {
        bool other=1;
        for (int v:g[c1]) {
            if (sz[c1]>sz[v] && sz[v]*2>n) {
                other=0;
                break;
            }
        }
        if (other) c2=c1;
        c1=prefer[c1];
    }
    // do centroids
    if (c1>0) {
        unvis(c1);
        long long t=getans(c1);
        long long t2=0x3f3f3f3f3f3f3f3f;
        bool other=0;   // is there a sz/2 subtree?
        for (int u:g[c1]) {
            if (sz[u]*2==sz[c1]) other=1;
        }
        for (std::pair<int,int> p:gw[c1]) {
            if (other && sz[p.first]*2!=n) continue;
            if (t2>p.second) {
                //printf("%d - %d can do %lld-%d\n",c1,p.first,t,p.second);
                t2=p.second;
            }
        }
        t-=t2;
        if (ans>t) {
            ans=t;
        }
    }
    if (c2>0) {
        unvis(c2);
        long long t=getans(c2);
        long long t2=0x3f3f3f3f3f3f3f3f;
        bool other=0;   // is there a sz/2 subtree?
        for (int u:g[c2]) {
            if (sz[u]*2==n) other=1;
        }
        for (std::pair<int,int> p:gw[c2]) {
            if (other && sz[p.first]*2!=n) continue;
            if (t2>p.second) {
                //printf("%d - %d can do %lld-%d\n",c2,p.first,t,p.second);
                t2=p.second;
            }
        }
        t-=t2;
        if (ans>t) {
            ans=t;
        }
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 16128
s = input()
n = list(s)
b = list(set(n))
m = []
a=0
d=0
if(len(b)!=2):
	print("No")
else:
	for i in range(0,4):
	    if n[i]==b[0]:
	        a+=1
	    elif n[i]==b[1]:
	        d+=1
if d==2 and a==2:
	print('Yes')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  long long h,w;
  cin >> h >> w;
  char c[h][w];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> c[i][j];
    }
  }
  long long dp[h][w]={};
  if(c[0][0]=='#'){
    dp[0][0]=1;
  }
  for(int i=0;i<h-1;i++){
    dp[i+1][0] = dp[i][0]+(c[i][0]=='.' and c[i+1][0]=='#');
  }
  for(int i=0;i<w-1;i++){
    dp[0][i+1] = dp[0][i]+(c[0][i]=='.' and c[0][i+1]=='#');
  }
  for(int i=1;i<h;i++){
    for(int j=0;j<w-1;j++){
      dp[i][j+1] = min(dp[i][j]+(c[i][j]=='.' and c[i][j+1]=='#'), dp[i-1][j+1]+(c[i-1][j+1]=='.' and c[i][j+1]=='#'));
    }
  }
  cout << dp[h-1][w-1] << endl;
  return 0;
}


Measured memory_bytes: 384
#!/usr/bin/env python3
from functools import reduce

mod = 10**9 + 7


def cmb(n, r, m):
    mul = lambda a,b: a*b%m
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over * pow(under, mod - 2, mod)


n, a, b = map(int, input().split())
print((pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)) % mod)


Measured memory_bytes: 9624
n, k = gets.split.map{|v|
  v.to_i
}

if k == 0 then
  puts n * n
  exit
end

ans = 0
for b in (k+1)..n
  div, mod = n.divmod(b)
#  printf "n, b: %d %d\n", n, b
#  printf "div, mod: %d %d\n", div, mod
  
#  puts div * (n - k)
#  puts [0, mod - k + 1].max
  ans += div * (b - k) + [0, mod - k + 1].max
end
puts ans


Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
	int N, A, B;
	string Aname = "Alice", Bname = "Borys";
	cin >> N >> A >> B;
	if (A > B) {
		swap(A, B);
		swap(Aname, Bname);
	}
	if ((B - A) % 2 == 0) {
		cout << Aname << endl;
	}
	else {
		cout << Bname << endl;
	}
	return 0;
}

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

using namespace std;

const int mod = 1e9 + 7;

int main(){
  int N, K;
  cin >> N >> K;
  
  long long ans = 0;
  for(int k = K; k <= N + 1; k++){
    ans += (long long)k * (N - k + 1) + 1;
    ans %= mod;
  }
  
  cout << ans << endl;
  
  return 0;
}



Measured memory_bytes: 3632
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())
  
n=i()
k=i()
x=intl()
a=0
for i in range(n):
	a+=min(2*x[i],2*abs(x[i]-k))
print(a)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define rep(i, n) for(int i = 0; i < n; i++)
#define repp(i, n) for(int i = 1; i <= n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define riverse(v) reverse((v).begin(), (v).end())
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
const ll MOD = 1e9+7;
vi alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m',
               'n','o','p','q','r','s','t','u','v','w','x','y','z'};

int main() {
    int N, Q;
    cin >> N >> Q;
    vvi g(N + 1);
    rep(i, N-1) {
        int x;
        cin >> x;
        int y;
        cin >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    vi p(Q);
    vi x(Q);
    rep(i, Q) {
        cin >> p[i];
        cin >> x[i];
    }
    vll counter(N + 1);
    rep(i, Q)counter[p[i]] += x[i];
    queue<int> q;
    q.push(1);
    vb visited(N + 1, false);
    visited[1] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : g[v]) {
            if (!visited[u]) {
                counter[u] += counter[v];
                visited[u] = true;
                q.push(u);
            }
        }
    }
    for (int i = 1; i <= N; i++) cout << counter[i] << " ";
}

Measured memory_bytes: 17908
import sys
N = int(input())

if N < 10:
	print(N)
	sys.exit()

if N < 100:
	cnt = 0
	for i in range(1,N+1):
		if i < 10:
			cnt += 1
			if (i*10)+i <= N:
				cnt += 1
		else:
			s = str(i)
			sa,sb = s[0],s[-1]
			if sb == '0':
				continue
			ss = sb+sa
			if int(ss) <= N:
				cnt += 1
			if sa == sb:
				cnt += 1
	print(cnt)
	sys.exit()



k = len(str(N))
auto = 0
for i in range(k-1):
	auto += 10**i

auto2 = (auto-10**(k-2)) + (int(str(N)[1:]) // 10)
auto3 = auto - 10**(k-2)
m = str(N)[0]
mm = str(N)[-1]
def solve(a,b):
	ans = 0
	if a == b:
		ans += 1
	if a < m:
		return ans + auto
	elif a == m:
		if b <= mm:
			return ans + auto2 + 1
		else:
			return ans + auto2
	else:
		return ans + auto3

cnt = 0
for i in range(1,N+1):
	s = str(i)
	if s[-1] == '0':
		continue
	if i < 10:
		cnt += solve(s,s)
	else:
		sa,sb = s[0],s[-1]
		cnt += solve(sb,sa)

print(cnt)

Measured memory_bytes: 3064
def solve():
    rec = [5] * 1000000
    rec[0] = 0
    
    tetra_num = [i * (i + 1) * (i + 2) // 6 for i in range(1, 181)]
    
    for i, a in enumerate(tetra_num):
        for j, b in enumerate(tetra_num[i:], start=i):
            if a + b >= 1000000:
                break
            for c in tetra_num[j:]:
                if a + b + c >= 1000000:
                    break
                rec[a + b + c] = 3
    
    for i, a in enumerate(tetra_num, start=0):
        for b in tetra_num[i:]:
            if a + b >= 1000000:
                break
            rec[a + b] = 2
    
    for n in tetra_num:
        rec[n] = 1
    
    for i, n in enumerate(rec[1:], start=1):
        if n == 3:
            for t in tetra_num:
                if i + t >= 1000000:
                    break
                if rec[i + t] == 5:
                    rec[i + t] = 4
    
    odd_rec = [1000000] * 1000000
    odd_rec[0] = 0
    
    odd_tetra_num = tetra_num[::4]
    
    for odd_t in odd_tetra_num:
        for i, tpl in enumerate(zip(odd_rec[odd_t:], odd_rec), start=odd_t):
            a, b = tpl
            b += 1
            if b < a:
                odd_rec[i] = b
    
    import sys
    file_input = sys.stdin
    n = int(file_input.readline())
    while n:
        print(rec[n], odd_rec[n])
        n = int(file_input.readline())

solve()


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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

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

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, A[100010];
  cin >> N;
  rep(i, N) cin >> A[i];
  sort(A, A+N);
  int sum[100010];
  sum[0] = 0;
  rep(i, N) sum[i+1] = sum[i] + A[i];
  bool ok[100010] = {};
  for(int i = N; i >= 1; i--) {
    if(2*sum[i] >= A[N-1] || 2*sum[i] >= A[i] && ok[i+1]) ok[i] = true;
  }
  cout << count(ok, ok+N+1, true) << endl;

  return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

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





return 0;
}


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

using namespace std;

//ゼロになる時が例外

int main(){
    int n;
    cin >> n;
    vector<int> A;
    string S;
    cin >> S;
    for (const auto &s: S)
        A.push_back(s - '0');
    int cnt = 0;
    for (const auto &a: A){
        if (a == 1)
            cnt++;
    }

    vector<int> D(n);
    if (cnt == 1){
        for (int i = 0; i < n; i++){
            if (A[i] == 1)
                cout << 0 << endl;
            else if (i == n - 1)
                cout << 2 << endl;
            else
                cout << 1 << endl;
        }
        return 0;
    }
    if (cnt == 0){
        for (int i = 0; i < n; i++){
            cout << 1 << endl;
        }
        return 0;
    }

    vector<vector<int>> B(3, vector<int>(n));
    for (int j = -1; j < 2; j++){
        int m = 1;    
        for (int i = 0; i < n; i++){
            B[j + 1][n - i - 1] = m;
            m *= 2;
            m %= (cnt + j);
        }
    }

    vector<int> C(3);
    for (int j = 0; j <= 2; j++){
        for (int i = 0; i < n; i++){
            if (A[i] == 1){
                C[j] += B[j][i];
                C[j] %= (cnt + j - 1);
            }
        }
    }


    for (int i = 0; i < n; i++){
        if (A[i] == 1)
            D[i] = (C[0] - B[0][i] + cnt - 1) % (cnt - 1);
        else
            D[i] = (C[2] + B[2][i]) % (cnt + 1);
    }

    map<int, int> ans;
    auto f = [&](int d, auto self) -> int{
        if (ans.count(d))
            return ans[d];
        if (d == 0)
            return 0;
        return ans[d] = self(d % __builtin_popcount(d), self) + 1;
    };

    for (int i = 0; i < n; i++){
        f(D[i], f);
    }

    for (int i = 0; i < n; i++)
        cout << ans[D[i]] + 1 << endl;
}

Measured memory_bytes: 8232
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;

int main(){
  ll n;
  cin >> n;
  vector<ll>a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  ll count=0;
  for(int i=0; i<n; i++){
    ll add=a[i]/2;
    if(a[i]%2 && i<n-1){
      if(a[i+1]>0){
        a[i+1]--;
        add++;
      }
    }
    count+=add;
  }
  
  
  cout << count << endl;
  
}
  
  
  


Measured memory_bytes: 1024