akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

//typedefリスト
typedef vector<long long int> vint;
typedef vector<string> vstr;
typedef long long int llint;



int main(void) {
	int n, odnum, evnum, ans1, ans2;
	ans1 = 100001;
	ans2 = 100001;
	int oddmax = 0;
	int evenmax = 0;
	cin >> n;
	map<int, int>oddmp;
	map<int, int>evenmp;
	vint v(n), odd, even;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		if (i % 2 == 0)odd.push_back(v[i]);
		else even.push_back(v[i]);
	}
	for (int i = 0; i != odd.size(); i++) {
		oddmp[odd[i]]++;
		oddmax = max(oddmax, oddmp[odd[i]]);
		if (oddmax == oddmp[odd[i]])odnum = odd[i];
	}
	for (int i = 0; i != even.size(); i++) {
		evenmp[even[i]]++;
		evenmax = max(evenmax, evenmp[even[i]]);
		if (evenmax == evenmp[even[i]])evnum = even[i];
	}

	if (evnum == odnum) {
		
		if (oddmp.size() != 1 && evenmp.size() != 1) {
			int oddmax2 = 0;
			oddmp.clear();
			evenmp.clear();
			for (int i = 0; i != odd.size(); i++) {
				if (odd[i] != evnum) {
					oddmp[odd[i]]++;
					oddmax2 = max(oddmax2, oddmp[odd[i]]);
					}
			}
			ans1 = (odd.size() - oddmax2) + (even.size() - evenmax);
			int evenmax = 0;
			for (int i = 0; i != even.size(); i++) {
				if (even[i] != odnum) {
					evenmp[even[i]]++;
					evenmax = max(evenmax, evenmp[even[i]]);
				}
			}
			ans2 = (odd.size() - oddmax) + (even.size() - evenmax);
		}
		else if (oddmp.size() == 1 && evenmp.size() != 1) {
			int evenmax = 0;
			oddmp.clear();
			evenmp.clear();
			for (int i = 0; i != even.size(); i++) {
				if (even[i] != odnum) {
					evenmp[even[i]]++;
					evenmax = max(evenmax, evenmp[even[i]]);
				}
			}
			ans2 = (odd.size() - oddmax) + (even.size() - evenmax);
		}
		else if (evenmp.size() == 1 && oddmp.size() != 1) {
			int oddmax = 0;
			oddmp.clear();
			evenmp.clear();
			for (int i = 0; i != odd.size(); i++) {
				if (odd[i] != evnum) {
					oddmp[odd[i]]++;
					oddmax = max(oddmax, oddmp[odd[i]]);
					
				}
			}
			ans1 = (odd.size() - oddmax) + (even.size() - evenmax);
		}
		else if (evenmp.size() == 1 && oddmp.size() == 1) {
			ans1 = min(odd.size(), even.size());
		}
	}
	else ans1 = (odd.size() - oddmax) + (even.size() - evenmax);
	cout << min(ans1, ans2) << endl;
}


Measured memory_bytes: 6516
#include <bits/stdc++.h>
using namespace std;
double calc(int a, int b)
{
    return sqrt(pow(a, 2) + pow(b, 2));
}
int main()
{
    int n, d;
    cin >> n >> d;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        ans += (calc(a, b) <= d ? 1 : 0);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3668
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        // String s = sc.next();
        // int[] a = new int[n];
        // for (int i = 0; i < n; i++) {
        // a[i] = Integer.parseInt(sc.next());
        // }
        long ans = 0;
        for (int i = 1; i <= n; i++)
            if (i % 3 != 0) {
                if (i % 5 != 0) {
                    ans += i;

                }
            }

        System.out.println(ans);
        sc.close();
    }
}

Measured memory_bytes: 35696
N = gets.to_i
A = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)

ans = 0

B.each_with_index do |b, i|
  current = B[i]

  if B[i] >= A[i]
    ans += A[i]
  else
    ans += current
  end

  current -= A[i]

  if current > 0
    if current >= A[i + 1]
      ans += A[i + 1]
      A[i + 1] = 0
    else
      ans += current
      A[i + 1] -= current
    end
  end

  # p "ans #{ans} current #{current}"
end

puts ans


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


int main(){
  	int n, q;
  	cin >> n >> q;
	string s;
  	cin >> s;
		
  	int mem[n];
  	mem[0] = 0;

  	for(int i=1; i<n; i++){
      	mem[i] = mem[i-1];
	    if(s[i-1] == 'A' && s[i] == 'C'){
        	mem[i] += 1;
        }
    }
  
	for(int i=0; i<q; i++){
    	int l, r;
      	cin >> l >> r;
      
      	int ans = mem[r-1] - mem[l-1];

      	cout << ans << endl;
    }

	return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>
int main(void)
{
	int j,i,n,a,b,c,d,t[100],r[100];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		t[i]=0;
		r[i]=1;
	}
	for(i=0;i<n*(n-1)/2;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if(c>d){
			t[a-1]+=3;
		}else if(c==d){
			t[a-1]++;
			t[b-1]++;
		}else{
			t[b-1]+=3;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(t[i]<t[j]){
				r[i]++;
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%d\n",r[i]);
	}
    return 0;
}

Measured memory_bytes: 2688
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n, k, q] <- getIntList
    as <- replicateM q getInt
    mapM_ putStrLn $ solve n k q as

solve n k q as = map (yn . flip (-) (q-k+1) . length) . group . sort $ as ++ [1..n]
    where yn x | x > 0 = "Yes"
               | otherwise = "No"

Measured memory_bytes: 36220
n, *A = map(int, open(0).read().split())

ans = s = r = 0
for l in range(n):
    while r < n:
        if s & A[r] != 0:
            break
        s += A[r]
        r += 1
    s -= A[l]
    ans += r-l
print(ans)

Measured memory_bytes: 91172
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  long long N,a[5];cin>>N;
  for(int i=0;i<5;++i)cin>>a[i];
  sort(a,a+5);
  cout<<4+(N+a[0]-1)/a[0]<<endl;
  return 0;
}


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

