akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

bool isOdd(int num) {
	if(num%2 == 0)
	    return false;
  	else
	    return true;
}

int main(){
    int N;
    double odd,even;

    cin >> N;
    odd, even = 0;

    for(int i = 1; i <= N; ++i) {
    	if(isOdd(i)) odd++;
      	else even++;
    }

    double result = odd / (odd + even);

    cout.precision(10);
    cout << showpoint << result << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int Nmax = 5010;

int main() {
    int n;
    string s;
    cin >> n >> s;

    vector<vector<int>> dp(Nmax,vector<int>(Nmax));
    for(int i = n-1; i >= 0; i--) {
        for(int j = n-1; j >= 0; j--) {
            if(s[i] == s[j]) {
                dp[i][j] = dp[i+1][j+1] + 1;
            }
        }
    }

    int ans = 0;
    rep(i, n) {
        rep(j, n) {
            if(i >= j) {
                continue;
            }
            int now = min(dp[i][j], j-i);
            ans = max(ans, now);
        }
    }

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

Measured memory_bytes: 98432
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] pos = new int[n];
        for(int i=0; i<n; i++){
            int tmp = sc.nextInt();
            a[i] = tmp;
            pos[tmp-1] = i;
        }

        TreeSet<Integer> ts = new TreeSet<Integer>();
        long ans = 0;

        for(int i=0; i<n; i++){
            int h, l;
            if(ts.higher(pos[i]) == null){
                h = n;
            }else{
                h = ts.higher(pos[i]);
            }
            if(ts.lower(pos[i]) == null){
                l = -1;
            }else{
                l = ts.lower(pos[i]);
            }

            ans += (long)(pos[i] - l) * (long)(h - pos[i]) * (long)(i+1);

            ts.add(pos[i]);
        }

        System.out.println(ans);
    }

}


Measured memory_bytes: 80620
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
XU = [tuple(input().split()) for _ in range(N)]

ans = 0
for x,u in XU:
    if u == "JPY":
        ans += float(x)
    else:
        ans += float(x)*380000

print(ans)

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline

def main():
	A, B, K = map(int, input().split())
	count = 0
	for i in range(1, min(A, B) + 1)[::-1]:
		if A % i == 0 and B % i == 0:
			count += 1
		if count == K:
			print(i)
			break

if __name__ == '__main__':
	main()

Measured memory_bytes: 2940
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

def abc080_c_np():
    N = int(readline())  # 他店の数
    # 他店の営業パターン：店→日付→営業01
    F = np.zeros((N, 10), dtype=np.int8)
    for i in range(N): F[i] = readline().split()
    # 他店と何回重なると利益がどうなるか：店→重複回数→利益
    P = np.zeros((N, 11), dtype=np.int32)
    for i in range(N): P[i] = readline().split()
    ans = -10**12  # 最悪 100 * -10**7

    # bit全探索
    from itertools import product
    for mask in product(range(2), repeat=10):
        if mask.count(1) == 0: continue
        profit = 0
        mask_np = np.array(mask, np.int8)
        for i in range(N):
            # 他店iの営業パターンと、自店の営業パターンmaskと、の要素積は、重複する営業日
            overlap = np.multiply(F[i,:], mask_np).sum()
            profit += P[i, overlap]
        ans = max(profit, ans)
    print(ans)

abc080_c_np()

Measured memory_bytes: 17868
# include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int main()
{
	fast;
    int n;
    cin>>n;
    int arr[n+1];
    for(int i=0; i<n; i++){
        cin>>arr[i+1];
    }
    int dp[n+1]={};
    dp[1] = 0;
    dp[2] = abs(arr[2]-arr[1]);
    for(int i=3; i<=n; i++){
        dp[i] = min(abs(arr[i]-arr[i-1])+dp[i-1],dp[i-2]+abs(arr[i]-arr[i-2]));
       //cout<<dp[i]<<endl;
    }
    cout<<dp[n];
    return 0;
}



Measured memory_bytes: 1024
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K
#define INF 1e18
#define MOD 100000007
#define SIZE 10005
#define PI 	3.14159265358979323846


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int s,r;
    cin >> s >> r;
    cout << 2*r-s << endl;
}

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

namespace ABC119
{
    public class D
    {
        long INF = 1000000000000000000;
        public void Solve()
        {
            int A, B, Q;
            string[] str = Console.ReadLine().Split(' ');
            A = int.Parse(str[0]);
            B = int.Parse(str[1]);
            Q = int.Parse(str[2]);
            long[] s = new long[A + 2];
            long[] t = new long[B + 2];
            s[0] = -INF;
            s[A + 1] = INF;
            t[0] = -INF;
            t[B + 1] = INF;
            long[] xs = new long[Q];
            for (int i = 0; i < A; i++) { s[i + 1] = long.Parse(Console.ReadLine()); }
            for (int i = 0; i < B; i++) { t[i + 1] = long.Parse(Console.ReadLine()); }
            for (int i = 0; i < Q; i++) { xs[i] = long.Parse(Console.ReadLine()); }
            for (int i = 0; i < Q; i++)
            {
                long x = xs[i];
                long sb = Array.BinarySearch(s, x);
                if (sb < 0) { sb = ~sb; }
                long tb = Array.BinarySearch(t, x);
                if (tb < 0) { tb = ~tb; }
                long resdist = INF;
                for (long m = sb - 1; m <=sb; m++)
                {
                    for (long n = tb - 1; n <= tb; n++)
                    {
                        long distA = Math.Abs(s[m] - x) + Math.Abs(t[n] - s[m]);
                        long distB = Math.Abs(t[n] - x) + Math.Abs(s[m] - t[n]);
                        resdist = Min(resdist, distA, distB);
                    }
                }
                Console.WriteLine("{0}", resdist);
            }
        }

