akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
  double a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  a *= 100; b *= 100;
  vector<double> water, sugar;
  rep(i, f+1){
    if(i * a > f) break;
    rep(j, f+1){
      double add = i*a + j*b;
      if(add <= f) water.push_back(add);
      else break;
    }
  }
  rep(i, f+1){
    if(i * c > f) break;
    rep(j, f+1){
      double add = i*c + j*d;
      if(add <= f) sugar.push_back(add);
      else break;
    }
  }
  double ap = 0;
  pair<double, double> ans;
  for(double wa : water){
    for(double su : sugar){
      if(wa + su == 0) continue;
      double p = su/(wa+su);
      if(p <= e/(100.+e) && wa + su <= f){
        if(ap <= p){
          ap = p;
          ans = make_pair(wa, su);
        }
      }
    }
  }
  int a1 = ans.first + ans.second, a2 = ans.second;
  cout << a1 << " " << a2 << endl;
  return 0;
}

Measured memory_bytes: 2420
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  string S;
  cin >> S;
  ll win = 0;
  int k = S.length();
  for (int i = 0; i < k; i++) {
    if (S[i] == 'o') {
      win++;
    }
  }
  string ans = ((15 - k) + win >= 8) ? "YES" : "NO";
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3592
N,M= map(int,input().split())
_input = []
for i in range(M):
    _input.append(list(map(int,input().split())))

counters = [0 for i in range(N)]

for i in range(len(_input)):
    counters[_input[i][0]-1] += 1
    counters[_input[i][1]-1] += 1

for i in range(N):
    print(counters[i])

Measured memory_bytes: 3064
#include<stdio.h>
int main(void)
{
    int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if (a==1&&b==0&&c==0||a==0&&b==1&&c==0||a==0&&b==0&&c==0){
	    printf("Close\n");
	}
	else if (a==0&&b==0&&c==1||a==1&&b==1&&c==0){
	    printf("Open\n");
	}
	return 0;
}
	