const int maxn = 1e5, mod = 1e9 + 7;
int n, m, a[maxn + 3], b[maxn + 3], N, M, L[maxn + 3], R[maxn + 3], o[maxn + 3], t[maxn + 3], bit[maxn + 3];

bool comp(int i, int j) {
	return L[i] == L[j] ? R[i] > R[j] : L[i] < L[j];
}

inline int func(int x) {
	return x < mod ? x : x - mod;
}

void add(int x, int y) {
	for (int i = x; i <= maxn; i += i & -i) {
		bit[i] = func(bit[i] + y);
	}
}

int query(int x) {
	int y = 0;
	for (int i = x; i; i ^= i & -i) {
		y = func(y + bit[i]);
	}
	return y;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; i++) {
		int l = lower_bound(b + 1, b + m + 1, a[i]) - (b + 1), r = l + 1;
		if (l == 0 || r == m + 1) continue;
		++N, L[N] = a[i] - b[l], R[N] = b[r] - a[i];
	}
	for (int i = 1; i <= N; i++) {
		o[i] = i;
	}
	sort(o + 1, o + N + 1, comp);
	for (int i = 1; i <= N; i++) {
		t[i] = L[i];
	}
	for (int i = 1; i <= N; i++) {
		L[i] = t[o[i]];
	}
	for (int i = 1; i <= N; i++) {
		t[i] = R[i];
	}
	for (int i = 1; i <= N; i++) {
		R[i] = t[o[i]];
	}
	for (int i = 1; i <= N; i++) {
		t[i] = L[i];
	}
	sort(t + 1, t + N + 1);
	M = unique(t + 1, t + N + 1) - (t + 1);
	for (int i = 1; i <= N; i++) {
		L[i] = lower_bound(t + 1, t + M + 1, L[i]) - t;
	}
	for (int i = 1; i <= N; i++) {
		t[i] = R[i];
	}
	sort(t + 1, t + N + 1);
	M = unique(t + 1, t + N + 1) - (t + 1);
	for (int i = 1; i <= N; i++) {
		R[i] = lower_bound(t + 1, t + M + 1, R[i]) - t;
	}
	int ans = 1;
	for (int i = 1; i <= N; i++) {
		if (L[i] == L[i - 1] && R[i] == R[i - 1]) continue;
		int x = query(R[i] - 1) + 1;
		ans = func(ans + x);
		add(R[i], x);
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2688
n = int(input())
a, b = map(int, input().split())
l = [int(x) for x in input().split()]

aa, ab, bb = [], [], []

for x in l:
  if x <= a:
    aa.append(x)
  elif a + 1 <= x and x <= b:
    ab.append(x)
  else:
    bb.append(x)

print(min(map(len, [aa, ab, bb])))

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

#define MAX_NUM (1000000000 + 7)

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

static const u32 A[] = {1, 1, 1, 2, 1, 2, 1, 5,  2, 2, 1, 5, 1, 2, 1, 14,
                        1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main() {
  cout << setprecision(15);
  u32 K;
  cin >> K;
  cout << A[K - 1] << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  ll h;
  cin >> h;
  ll pw=0;
  while(h>1){
    h/=2;
    pw++;
  }
  ll ans=1;
  rep(i,pw+1){
    ans *= 2;
  }
  cout << ans -1 << endl;

  
  return 0;
    

}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    val a = scanner.next().toCharArray()
    var first = a[0]
    var second = 'A'
    var firstC = 0
    var secondC = 0
    var check = false
    for(i in a){
        if(i != first && !check) {
            second = i
            check = true
        }
        if(i == first) firstC++
        else if(i == second) secondC++
    }
    if(firstC === 2 && secondC === 2) println("Yes")
    else println("No")
}

Measured memory_bytes: 29476
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define vv vector<lli>
#define vp vector<pair<lli,lli>>
#define vpp vector<pair<lli,pair<lli,lli>>>
#define lims(w) (w).begin(),(w).end()
#define rlims(w) (w).rbegin(),(w).rend()
#define pb push_back
#define mp make_pair
#define f(i,a,b) for(lli i=a;i<b;i++)
#define ff first
#define ss second
#define sz(a) (lli)(a.size())
lli inf = (1e18 + 2);

int main()
{
	lli n;
	cin>>n;
	lli l[n+1];
	lli ans = 0, sum;
	vv v;

	f(i,0,n)
		cin>>l[i];

	f(i,0,n)
	{
		f(j,i+1,n)
		{
			f(k,j+1,n)
			{
				v.clear();
				v.pb(l[i]);v.pb(l[j]);v.pb(l[k]);
				sort(lims(v));
				sum = v[0] + v[1];

				if(v[0] != v[1] && v[1] != v[2] && sum > v[2])						ans++;
			}
		}
	}

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


Measured memory_bytes: 3628
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define LL long long
#define pii pair<int,int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define rep(i,a,b) for(int i = (a) ; i <= (b) ; i++)
#define per(i,a,b) for(int i = (a) ; i >= (b) ; i--)
#define mem(a) memset(a,0,sizeof(a))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define fast_io ios::sync_with_stdio(false)

const int INF = 1e9;
const LL mod = 1e9 + 7;
const int maxn = 2e5 + 7;

int main() {
    LL n,k;
    while(~scanf("%lld%lld",&n,&k)) {
        LL ans = 0;
        for(LL i = k ; i <= n + 1 ; i++) {
            LL res = ((n - i + 1) * i + 1) % mod;
            ans = ((ans% mod) + (res % mod)) % mod;
        }
        plld(ans);
    }
    return 0;
}


Measured memory_bytes: 3824
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


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

    ll N, D, A; cin >> N >> D >> A;
    vector<pair<ll, ll>> xh(N);
    rep(i, N) {
        ll x, h; cin >> x >> h;
        xh[i] = make_pair(x, h);
    }
    sort(xh.begin(), xh.end());

    ll ans = 0; ll cum_damage = 0;
    queue<pair<ll, ll>> qu;
    rep(i, N) {
        while(qu.size() && qu.front().first<xh[i].first) { cum_damage-=qu.front().second; qu.pop(); }
        ll nowh = xh[i].second-cum_damage;
        if (nowh<=0) continue;
        
        ans += (nowh + A-1) / A;
        qu.push(make_pair(xh[i].first+2*D, (nowh + A-1)/A * A));
        cum_damage += (nowh + A-1)/A * A;
    }
    cout << ans << endl;
    
    return 0;
}




Measured memory_bytes: 4992
N = input()
INF = 10 ** 9
N = N[::-1] + '0'
dp = [[INF for _ in range(2)] for _ in range(len(N) + 1)]
dp[0][0] = 0

for i in range(len(N)):
    for j in range(2):
        x = int(N[i])
        x += j
        for k in range(10):
            nexti = i + 1
            nextj = 0
            b = k - x
            if b < 0:
                nextj = 1
                b += 10
            dp[nexti][nextj] = min(dp[nexti][nextj], dp[i][j] + k + b)
print(dp[len(N)][0])

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

using namespace std;
using namespace std::chrono;

#define rep(i,a,b) for(int i = a;i<(b);++i)
#define trav(a,v) for(auto& a : v)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

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

const ll big = 1000000007ll;
const ll big2 = 1000000009ll;
ll n,m,k,q,h,T;

vector<ll> A;

ll MI[2003] = {0};
ll MA[2003] = {0};
ll DP[2003][2003][2] = {0};

ll mi = big;
ll ma = -big;

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,d;

    cin >> n >> a >> b;
    A.push_back(a);
    A.push_back(b);
    for(ll c1 = 0; c1 < n; c1++){
        cin >> a;
        A.push_back(a);
    }
    n += 2;

    for(ll c1 = 0; c1 < n-1; c1++){
        MI[c1] = big;
        MA[c1] = -big;
    }

    for(ll c1 = n-1; c1 >= 0; c1--){
        for(ll c2 = n-1; c2 >= 0; c2--){
                if(c1 == c2)continue;
                ll c3 = 0;
                if(c1 > c2)c3 = 1;

                //cout << ma << " " << mi << "\n";

                if(c3 == 0){
                    if(c2 == n-1){
                        DP[c1][c2][c3] = abs(A[c1]-A[c2]);
                    }
                    else{
                        DP[c1][c2][c3] = MA[c2];
                    }
                    MI[c1] = min(MI[c1],DP[c1][c2][c3]);
                    //MA[c2] = max(MA[c2],DP[c1][c2][c3]);
                }
                else{
                    if(c1 == n-1){
                        DP[c1][c2][c3] = abs(A[c1]-A[c2]);
                    }
                    else{
                        DP[c1][c2][c3] = MI[c1];
                    }
                    //MI[c1] = min(MI[c1],DP[c1][c2][c3]);
                    MA[c2] = max(MA[c2],DP[c1][c2][c3]);
                }

                //cout << c1 << " " << c2 << " " << c3 << "   -  " << DP[c1][c2][c3] << " " << MA[c2] << "\n";


        }
    }


    cout << DP[0][1][0] << "\n";

    return 0;
}