        long Min(params long[] nums)
        {
            if (nums.Length == 0) { return 0; }
            long min = INF;
            for (int i = 0; i < nums.Length; i++) { min = (nums[i] < min) ? nums[i] : min; }
            return min;
        }
    }
}

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            new ABC119.D().Solve();
        }
    }
}

Measured memory_bytes: 19892
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h, w, n,m,k; string s;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}

int main() {
	cin >> s;
	rep(i, s.size()) {
		if ((i % 2 == 0&&s[i]=='L')||(i % 2 == 1 && s[i] == 'R')) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 384
/*
    Stay motivated and keep working hard
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9 + 7;
int n, k;
int dp[100007], h[100007];
int recur(int n){
    if(n <= 0){
        return INF;
    }
    if(n == 1){
        return 0;
    }
    if(dp[n] != INF){
        return dp[n];
    }
    int ans = INF;
    for(int i=1;i<=k && (n-i >= 0);i++){
        // return dp[n] = min(dp[n], abs(h[n] - h[n-i]) + recur(n-i));
        ans = min(ans, abs(h[n] - h[n-i]) + recur(n-i));
    }
    return dp[n] = min(ans, dp[n]);
}
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // int n, k;
    cin >> n >> k;
    // int dp[n+7];
    for(int i=0;i<n+7;i++){
        dp[i] = INF;
    }
    // int h[n+7];
    for(int i=1;i<=n;i++){
        cin >> h[i];
    }
    recur(n);
    cout << dp[n] << "\n";
    // dp[0] = 0;
    // for(int i=0;i<n;i++){
    //     for(int j=i+1;j<=i+k;j++){
    //         if(j < n){
    //             dp[j] = min(dp[j], abs(h[j] - h[i]) + dp[i]);
    //         }
    //     }
    // }
    // cout << dp[n-1] << "\n";


    return 0;
}

Measured memory_bytes: 7296
/*
 *    author:  Gary Shih
 *    created: 2020-05-03 22:21:09
 */
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.setf(ios::fixed), cout.precision(9);
  int n, W;
  cin >> n >> W;
  vector<int> w(n), v(n);
  for (int i = 0; i < n; ++i) cin >> w[i] >> v[i];

  vector<long long> dp(W + 1, LLONG_MIN);
  dp[0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = W; j >= 0; --j) {
      if (j - w[i] < 0) break;
      if (dp[j - w[i]] != LLONG_MIN) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
      }
    }
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> cnt(26, Inf);
    rep (i, n) {
        string s;
        cin >> s;
        vector<int> tmp(26);
        rep (j, s.size()) tmp[s[j] - 'a']++;
        rep (j, 26) cnt[j] = min(cnt[j], tmp[j]);
    }
    rep (i, 26) {
        rep (j, cnt[i]) cout << char('a' + i);
    }
    cout << endl;
    
    return 0;
}



Measured memory_bytes: 256
def resolve():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    M=int(1e6+1)
    f=[0]*M
    for x in a:
        if f[x]!=0:
            f[x]+=1
            continue
        for nx in range(x,M,x):
            f[nx]+=1
    ans=0
    for x in a:
        if f[x]==1:ans+=1
    print(ans)
resolve()


Measured memory_bytes: 32004
from sys import stdin
import math
import fractions
from decimal import *

A, B, C, D = list(map(Decimal, stdin.readline().split()))
cd = C * D / Decimal(str(fractions.gcd(C,D)))

Nc = Decimal(B / C).quantize(Decimal("0"), rounding=ROUND_FLOOR) - Decimal(A / C).quantize(Decimal("0"), rounding=ROUND_CEILING) + Decimal("1")
Nd = Decimal(B / D).quantize(Decimal("0"), rounding=ROUND_FLOOR) - Decimal(A / D).quantize(Decimal("0"), rounding=ROUND_CEILING) + Decimal("1")
Ncd = Decimal(B / cd).quantize(Decimal("0"), rounding=ROUND_FLOOR) - Decimal(A / cd).quantize(Decimal("0"), rounding=ROUND_CEILING) + Decimal("1")

print(B-A+Decimal("1")-(Nc+Nd-Ncd))


Measured memory_bytes: 5048
#include <iostream>
#include<iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e16
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 100000;