Measured memory_bytes: 1012
#include<stdio.h>
int main(void){
  int n;
    scanf("%d",&n);
    if(n%10==3){
      printf("bon\n");
    }else if(n%10==0||n%10==1||n%10==6||n%10==8){
      printf("pon\n");
    }else{
      printf("hon\n");
    }
    return 0;
}


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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q>
ostream& operator << (ostream& os, pair<P, Q> p)
{
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template<typename T>
ostream& operator << (ostream& os, vector<T> v)
{
  os << "(";
  each (i, v) os << i << ", ";
  os << ")";
  return os;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  while (cin >> n >> k) {
    cout << bool(n % k) << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int H,W;
	while(1){
		scanf("%d %d",&H,&W);
		if(H==0&&W==0){
			break;
		}
		for(int x=0;x<H;x++){
			for(int y=0;y<W;y++){
				printf("#");
			}
printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 2620
n,*d = map(str, open(0).read().split())
AC,WA,TLE,RE=0,0,0,0

for i in range(int(n)):
    if d[i]=="AC":
        AC+=1
    if d[i]=="WA":
        WA+=1
    if d[i]=="TLE":
        TLE+=1
    if d[i]=="RE":
        RE+=1

print("AC x {}".format(AC))
print("WA x {}".format(WA))
print("TLE x {}".format(TLE))
print("RE x {}".format(RE))

Measured memory_bytes: 17324
# -*- coding: utf-8 -*-
M, D = map(int, input().split())
cnt = 0

for i in range(1, M + 1):
	for j in range(1, D + 1):
		j = str(j).zfill(len(str(D)))

		if int(j[0]) >= 2 and int(j[1]) >=2:

			if int(j[0]) * int(j[1]) == i:
				#print(i,j)
				cnt += 1

print(cnt)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep2(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) rep2(i,0,n)
#define FOR(i) for(cin>>i;i>0;i--)
#define elif else if
#define pb push_back
#define ll long long
#define mp make_pair
#define all(x) x.begin(),x.end()
#define re(x) {cout<<x<<endl;return 0;}
//#define x first
//#define y second

using namespace std;
int a,b,n,d[111]={0};
int main()
{
	cin>>n;
	rep2(i,1,n+1)
	{
		cin>>a>>b;
		d[i]=d[i-1];
		if(a==b) d[i]++;
	}
	rep(i,n-2)
	{
		if(d[i+3]-d[i]==3) re("Yes")
	}
	re("No")
	return 0;}

Measured memory_bytes: 3624
# -*- coding: utf-8 -*-
"""
A - Digit Sum 2
https://atcoder.jp/contests/agc021/tasks/agc021_a

"""
import sys


def calc_digit_sum(s):
    return sum([int(ch) for ch in s])

def solve(N):
    l = len(N)
    all_nine = True
    res = []
    for i, n in enumerate(N[::-1], start=1):
        if i != l:
            if n != '9':
                all_nine = False
            res.append('9')
        else:
            res.append(str(int(n)-1))

    if all_nine or l == 1:
        return calc_digit_sum(N)
    return calc_digit_sum(res)



def main(args):
    N = input()
    ans = solve(N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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

using namespace std;
#define int long long
const int N = 2e5 + 10, inf = 1e9, MOD = 1e9 + 7;
int a[N], sz[N], n, ans, X;
vector <int> g[N];

int Pow(int a, int m)
{
    if (m == 0) return 1;
    int x = Pow(a, m / 2);
    return ( ((x * x) % MOD) * (m % 2 ? a : 1) ) % MOD;
}

int dfs(int v, int p = 0)
{
    sz[v] = 1;
    vector <int> vec;
    for (int u : g[v]) if (u != p) {
        dfs(u, v);
        sz[v] += sz[u];
        vec.push_back(sz[u]);
    }
    vec.push_back(n - sz[v]);
    int val = 0;
    for (int i : vec) {
        val = (val + Pow(X, n - i - 1) - Pow(X, n - 1) + MOD) % MOD;
    }
    val = (val + Pow(X, n - 1)) % MOD;
    ans = (ans + X * (1 - val + MOD)) % MOD;
}

int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    X = Pow(2, MOD - 2);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    cout << ans << "\n";
}


Measured memory_bytes: 31104
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60;
const ll mod=1e9+7 ;
struct edge{int to;ll cap;int rev;};
int main(){
    // ll N;
    vector<ll> h,dp;
    ll N,K;
    cin>>N>>K;
    dp.resize(N+1);
    h.resize(N);
    rep(i,N+1)dp[i]=inf;
    rep(i,N) cin>>h[i];
    dp[0] = 0;
    REP(i,1,N) REP(j,max(0LL,i-K),i) dp[i] = min(dp[i],dp[j]+(ll)abs(h[i]-h[j]));
    // rep(i,N) cout<<dp[i]<<endl;
    cout<<dp[N-1]<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using ull=unsigned long long;
constexpr auto inf=static_cast<ll>(1e18);
template<typename T=ll>inline T in(){T ret;cin>>ret;return ret;}
template<typename T=ll>inline auto vec2(size_t h,size_t w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}
inline void setp(int n){cout<<fixed<<setprecision(n);}
inline void delnl(){cin.ignore(numeric_limits<streamsize>::max(),'\n');}

int main()
{
    string s;cin>>s;
    cout<<(
        s=="AKIHABARA"||
        s=="AKIHABAR"||
        s=="AKIHABRA"||
        s=="AKIHABR"||
        s=="AKIHBARA"||
        s=="AKIHBAR"||
        s=="AKIHBRA"||
        s=="AKIHBR"||
        s=="KIHABARA"||
        s=="KIHABAR"||
        s=="KIHABRA"||
        s=="KIHABR"||
        s=="KIHBARA"||
        s=="KIHBAR"||
        s=="KIHBRA"||
        s=="KIHBR"?"YES":"NO")<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <stack>

using namespace std;
typedef long long ll;

#define MAX_N 1000000
#define INF 1000000

int A[MAX_N];

int main() {

  // ---------------------
  // Input
  
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

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

  // ---------------------
  // 


  
  for (int i = 0; i < N; i++) {
    
    if (A[i] % 2 == 0) {
      if ( (A[i] % 3 != 0) && (A[i] % 5 != 0) ) {
	cout << "DENIED" << endl;
	return 0;
      }
    }
    
  }

  cout << "APPROVED" << endl;


  return 0;
  
}


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

int main() {
  int x[5], k;
  for (int i = 0; i < 5; i++)
  {
    cin >> x[i];
  }
  cin >> k;
  for (int i = 0; i < 5; i++)
  {
    for (int j = i + 1; j < 5; j++)
    {
      if (x[j] - x[i] > k)
      {
        cout << ":(" << endl;
        return 0;
      }
      
    }
  }
  
  cout << "Yay!" << endl;
  return 0;
}


Measured memory_bytes: 3680
N, X, Y = map(int, input().split())
count = [0]*N
for i in range(1, N):
    for j in range(i+1, N+1):
        if i <= X and Y <= j:
            # print(i, j, j-i-(Y-X)+1)

            count[j-i-(Y-X)+1] += 1
        else:
            # print(i, j, j-i)
            # min((j-i), abs(X-i)+abs(Y-j)+1)

            count[min((j-i), abs(X-i)+abs(Y-j)+1)] += 1
for c in count[1:]:
    print(c)

Measured memory_bytes: 47068
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;

int main(){
  
  Int A, B, K, x, y;
  cin >> A >> B >> K;
  
  if (A >= K) {
    x = A - K;
    y = B;
  }
  else if (B >= (K - A)) {
    x = 0;
    y = B - (K - A);
  }
  else {
    x = 0;
    y = 0;
  }
  
  cout << x << " " << y << endl;
}

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

import bisect

N = int(input())
indexess = [[] for _ in range(26)]

S = list(input())
for i, s in enumerate(S):
    indexess[ord(s) - 97].append(i)


Q = int(input())
for _ in range(Q):
    q1,q2, q3 = input().split()
    q2 = int(q2)

    if q1 == '1':
        s0 = S[q2-1]
        if s0 != q3:
            S[q2-1] = q3
            
            indexes = indexess[ord(s0) - 97]
            del indexes[bisect.bisect_left(indexes, q2-1)]
            bisect.insort(indexess[ord(q3) - 97], q2-1)

    else:
        cnt = 0
        q3 = int(q3)
        for indexes in indexess:
            
            if bisect.bisect_left(indexes, q2-1) < bisect.bisect_right(indexes, q3-1):
                cnt += 1

        print(cnt)


Measured memory_bytes: 29448
use std::io::*;
use std::str::FromStr;

fn main() {
	let k: u32 = read();
	let (a,b): (u32, u32) = (read(), read());
	for i in a..b+1 {
		if i % k == 0 {
			println!("OK");
			return ();
		}
	}
	println!("NG");
}

fn read<T: FromStr>() -> T {
	let stdin = stdin();
	let stdin = stdin.lock();
	let token: String = stdin
		.bytes()
		.map(|c| c.expect("failed to read char") as char)
		.skip_while(|c| c.is_whitespace())
		.take_while(|c| !c.is_whitespace())
		.collect();
	token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 2108
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		while(true) {
			int n = stdIn.nextInt();
			int q = stdIn.nextInt();
			if(n == 0 && q == 0) break;
			int[] list = new int[101];
			for(int i = 0; i < n; i++) {
				int m = stdIn.nextInt();
				for(int j = 0; j < m; j++) {
					list[stdIn.nextInt()]++;
				}
			}
			int max = 0;
			int id = 0;
			for(int i = 0; i < 101; i++) {
				if(list[i] > max) {
					max = list[i];
					id = i;
				}
			}
			if(max < q) {
				System.out.println(0);
			}
			else {
				System.out.println(id);
			}
		}
	}
 }

Measured memory_bytes: 62520
#include <bits/stdc++.h>
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; }
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // 移動方向

ll N, T;
ll t[200010];

void input(){
    cin >> N >> T;
    for(int i=0;i<N;++i) cin >> t[i];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    ll sum = 0;
    for(int i=0;i<N-1;++i){
        if((t[i+1] - t[i]) > T) sum += T;
        else sum += (t[i+1] - t[i]);
    }
    sum += T;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1792
n = gets.to_i

xs = []

n.times{
	x, l = gets.split.map &:to_i
	xs << [x - l, x + l]
}

xs.sort!{ |a, b|
	if a[1] != b[1] then
		a[1] <=> b[1]
	else
		a[0] <=> b[0]
	end
}

count = 1

memo = xs[0]

xs[1..-1].each{ |x|
	if x[0] != memo[0] && x[0] >= memo[1] then
		count += 1
		memo = x
	end
}

puts count


Measured memory_bytes: 12048
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <cmath>
using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// 0 <= unsigned int <= 4.2e9

int main()
{
    ullong N, A, B;
    cin >> N >> A >> B;
    if (A == 0) {
        cout << 0 << endl;
        return 0;
    }
    ullong numSetAB = N / (A + B);
    ullong numA = numSetAB * A;
    ullong r = N % (A + B);
    numA = numA + min(r, A);
    cout << numA << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = sc.nextLong();
        long ans = b/x - a/x;
        if(a % x == 0) ans++;
        System.out.println(ans);
    }
}


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

typedef long long ll;
typedef long double ld;

using namespace std;

#define rep(i,n) for(auto i=0*(n);i<(n);++i)

int main(){
    while(true){
        ll m, n;
        cin >> m >> n;
        if(m==0 && n == 0) break;
        vector<string> a(n);
        rep(i,n) cin >> a[i];
        
        using P = bitset<128>;
        vector<P> yes(m), no(m);
        rep(i, m) rep(j, n) yes[i][j] = a[j][i] == '1';
        rep(i, m) rep(j, n) no[i][j] = a[j][i] == '0';
        
        map<ll, ll> cost;
        function<ll(P, vector<int> &)> dfs = [&](P x, vector<int> & used) {
            //cout << x.to_string() << endl;
            //rep(i, m) cout << used[i] << " ";
            //cout << endl;
            
            if (x.count() <= 1) return 0ll;
            
            ll id = 0; rep(i, n) { id *= 3; id += used[i]; }
            if(cost.find(id) != cost.end()) return cost[id];
            ll ans = 1e16;
            rep(i, m) {
                if (used[i] != 0) continue;
                ll ma = 0;
                used[i] = 1;
                ma = max(ma, dfs(x & no[i], used));
                used[i] = 2;
                ma = max(ma, dfs(x & yes[i], used));
                used[i] = 0;
                ans = min(ans, ma);
            }
            assert(ans != 1e16);
            return cost[id] = ans + 1;
        };
        
        P x; rep(i, n) x[i] = 1;
        vector<int> used(m, 0);
        cout << dfs(x, used) << endl;
    }
        
    return 0;
}

Measured memory_bytes: 24500
#include "bits/stdc++.h"
using namespace std;
int a,b,c;
int n;
int main(){
cin>>n;
pair<int,int> p[n];
for (int i = 0; i < n; ++i) {
	cin>>a>>b;
	p[i].second=a;p[i].first=-b;
}
sort(p,p+n);
cout<<p[0].second<<" "<<-p[0].first<<endl;
//cout<<p[n-1].second<<" "<<-p[n-1].first<<endl;
}

Measured memory_bytes: 3088
import numpy as np
import collections

Robot = collections.namedtuple('Robot', ['l', 'r'])

N = int(input())
MOD = 998244353
robots = []
for _ in range(N):
    x, d = map(int, input().split())
    robots.append(Robot(x, x + d))
robots.sort()

robots.append(Robot(10**10, 10**10 + 1))
stack = [N]

dp = np.zeros(N + 1, dtype=int)
dp[N] = 1

for i in range(N - 1, -1, -1):
    # For each i, we want the stack contains all the j such that
    # robots[j] is not affected by robot[i], therefore
    # we remove those robots that are intersected with robot[i]
    while robots[stack[-1]].l < robots[i].r:
        stack.pop()

    # dp[i] = dp[i + 1] (not activate robot i) + dp[j] (activate robot i)
    j = stack[-1]
    dp[i] = (dp[i + 1] + dp[j]) % MOD
    stack.append(i)

print(dp[0])

Measured memory_bytes: 59696
#include<stdio.h>
#include<string.h>
main(){
  int n,i=0,l,j;
  char str[1500];
  
  scanf("%d ",&n);
  for(j=0;j<n;j++){
    fgets(str,1100,stdin);
  for(i=0;str[i]!='\n';i++){
    if(str[i]=='H'&&str[i+1]=='o'&&str[i+2]=='s'&&str[i+3]=='h'&&str[i+4]=='i'&&str[i+5]=='n'&&str[i+6]=='o'){
      str[i+6]='a';
    }
  }
  for(i=0;str[i+1]!='\0';i++){
  printf("%c",str[i]);
    }
  puts("");
  }
  return 0;
}

Measured memory_bytes: 584
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
    u,k,*v = x
    for y in v:
        graph[u].append(y)
seen = [0]*(n+1) #1_indexed
stack = []
time = 0
seentime = [0]*(n+1) #1_indexed
donetime = [0]*(n+1) #1_indexed
def dfs(j):
    global time
    seen[j] = 1
    stack.append(j)
    time += 1
    seentime[j] = time
    while stack:
        s = stack[-1]
        if not graph[s]:
            stack.pop()
            time += 1
            donetime[s] = time
            continue
        g_NO = graph[s].popleft()
        if seen[g_NO]:
            continue
        seen[g_NO] = 1
        stack.append(g_NO)
        time += 1
        seentime[g_NO] = time
for j in range(1,n+1):
    if seen[j]:
        continue
    dfs(j)
for k,a,b in zip(range(1,n+1),seentime[1:],donetime[1:]):
    print(k,a,b)


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

int main() {
  int A;
  cin >> A;
 
    if(A % 10 == 2 ||A % 10 == 4 ||A % 10 == 5 ||A % 10 == 7 ||A % 10 == 9){
      cout << "hon" << endl;
    }
  
  if(A % 10 == 3){
    cout << "bon" << endl;
  }
  
  if(A % 10 == 0 || A % 10 == 1 || A % 10 == 6 || A % 10 == 8){
    cout << "pon" << endl;
  }
}


Measured memory_bytes: 3624
def win_cou(n,m):
    cou = 0
    while m > n:
        n = n * 2
        cou = cou + 1
    return cou



Input = input().split()
N = int(Input[0])
K = int(Input[1])
rate = 0

for i in range(N):
    rate = rate + 2 ** (win_cou(i+1,K)*(-1)) / N

print(rate)


Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define int long long
#define _GLIBCXX_DEBUG
int INF = 1e9+7;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
unsigned day;
if(dow < dow1) dow += 7;
day = dow - dow1;
day += 7 * n - 6;
return day;
}
unsigned DayToWeekNumber(unsigned day)
{
  return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
  return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
signed main(){
  int N,A,B; cin>>N>>A>>B;
  cout<<(N/(A+B))*A+min(N%(A+B),A)<<endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

template <typename T>
pair<T, vector<vector<T> > >
edmonds_karp(const vector<vector<T> >& capacity, int source, int sink)/*{{{*/
{
  const int N = capacity.size();
  vector<vector<T> > flow(N, vector<T>(N, 0));
  T max_flow = 0;

  while (true) {
    vector<int> parent(N, -1);
    queue<int> q;
    q.push(source);

    while (!q.empty() && parent[sink] < 0) {
      const int v = q.front();
      q.pop();

      for (int u = 0; u < N; u++) {
        if (parent[u] < 0 && capacity[v][u] - flow[v][u] > 0) {
          parent[u] = v;
          if (u == sink) {
            break;
          }
          q.push(u);
        }
      }
    }

    if (parent[sink] < 0) {
      break;
    }

    T aug = numeric_limits<T>::max();
    for (int v = sink; v != source; v = parent[v]) {
      const int u = parent[v];
      aug = min(aug, capacity[u][v] - flow[u][v]);
    }
    max_flow += aug;
    for (int v = sink; v != source; v = parent[v]) {
      const int u = parent[v];
      flow[u][v] += aug;
      flow[v][u] -= aug;
    }
  }

  return make_pair(max_flow, flow);
}/*}}}*/

int main()
{
  int N, M;
  cin >> N >> M;
  vector<vector<int> > capacity(N, vector<int>(N, 0));
  vector<pair<int,int> > edges;
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    --u;  --v;
    ++capacity[u][v];
    ++capacity[v][u];
    edges.push_back(make_pair(u, v));
  }
  int S, T;
  cin >> S >> T;
  --S;  --T;

  const pair<int, vector<vector<int> > > r = edmonds_karp(capacity, S, T);
  cout << r.first << endl;
  vector<int> ans;
  const vector<vector<int> >& flow = r.second;
  for (int i = 0; i < M; i++) {
    if (flow[edges[i].second][edges[i].first] > 0) {
      ans.push_back(i);
    }
  }
  cout << ans.size() << endl;
  for (vector<int>::const_iterator it = ans.begin(); it != ans.end(); ++it) {
    cout << *it+1 << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int d[60][200010];
int main(){
	long long n,k;
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&d[0][i]);
	for(int x=1;x<60;x++)for(int i=1;i<=n;i++)d[x][i]=d[x-1][d[x-1][i]];
	int pos=1;
	for(int x=59;x>=0;x--)if((k>>x)&1)pos=d[x][pos];
	printf("%d",pos);
}

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

#define int long long
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
#define vi vector < int >
#define pii pair < int, int >

const int K = 1e5 + 7;
const int N = 107;
const int mod = 1e9 + 7;

int a[N], pr[N][K + 1], ar[N][K + 1];
int n, k;

main (){
    fill(pr[0], pr[0] + K + 1, 1);
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        for (int j = K; j >= 0; j--){
            ar[i][j] = pr[i - 1][j];
            if (j - a[i] - 1 >= 0){
                ar[i][j] = (ar[i][j] - pr[i - 1][j - a[i] - 1] + mod) % mod;
            }
        }
        pr[i][0] = ar[i][0];
        for (int j = 1; j <= K; j++){
            pr[i][j] = pr[i][j - 1] + ar[i][j];
            pr[i][j] %= mod;
        }
    }
    cout << ar[n][k];
}


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

int main(){
    int N; cin >> N;
    int ans = 0;
    for( int i = 1; i <= N; i++ ){
        if( (int)floor(log10( (float)i ) ) % 2 == 0 ) ans++;
    }

    cout << ans << endl;
}

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

int main() {
  int n;
  cin >> n;
  if (n % 10 == 2 || n % 10 == 4 || n % 10 == 5 || n % 10 == 7 || n % 10 == 9) {
    cout << "hon" << endl;
  }
  else if (n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) {
    cout << "pon" << endl;
  }
  else {
    cout << "bon" << endl;
  }
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define ll long long

using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    ll n; cin>>n;
    ll d; cin>>d;
    ll c=0;
    for(ll i=0;i<n;i++)
    {
        ll x,y; cin>>x>>y;
        if(sqrt(x*x+y*y)<=d)
        c++;
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 3696
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define inf 1e+9
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define msg(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define pri(a) cout << a << endl;

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

  ll n,k,ans=0,ans1=0;
  cin >> n >> k;
  ll s[k],c[k];
  rep(i,k){
    cin >> s[i] >> c[i];
  }

  rep(i,k){
    rep(j,k){
      if(n==3 && s[j]==1 && c[j]==0){
        pri("-1");
        return 0;
      }
      else if(n==2 && s[j]==1 && c[j]==0){
        pri("-1");
        return 0;
      }
      else if(i==j){
        ans1++;
      }
      else if(n==3 && c[j]==0 && s[j]!=3 && s[j]!=0){
        pri("-1");
        return 0;
      }
      else if(n==2 && c[j]==0 && s[j]==1){
        pri("-1");
        return 0;
      }
      else if(s[i]==s[j] && c[i]!=c[j]){
        pri("-1");
        return 0;
      }
      else if(s[i]==s[j] && c[i]==c[j]){
        s[i] = 0;
        c[i] = 0;
      }
    }
  }


  // rep(i,k){
  //   cout << s[i] << c[i];
  // }


  rep(i,k){
    if(n==3){
      if(s[i]==1){
        ans += 100*c[i];
      }
      else if(s[i]==2){
        ans += 10*c[i];
      }
      else{
        ans += c[i];
      }
    }
    else if(n==2){
      if(s[i]==1){
        ans += 10*c[i];
      }
      else{
        ans += c[i];
      }
    }
    else{
      ans += c[i];
    }
  }

  if(n==3 && ans/100==0){
    ans += 100;
  }
  else if(n==2 && ans/10==0){
    ans += 10;
  }

  pri(ans);

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define f first
	#define s second
	
	using namespace std;

	vector<vector<ll>> v;
	ll dp[3][100005] = {0};


	ll maxPoints(vector<vector<ll> > &v,ll n, ll i, bool A, bool B, bool C) {
		if(i == n-1) {
			if(C) {
				return max(v[i][0],v[i][1]);
			}
			else if(B) {
				return max(v[i][0],v[i][2]);
			}
			else {
				return max(v[i][1],v[i][2]);	
			}
		}

		if(A) {
				if(!dp[1][i]) {
					dp[1][i] = v[i][1] + maxPoints(v,n,i+1,false,true,false);
				}
				if(!dp[2][i]) {
					dp[2][i] = v[i][2] + maxPoints(v,n,i+1,false,false,true);
				}
				return max(dp[1][i],dp[2][i]);
			
		}

		else if(B) {
			if(!dp[0][i]) {
				dp[0][i] = v[i][0] + maxPoints(v,n,i+1,true,false,false);
			}
			if(!dp[2][i]) {
				dp[2][i] = v[i][2] + maxPoints(v,n,i+1,false,false,true);
			}
			return max(dp[0][i],dp[2][i]);
		}

			if(!dp[0][i]) {
				dp[0][i] = v[i][0] + maxPoints(v,n,i+1,true,false,false);
			}
			if(!dp[1][i]) {
				dp[1][i] = v[i][1] + maxPoints(v,n,i+1,false,true,false);
			}
			return max(dp[0][i],dp[1][i]);


	}

	int main()
	{
		std::ios::sync_with_stdio(false);
		
		ll n;
		cin>>n;

		

		for(ll i=0; i<n; i++) {
			ll a,b,c;
			cin>>a>>b>>c;
			v.push_back({a,b,c});
		}

		

		cout<<max(maxPoints(v,n,0,true,false,false), max(maxPoints(v,n,0,false,true,false), maxPoints(v,n,0,false,false,true)))<<endl;

		return 0;
	}


Measured memory_bytes: 14768
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

A = input()
Ac = Counter(A)
cnt = 0
# 前からdp等して数え上げするか
# グルーピングして掛け算するか

# A = 'babab'だった場合
# (1, 2):abbab
# (1, 3):babab
# (1, 4):ababb
# (1, 5):babab

# (2, 3):bbaab
# (2, 4):babab
# (2, 5):bbaba

# (3, 4):babba
# (3, 5):babab

# (4, 5):babab

# i < jでAi = Ajだった場合、
# Ai+1 と Aj-1とで結果がダブる
for val in Ac.values():
    cnt += val * (val - 1) // 2
print(len(A) * (len(A)-1) // 2 - cnt + 1)

Measured memory_bytes: 11220
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

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

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  int a, b, c; cin >> a >> b >> c;
  swap(a, b);
  swap(a, c);
  cout << a << " " << b << " " << c << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
s = input()

ans = ''
for i in s:
    t = ord(i) + n
    if t > ord('Z'):
        t = ord('A') + (t - ord('Z')) - 1
    ans += chr(t)
print(ans)

Measured memory_bytes: 40684
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K,Q;
  cin >> N >> K >> Q;
  
  vector<int>A(Q);
  for(int i=0; i<Q; i++) cin >> A.at(i);
  sort(A.begin(),A.end());
  
  vector<int>H(N);
  for(int j=0; j<N; j++) H.at(j)=K;

  int j=0;
  
  for(int i=0; i<Q; i++){
      if(A.at(i)==j+1){
        H.at(j)++;
    }
    
    else{
      while(j+1<A.at(i)) j++;
      H.at(j)++;
    }
  }
  
  for(int j=0; j<N; j++) H.at(j)-=Q;
  
  for(int j=0; j<N; j++){
    if(H.at(j)>0) cout <<  "Yes" << endl;
    else cout << "No" << endl;
  }
  
}


Measured memory_bytes: 1408
#include<stdio.h>
int numcheck(int a[], int num){
    int i;
    for(i=0; i<6; i++)if(a[i]==num)return i;
}
void pickupch(int a[], int num){
    int i;
    switch(num){
        case 0:a[0]=1; a[1]=2; a[2]=4; a[3]=3;
            break;
        case 1:a[0]=0; a[1]=3; a[2]=5; a[3]=2;
            break;
        case 2:a[0]=0; a[1]=1; a[2]=5; a[3]=4;
            break;
        case 3:a[0]=0; a[1]=4; a[2]=5; a[3]=1;
            break;
        case 4:a[0]=0; a[1]=2; a[2]=5; a[3]=3;
            break;
        case 5:a[0]=1; a[1]=3; a[2]=4; a[3]=2;
            break;
        default:break;
    }
}
int lctcheck(int a[], int dsgnum){
    if(dsgnum==a[0])return a[1];
    else if(dsgnum==a[1])return a[2];
    else if(dsgnum==a[2])return a[3];
    else if(dsgnum==a[3])return a[0];
}
int main(){
    int i, q, a[6];
    for(i=0; i<6; i++)scanf("%d", &a[i]);
    scanf("%d", &q);
    for(i=0; i<q; i++){
        int b[4], s, t;
        scanf("%d", &s);
        pickupch(b, numcheck(a, s));
        scanf("%d", &t);
        printf("%d\n", a[lctcheck(b, numcheck(a, t))]);
    }
    return 0;
}

Measured memory_bytes: 596
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, ans;

int main()
{
	in >> N;
	std::vector<LL>a(N);
	rep(i, N) in >> a[i];
	rep(i, N) ans += a[i] - 1;
	out << ans << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define for_int(i,a,b) for(int i=(a);i<=(b);++i)
#define rep_int(i,a,b) for(int i=(a);i>=(b);--i)
#define for_ll(i,a,b) for(ll i=(a);i<=(b);++i)
#define rep_ll(i,a,b) for(ll i=(a);i>=(b);--i)
#define ull unsigned long long
#define ll long long
#define db double
#define HPMAX 1005
#define KMP_MAX 1005
#define prime_MAX 1e6+5
#define quick_pow_mod 1e9+7
#define PII pair<int,int>
const int factor_N = 1e7 + 5;
const int tree_arr_N = 1e6 + 5;
using namespace std;
//快读
int read() {
	char c = getchar();
	int x = 0, f = 1;
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (; isdigit(c); c = getchar())
		x = x * 10 + c - 48;
	return x * f;
}
int l,r,d;
int main() {
	l = read(); r = read(); d = read();
	int ans = 0;
	for_int(i, l, r) if (i % d == 0) ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,l,r) for(i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define P pair<ll,ll>
#define F first
#define S second
signed main(){
  ll L,R,D;cin>>L>>R>>D;
  cout<<R/D-(L-1)/D<<endl;
  return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

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

int N, K;
int x[60], y[60];
ll ans;

int main() {
	cin >> N >>K;
	for (int i = 0;i < N;i++) {
		cin >> x[i] >> y[i];
	}

	ans = 9223372036854775807;
	for (int a = 0;a < N;a++) {
		for (int b = 0;b < N;b++) {
			for (int c = 0;c < N;c++) {
				for (int d = 0;d < N;d++) {
					int xu = x[a];
					int xd = x[b];
					int yu = y[c];
					int yd = y[d];
					if (xu > xd || yu > yd) continue;

					int cnt = 0;
					for (int i = 0;i < N;i++) {
						if (x[i] >= xu && x[i] <= xd && y[i] >= yu && y[i] <= yd) cnt++;
					}

					if (cnt < K) continue;

					ll xdl = xd;
					ll xul = xu;
					ll ydl = yd;
					ll yul = yu;
					ll tmp = (xdl - xul)*(ydl - yul);

					ans = min(ans, tmp);
				}
			}
		}
	}

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

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int x1, y1, x2, y2,Xj,Yj;
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	Xj = x2 - x1;
	Yj = y2 - y1;
	printf("%d %d %d %d\n",x2-Yj,y2+Xj,x1-Yj,y1+Xj);
	return 0;
}

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

long long A[200005];

int main(){
	long long N;

	cin >> N;
	for(long long i = 0; i < N; i++){
		cin >> A[i];
	}

	map<long long, long long> count;

	long long ans = 0;
	for(long long i = 0; i < N; i++){
		ans += count[i - A[i]];
		count[i + A[i]]++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 27908
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
#define PP P<int,P<int,int>> 
using namespace std;
int n,p[55][5005];
bool sol[55][5005];
struct node{
	int to,co,ti;
};
V<node> v[55];
int c[55],d[55],ans[55];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m,s;
	cin>>n>>m>>s;
	gmin(s,5000ll);
	int from,to,co,ti;
	FOR(i,1,m){
		cin>>from>>to>>co>>ti;
		v[from].PB((node){to,co,ti});
		v[to].PB((node){from,co,ti});
	}
	FOR(i,1,n)cin>>c[i]>>d[i],ans[i]=1e17;
	FILL(p,-1);
	priority_queue<PP,V<PP>,greater<PP>> q;
	q.emplace(MP(0,MP(1,s)));
	p[1][s]=0;
	PP cur;
	int toti;
	while(!q.empty()){
		cur=q.top();q.pop();
		if(sol[cur.S.F][cur.S.S])continue;
		sol[cur.S.F][cur.S.S]=1;
		gmin(ans[cur.S.F],cur.F);
		toti=cur.S.S+c[cur.S.F];
		if(toti<=5000){
			if(!sol[cur.S.F][toti]){
				if(p[cur.S.F][toti]==-1||p[cur.S.F][toti]>cur.F+d[cur.S.F]){
					p[cur.S.F][toti]=cur.F+d[cur.S.F];
					q.emplace(MP(cur.F+d[cur.S.F],MP(cur.S.F,toti)));
				}
			}
		}
		for(auto u:v[cur.S.F]){
			toti=cur.S.S-u.co;
			if(toti>=0){
				if(!sol[u.to][toti]){
					if(p[u.to][toti]==-1||p[u.to][toti]>cur.F+u.ti){
						p[u.to][toti]=cur.F+u.ti;
						q.emplace(MP(cur.F+u.ti,MP(u.to,toti)));
					}
				}
			}
		}
	}
	FOR(i,2,n)cout<<ans[i]<<'\n';
	RE 0;
}




Measured memory_bytes: 11840
n = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

def solve(ho, cost, cnt):
    if cnt == n:
        return ho - cost
    return max(solve(ho, cost, cnt + 1), solve(ho + V[cnt], cost + C[cnt], cnt + 1))

print(solve(0, 0, 0))

Measured memory_bytes: 3060
n = input()
N = int(n)
list = input().rstrip().split(" ")
nums = []
j = 0
for i in list:
    if j % 2 ==0:
        f = int(i)
        nums.append(f)
    j += 1
ans = 0
for k in nums:
    if k % 2 != 0:
        ans +=1
print(ans)         

Measured memory_bytes: 9180
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <iomanip>
using namespace std;
int n,q;
int par[200000];
int ran[200000];
vector<int> ch[200000];
long long dp[200000];
int y[200000];
bool used[200000];
void dfs(int now,int mow){
	for(int i=0;i<ch[now].size();i++){
		if(par[ch[now][i]]==-1){
			par[ch[now][i]]=now;
			ran[ch[now][i]]=mow+1;
			dfs(ch[now][i],mow+1);
		}
	}
	return;
}
void solve(int now,int mow){
	used[now]=1;
	dp[now]+=mow;
	dp[now]+=y[now];
	for(int i=0;i<ch[now].size();i++){
		if(used[ch[now][i]]){
			continue;
		}
		solve(ch[now][i],dp[now]);
	}
}
int main(){
	cin>>n>>q;
	for(int i=0;i<n-1;i++){
		int a,b;
		par[i]=-1;
		cin>>a>>b;
		a--;
		b--;
		ch[a].push_back(b);
		ch[b].push_back(a);
	}
	par[0]=1e9+7;
	for(int i=0;i<q;i++){
		int p,x;
		cin>>p>>x;
		p--;
		y[p]+=x;
	}
	//
	dfs(0,0);
	solve(0,0);
	for(int i=0;i<n;i++){
		cout<<dp[i];
		if(i!=n-1){
			cout<<" ";
		}else{
			cout<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 26624
a,b,c,d=map(int,input().split())
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
e=lcm(c,d)
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
ee=b//e-(a-1)//e
print(b-a+1-cc-dd+ee)

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

using namespace std;

using ll = long long;

int N;
char s[125252][12];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        cin >> s[i];
    }
    map<string, int> M;
    for (int i=0; i<N; i++) {
        string sorted_s(s[i]);
        sort(sorted_s.begin(), sorted_s.end());
        M[sorted_s]++;
    }
    ll ans = 0;
    for (auto P: M) {
        ans += (ll)P.second*(P.second-1)/2;
    }
    
    cout << ans << endl;
    
    return 0;
}



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

int main()
{
    int n;
    cin >> n;
    int a[n+1], b[n+2];

    for(int i = 1; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i <= n; i++)
    {
        b[i] = 0;
    }
    for(int i = 1; i < n; i++)
    {
        b[a[i]]++;

    }
    for(int i = 0; i < n; i++)
    {
        cout << b[i+1] << endl;
    }
    return 0;
}


Measured memory_bytes: 5196
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
int main(){
    string s;
    cin >> s;
    if(s.size() == 26){
        rep(i,27){
            //うしろi文字を並べ替えて次の辞書順最小文字列をつくる
            string t = "";
            for(int j = 26 - i + 1; j < s.size(); j++){
                if(s[26 - i] < s[j]) t += s[j];
            }

            if(t != ""){
                sort(t.begin(),t.end());
                cout << s.substr(0,26-i) << t[0] << endl;
                return 0;
            }
        }
        cout << -1 << endl;
    }else{
        vector<int> a(26,0);
        rep(i,s.size())a[s[i]-'a']++;
        rep(i,26)if(a[i] == 0){
            cout << s << char('a'+i) << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll d, m;
string str;

int main(){
	cin >> m >> d;
	
	ll ans = 0;
	
	for(ll j = 1; j <= d; j++){
		ll d1 = j%10;
		ll d2 = j/10;
		if(d1 >= 2 && d2 >= 2 && d1*d2 <= m){
			ans++;
		}
	}
	
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
S = list(input())
lens = len(S)
if S[0]=='0':
  s = ['0' if i%2==0 else '1' for i in range(lens)]
else:
  s = ['1' if i%2==0 else '0' for i in range(lens)]
cnt = 0
for j in range(lens):
  if S[j]!=s[j]:
    cnt+=1
print(cnt)

Measured memory_bytes: 4652
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int a, b;
  cin >> a >> b;
  if (a < b) swap(a, b);
  int ans = a;
  a--;
  cout << max(a, b) + ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll> ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define tr1(x) cerr << #x << ": " << x << endl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define tr4(x,y,z,w) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#w<<": "<<w<<endl
#define trv(a) cerr<<#a<<": ";for(ll zz=0;zz<a.size();zz++) cerr<<a[zz]<<" ";cerr<<endl
#define trset(s) cerr<<#s<<": ";for(auto &i:s) cerr<<i<<" ";cerr<<"\n"
#define mod 1000000007ll
#define inf 9999999999999999ll
#define nl endl

  

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    vi a(n);
    for(ll i=0;i<n;i++)
        cin>>a[i];
    ll ans=inf;
    ll i=0;
    ll j=k-1;
    while(j<n)
    {
        ll p1=a[i];
        ll p2=a[j];
        ll d1=abs(0-a[i])+abs(a[i]-a[j]);
        ll d2=abs(0-a[j])+abs(a[i]-a[j]);
        ans=min(ans,min(d1,d2));
        i++;
        j++;
    }
    cout<<ans<<nl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;



void solve(){
    int r;
    cin >> r;
    cout << r*r << endl;
}

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


Measured memory_bytes: 256
#
# File    : B.rb
# Author  : Kazune Takahashi
# Created : 1/12/2019, 9:02:39 PM
# Powered by Visual Studio Code
#

n = gets.to_i
a, b = gets.chomp.split(" ").map{|i| i.to_i}
q = gets.chomp.split(" ").map{|i| i.to_i}

cnt = Array.new(3){0}

q.each{|x|
  if x <= a
    cnt[0] += 1
  elsif x <= b
    cnt[1] += 1
  else
    cnt[2] += 1
  end
}

puts cnt.min




Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define pd(a,n) for(int i=0;i<n;i++)cout<<a[i]<<((i==n-1)?"\n":" ");cout<<endl;
#define pdd(a,n,m)for(int i=0;i<n;i++){for(int j=0;j<m;j++)cout<<a[i][j]<<" ";cout<<endl;}
#define mp make_pair
#define pb push_back
#define ll long long
//#define __int64 lng long
#define P pair<int,int>
#define PP pair<P,int>

int n,m;
int w[111],v[222];
int dp[2][11111];

int main(){
  cin>>n>>m;

  rep(i,n)
    cin>>v[i]>>w[i];

  rep(i,n){
    rep(j,m+1){
      dp[(i+1)&1][j]=max(dp[(i+1)&1][j],dp[i&1][j]);
      if(j+w[i]<=m)dp[(i+1)&1][j+w[i]]=max(dp[(i+1)&1][j+w[i]],dp[i&1][j]+v[i]);
    }
  }
  int ans=0;
  rep(i,m+1)ans=max(ans,dp[n&1][i]);
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3184
#include<bits/stdc++.h>
using namespace std;
int main(){
	long int n;
	cin>>n;
	if(n<=9&&n>=1)cout<<n<<endl;
	else if(n>=10&&n<=99)cout<<9<<endl;
	else if(n>=100&&n<=999)cout<<9+n-99<<endl;
	else if(n>=1000&&n<=9999)cout<<909<<endl;
	else if(n>=10000&&n<=99999)cout<<909+n-9999<<endl;
	else cout<<90909<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int count = 1;
		
		while(true) {
			if((count*N)%N==0 && (count*N)%2==0) {
				System.out.println(N*count);
				break;
			}
			count++;
		}
		
 
	}
 
}


Measured memory_bytes: 21716
/**
 *    author:   K.R.Surrya  
 *    created:  03/05/2020 17:31:09
**/
#include<bits/stdc++.h>
#define vi vector<int>
#define vii vector<vector<int> >
#define vpi vector<pair<int,int> >
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define pb push_back
using namespace std; 

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it)  { return ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a,Args... args)
{
    cerr << *it << " = " << a <<endl;
    err(++it,args...);   //args is going to end.
}


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

    // freopen("input.txt", "r", stdin);
     //freopen("output.txt", "w", stdout);


     auto start = chrono::high_resolution_clock::now();
     string s;
     cin >> s;
     if(s=="ABC") cout << "ARC" << '\n';
     else         cout << "ABC" << '\n';
     auto end = chrono::high_resolution_clock::now();

     cerr << " Execution time : " << chrono::duration_cast<chrono::milliseconds>(end-start).count()<<"ms"<<endl;

   
    return 0;
}


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

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

  vector<int> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];

  int x = 0;
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0)
      x += a[i];
    else
      x -= a[i];
  }

  for (int i = 0; i < n; ++i) {
    printf("%d%c", x, i == n - 1 ? '\n' : ' ');
    x = 2 * a[i] - x;
  }
}

Measured memory_bytes: 1664
import re
import numpy as np


S = str(input())

s0=len(re.findall(S[0],S))
s1=len(re.findall(S[1],S))
s2=len(re.findall(S[2],S))
s3=len(re.findall(S[3],S))

flag=np.array([s0,s1,s2,s3])
if np.sum(flag==2)==4:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 21020