akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";}

// #define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
typedef long long ll;
typedef double ld;
#define pll pair<ll,ll>
#define pii pair<int, int>
#define pb push_back
#define mp(x, y) make_pair((x), (y))
#define F first
#define S second
#define I insert
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pll>
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()
   
const ll Mod = -1e9 - 7;

ll n , ga , sa , ba , gb , sb , bb  ;
ll dp[25000007];
map<ll , ll > m;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    
    cin >> n >> ga >> sa >> ba >> gb >> sb >> bb;
  
    for(int i = 1 ;i <= n; i++){
        dp[i] = i;
        if(i >= ga)
            dp[i] = max(dp[i] , dp[i-ga]+gb);
        if(i >= sa)
            dp[i] = max(dp[i] , dp[i-sa]+sb);
        if(i >= ba)
            dp[i] = max(dp[i] , dp[i-ba]+ bb);
    }
    
    swap(ga , gb);
    swap(sa , sb);
    swap(ba, bb);
    m.clear();
    n = dp[n];
    for(int i = 1 ;i <= n; i++){
        dp[i] = i;
        if(i >= ga)
            dp[i] = max(dp[i] , dp[i-ga]+gb);
        if(i >= sa)
            dp[i] = max(dp[i] , dp[i-sa]+sb);
        if(i >= ba)
            dp[i] = max(dp[i] , dp[i-ba]+ bb);
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 195584
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}

template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}


signed main(void) {
	int n;
	cin >> n;
	vector<int>c(n-1);
	vector<int>s(n-1);
	vector<int>f(n-1);
	vector<pair<int, int>>point(n);
	rep(i, n-1) {
		cin >> c[i] >> s[i] >> f[i];
	}
	rep(i, n) {
		point[i] = make_pair(i, 0);//point,time
	}
	rep(i, n-1) {
		rep(j, n) {
			if (point[j].first == i) {
				int time = point[j].second;
				while (true) {
					if (time >= s[i] && time%f[i] == 0)break;
					time++;
				}
				point[j].first++;
				point[j].second = time+c[i];
			}
		}
	}
	rep(i, n) {
		cout << point[i].second << endl;
	}
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    string st;
    cin >> st;
    
    int ret = INF, ans = 0;
    rep(i, st.size()) {
        if (i % 2) {
            if (st[i] == '0') ans++;
        } else {
            if (st[i] == '1') ans++;
        }
    }
    ret = ans;
    ans = 0;
    rep(i, st.size()) {
        if (i % 2) {
            if (st[i] == '1') ans++;
        } else {
            if (st[i] == '0') ans++;
        }
    }

    std::cout << min(ans, ret) << std::endl;

    return 0;
}


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

int main(){
 int n;
 int Acard,Bcard,Apoint,Bpoint;
 while(true){
  cin>>n;
  if(n==0){
   break;
  }else{
    for(int i=0;i<n;i++){
     cin>>Acard>>Bcard;
     if(Acard>Bcard){
      Apoint+=Acard+Bcard;
     }else if(Acard<Bcard){
      Bpoint+=Acard+Bcard;
     }else{
      Apoint+=Acard;
      Bpoint+=Bcard;
     }
    }
   cout<<Apoint<<' '<<Bpoint<<'\n';
   Apoint=0;
   Bpoint=0;
  }
 }
 return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <cstdint>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <numeric>
#include <algorithm>
#include <cassert>

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

using namespace std;

template<class T, class U>
istream& operator>>(istream& is, pair<T, U>& pair)
{
    is >> pair.first >> pair.second;
    return is;
}

template<class T>
istream& operator>>(istream& is, T& collection)
{
    for(auto& item : collection) is >> item;
    return is;
}

struct person_t {
    int n = 0;
    int64_t h = 0;
};

void solution()
{
    int n;
    cin >> n;
    unordered_map<int, int> counts;
    rep(i,n-1){
        int a;
        cin >> a;
        counts[a-1]++;
    }
    rep(i,n){
        cout << counts[i] << '\n';
    }
}

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


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

int main(){
  int a,b;
  cin >>a >>b;
  if((a+b)%2 == 0) cout << (a+b)/2 << endl;
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


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

int main()
{
        int N; cin >> N;
        vector<int> a(N, 0);
        for (int i = 0; i < N; ++i) {
                cin >> a[i];
        }
        sort(a.begin(), a.end());
        cout << a[N-1] - a[0] << endl;


}


Measured memory_bytes: 256
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]

from math import ceil
h,w = map(int, input().split())
ans = 0

if h==1 or w == 1:
    print(1)
else:
    print((h-h//2)*(w-w//2) + (h//2) * (w//2))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define all(c) c.begin(), c.end()
#define rep(i,a,b) for(int i = a;i < b; ++i)
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
using namespace std;

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

const int N = 1e5+5;
const int MOD = 1e9 + 7;

int add(int x,int y){
	return (x+y)%MOD;
}

int mul(ll x,ll y){
	return (x*y)%MOD;
}

int mod_pow(int x, int p){
	int res = 1;
	while(p){
		if(p&1)res = mul(res, x);
		x = mul(x,x);
		p/=2;
	}
	return res;
}

int fac[N],inv[N];

int choose(int n, int k){
	if(k > n)return 0;
	return mul(mul(fac[n], inv[k]), inv[n-k]);;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	fac[0] = inv[0] = 1;
	rep(i,1,N){
		fac[i] = mul(fac[i-1],i);	
		inv[i] = mod_pow(fac[i],MOD - 2);
	}
	int n,k;
	cin >> n >> k;
	int a[n];
	rep(i,0,n)cin >> a[i];
	sort(a,a+n);
	int ans = 0;
	rep(i,0,n){
		int mx = mul(a[i],choose(i,k-1));
		int mn = mul(-a[i],choose(n-i-1,k-1));
		ans = add(ans, mx);
		ans = add(ans, mn);
	}
	cout << ans << '\n';
}


Measured memory_bytes: 1408
N, Y = map(int, input().split())
for x in range(N + 1):
    for y in range(N - x + 1):
        z = N - x - y
        if Y == 10000 * x + 5000 * y + 1000 * z:
            print(x, y, z)
            exit()
print(-1, -1, -1)

Measured memory_bytes: 9184
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        public static void Main()
        {
            new Program().Solve();
        }

        void Solve()
        {
            var tmp = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = tmp[0];
            int b = tmp[1];
            int x = tmp[2];
            int t = x - a;
            if (t < 0)
            {
                Console.WriteLine("NO");
                return;
            }
            t = b - t;
            if (t < 0)
            {
                Console.WriteLine("NO");
            }
            else
            {
                Console.WriteLine("YES");
            }
        }
    }
}


Measured memory_bytes: 13268
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}