int main(){
    
    ll N;
    cin >> N;
    
    ll ans=INF;
    
    for(ll i=1;i*i<=N;i++){
        if(N%i==0){
            ll a=i-1;
            ll b=N/i-1;
            ans=min(ans,a+b);
        }
    }
    
    cout << ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)) {

			int n = sc.nextInt();
			
			double[] xArray = new double[n];
			double[] yArray = new double[n];
			
			for(int i = 0 ; i < n ; i++ ) {
				xArray[i] = sc.nextDouble();
				yArray[i] = sc.nextDouble();
			}
			
			double sum = 0f;
		
			for(int i = 0 ; i < n ; i++ ) {
				List<Integer> remainingNodes = new ArrayList<>();
				for(int j = 0 ; j < n ; j++ ) {
					if ( i != j ) {
						remainingNodes.add(j);
					}
				}
				
				sum += calc(xArray, yArray, i, remainingNodes);
				
			}
			
			//calc pattern
			double p = calcPermutation(n);
			
			System.out.println(sum / p);
		}
	}
	
	private static double calcPermutation(int n) {
		if ( n == 0 || n == 1 ) { 
			return 1f;
		}
		else {
			return calcPermutation(n-1) * n;
		}
	}
	
	private static double calc(double[] xArray, double[] yArray, int startIndex, List<Integer> remainingNodes) {
		if ( remainingNodes.size() == 0 ) {
			return 0f;
		}
		
		double sum = 0f;
		for(int i  : remainingNodes ) {
			List<Integer> copiedRemainingNodes = new ArrayList<>(remainingNodes);
			copiedRemainingNodes.remove(new Integer(i));
			
			double p = calcPermutation(copiedRemainingNodes.size());
			
			sum += p * dist(xArray, yArray,startIndex, i) + calc(xArray, yArray, i, copiedRemainingNodes);
		}
		
		return sum;
	}
	
	private static double dist(double[] xArray, double[] yArray, int startIndex, int endIndex) {
		return Math.pow(Math.pow((xArray[startIndex] - xArray[endIndex]), 2) + Math.pow((yArray[startIndex] - yArray[endIndex]), 2), 0.5);
	}
	
}

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

int main(){

  ll n;
  cin >> n;
  vector<int> a(n+1);
  for(int i=1; i<=n; i++){
    cin >> a[i];
  }
  vector<int> id(n+1);
  for(int i=1; i<=n; i++){
  	id[a[i]] = i;
  }
  for(int i=1; i<=n; i++){
  	cout << id[i] << " ";
  }
}

Measured memory_bytes: 1536
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
if n == 0:
    if lst1[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if lst1[0] != 0:
    print(-1)
    exit()
res2 = [0]
for i in lst1[::-1]:
    res2.append(res2[-1]+i)

res2.reverse()
INF = res2[0]
res = [1] 
res3 = [1]
for i in range(1,len(lst1)):
    res3.append(min(INF,res[-1]*2))
    cache = res[-1]*2-lst1[i]
    if cache <= 0 and i != n:
        print(-1)
        exit()
    elif cache < 0 and i == n:
        print(-1)
        exit()
    res.append(min(INF,cache))

ans = 0
res2 = res2[:-1]
for i in range(len(res3)):
    ans += min(res2[i],res3[i])
print(ans)

Measured memory_bytes: 105008
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long N,T,A,t,a;
	cin>>N;
	t=a=1;
	for(long long n=0;n<N;n++){
	cin>>T>>A;
	long long k=max((t+T-1)/T,(a+A-1)/A);
	t=k*T;
	a=k*A; 
	}
	cout<<t+a<<endl;
	return 0;
}


Measured memory_bytes: 256
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    leftmax = [-1] * N
    rightmax = [-1] * N
    for i in range(1, N):
        leftmax[i] = max(leftmax[i-1], A[i-1])
        rightmax[N-i-1] = max(rightmax[N-i], A[N-i])
    #print(leftmax)
    #print(rightmax)
    ans = ""
    for i in range(N):
        ans += str(max(leftmax[i], rightmax[i])) + " "
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

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