Measured memory_bytes: 62976
n = int(input())

element = []
i = 1
while  i * i <= n:
    if n % i == 0:
        element.append([len(str(i)),len(str(n//i))])
    i += 1
ans = max(element[0][0],element[0][1])
for i in range(len(element)):
    ans = min(max(element[i][0],element[i][1]),ans)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;
string alp="abcdefghijklmnopqrstuvwxyz";

int main(){
    ll N,M;
    cin >> N >> M;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
    }
    vector<ll> B(N+1);
    B[0]=0;
    rep(i,N){
        B[i+1]=B[i]+A[i];
        B[i+1]%=M;
    }
    map<ll,ll> m;
    rep(i,N+1){
        m[B[i]]++;
    }
    ll ans=0;
    for (auto x:m){
        ll a=x.second;
        ans+=a*(a-1)/2;
    }
    cout << ans << endl;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

int n;
int k[111];
char s[111];

int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>n;
		if(n==0)break;
		rep(i,n)cin>>k[i];
		cin>>s;
		int l=0;
		rep(i,strlen(s)){
			rep(j,k[l]){
				s[i]--;
				if(s[i]+1=='a')s[i]='Z';
				if(s[i]+1=='A')s[i]='z';
			}
			l++;
			if(l==n)l=0;
		}
		cout<<s<<endl;
	}
	return 0;
}

Measured memory_bytes: 3140
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;

int main(){
  int n, ans;
  for(int i=0;i<5;i++){
    cin >> n;
    if( n == 0 ){
      ans = i + 1;
    }
  }
  cout << ans <<endl;
  return 0;
}

Measured memory_bytes: 3148
#include<stdio.h>
#define N 100000
#define NUM 3

int max(int a, int b);

int a[N];
int b[N];
int c[N];
int happy[NUM][N];

int main(void){
	int i;
	int n;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	happy[0][0]=a[0];
	happy[1][0]=b[0];
	happy[2][0]=c[0];
	for(i=1;i<n;i++){
		happy[0][i]=max(happy[1][i-1]+a[i],happy[2][i-1]+a[i]);
		happy[1][i]=max(happy[0][i-1]+b[i],happy[2][i-1]+b[i]);
		happy[2][i]=max(happy[0][i-1]+c[i],happy[1][i-1]+c[i]);

	}
	printf("%d",max(happy[0][n-1],max(happy[1][n-1],happy[2][n-1])));
	return 0;

}

int max(int a, int b){
	int ret;
	if(a>=b){
		ret=a;
	}else{
		ret=b;
	}
	return ret;
}

Measured memory_bytes: 2560
import sys
from sys import stdin
input = stdin.readline

def main():
    n = int(input())
    max_a, max_b = 0, 0 # type:int
    for _ in range(n):
        a, b = input().split()
        a = int(a)
        if max_a < a:
            max_a = a
            max_b = int(b)
    print(max_a + max_b)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll h, w, n;
	cin >> h >> w >> n;
	print((n+max(h, w)-1)/max(h, w))
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

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

typedef long long ll;

#define MAX_N 10000
#define ORD_MONEY 1000000000000000

struct Edge {
    int to;
    ll weight_yen;
    ll weight_sunuke;
    Edge(int t, ll y, ll s)
        : to(t)
        , weight_yen(y)
        , weight_sunuke(s)
    {
    }
};
using Graph = vector<vector<int>>;
using Graph_e = vector<vector<Edge>>;

vector<int> dx = { 1, 0, -1, 0 };
vector<int> dy = { 0, 1, 0, -1 };
typedef pair<ll, int> P; // first:最短距離，second:頂点番号

void dijkstra(int s, int V, Graph_e G, ll* d, bool mode)
{ // mode=trueならsから，falseならtから
    fill(d, d + V, INF_64);
    d[s] = 0;

    priority_queue<P, vector<P>, greater<P>> que; // 距離が小さいものから取り出せるように
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second; //更新した頂点の中で距離が最小の頂点
    

        for (auto e : G[v]) {
            if (mode) {
                if (d[e.to] > d[v] + e.weight_yen) {
                    d[e.to] = d[v] + e.weight_yen;
                    que.push(P(d[e.to], e.to));
                }
            } else {
                if (d[e.to] > d[v] + e.weight_sunuke) {
                    d[e.to] = d[v] + e.weight_sunuke;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }
}

int main()
{
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--;
    t--;

    Graph_e G(n);
    ll d_s[n];
    ll d_t[n];

    rep(i, m)
    {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        G[u].push_back(Edge(v, a, b));
        G[v].push_back(Edge(u, a, b));
    }
    // どこかで両替したら以降はずっとsunuke
    //
    // 両替を都市iで行う場合，
    // sからiに円による支払いで移動する際の最小金額（yen)
    // iからtにsunukeによる支払いで移動する際の最小金額（sunuke）
    // の和になる
    // tからiにスヌークによる支払いで移動する際の最小金額とiからtにスヌークによる支払いで移動する際の最小金額は同じ
    // これらをダイクストラ法でそれぞれ求めれば良い

    dijkstra(s, n, G, d_s, true);
    dijkstra(t, n, G, d_t, false);

    ll d_sum[n];
    ll ans[n];
    rep(i, n)
    {
        d_sum[i] = d_s[i] + d_t[i];
    }

    ll min = INF_64;
    for (int i = n - 1; i >= 0; i--) {
        if (d_sum[i] < min) {
            min = d_sum[i];
        }
        ans[i] = ORD_MONEY - min;
    }

    rep(i, n)
    {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 20220
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)
#define Graph vector<vecctor<ll>>
#define pairs vector<pair<ll,ll>>
#define pb push_back



using namespace std;
using ll = long long;
const ll INF = 1e18;
const double PI = acos(-1);

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



int main(void)
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll d,t,s;
    cin >> d >> t >> s;
    if(t*s >= d){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    



    return 0;
}


Measured memory_bytes: 3692
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

typedef long long ll;
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int m, d;
  cin >> m >> d;

  int ans = 0;
  for(int i = 2; i <= 9; i++) {
    for(int j = 1; j <= m; j++) {
      if(j % i == 0 && j / i <= 9 && j / i >= 2) {
        int newd = i * 10 + (j / i);
        if(newd <= d) {
          ans++;
        };
      }
    }
  }
  cout << ans << "\n";
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi        first
#define se        second
#define PI        acos(-1)
#define LC(a)     ((a<<1))
#define RC(a)     ((a<<1)+1)
#define MID(a,b)  ((a+b)>>1)
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<ll,ll>   PLL;
typedef pair<ll,int>  PLI;
const int INF = 0X3F3F3F3F;
const int MIN = -(1<<30);
const ll N = 1e5+7;
int main()
{
	IOS();
	
	int x,k;
	
	cin>>k>>x;
	if(500*k>=x) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}



Measured memory_bytes: 384
#ifdef MY_LOCAL
#define MY_NAMESPACE(ns) namespace ns {
#define MY_NAMESPACE_    }
#else
#define MY_NAMESPACE(ns) 
#define MY_NAMESPACE_    
#endif

#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


MY_NAMESPACE(testbed)
ll gcd(ll a, ll b)
{
	if (a < b)
		swap(a, b);
	if (a % b == 0)
		return b;
	return gcd(b, a % b);
}

ll modpow(ll base, ll exponent, ll mod)
{
	ll retval = 1;
	while (exponent > 0)
	{
		if (exponent % 2)
			retval = (retval * base) % mod;
		exponent /= 2;
		base = (base * base) % mod;
	}
	return retval;
}

class HashPair
{
public:
	static size_t m_hash_pair_random;

	template<class T1, class T2>
	size_t operator()(const pair<T1, T2>& p) const {

		auto hash1 = hash<T1>{}(p.first);
		auto hash2 = hash<T2>{}(p.second);

		size_t seed = 0;
		seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
		seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
		seed ^= m_hash_pair_random + 0x9e3779b9 + (seed << 6) + (seed >> 2);
		return seed;
	}
};

size_t HashPair::m_hash_pair_random = (size_t)random_device()();

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

	ll modval = 1000000007;

	int n;
	cin >> n;
	//map<pll, int> cnt;
	unordered_map<pll, int, HashPair> cnt;
	for (int i = 0; i < n; i++)
	{
		ll a, b;
		cin >> a >> b;
		if (a != 0 && b != 0)
		{
			if (a < 0)
			{
				a *= -1;
				b *= -1;
			}
			ll g = gcd(abs(a), abs(b));
			cnt[{a / g, b / g}]++;
		}
		else if (a == 0 && b == 0)
			cnt[{0, 0}]++;
		else if (a == 0)
			cnt[{0, 1}]++;
		else  // b == 0
			cnt[{1, 0}]++;
	}

	ll num00 = cnt[{0, 0}];
	cnt.erase(make_pair(0, 0));

	ll num = 1;
	while (!cnt.empty())
	{
		auto this_item = cnt.begin();
		pll this_pair = this_item->first;
		pll anti_pair = { this_pair.second, -this_pair.first };
		if (anti_pair.first < 0)
			anti_pair = { -this_pair.second, this_pair.first };
		else if (anti_pair.first == 0)
			anti_pair = { 0, 1 };
		if (cnt.find(anti_pair) == cnt.end())
			cnt[anti_pair] = 0;
		auto anti_item = cnt.find(anti_pair);

		num = num * (modpow(2, this_item->second, modval) - 1 + modpow(2, anti_item->second, modval) - 1 + 1) % modval;
		cnt.erase(this_item);
		cnt.erase(anti_item);
	}
	ll retval = (num00 + (num - 1) + modval) % modval;  // -1 for nothing chosen case
	cout << retval << "\n";

	return 0;
}
MY_NAMESPACE_

Measured memory_bytes: 14684
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

class Stream{
public:
    Stream(){

    }
    //配列以外の入力を受け取る
    void read(){

    }
    template<typename First, typename... Rest>
    void read(First& first, Rest&... rest){
        cin >> first;
        read(rest...);
    }
    //配列を区切って出力する
    template<typename T>
    void write_vec(vector<T>& v, char divider){
        for(size_t i = 0; i < v.size(); i++){
            cout << v[i] << divider;
        }
    }
};

int main(){
    Stream io;
    
    string n;
    io.read(n);
    for(int i = 0; i < n.size(); i++){
        switch(n[i]){
            case '1':
            n[i] = '9';
            break;
            case '9':
            n[i] = '1';
            break;
        }
    }
    cout << n;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int main() {
    int n;cin>>n;
    int p[n],p2[n];
    rep(i,n){
        cin>>p[i];
        p2[i]=p[i];
    }
    sort(p,p+n);
    int count=0;
    rep(i,n){
        if (p[i]!=p2[i])
        {
            /* code */
            count++;
        }
        
    }
    if (count>2)
    {
        /* code */
        cout<<"NO"<<endl;
    }
    else
    {
        cout<<"YES"<<endl;
    }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, start, n) for (ll i = (ll)(start); i < (ll)(n); ++i)
static const ll INFTY = 1L << 62L;
ll solver(ll *a, ll N, ll sum)
{
    ll x = a[0];
    sum -= a[0];
    ll ans = abs(sum - x);
    rep(i, 1, N - 1)
    {
        x += a[i];
        sum -= a[i];
        ll tmp = abs(sum - x);
        ans = tmp < ans ? tmp : ans;
    }
    return ans;
}
int main()
{
    ll N;
    cin >> N;
    ll a[N], sum = 0;
    rep(i, 0, N)
    {
        cin >> a[i];
        sum += a[i];
    }
    cout << solver(a, N, sum) << endl;
}

Measured memory_bytes: 5200
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;

#define ll long long

void exgcd(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1, y = 0;
	} else {
		exgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
}

int inv(int a, int n) {
	int x, y;
	exgcd(a, n, x, y);
	return (x < 0) ? (x + n) : (x);
}

const int Mod = 1e9 + 7;

template <const int Mod = :: Mod>
class Z {
	public:
		int v;

		Z() : v(0) {	}
		Z(int x) : v(x){	}
		Z(ll x) : v(x % Mod) {	}

		Z operator + (Z b) {
			int x;
			return Z(((x = v + b.v) >= Mod) ? (x - Mod) : (x));
		}
		Z operator - (Z b) {
			int x;
			return Z(((x = v - b.v) < 0) ? (x + Mod) : (x));
		}
		Z operator * (Z b) {
			return Z(v * 1ll * b.v);
		}
		Z operator ~() {
			return inv(v, Mod);
		}
		Z operator - () {
			return Z(0) - *this;
		}
		Z& operator += (Z b) {
			return *this = *this + b;
		}
		Z& operator -= (Z b) {
			return *this = *this - b;
		}
		Z& operator *= (Z b) {
			return *this = *this * b;
		}
};

Z<> qpow(Z<> a, int p) {
	Z<> rt = Z<>(1), pa = a;
	for ( ; p; p >>= 1, pa = pa * pa) {
		if (p & 1) {
			rt = rt * pa;
		}
	}
	return rt;
}

typedef Z<> Zi;

const int N = 2005, M = N * N;

int n, m;
Zi f[N][N];
Zi fac[M], _fac[M];

void init_fac(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = fac[i - 1] * i;
	}
	_fac[n] = ~fac[n];
	for (int i = n; i; i--) {
		_fac[i - 1] = _fac[i] * i;
	}
}

Zi comb(int n, int m) {
	return (n < m) ? (0) : (fac[n] * _fac[m] * _fac[n - m]);
}

int main() {
	scanf("%d%d", &n, &m);
	if (m == 1) {
		puts("1");
		return 0;
	}
	init_fac(n * m);
	f[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j; j--) {
			f[i][j] = f[i - 1][j - 1] * comb(i * m - j - 1, m - 2) + f[i][j + 1];
		}
		f[i][0] += f[i][1];
	}
	printf("%d\n", (f[n][0] * fac[n]).v);
	return 0;
}


Measured memory_bytes: 47360
#include <iostream>
#include <algorithm>
#define FAIL { cout << "No\n"; return 0; }
using namespace std;

int main() {
    int R, C, R2, C2, r, c;
    cin >> R >> C >> R2 >> C2;

    if (R % R2 == 0 && C % C2 == 0) FAIL;

    int b[500][500] = {};
    int useRow = (R%R2 != 0);
    for (r = 0; r < R; r++) {
        for (c = 0; c < C; c++) {
            if (useRow) {
                b[r][c] = (r%R2 == 0) ? 1000*(R2-1)-1 : -1000;
            } else {
                b[r][c] = (c%C2 == 0) ? 1000*(C2-1)-1 : -1000;
            }

        }
    }

    // check sum
    cout << "Yes\n";
    for (r = 0; r < R; r++) {
        cout << b[r][0];
        for (c = 1; c < C; c++) {
            cout << ' ' << b[r][c];
        }
        cout << '\n';
    }
}

Measured memory_bytes: 2688
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18

ll mod = 1e9+7;
  
// 検索タグ
int main() {
	// 入力
	ll X,Y,num_R,num_B,num_W;cin>>X>>Y>>num_R>>num_B>>num_W;
	ll R[num_R];REP(i,num_R)cin>>R[i];
	ll B[num_B];REP(i,num_B)cin>>B[i];
	ll W[num_W];REP(i,num_W)cin>>W[i];
    
	// 解法
	sort(R, R+num_R, greater<ll>());
	sort(B, B+num_B, greater<ll>());
	sort(W, W+num_W, greater<ll>());

	ll selected_R = X;
	ll selected_B = Y;
	ll ans = 0;
	REP(i, selected_R) ans += R[i];
	REP(i, selected_B) ans += B[i];
	// printf("ans %lld\n", ans);
	REP(i, num_W){
		if (selected_R>=1 & selected_B>=1){ // R B 共に残ってる
			if (R[selected_R-1]<B[selected_B-1] & R[selected_R-1]<W[i]){ // Rの最小がBの最小より小さく、W[i]よりも小さい
				ans = ans - R[selected_R-1] + W[i];
				selected_R--; // Rを一つWと取り換える
				// printf("flag R\n");
			}
			else if (B[selected_B-1]<=R[selected_R-1] & B[selected_B-1]<W[i]){ // Bの最小がRの最小より小さく、W[i]よりも小さい
				ans = ans - B[selected_B-1] + W[i];
				selected_B--; // Rを一つWと取り換える
				// printf("flag B\n");
			}
		}
		else if (selected_R>=1 & selected_B==0){ // Rは残っていて Bは尽きた
			if (R[selected_R-1]<W[i]){ // Rの最小がBの最小より小さく、W[i]よりも小さい
				ans = ans - R[selected_R-1] + W[i];
				selected_R--; // Rを一つWと取り換える
				// printf("flag R\n");
			}
		}
		else if (selected_B>=1 & selected_R==0){ // Bは残っていて Rは尽きた
			if (B[selected_B-1]<W[i]){ // Rの最小がBの最小より小さく、W[i]よりも小さい
				ans = ans - B[selected_B-1] + W[i];
				selected_B--; // Rを一つWと取り換える
				// printf("flag R\n");
			}
		}

		// printf("i: %lld, ans: %lld\n", i, ans);
	}

	//出力
	printf("%lld\n", ans);
}


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

int main() {
    int n, Y, x = 0, y, z;
    cin >> n >> Y;
    bool can = false;

    int t = Y / 1000 - n;
    while (t >= 0) {
        y = t / 4; // >= 0
        z = n - x - y;
        if (t % 4 == 0 && z >= 0) {
            can = true;
            break;
        }
        t -= 9;
        x++;
    }

    if (can) cout << x << ' ' << y << ' ' << z << endl;
    else cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 3568
#include <iostream>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
//#define rep(i, n) for(int (i) = 0, TmP = (n); (i) < (int)TmP ; ++(i))
//rep(i, v.size()) v[i]=i;
//#define int long long
#define asort(v, n) sort((v), (v + n)) //Using array
#define vsort(v) sort((v).begin(), (v).end()) // Using vector
#define vint vector<int>

using namespace std;

signed main(){
  int a, b, c;
  cin >> a >> b >> c;

  if(a + b + c >= 22)cout << "bust" << endl;
  else cout << "win" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < (int)n;i++)
#define repb(i, n) for(int i = (int)n;i >= 0;i--)
#define reps(i, m, n) for(int i = (int)m;i < (int)n;i++)
#define repsb(i, m, n) for(int i = (int)m;i >= (int)n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define INF 999999999999999999
using namespace std;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
using namespace std;
int main(int argc, char const *argv[]) {
    int temp[3];
    rep(i,3){
      cin>>temp[i];
    }
    cout<<(temp[0]+temp[1]>=temp[2]?"Yes":"No")<<endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    from collections import deque
    N, X, Y = (int(i) for i in input().split())
    X -= 1
    Y -= 1
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        edge[i].append(i+1)
        edge[i+1].append(i)
    edge[X].append(Y)
    edge[Y].append(X)

    def bfs(s):
        d = [-1 for _ in range(N)]
        que = deque()
        d[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in edge[u]:
                if d[v] != -1:
                    continue
                d[v] = d[u] + 1
                que.append(v)
        return d

    dist = [[] for _ in range(N)]
    for i in range(N):
        dist[i] = bfs(i)
    cnt = [0]*N
    for i in range(N):
        for j in range(i+1, N):
            cnt[dist[i][j]] += 1
    for c in cnt[1:]:
        print(c)


if __name__ == '__main__':
    main()


Measured memory_bytes: 80348
#include<stdio.h>

int fx(int x)
{
  int X=x;
  int fx=0;
  while(1){
    fx+=X%10;
    if(X/10==0){
      break;
    } else if(X/10!=0){
      X/=10;
    }
  }
  return fx;
}

int main()
{
  int n,a,b;
  int fa,fb;
  int s_old,s_new;
  int i;
  s_old=1000;
  s_new=1000;
  scanf("%d",&n);
  for(i=1;i<n;i++){
    a=i;
    b=n-i;
    fa=fx(a);
    fb=fx(b);
    s_new=fa+fb;
    if(s_new<s_old) s_old=s_new;
  }
  printf("%d",s_old);
  return 0;
}


Measured memory_bytes: 1736
li = []
while True:
    h, w = map(int, input().split(' '))
    if h == w == 0:
        break
    li.append((h, w))

for t in li:
    h, w = t
    for i in range(0, h):
        for j in range(0, w):
            if i == 0 or i == h - 1:
                print('#', end='')
            elif j == 0 or j == w - 1:
                print('#', end='')
            else:
                print('.', end='')
        print()
    print()



Measured memory_bytes: 7008
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Edge=pair<int,int>;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
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;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int N,K;
vector<int> E[101010];
ll ret=1;

void dfs(int cur,int pre,int num){
  ret=ret*num%MOD;
  
  num=K-1;
  if(pre!=-1) num--;
  FORE(e,E[cur]){
    if(e!=pre){
      dfs(e,cur,num);
      num--;
    }
  }
}

int main(){
  cin>>N>>K;
  RREP(i,N-1){
    int x,y;
	cin>>x>>y;
	x--,y--;
    E[x].push_back(y);
    E[y].push_back(x);
  }
  dfs(0,-1,K);
  cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 12532
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[500000];
void read(int &res){
	res=0;char c;
	while((c=getchar())<48);
	do res=(res<<1)+(res<<3)+(c^48);
	while((c=getchar())>47);
}
int main(){
	int f=1,i,n,l=250000,r=249999;
	read(n);
	for(i=1;i<=n;++i){
		if(f==1)read(a[++r]);
		else read(a[--l]);
		f*=-1;
	}
	if(n&1)for(i=r;i>=l;--i)printf("%d ",a[i]);
	else for(i=l;i<=r;++i)printf("%d ",a[i]);
	return 0;
}

Measured memory_bytes: 2944
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,P> PP;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=4999999996000000001;


int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> p(n),c(n);
    for(ll i=0;i<n;i++){
        cin>>p[i]; p[i]--;
    }
    for(ll i=0;i<n;i++) cin>>c[i];
    vector<ll> r(n), v(n);
    vector<bool> f(n,false);
    for(ll i=0;i<n;i++){
        if(f[i]) continue;
        vector<ll> visited(n,0);
        ll now=i;
        ll roop=0;
        ll value=0;
        while(true){
            now=p[now];
            if(visited[now]==0){
                roop++;
                value+=c[now];
                visited[now]++;
            }else if(visited[now]==1){
                r[now]=roop;
                v[now]=value;
                f[now]=true;
                visited[now]++;
            }else{
                break;
            }
        }
    }

    ll ans=-INF;
    for(ll i=0;i<n;i++){
        ll buf=0;
        if(k>r[i]){
            if(v[i]>0){
                ll num=k/r[i];
                num--;
                buf+=num*v[i];
            }
            ans=max(ans,buf);
            ll num=k%r[i];
            num+=r[i];
            ll now=i;
            while(num){
                now=p[now];
                buf+=c[now];
                ans=max(ans,buf);
                num--;
            }
        }else{
            ll num=k;
            ll now=i;
            while(num){
                now=p[now];
                buf+=c[now];
                ans=max(ans,buf);
                num--;
            }
        }
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 3428
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }


int main(){
    int a, b; cin >> a >> b;
    if(a==1 or b==1){
        if(a==b)cout << "Draw" << ln;
        else if(a==1)cout << "Alice" << ln;
        else cout << "Bob" << ln;
    }else{
    if(a>b)cout << "Alice" << ln;
    else if(a<b)cout << "Bob" << ln;
    else cout << "Draw" << ln;
    }
}

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

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i=0; i<n; i++){
    cin >> h.at(i);
  }
  int hmax = 0;
  for (int i=0; i<n; i++){
    hmax = max(hmax, h.at(i));
  }
  
  int ans = 0;
  int cycle = 0;
  while (cycle<hmax){
    if (h.at(0) != 0){
      ans += 1;
    }
    for (int i=0; i<n-1; i++){
      if (h.at(i) == 0 && h.at(i+1) != 0){
        ans += 1;
      }
    }
    for (int j=0; j<n; j++){
      if (h.at(j)>0){
        h.at(j) -= 1;
      }
    }
  cycle += 1;
  }
  cout << ans << endl;
  return 0;  
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){

    int K,N;
    cin>>K>>N;
    int A[200100];
    for(int i=0;i<N;i++) cin>>A[i];
    int dist=0;
    int result=0;
    int max=0;
    for(int i=0;i<N-1;i++){
        dist=-(A[i]-A[i+1]);
        if(max<dist){
            max=dist;
        }
        
    }
    if(max<K-A[N-1]+A[0]){
        max=K-A[N-1]+A[0];
    }
    result=K-max;
    cout<<result<<endl;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
 
int main(void){
  int n,k;
  cin>>n>>k;
  int comp = 1;
  int digit = 0;
  
  while(comp<=n){
	digit++;
    comp *= k;
  }
  
  cout<<digit<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    int ans = 0;
    for(int i=1;i<n;i++){
        ans+=abs(a[i]-a[i-1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 123456*2

int main(void){
  int n, i, j;
  int count=0;
  int p_num[MAX];

  p_num[0]=p_num[1]=0;
  for(i=2;i<MAX;i++)
    p_num[i]=1;

  while(1){
    count=0;
    scanf("%d", &n);

    if(n==0 || 123456<n)
      break;

    for(i=n+1;i<=2*n;i++){
      for(j=2; j*j<=i;j++){
	if(i%j==0)
	  p_num[i]=0;
      }
      if(p_num[i]==1)
	count+=p_num[i];
    }
    
    printf("%d\n", count);
  }

  return 0;
}

Measured memory_bytes: 1564
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(a < b) {
			System.out.println("a < b");
		}else if(a == b) {
			System.out.println("a == b");			
		}else {
			System.out.println("a > b");
		}
	}

}



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

using namespace std;

int main () {
    int n;
    int v[51];
    int c[51];
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> v[i];
    }
    for (int i=0; i<n; i++) {
        cin >> c[i];
    }
    int s = 0;
    for (int i=0; i< n; i++) {
        int diff = v[i] - c[i];
        if (diff > 0) {
            s += diff;
        }
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	k := nextInt()
	a := make([]int, n)

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

	//ans := (float64(n) - 1.0) / (float64(k) - 1.0)
	fmt.Println((n + k - 3) / (k - 1))

}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 3336
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
int GCD(int a,int b){return b?GCD(b,a%b):a;}
int LCM(int a,int b){return (a*b)/GCD(a,b);}
int abs(int x){return x>0?x:-x;}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	int n;
	cin >> n;
	double x[n];
	string u[n];
	double ans = 0;
	REP(i, n){
		cin >> x[i] >> u[i];
		if (u[i] == "JPY") ans += x[i];
		else ans += x[i] * 380000;
	}
	
	printf("%lf\n", ans);

}


Measured memory_bytes: 256