enum MOD = (10 ^^ 9) + 7;

void main()
{
    long W, a, b;
    scan(W, a, b);
    solve(W, a, b).writeln();
}

long solve(long W, long a, long b)
{
    if (a + W < b)
    {
        return b - (a + W);
    }
    if (b + W < a)
    {
        return a - (b + W);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using Graph = vector<vector<int>>;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll modinv(ll a, ll m){
    ll b = m, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if(u < 0) u += m;
    cout << u << endl;
    return u;
}

ll paty_counter(ll level, ll x){
    ll size = pow(2, level+2) - 3;
    ll pmi = pow(2, level) - 1;
    if(x == 0){
        return 0;
    }else if(level == 0){    
        return 1;
    }else{
        if(x <= (size - 1)/2){
            return paty_counter(level-1, x-1);
        }else{
            return pmi + 1 + paty_counter(level-1, x - pow(2, level+1) + 3 - 2);
        }
    }

}
 
int main() {
    ll k,a,b;
    cin >> k >> a >> b;
    string ans = "NG";
    FOR(i, a, b+1){
        if(i % k == 0){
            ans = "OK";
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 3580
import Data.List
main = do
  n <- readLn :: IO Int
  p <- map (read::String->Int) . words <$> getLine
  print $ f p 0

f (_:_:[]) counter = counter
f (x:y:z:xs) counter
  |x<y && y<z = f (y:z:xs) (counter+1)
  |x>y && y>z = f (y:z:xs) (counter+1)
  |otherwise  = f (y:z:xs)  counter

Measured memory_bytes: 4024
import math
from queue import Queue
import copy

h, w = map(int, input().split(" "))
ili = [list(input()) for _ in range(h)]

q = Queue()
ans = 0

for y in range(h):
    for x in range(w):
        li = copy.deepcopy(ili)
        if li[y][x] == "#": continue
        q.put([x, y])
        li[y][x] = 0
        while not q.empty():
            c = q.get()
            # 上(0, -1) 右(1, 0) 下(0, 1) 左(-1, 0)
            for dr in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
                nX = c[0] + dr[0]
                nY = c[1] + dr[1]

                if not (0 <= nX <= w - 1): continue
                if not (0 <= nY <= h - 1): continue

                if li[nY][nX] == ".":
                    li[nY][nX] = li[c[1]][c[0]] + 1
                    q.put([nX, nY])

        li = list(
            map(lambda item: 0 if item == "#" or item == "." else item,
                sum(li, [])))
        ans = max(li + [ans])

print(ans)

Measured memory_bytes: 4080
import math
a,b,h,m = list(map(int,input().split()))

a1 = (30 * h) + (0.5 * m)
b1 = 6 * m

if a1 > b1:
    k = a1 - b1
else:
    k = b1 - a1

res = (a ** 2) + (b ** 2) - (2 * a * b * math.cos(math.radians(k)))
res = math.sqrt(res)

print(res)

Measured memory_bytes: 9516
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll N, M, K;
  cin>>N>>M>>K;
  vector<ll> A(N+1), B(M+1);
  for(int i=0;i<N;++i) cin>>A[i+1];
  for(int i=0;i<M;++i) cin>>B[i+1];
  for(int i=1;i<=N;++i) A[i] += A[i-1];
  for(int i=1;i<=M;++i) B[i] += B[i-1];
  ll sum;
  ll ans = 0;
  ll index;
  for(int i=0;i<=N;++i){
    sum = A[i];
    if(sum>K) continue;
    index = upper_bound(B.begin(), B.end(), K-sum) - B.begin()-1;
    ans = max(ans, i+index);
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 6376
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<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()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let (N, M): (usize, usize) = (read(), read());
    use std::collections::{HashMap, VecDeque};
    let mut graph: HashMap<usize, Vec<usize>> = HashMap::new();
    for _ in 0..M {
        let a: usize = read();
        let b: usize = read();
        let entry = graph.entry(a).or_insert_with(|| vec![]);
        entry.push(b);
        let entry = graph.entry(b).or_insert_with(|| vec![]);
        entry.push(a);
    }
    let mut queue: VecDeque<usize> = VecDeque::new();
    queue.push_front(1);
    let mut ans: Vec<usize> = vec![0; N + 1];
    while let Some(now) = queue.pop_back() {
        for &next in graph.get(&now).unwrap() {
            if ans[next] != 0 {
                continue;
            }
            ans[next] = now;
            queue.push_front(next);
        }
    }
    println!("Yes");
    for &v in ans.iter().skip(2) {
        println!("{}", v);
    }
}


Measured memory_bytes: 13724
#include <stdio.h>
int main(void){
	int n,l[200],i,j,t,ans=0;
	scanf("%d",&n);
	for(i=0;i<2*n;i++){
		scanf("%d",&l[i]);
	}
	for(i=0;i<2*n-1;i++){
		for(j=2*n-1;j>i;j--){
			if(l[j-1]>l[j]){
				t=l[j-1];
				l[j-1]=l[j];
				l[j]=t;
			}
		}
	}
	for(i=0;i<n;i++){
		ans+=l[2*i];
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long int li;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef pair<ll, ll>P;
#define PI 3.14159265359
#define MOD 998244353
const int MAX = 510000;

int main() {
  ll N,K;cin>>N>>K;
  vector<ll>memo(N);
  rep(i,N){
  	ll p;cin>>p;
    p--;
    memo[p]++;
  }
  sort(memo.begin(),memo.end());
  ll ans=0;
  for(int i=0;i<=N-K-1;i++){ans+=memo[i];}
  cout<<ans;
}

Measured memory_bytes: 1792
open Printf
open Scanf

let id x = x
let pair x y = x, y

let a, b, k = scanf "%d %d %d" (fun a b k -> a, b, k)

let op a b =
  (if !a mod 2 <> 0 then a := !a - 1);
  let ha = !a / 2 in
  a := !a - ha;
  b := !b + ha

let () =
  let ra = ref a in
  let rb = ref b in
  let a = ref ra in
  let b = ref rb in
  for i = 1 to k do
    op !a !b;
    let t = !a in
    a := !b;
    b := t
  done;
  printf "%d %d\n" !ra !rb


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



int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	long long sum = 0;
	const int mx = 1e5;
	vector<int> cnt(mx + 1);
	for(auto i = 0; i < n; ++ i){
		int x;
		cin >> x;
		++ cnt[x];
		sum += x;
	}
	int qq;
	cin >> qq;
	while(qq --){
		int b, c;
		cin >> b >> c;
		cout << (sum += 1LL * (c - b) * cnt[b]) << "\n";
		cnt[c] += cnt[b];
		cnt[b] = 0;
	}
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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

#define pb push_back
#define mp make_pair
typedef long long int ll;
#define mod 1000000007

bool check(vector<bool> v, ll n)
{
	for (; n > 0; n /= 10)
		if (v[n % 10] )
			return false;

	return true;
}

void solve()
{
	ll n, k;
	cin >> n >> k;

	vector<bool> v(10);
	for (ll i = 0; i < k; i++)
	{
		ll index;
		cin >> index;
		v[index] = true;
	}

	while (!check(v, n))
		n++;

	cout << n;
}



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

#ifndef ONLINE_JUDGE
	freopen("1input.txt", "r", stdin);
	freopen("1output.txt", "w", stdout);
#endif

	int t = 1;
	// cin >> t;

	while (t--)
	{
		solve();
		cout << "\n";
	}

	return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n,m,x,y;
  cin>>n>>m>>x>>y;
  int cnt;
  int sum;
  string ans="War";
  vector<int> a(n);
  rep(i,n){
    cin>>a[i];
  }
  vector<int> b(m);
  rep(i,m){
    cin>>b[i];
  }
  for(int i=x+1;i<y;i++){
    cnt=0;
    for(int j=0;j<n;j++){
      if(i>a[j]) cnt++;
    }
    sum=0;
    if(cnt==n){
      for(int j=0;j<m;j++){
        if(i<=b[j]) sum++;
      }
    }
    if(sum==m) ans="No War";
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	while(cin>>n&&n!=0){
		long long a[n];
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		sort(a,a+n);
		long long b[n];
		b[0]=0;
		for(int i=0;i<n;i++){
			b[i+1]=b[i]+a[i];
		}
		long long sum=0;
		for(int i=0;i<n;i++){
			sum+=b[i];
		}
		cout<<sum<<endl;
	}
}

Measured memory_bytes: 3248
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//ここまでテンプレ
int depth[SIZE]={};
vint node[SIZE];
vint rev[SIZE];
void DFS(int D,int ind){
	depth[ind]=D;
	for(int i=0;i<node[ind].size();i++){
		DFS(D+1,node[ind][i]);
	}
}
int main(){
	int N;
	cin>>N;
	for(int i=2;i<=N;i++){
		int c;
		cin>>c;
		node[c].pb(i);
	}
	DFS(0,1);
	//ノードを深い順に並べる
	vector<pint> SOR;
	for(int i=1;i<=N;i++)
		SOR.pb(mp(depth[i],i));
	sort(SOR.begin(),SOR.end(),greater<pint>());
	//DPテーブル
	//DP[i]=頂点i以下のトーナメント表の最小深さ
	int DP[SIZE]={};
	for(int i=1;i<=N;i++){
		if(node[i].size()==0)
			DP[i]=1;
	}
	/*
	for(int i=1;i<=N;i++)
		cout<<depth[i]<<" ";
	cout<<endl;
	for(int i=1;i<=N;i++)
		cout<<DP[i]<<" ";
	cout<<endl;
	for(int i=0;i<N;i++)
		cout<<SOR[i].second<<" ";
	cout<<endl;
	*/
	for(int i=0;i<N;i++){
		int now=SOR[i].second;
		if(node[now].size()==0)
			continue;
		vint vec;
		for(int j=0;j<node[now].size();j++)
			vec.pb(DP[node[now][j]]);
		/*
		for(int j=0;j<node[now].size();j++)
			cout<<node[now][j]<<" ";
		cout<<endl;
		for(int j=0;j<vec.size();j++)
			cout<<vec[j]<<" ";
		cout<<endl;
		*/
		sort(vec.begin(),vec.end(),greater<int>());
		for(int j=0;j<vec.size();j++)
			DP[now]=max(DP[now],vec[j]+j+1);
	}
	/*
	for(int i=1;i<=N;i++)
		cout<<DP[i]<<" ";
	cout<<endl;
	*/
	cout<<DP[1]-1<<endl;
	return 0;
}

Measured memory_bytes: 14448
#include <iostream>
#include <algorithm>
using namespace std;
long long v[100005],A;
int n,i,cnt;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    sort(v+1,v+n+1);
    A=1;
    for(i=n;i>=1;i--)
    {
        if(v[i]==v[i+1])
        {
            if(cnt<2)
            {
                A=1LL*A*v[i];
                v[i]=0;
                cnt++;
            }
        }
    }
    if(cnt==0||cnt==1) A=0;
    cout<<A;
    return 0;
}

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


int main() {
    int H, A;
    cin >> H >> A;
    int ans = 0;
    while(H > 0){
        H -= A;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n,k,i,r=0,t=-1;
  cin>>n>>k;
  long long int a[n];
  
  for(i=0;i<n;i++)
  { cin>>a[i];
     r+=a[i];
   if(r>k && t==-1) t=i; 
  }
  if(t==-1) cout<<n+1;
  else 
  cout<<t+1;
  return 0;
  
}


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

int64_t lucas (int N, int count, int64_t a, int64_t b) {
  if (count == N) {
    return b;
  }
  a = a + b;
  count++;
  return lucas (N, count, b, a);
}
  
  

int main () {
  int N;
  int64_t L0 = 2, L1 = 1;
  cin >> N;
  cout << lucas (N, 1, L0, L1) << endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() 
{
 ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin>>s;
ll ans=0;
 if(s[0]=='S' && s[1]=='S' && s[2]=='S')
 {
     ans=0;
 }
  
 else if(s[0]=='S' && s[1]=='S' && s[2]=='R')
 {
     ans=1;
 }
 else if(s[0]=='S' && s[1]=='R' && s[2]=='S')
 {
     ans=1;
 }
 else if(s[0]=='R' && s[1]=='S' && s[2]=='S')
 {
     ans=1;
 }
 else if(s[0]=='S' && s[1]=='R' && s[2]=='R')
 {
     ans=2;
 }
 else if(s[0]=='R' && s[1]=='S' && s[2]=='R')
 {
     ans=1;
 }
 else if(s[0]=='R' && s[1]=='R' && s[2]=='S')
 {
     ans=2;
 }
 else if(s[0]=='R' && s[1]=='R' && s[2]=='R')
 {
     ans=3;
 }
 
cout<<ans<<endl;
return(0);
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
namespace run{
	const int N=1e5+9,mod=1e9+7;
	inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;}
	int n,a[N],cir[N],vis[N],deg[N],len[N],top[N],sum[N],f[N];

	int ans=1;
	inline void solve(int x){
		int tmp=a[x],las=0,now=0,ret=1;
		while(cir[tmp]==1){
			now++;
			if(len[tmp]){
				int res=(now-las>=len[tmp])+(now-las>len[tmp]);
				ret=1LL*ret*res%mod,las=now;
			}
			cir[tmp]=2,tmp=a[tmp];
		}
		ans=1LL*ans*ret%mod;
	}
	int main(){
		n=read<int>();
		for(int i=1;i<=n;i++) deg[a[i]=read<int>()]++;
		
		for(int i=1;i<=n;i++){
			int tmp=i;
			while(!vis[tmp]) vis[tmp]=i,tmp=a[tmp];
			if(vis[tmp]==i){
				int now=tmp;
				do{cir[now]=1,now=a[now];}while(now!=tmp);
			}
		}

		for(int i=1;i<=n;i++)
			if((cir[i] && deg[i]>2) || (!cir[i] && deg[i]>1)) puts("0"),exit(0);
		for(int i=1;i<=n;i++) if(!deg[i]){
			int tmp=i,siz=0;
			while(!cir[tmp]) siz++,tmp=a[tmp];
			len[tmp]=siz,top[i]=tmp;
		}
		for(int i=1;i<=n;i++) if(!deg[i] && cir[top[i]]==1) solve(top[i]);

		for(int i=1;i<=n;i++) if(cir[i]==1){
			int tmp=i,siz=0;
			while(cir[tmp]==1) cir[tmp]=2,siz++,tmp=a[tmp];
			sum[siz]++;
		}

		for(int i=1;i<=n;i++) if(sum[i]){
			f[0]=1;
			for(int j=1;j<=sum[i];j++){
				if(i>1 && (i&1)) f[j]=add(f[j-1],f[j-1]);
				else f[j]=f[j-1];
				if(j>1) f[j]=(1LL*f[j-2]*i%mod*(j-1)+f[j])%mod;
			}
			ans=1LL*ans*f[sum[i]]%mod;
		}
		printf("%d\n",ans);
		return 0;
	}
}
int main(){
#ifdef my
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	return run::main();
}

Measured memory_bytes: 6124
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


def main():
    nun, k = map(int, input().split())
    data = list(map(int, input().split()))

    aaa = [0 for i in range(nun)]
    for i in range(nun):
        for j in range(nun):
            if i == j:
                continue
            if data[i] > data[j]:
                aaa[i] += 1

    mod = 10 ** 9 + 7
    ans = 0
    # print(aaa)
    for i in range(nun):
        shokou = 0
        for j in range(i + 1, nun):
            if data[i] > data[j]:
                # ans += 1
                shokou += 1
        # print(shokou)
        ans += (shokou + shokou + (k - 1) * aaa[i]) * k // 2
        # print(ans)
        ans %= mod

    print(ans)





if __name__ == '__main__':
    main()



Measured memory_bytes: 42348
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define PI 3.141592653589793
#define MOD 1000000007
//#define DEBUG



//qsort用、昇順
int compare_int(const void *a, const void *b)
{
	return *(int*)a-*(int*)b;
}
//qsort(array, 10, sizeof(int), compare_int)



int main(){
	long long int a, b, c, d;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	long long int x, y, z, w;
	x = a*c;
	y = a*d;
	z = b*c;
	w = b*d;
	if(x<y) x = y;
	if(x<z) x = z;
	if(x<w) x = w;

	printf("%lld\n", x);
	
	return 0;
}



Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std ;
int main()
{
    int n , a[101] = {0} ;
    cin >> n ;
    int x = 0 ;
    for(int i = 1 ; i <= n ; i++)
    {
         cin >> a[i] ;
         if(i%2)
         {
              if(a[i]%2)
              {
                   x++ ;
              }
         }
    }
    cout << x << endl ;
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
#define oo (long long)1e18
#define ll long long
#define setdp memset(dp,-1,sizeof(dp))
const ll mod = 1e9+7;
void _IOS(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);}
#define PI 3.14159265359
int sx,sy,tx,ty;
struct threeElements{
int _1st,_2nd,_3rd;
};
vector<vector<int>>adj(100);
ll n;
ll a[2000009];
bool check(string s,string t)
{
    int n1=s.length(),n2=t.length(),j=0;
    for(int i=0;i<n1;i++)
    {
        if(s[i]==t[j])
            j++;
        if(j==n2)
            return 1;
    }
    return 0;
}
int main()
{
   // freopen ("jumping.in","r",stdin);
   _IOS();
   //18:52
    ll n,k;
    cin>>n>>k;
    map<ll,ll>mp;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        mp[a]+=b;
    }
    ll sum=0;
    for(int i=1;i<=100000;i++)
    {
        sum+=mp[i];
        if(sum>=k)
            return cout<<i,0;
    }


}


Measured memory_bytes: 9848
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String answer = "No";
		for (int i = 1; i <= 9; i++) {
			if (n % i == 0 && n / i <= 9) {
				answer = "Yes";
				break;
			}
		}
		System.out.println(answer);
	}
}

Measured memory_bytes: 22740
unittest
{
	assert( [ "5 3", "96 98 95 100 20" ].solve == "Yes\nNo" );
	assert( [ "3 2", "1001 869120 1001" ].solve == "No" );
	assert( [ "15 7", "3 1 4 1 5 9 2 6 5 3 5 8 9 7 9" ].solve == "Yes\nYes\nNo\nYes\nYes\nNo\nYes\nYes" );
}



import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto k = 0L;
	input.front.formattedRead!"%s %s"( n, k );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	
	auto anss = new string[ n - k ];
	foreach( i, ref ans; anss )
	{
		ans = ( as[ i ] < as[ k + i ] ) ? "Yes" : "No";
	}
	return anss.join( "\n" );
}


Measured memory_bytes: 16080
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
#define MOD 1000000007

int main(){
  int A,B;
  cin>>A>>B;
  int H=100;
  int W=100;
  vector<vector<char>> c(H,vector<char>(W));
  for(int i=0;i<H/2;i++){
    for(int j=0;j<W;j++){
      c[i][j]='.';
    }
  }
  for(int i=H/2;i<H;i++){
    for(int j=0;j<W;j++){
      c[i][j]='#';
    }
  }
  A--;
  B--;

  for(int i=0;i<H/2;i+=2){
    for(int j=0;j<W;j+=2){
      if(B==0){
        break;
      }
      c[i][j]='#';
      B--;
    }
  }
  for(int i=H/2+1;i<H;i+=2){
    for(int j=0;j<W;j+=2){
      if(A==0){
        break;
      }
      c[i][j]='.';
      A--;
    }
  }
  
  cout<<H<<" "<<W<<endl;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout<<c[i][j];
    }
    cout<<endl;
  }
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int isreverse = 0;
	int q;
	string a;
	cin>>a;
	cin>>q;
	string s[2];
	for(int i=0;i<q;i++)
	{
		int t;
		cin>>t;
		if(t == 1)
		{ 
			isreverse = !isreverse; 
		}
		else
		{
			int f;char c;
			cin>>f>>c;
			if(f == 1)
			{
				s[isreverse]+=c;
			}
			else
			{
				s[!isreverse]+=c;
			}
		}
	}
	if(isreverse)
	{
		reverse(a.begin(),a.end());
	}
	reverse(s[isreverse].begin(),s[isreverse].end());
	a = s[isreverse]+a+s[!isreverse];
	cout<<a<<endl;
	return 0;
 } 

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

using namespace std;

int n;
vector<int> G[100005];
bool flag[100005];
bool used[100005];
vector<int> path;
bool vi;

void dfs(int v,int p){
	used[v]=true;
	path.push_back(v);
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i];
		if(nv==p)continue;
		if(used[nv] && !vi){
			vi=true;
			int j=path.size()-1;
			while(path[j]!=nv){
				//printf("%d %d\n",nv,path[j]);
				flag[path[j]]=true;
				j--;
			}
			flag[path[j]]=true;
		}else if(!used[nv]){
			dfs(nv,v);
		}
	}
	path.pop_back();
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0,-1);
	int q;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		if(flag[a] && flag[b]){
			printf("%d\n",2);
		}else{
			printf("%d\n",1);
		}
	}
	return 0;
}