int main() {
	string S;
	cin>>S;
	int s = -1, t = -1;
	if(S.size()==2){
		if(S[0]==S[1]){
			s = 1;
			t = 2;
		}
	}
	else {
		for(int i=0;i<S.size()-3;++i){
			if((S[i] == S[i+1]) | (S[i] == S[i+2]) | (S[i+1] == S[i+2])){
				s = i+1;
				t = i+3;
			}
		}
	}
	cout<<s<<" "<<t<<endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;


ll modNorm(ll a, ll m) {
  return (a%m+m)%m;
}

// ax+by=gcd(a,b)
ll extgcd(ll a, ll b, ll &x, ll &y) {
  ll g = a;
  x = 1; y = 0;
  if (b) {
    g = extgcd(b, a%b, y, x);
    y -= (a/b) * x;
  }
  return g;
}

ll invMod(ll a, ll p) {
  ll x, y;
  if (extgcd(a,p,x,y) == 1) return (x+p)%p;
  return 0;
}

// p > n
struct ModFact {
  vector<ll> fact;
  ll p;
  int maxn;
  ModFact(int maxn, ll p) : maxn(maxn), p(p), fact(maxn+1) {
    fact[0] = 1;
    REP(i, maxn)
      fact[i+1] = fact[i] * (i+1) % p;
  }
  int combi(int n, int k) {
    if (n<0||k<0||n<k) return 0;
    assert(n <= maxn);
    return fact[n] * invMod(fact[k]*fact[n-k]%p, p) % p;
  }
};

int main() {
  const int M = 1e9+7;
  int n,m,k;
  ModFact mof(300000, M);
  while(cin>>n>>m>>k) {
    ll ans = 0;
    for (int i=0; i<=k; ++i) {  // iツ嘉アツ債カツづ可行ツつュ
      ll lr = modNorm(mof.combi(n+2*i,i) - mof.combi(n+2*i,i-1), M);
      int j = k-i;
      ll ud = modNorm(mof.combi(m+2*j,j) - mof.combi(m+2*j,j-1), M);
      //cout << lr << " " << ud << " " << mof.combi(n+i+m, n+i) << endl;
      int hoge = mof.combi(n+2*i+m+2*j,n+2*i);                // ツつアツづ個づつォツづ個債カツ右ツ湘」ツ可コツづ個渉氾板づ個組ツづ敖債づュツつケ
      //cout << hoge << endl;
      ans = (ans + lr*ud%M * hoge) % M;
    }
    //ans = (ans * mof.combi(n+m, n)) % M;
    cout << ans << endl;
  }
}

Measured memory_bytes: 3208
//by xxj
#include<bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
//const int mod=;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int q;
	scanf("%d",&q);
	while (q--){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		//aaaabaaaabaaaabaaaababbbbabbbbabbbb
//		if (a==b-1){
//			for (int i=c;i<=d;i++){
//				if (i%2==0){
//					printf("A");
//				}
//				else{
//					printf("B");
//				}
//			}
//			puts("");
//			continue;
//		}
		int len;
		if (a>b){
			len=(a-1)/(b+1)+1;
		}
		else{
			len=(b-1)/(a+1)+1;
		}
//		cout<<len<<endl;
		int k=(a-1)/len+1;
//		cout<<k<<endl;
		int l=0,r=k,mid,ans=0;
//		puts("begin");
		while (l<=r){
			mid=(l+r)>>1;
//			cout<<mid<<' '<<mid*len+(b-mid)/len<<endl;
			if (mid*len+(b-mid)/len<=a){
				l=mid+1;
				ans=mid;
			}
			else{
				r=mid-1;
			}
		}
//		puts("end");
//		cout<<ans<<endl;
		int zz=ans*(len+1);
		int sya=a-(ans*len+(b-ans)/len);
		int syb=b-(ans+(b-ans)/len*len);
//		cout<<sya<<' '<<syb<<endl;
		int zz2=zz+sya+syb;
//		cout<<zz2<<endl;
		for (int i=c;i<=d;i++){
			if (i<=zz){
				if (i%(len+1)==0){
					printf("B");
				}
				else{
					printf("A");
				}
			}
			else if (i<=zz2){
				if (i-zz<=sya){
					printf("A");
				}
				else{
					printf("B");
				}
			}
			else{
				if ((a+b-i)%(len+1)==len){
					printf("A");
				}
				else{
					printf("B");
				}
			}
		}
		puts("");
	}
	return 0;
}
/*
input:
1
8 10 1 18
*/


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#define MAX_N 1000
using namespace std;
int main(){
  long long X, Y;
  cin >> X >> Y;
  long long i = X, ans = 0;
  while(i <= Y){
    ans ++;
    i = i * 2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main() {
  string S, T; cin >> S >> T;
  int N = S.size(), M = T.size();
  long dp[N+1][M+1]; int dir[N+1][M+1];
  for (int i = 0; i <= N; i++) dp[i][0] = 0;
  for (int j = 0; j <= M; j++) dp[0][j] = 0;
  for (int i = 0; i <= N; i++) for (int j = 0; j <= M; j++) dir[i][j] = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      dp[i][j] = -1;
      if (dp[i-1][j] > dp[i][j]) { dp[i][j] = dp[i-1][j]; dir[i][j] = 1; }
      if (dp[i][j-1] > dp[i][j]) { dp[i][j] = dp[i][j-1]; dir[i][j] = 2; }
      if (S[i-1] == T[j-1] && dp[i-1][j-1] + 1 > dp[i][j])
      { dp[i][j] = dp[i-1][j-1] + 1; dir[i][j] = 3; }
    }
  }
  vector<char> V;
  int i = N, j = M;
  while (dir[i][j]) {
    if (dir[i][j] == 1) i--;
    else if (dir[i][j] == 2) j--;
    else { V.push_back(S[i-1]); i--; j--; }
  }
  for (auto it = V.rbegin(); it != V.rend(); it++) cout << *it;
  cout << endl;
}

Measured memory_bytes: 109088
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i=(l); i<(r); ++i)
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void set_square(int x, int y, int k, vector<vector<int>> &imos){
    if(x<0 || y<0 || x>=3*k-1 || y>=3*k-1) return;
    imos[ max(0, x-k+1) ][ max(0, y-k+1) ] += 1;
    imos[ max(0, x-k+1) ][ min(y+1, 2*k) ] -= 1;
    imos[ min(x+1, 2*k) ][ max(0, y-k+1) ] -= 1;
    imos[ min(x+1, 2*k) ][ min(y+1, 2*k) ] += 1;
}

void set_imos(int x, int y, int k, vector<vector<int>> &imos){
    set_square(x, y, k, imos);
    set_square(x+k, y-k, k, imos);
    set_square(x-k, y-k, k, imos);
    set_square(x+k, y+k, k, imos);
    set_square(x-k, y+k, k, imos);
    set_square(x, y+2*k, k, imos);
}

int main(){
    int n, k; cin >> n >> k;
    // 入力を受け取り、扱いやすいように希望を同値変形して座標を圧縮する
    // 具体的には全ての希望を、「(x,y)∈[0,2k)*[0,2k)を黒に塗りたいな」という希望に同値変形する
    vector<int> x(n), y(n);
    rep(i, 0, n){
        cin >> x[i] >> y[i];
        char c; cin >> c;
        if(c=='W') x[i] += k;
        x[i]%=2*k; y[i]%=2*k;
    }

    // 市松模様は[0,2k)*[0,2k)のどこを黒い部分の左下にするかという情報で一意に定まる（全単射）ので、そのように表す
    // imos[i][j] := (i,j)が黒い部分の左下になるような市松模様を塗った時に叶えられる希望の数
    vector<vector<int>> imos(2*k+5, vector<int>(2*k+5, 0));
    rep(i, 0, n){
        // (x[i],y[i])を黒に塗れるような市松模様(X, Y)について、最後に累積した時に imos[X][Y]+=1 になるように重みを加算する
        set_imos(x[i], y[i], k, imos);
    }

    // 左→右へ累積
    rep(i, 0, 2*k) rep(j, 1, 2*k) imos[i][j] += imos[i][j-1];
    // （問題文の画像で）下→上へ累積
    rep(j, 0, 2*k) rep(i, 1, 2*k) imos[i][j] += imos[i-1][j];

    // 最大値の検索
    int ans=0;
    rep(i, 0, 2*k) rep(j, 0, 2*k) chmax(ans, imos[i][j]);

    cout << ans << '\n';
    return 0;
}


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

const string YES = "Yes";
const string NO = "No";

void solve(){

}

int main(){
    int N;
    cin >> N;
    bool flg = false;
    for(int i = 1; i <= 9; i++){
        if(N % i==0){
            int j = N/i;
            if(j >= 1 && j <= 9){
                flg = true;
                break;
            }
        }
    }
    cout << (flg ? YES : NO ) <<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[500010];
char s[500010];
int main(){
    int n;
    string c;
    while(cin>>c){
        ll ans=0;
        int n=c.size();
        for(int i=0; i<n; ++i){
            s[i+1]=c[i];
        }
        memset(a, -1, sizeof a);
        for(int i=1; i<n+2; ++i){
            if((i==1||s[i-1]=='>')&&(i==n+1||s[i]=='<')){
                a[i]=0;
//                cout<<"*"<<i<<endl;
                for(int j=i+1; j<n+2; ++j){
                    if(s[j-1]!='<')
                        break;
                    if(a[j]!=-1){
                        a[j]=max(a[j], j-i);
                        break;
                    }
                    a[j]=j-i;
                }
                for(int j=i-1; j>=1; --j){
                    if(s[j]!='>')
                        break;
                    if(a[j]!=-1){
                        a[j]=max(a[j], i-j);
                        break;
                    }
                    a[j]=i-j;
                }
            }
        }
        for(int i=1; i<n+2; ++i){
            ans+=a[i];
//            cout<<a[i]    <<" ";
        }
        cout<<ans<<endl;
    }
  return 0;
}




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

using namespace std;

int main(){
    int r, n;
    while(cin >> r >> n && r != 0) {
        map<int, int> h;
        REP(_, n) {
            int L, R, a;
            cin >> L >> R >> a;
            for(int i = L; i < R; i++) {
                h[i] = max(h[i], a);
            }
        }

        double ans = 1e16;
        for(int i = -r; i < r; i++) {
            double p = (i < 0 ? i + 1: i);
            ans = min(ans, r - sqrt(r * r - p * p) + h[i]);
        }
        printf("%.12f\n", ans);
    }
    return 0;
}

Measured memory_bytes: 1208
package main

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

const (
	initialBufSize = 10000
	maxBufSize     = 1000000
	mod            = 1e9 + 7
)

var (
	sc *bufio.Scanner = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, initialBufSize)
	sc.Buffer(buf, maxBufSize)
		sc.Split(bufio.ScanWords)
		return sc
	}()
)