Measured memory_bytes: 13892
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int n, m, q, mod, g;
int l[maxn + 10], r[maxn + 10], w[maxn + 10];
int fa[maxn + 10], idcnt;
int id[maxn + 10][3][2];
bool vis[2][maxn + 10];

int getf(int p) {
	return fa[p] == p ? p : fa[p] = getf(fa[p]);
}

void merge(int x, int y) {
	fa[getf(x)] = getf(y);
}

int main() {
	scanf("%d%d%d%d", &n, &m, &q, &mod);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &l[i], &r[i], &w[i]);
		g = __gcd(g, abs(w[i] - w[1]));
	}
	for (int i = m + 1; i <= m * 2; ++i) {
		l[i] = r[i - m]; r[i] = l[i - m]; 
		w[i] = w[i - m];
	}
	m *= 2;
	mod = __gcd(mod, g * 3);
	if (!g) g = mod;
	int det = w[1] % g;
	for (int i = 1; i <= n; ++i)
		for (int x = 0; x < 3; ++x)
			for (int y = 0; y < 2; ++y) {
				id[i][x][y] = ++idcnt;
				fa[idcnt] = idcnt;
			}
	for (int i = 1; i <= m; ++i) {
		w[i] -= det;
		assert(w[i] % g == 0);
		w[i] /= g;
		for (int x = 0; x < 3; ++x)
			for (int y = 0; y < 2; ++y)
				merge(id[l[i]][x][y], id[r[i]][(x * 2 + w[i]) % 3][y ^ 1]);
	}
	for (int i = 0, d = 0, v = det; i < mod * 2; ++i) {
		vis[d][v] = 1; d ^= 1; v = (v * 2) % mod;
	}
	while (q--) {
		int s, t, r; scanf("%d%d%d", &s, &t, &r);
		bool fd = 0;
		for (int x = 0; x < 3; ++x)
			for (int y = 0; y < 2; ++y)
				if (getf(id[t][0][0]) == getf(id[s][x][y])) {
					if (vis[y][(det + r - 1ll * x * g % mod + mod) % mod]) {
						fd = 1;
					}
				}
		printf("%s\n", fd ? "YES" : "NO");
	}
}