func main() {
	A := getInt()
	B := getInt()

	num := 1
	cnt := 0
	for ; num < B; {
		num += A
		num--
		cnt++
	}

	fmt.Println(cnt)
}

type Graph struct {
	n     int
	edges [][]int
}

func NewGraph(n int) *Graph {
	g := &Graph{
		n:     n,
		edges: make([][]int, n),
	}
	return g
}

func (g *Graph) AddEdge(u, v int) {
	g.edges[v] = append(g.edges[v], u)
	g.edges[u] = append(g.edges[u], v)
}

func dfs(c int, edges [][]int, visited map[int]struct{}) {
	visited[c] = struct{}{}

	for _, v := range edges[c] {
		_, flag := visited[v]
		if flag {
			continue
		}
		dfs(v, edges, visited)
	}
}

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func powMod(n, p int) int {
	if p == 0 {
		return 1
	} else if p%2 == 0 {
		t := powMod(n, p/2)
		return calcMod(t * t)
	} else {
		return calcMod(n * powMod(n, p-1))
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func printIntArray(array []int) {
	strArray := fmt.Sprint(array)
	fmt.Println(strArray[1 : len(strArray)-1])
}

func calcMod(x int) int {
	return x % mod
}

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func isPrime(n int) bool {
	if n < 2 {
		return false
	} else if n == 2 {
		return true
	} else if n % 2 == 0 {
		return false
	}

	sqrtN := int(math.Sqrt(float64(n)))
	for i := 3; i <= sqrtN; i += 2 {
		if n % i == 0 {
			return false
		}
	}

	return true
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


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

  Int N;
  cin>>N;

  Int s = 0;
  for(Int i=0;i<=N;i++){
    if(i%3 == 0) continue;
    if(i%5 == 0) continue;
    s += i;
  }

  cout<<s<<endl;

  return 0;
}


Measured memory_bytes: 3648
import sys


def read():
    return sys.stdin.readline()


def main():
    n = int(read())
    d = [0] * n
    present = [[] for i in range(n)]
    for i in range(n - 1):
        u, v = sorted(map(lambda x: int(x) - 1, read().split()))
        d[v] += 1
        present[u].append(v)
    ans, cur = 0, 0
    for v in range(n):
        cur += (n - v) * d[v]
    for L in range(n):
        ans += (L + 1) * (L + 2) // 2 - cur
        for v in present[L]:
            cur -= (n - v)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 97932
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  string s;
  int q;
  cin >> s >> q;
  bool order = true;
  string f, b;
  REP(i, q){
    int t;
    cin >> t;
    if(t == 1){
      order = !order;
    }else{
      char c;
      cin >> t >> c;
      if(t == 1){
        if(order) f += c;
        else b += c;
      }else{
        if(order) b += c;
        else f += c;
      }
    }
  }

  s += b;
  reverse(ALL(s));
  s += f;
  if(order) reverse(ALL(s));
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 1348
#include <iostream>
#include <set>
using namespace std;
set < pair <int, int> > s;
int main(){
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= k; ++ i){
		int x, y;
		cin >> x >> y;
		s.insert(make_pair(x, y));
	}
	int cnt = 0, ans = n;
	for (set < pair <int, int> > :: iterator it = s.begin(); it != s.end(); ++ it){
		int x = (*it).first, y = (*it).second;
		if (x - y == cnt)
			++ cnt;
		if (x - y > cnt)
			ans = min(ans, x - 1);
	}
	cout << ans << endl;
}


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

int main(){
    int n;
    cin>>n;
    int vec[n]={};

    for(int i=0;i<n;i++){
        cin>>vec[i];
    }
    for(int i=n-1;i>=0;i--){
        cout<<vec[i];
        if(i!=0) cout<<" ";
    }
    cout<<endl;
}



Measured memory_bytes: 3120
#include<stdio.h>
int main(void){
	int a, b, n, i;
	while(scanf("%d %d", &a, &b) != EOF){
		n = a+b;
		for(i=0;n;i++){
			n/=10;
		}
		printf("%d\n", i);
	}
	return 0;
}

Measured memory_bytes: 1028
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
f=lambda:map(int,input().split())
N,M,K=f()
uf=UnionFind(N)
bro=[0]*(N+1)
AB=[]
for _ in [0]*M:
    a,b=f()
    AB.append((a,b))
    uf.unite(a,b)
for a,b in AB:
    if uf.is_same_group(a,b):
        bro[a]+=1
        bro[b]+=1
for _ in [0]*K:
    c,d=f()
    if uf.is_same_group(c,d):
        bro[c]+=1
        bro[d]+=1
for i in range(1,N+1):
    print(uf.count(i)-1-bro[i])

Measured memory_bytes: 90904
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int x = 0;
        int[] ans = new int[2];
        while(x < n){
            ans[0] += b;
            x += a;
        }
        x = 0;
        while(x < n){
            ans[1] += d;
            x += c;
        }
        System.out.println(Math.min(ans[0], ans[1]));
    }
}



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