Measured memory_bytes: 12672
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

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

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int A, B, C, D; std::cin >> A >> B >> C >> D;
  std::cout << (A*B>C*D?A*B:C*D) << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
int main(){
	int a=0;
	int b=0;
	int c=0;
	std::cin>> a;
	std::cin>> b;
	std::cin>> c;
	if(b-a==c-b){std::cout<< "YES" <<std::endl;}
	else{std::cout<< "NO" <<std::endl;}
	return 0;
}

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

int main() {
  int n,k,r,s,p;
  cin >> n >> k >> r >> s >> p;
  string S; cin >> S;
  ll ans = 0;
  vector<bool> skip(n,false);
  
  rep(i,n){
    
    if(i < k){ //「k個前」を考えなくてよいとき
      if(S[i] == 'r') ans += p;
      if(S[i] == 's') ans += r;
      if(S[i] == 'p') ans += s;
    }
    
    else{ //「k個前」を考えないといけないとき
      if(S[i] != S[i-k]){ //不一致なら素直に足してよい
        if(S[i] == 'r') ans += p;
        if(S[i] == 's') ans += r;
        if(S[i] == 'p') ans += s;
      }
      else{ //一致なら、すでに飛ばしたかを検討
        if(skip[i-k] == false) skip[i] = true;
        else{
          if(S[i] == 'r') ans += p;
          if(S[i] == 's') ans += r;
          if(S[i] == 'p') ans += s;
        }
      }
    }
    
  }
   
  cout << ans << endl;
}

Measured memory_bytes: 3716
void main()
{
    long[] tmp = readln.split.to!(long[]);
    long n = tmp[0], c = tmp[1], k = tmp[2];
    long[] t = new long[n];
    foreach (i; 0 .. n)
    {
        t[i] = readln.chomp.to!long;
    }

    t.sort!"a < b";
    long cnt;
    long a = t[0];
    long bus = 1;
    foreach (x; t)
    {
        if (a <= x && x <= a + k && cnt < c)
        {
            ++cnt;
        }
        else
        {
            a = x;
            ++bus;
            cnt = 1;
        }
    }

    bus.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 4092
using System;

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var m = int.Parse(line[1]);
        var t = int.Parse(line[2]);
        string[] line2 = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line2, int.Parse);
        var ans = 0;
        var pos = "s";
        var ptime = 0;
        foreach (var x in a)
        {
            switch (pos)
            {
                case "s":
                    ans += x - ptime - m;
                    pos = "g";
                    break;
                case "g":
                    if (x - ptime > 2 * m) ans += x - ptime - 2 * m;
                    break;
            }
            ptime = x;
        }
        if (t - ptime > m) ans += t - ptime - m;
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 9296
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

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

	int n;
	cin >> n;


	int answer = 0;

	for (int i = 0; i < n; ++i) {
		int l, r;
		cin >> l >> r;
		answer += (r - l + 1);
	}

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
static const int INFTY = (1<<21);