#define CK(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)
#define F first
#define S second
#define ll long long;

const int INF = 1e9;
const long long  LLINF = 1e15;

using namespace std;

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

int W,H,sy,sx,dustsNum;
string C[25];

int dp[25][25][1050];
map<pair<int,int>, int> m;

/*
void dfs(int y, int x, int state, int step){
  if(dp[y][x][state] <= step) return;
  dp[y][x][state] = step;

  if(state == 0) return;

  REP(k,0,4){
    int nextY = y + dy[k], nextX = x + dx[k];
    if(!CK(nextY,0,H) || !CK(nextX,0,W)) continue;
    if(C[nextY][nextX] == 'x') continue;

    if(C[nextY][nextX] == '*'){
      int dust = m[make_pair(nextY,nextX)];
      dfs(nextY, nextX, state&~(1<<dust), step+1);
    }else{
      dfs(nextY, nextX, state, step+1);
    }

  }
}
*/

int main() {
  while(1){
      cin>>W>>H;
      if(W==0&&H==0) break;
      dustsNum=0;
      m.clear();
      REP(i,0,H){
        cin>>C[i];
        REP(j,0,W){
          if(C[i][j] == 'o') sy = i, sx = j;
          if(C[i][j] == '*'){
            m[make_pair(i,j)] = dustsNum;
            dustsNum++;
          }
        }
      }
      REP(i,0,H)REP(j,0,W){
        REP(k,0,(1<<dustsNum)){
          dp[i][j][k] = INF;
        }
      }


/*
      dfs(sy, sx, (1<<dustsNum)-1, 0);

      int ans = INF;
      REP(i,0,H)REP(j,0,W){
        ans = min(ans, dp[i][j][0]);
      }

      if(ans == INF) cout<<-1<<endl;
      else cout<<ans<<endl;
*/

    priority_queue<pair< pair<int,int>, pair<int,int> > > PQ;  //step, state, Y, X
    PQ.push(make_pair(make_pair(0,(1<<dustsNum)-1), make_pair(sy, sx)));

    while(!PQ.empty()){
      int nowStep = (-1)*PQ.top().F.F;
      int nowState = PQ.top().F.S;
      int nowY =PQ.top().S.F, nowX = PQ.top().S.S;
      PQ.pop();

      if(dp[nowY][nowX][nowState] <= nowStep) continue;
      dp[nowY][nowX][nowState] = nowStep;

      REP(k,0,4){
        int nextY = nowY + dy[k], nextX = nowX + dx[k];
        if(!CK(nextY,0,H) || !CK(nextX,0,W)) continue;
        if(C[nextY][nextX] == 'x') continue;

        if(C[nextY][nextX] == '*'){
          int dust = m[make_pair(nextY,nextX)];
          PQ.push(make_pair(make_pair((-1)*(nowStep+1), nowState&~(1<<dust)), make_pair(nextY, nextX)));
        }else{
          PQ.push(make_pair(make_pair((-1)*(nowStep+1), nowState), make_pair(nextY, nextX)));
        }
      }
    }

    int ans = INF;
    REP(i,0,H)REP(j,0,W){
      ans = min(ans, dp[i][j][0]);
    }

    if(ans == INF) cout<<-1<<endl;
    else cout<<ans<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 5192
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,q,x;
int nex[maxn*2],to[maxn*2],head[maxn];
ll sum[maxn];
int tot=0;
void add(int u,int v)
{
    to[++tot]=v,nex[tot]=head[u],head[u]=tot;
}
void dfs(int u,int fa)
{
    sum[u]+=sum[fa];
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];
        if(v==fa)
            continue;
        dfs(v,u);
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        sum[a]+=b;
    }
    dfs(1,0);
    printf("%lld",sum[1]);
    for(int i=2; i<=n; i++)
        printf(" %lld",sum[i]);
}


Measured memory_bytes: 14080
import java.util.Map.Entry;
import java.util.*;
 
//import org.w3c.dom.css.Counter;
 
public class Main {
//public class App {
 
    public static void main(final String[] args){
     //スキャン
     final Scanner s = new Scanner(System.in);
      int N = Integer.parseInt(s.next());
      int X = Integer.parseInt(s.next());
      int T = Integer.parseInt(s.next());
      int ans = N /X;
      if(N%X !=0){ans ++;}
      System.out.println(ans*T);
    }
}


Measured memory_bytes: 35604
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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

const long long INF = 100000000;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
int h,w, n, m;
char maze[60][60];
int dis[60][60];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
	int a[5];int b[5];int c[5];
	rep(i, 5) {
		cin >> a[i];
		b[i] = 10-(a[i] % 10);
		if (b[i] == 10) {
			b[i] = 0;
		}
		c[i] = a[i] + b[i];
	}
	int res = INF;
	for (int i = 0;i < 5;i++) {
		int f = 0;
		for (int j = 0;j < 5;j++) {
			if (i == j) {
				f += a[j];
			}
			else {
				f += c[j];
			}
		}
		chmin(res, f);
	}
	
	cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int inf = 1012345678;