int A[MAX][MAX],n,v,i;

int prim(){
  int u,mincost,sum=0;
  int d[MAX],p[MAX],color[MAX];
 
  for(i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=-1;
    color[i]=WHITE;
  }
 
  d[0]=0;
   
  while(1){
    mincost=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(mincost>d[i]&&color[i]!=BLACK){
        u=i;
        mincost=d[i];
      }
    }
    if(u==-1)  break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK&&A[u][v]!=INFTY){
        if(d[v]>A[u][v]){
          d[v]=A[u][v];
          p[v]=u;
          color[v]=GRAY;
        }
      }
    }
  }
  for(i=0;i<n;i++){
    if(p[i]!=-1) sum+=A[i][p[i]];
  }
  return sum;
}

int main(){
  int e,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      A[i][j]=(e==-1)?INFTY:e;
    }
  }
  printf("%d\n",prim());
  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n , dp[100000][2];
const int mod = 1e9 + 7;
vector<vector<int> > g;
int DFS( int u = -1 , int p = -1 , bool b = 0 )
{
    if( u == -1 )
        return DFS(0) + DFS(0,-1,1) ;
    if( g[u].size() == 1 && p != -1 )
        return 1;
    ll &d= dp[u][b];
    if( d != -1 )
        return d;
    d = 1;
    for(int i=0;i<g[u].size();++i)
    {
        if( g[u][i] == p )
            continue;
        d*=( DFS( g[u][i] , u )%mod + ( b == 0 ? DFS( g[u][i] , u , 1 ) : 0 )%mod )%mod;
        d%=mod;
    }
    return d;
}
int main()
{
    memset(dp,-1,sizeof dp);
    cin >> n;
    g.resize(n);
    for(int i=1;i<n;++i)
    {
        int f , t; cin >> f >> t;
        g[f-1].push_back(t-1);
        g[t-1].push_back(f-1);
    }
    cout << DFS()%mod;
    
    return 0;
}


Measured memory_bytes: 15616
from collections import defaultdict
from bisect import bisect_right

balls_count = defaultdict(int)

N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
ans = 0
beki_list = [pow(2, i) for i in range(1, 32)]
for a in A:
    balls_count[a] += 1

for a in A:
    if balls_count[a] == 0:
        continue
    balls_count[a] -= 1
    index = bisect_right(beki_list, a)
    pair = beki_list[index] - a
    if balls_count[pair] > 0:
        balls_count[pair] -= 1
        ans += 1
print(ans)

Measured memory_bytes: 55136
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  string s;cin >> s;
  reverse(all(s));
  int index = 0;
  bool issat = true;
  while(index<s.length()){
    if(s.substr(index,5) == "maerd") index+=5;
    else if(s.substr(index,5) == "esare") index+=5;
    else if(s.substr(index,6) == "resare") index+=6;
    else if(s.substr(index,7) == "remaerd") index+=7;
    else issat = false;
    if(!issat) break;
  }
  YESNO(issat);
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#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 a,b,c;

vector<int> vec(9);
rep(i,3)
{int x;
cin>>x;
vec.at(x-1)++;
}
bool flag1=false,flag2=false;

rep(i,9)
{
  if(vec.at(i)==2)
  {flag2=true;}
  if(vec.at(i)==1)
  {flag1=true;}
}