int main(){
    vector<int> A(5);
	cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4];
	vector<int> P = { 0, 1, 2, 3, 4 };
	int final_answer = inf;
	do {
		int ans = 0;
		for (int i = 0; i < 5; ++i) {
			while (ans % 10 != 0) ans += 1;
			ans += A[P[i]];
		}
		final_answer = min(final_answer, ans);
	} while (next_permutation(P.begin(), P.end()));
	cout << final_answer << endl;
	return 0;
}




Measured memory_bytes: 256
//import java.util.ArrayList;
import java.util.*;
//import java.lang.*;
import java.util.regex.*;
 class Main{
     public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String str=sc.next();
        if(Pattern.matches("[A-Z]", str)){
            System.out.print('A');
        }else{
            System.out.print('a');
        }
    }
}


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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//実行部
void Main()
{
  str s; cin >> s;
  ll ans = 1;
  vs flag(s.size());
  flag[0] = s.substr(0, 1);
  ll q = 1;
  for(ll i = 1;i < s.size();i++)
  {
    flag[q] = s.substr(i, 1);
    if(flag[q] == flag[q - 1])
    {
      flag[q] = s.substr(i, 2);
      i++;
    }
    q++;
  }
  if(flag[q - 1] == flag[q - 2]) q--;
  fin(q)
  return;
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}

/*
//test時
  g++ test.cpp -o test;./test
*/


Measured memory_bytes: 11028
#include <bits/stdc++.h>
#define ll long long int
#define dbg(x) cout<<"( "<<#x<<" -> "<<x<<" )"<<endl;
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    map<int,int> mp;
    for (int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        mp[a[i]]++;
    }
    ll sum1=0;
    for (auto it=mp.rbegin();it!=mp.rend();it++)
    {
        mp[it->first]=mp[it->first]*2;
        int mini=min(n,mp[it->first]);
        sum1=sum1+1LL*(it->first)*mini;
        n=n-mini;
        if (n==0)
        break;
    }
    auto it1=mp.rbegin();
    sum1=sum1-(it1->first);
    printf("%lld\n",sum1);
    return 0;
}

Measured memory_bytes: 13900
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i< (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
//long long ccw(const Point& A, const Point& B, const Point& C) {
//	return 1LL * (B.x - A.x)*(C.y - A.y) - 1LL * (B.y - A.y)*(C.x - A.x);
//}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string a, b; cin >> a >> b;
	int n = a.size();

	rep(i, n) {
		int j = 0;
		int l = i;
		if (a[l] == b[j]) {
			l = (i + 1) % n;
			j += 1;
			bool f = false;
			while (l != i) {
				if (a[l] != b[j]) { f = true; break; }
				l = (l + 1) % n;
				j += 1;
			}
			if (!f) {
				cout << "Yes" << '\n'; return 0;
			}
		}
	}

	cout << "No" << '\n';


}

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

int main()
{
    int64_t N;
    cin >> N;
    vector<int64_t> L(N + 1);
    L.at(0) = 2;
    L.at(1) = 1;
    for (int i = 0; i < (int)(L.size() - 2); i++)
    {
        L.at(i + 2) = L.at(i) + L.at(i + 1);
    }
    cout << L.at(N) << endl;
}

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

int main()
{
    ll a,b,k;
    cin>>a>>b>>k;
    if(k>=a+b) cout<<0<<" "<<0;
    else if(k>=a) cout<<0<<" "<<b-(k-a);
    else  cout<<a-k<<" "<<b;
    return 0;
}


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

int A,B,K;

int main() {
    cin>>K>>A>>B;
    string ans="NG";
    for (int i=A; i<=B; i++) {
        if (i%K==0) ans="OK";
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3620
/**
 * Created by abhishek on 8/22/2016.
 */
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        long dp[][][] = new long[n + 1][n + 1][2505];
        dp[0][0][0] = 1;
        int array[] = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1;i <= n;i++)
            array[i] = Integer.parseInt(st.nextToken());
        for(int i = 1;i <= n;i++){
            for(int j = 0;j <= n;j++){
                for(int k = 0;k < 2505;k++){
                    dp[i][j][k] += dp[i - 1][j][k];
                    if(j >= 1 && k >= array[i])
                    dp[i][j][k] += dp[i - 1][j - 1][k - array[i]];
                }
            }
        }
        long ans = 0;
        for(int i = 0;i <= n;i++){
            ans += dp[n][i][i*a];
        }
        System.out.print(ans - 1);
    }
}


Measured memory_bytes: 60372
import sys
sys.setrecursionlimit(200000)

N = int(input())

neighbors = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    neighbors[u].append((v, w))
    neighbors[v].append((u, w))

ans = [None for _ in range(N)]


def dfs(v, p, c):
    ans[v - 1] = c
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else 1 - c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans:
    print(e)


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

int main()
{
    int N;

    cin >> N;

    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            if (N == (i * j))
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256