if(flag1&&flag2)
{cout << "Yes"<<endl;}
else
{
  cout << "No"<<endl;
}


}
/*vector <int> a(3);
for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }*/

Measured memory_bytes: 256
from collections import defaultdict
from math import factorial

n = int(input())

if n == 1:
    print(0)
    exit()


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


ls = factorization(n)
ans = 0

for i, j in ls:
    cnt = 0
    for i in range(1, 10*10):
        cnt += i
        if cnt > j:
            break
        ans += 1

print(ans)


Measured memory_bytes: 9732
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        g.append(list(map(int, input().split())))
    for i in range(h):
        k = list(map(int, input().split()))
        for j in range(w):
            g[i][j] = abs(g[i][j] - k[j])

    m = (h + w) * 80

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                dp[j][k + g[0][j]] = True
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                new_dp[0][k + g[i][0]] = True
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    new_dp[j][k + g[i][j]] = True
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()

Measured memory_bytes: 272660
#include<bits/stdc++.h>
#define db(x) cerr<<#x<<" = "<<x<<endl;
using namespace std;
int dis[100005],d[100005];
int main(){
	int n;
	cin>>n;
	dis[0]=1;
	long long ans=1;
	int tmp;
	cin>>tmp;
	if(tmp!=0) {
		puts("0");
		return 0;
	}
	for(int i=1; i<n; ++i) {
		cin>>d[i];
	}
	sort(d+1,d+n);
	for(int i=1; i<n; ++i) {
		if(d[i]==0) {
			puts("0");
			return 0;
		}
		ans*=1ll*dis[d[i]-1];
		ans%=998244353;
		++dis[d[i]];
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll ;
typedef double db;
const double pi = acos(-1) ;
#define pb         push_back
#define forab(i,a,b)       for(int i=(a);i<=(b);i++)
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define pcase(z,x)     printf("Case %ld: %lld\n",z,x)
#define nw				"\n"


int main(void)
{
	CIN;
	ll tc,l,k,sum=0,x=0,y,z=0,m=1,n=0,ans;

	cin>>k>>n;
	n--,k--;
	cout<<ceil(n*1.0/k);

}


Measured memory_bytes: 3764
import collections

def judge(k):
  pos=[0]*n
  dic=collections.defaultdict(int)
  s=set()
  for i in range(n):
    dic[arr[i][0]]+=1
  while 1:
    key=list(dic.keys())
    for i in key:
      if dic[i]>k:
        s.add(i)
        del dic[i]
    flag=True
    for i in range(n):
      if arr[i][pos[i]] in s:
        flag=False
        pos[i]+=1
        if pos[i]==m:
          return False
        dic[arr[i][pos[i]]]+=1
    if flag==True:
      return True

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
l=0
r=n+1
while r-l!=1:
  mid=(l+r)//2
  if judge(mid)==True:
    r=mid
  else:
    l=mid
print(r)

Measured memory_bytes: 4596
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    long long M;
    cin >> N >> M;
    vector<int> A(N);
    for (auto & a : A) cin >> a;
    long long tmp = 1;
    for (auto a : A) {
        long long b = a/2;
        tmp = tmp*b/__gcd(tmp, b);
        if (tmp > M || tmp/b%2 == 0) {
            puts("0");
            return 0;
        }
    }
    printf("%lld\n", (M/tmp+1)/2);
    return 0;
}


Measured memory_bytes: 640
a, b, c, d = [x for x in input()]

for bit in range(2**3):
  tmp = []
  for i in range(3):
    if bit & (1 << i):
      tmp.append(i)

  ops = ['-', '-', '-']
  for p in tmp:
    ops[p] = '+'
  eq = a + ops[0] + b + ops[1] + c + ops[2] + d
  if eval(eq) == 7:
    break
print(eq + '=7')

Measured memory_bytes: 3064