akhauriyash/Code-Regression huggingface dataset:
fun main(args: Array<String>) {
    val (n, x) = readLine()!!.split(' ').map(String::toInt)
    val ll = readLine()!!.split(' ').map(String::toInt)
    var p = 0
    var c = 1
    for (l in ll) {
        p += l
        if (x < p) break
        c++
    }
    println(c)
}


Measured memory_bytes: 38056
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        double sum = 0;
        for(int i=0; i<n; i++){
            sum += 1/sc.nextDouble();
        }
        
        System.out.println(1/sum);
    }
}

Measured memory_bytes: 26580
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

#include <cstdlib>

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n + 1, 0);
    REP(i, 0, n) {
        ll t;
        cin >> t;
        a[i + 1] = a[i] + t;
    }
    ll ans = 1LL << 60;
    REP(i, 1, n) {
        ll l = a[i];
        ll r = a[n] - a[i];
        chmin(ans, abs(l - r));
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N, A; cin >> N;
  
  bool ok  = true;

  for (int i = 0; i < N; i++) {
    cin >> A;
    if (A % 2) {
      continue;
    }
    if (A % 3 && A % 5) {
      ok = false;
    }
  }
  cout << (ok?"APPROVED":"DENIED");
  return 0;
  
}

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

////////////// Prewritten code follows. Look down for solution. ////////////////
#define x first
#define y second
#define len(x) ((int)(x).size())
using pii = pair<int, int>;
using ll = long long;
using llu = long long unsigned;
using ld = long double;

const ld EPS = 1e-9;
inline int cmp(ld x, ld y = 0, ld tol = EPS) {
	return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}

const int MOD = 1;
inline int mod (ll x, int m = MOD) {
	return (int)(((x%m) + m)%m);
}

////////////////////////// Solution starts below. //////////////////////////////

const int N = 3005;

int dp[N][N];
string s1, s2;
char ans[N];

void recu (int x, int y) {
	if (x == 0 or dp[x][y] == 0) return;
	while (dp[x-1][y] == dp[x][y]) --x;
	while (dp[x][y-1] == dp[x][y]) --y;
	ans[dp[x][y]] = s1[x-1];
	recu (x-1, y-1);
}

int main () {
	cin.tie (0);
	ios::sync_with_stdio (false);
	cin >> s1 >> s2;
	for (int i = 1; i <= len (s1); i++) {
		for (int j = 1; j <= len (s2); j++) {
			dp[i][j] = max (dp[i-1][j], dp[i][j-1]);
			if (s1[i-1] == s2[j-1])
				dp[i][j] = max (dp[i][j], dp[i-1][j-1] + 1);
// 			cout << dp[i][j] << ' ';
		}
// 		puts ("");
	}

	recu (len (s1), len (s2));
	for (int i = 1; i <= dp[len (s1)][len (s2)]; i++)
		cout << ans[i];
	cout << '\n';
	
	return 0;
}


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

N = int(input())

def g1(n, p):
    if n == 0:
        return 0

    return n // p + g1(n // p, p)


def g2(n, p):
    if n % 2 == 1:
        return g1(n, p) - g2(n - 1, p)
    res = g1(n // 2, p)
    if p == 2:
        res += n // 2
    return res


ans = min(g2(N, 2), g2(N, 5))
print(ans)


Measured memory_bytes: 3060
/// awoooooo

# include <bits/stdc++.h>
# define sz(x) (int)((x).size())

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair < int, int > pii;

const int N = (int)2e5 + 5;
const int inf = (int)1e9 + 7;


int n;
string s;

int main(){
  cin >> n >> s;
  if(n % 2){
    cout << "No\n";
    return 0;
  }
  string f1, f2;
  for(int i = 0; i < n; ++i){
    if(i < n / 2){
      f1 += s[i];
    } else{
      f2 += s[i];
    }
  }
  cout << (f1 == f2 ? "Yes" : "No") << "\n";
  return 0;
}


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

// Begin {{{
using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0; i < (n); ++i)
#define reps(i, s, n) for (i64 i = (s); i <= (n); ++i)
#define VAR(Type, ...) Type __VA_ARGS__; IN(__VA_ARGS__)
#define Float(x) OUTN(fixed, setprecision(x));

using i64 = int_fast64_t;
using pii = pair<i64, i64>;

template <class A, class B>
inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }

template <class A, class B>
inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

// IN
void IN() {}
template <class Head, class... Tail>
void IN(Head&& head, Tail&&... tail) {
  cin >> head;
  IN(forward<Tail>(tail)...);
}

// OUTS
void OUTS() {}
template <class Head, class... Tail>
void OUTS(Head&& head, Tail&&... tail) {
  cout << head << " \n"[sizeof...(tail)==0];
  OUTS(forward<Tail>(tail)...);
}

template <class T>
void OUTS(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e==&vec.back()]; }

template <class T>
void OUTS(vector<vector<T>> &df) { for (auto &vec : df) OUTS(vec); }

// OUTL
void OUTL() {}
template <class Head, class... Tail>
void OUTL(Head&& head, Tail&&... tail) {
  cout << head << "\n";
  OUTL(forward<Tail>(tail)...);
}

template <class T>
void OUTL(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

// OUTN
void OUTN() {}
template <class Head, class... Tail>
void OUTN(Head&& head, Tail&&... tail) {
  cout << head;
  OUTN(forward<Tail>(tail)...);
}

template <class T>
void OUTN(vector<T> &vec) { for (auto &e : vec) cout << e; }
// }}} End

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<int> vec(10);
  rep(i, 5) IN(vec[i]);
  VAR(int, k);
  for (int i = 0; i < 5; ++i) {
    for (int j = i + 1; j < 5; ++j) {
      if (abs(vec[j] - vec[i]) > k) {
        OUTL(":(");
        return 0;
      }
    }
  }
  OUTL("Yay!");
  return 0;
}


Measured memory_bytes: 256
from collections import deque

N, M = map(int, input().split())

miti = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    miti[A].append(B)
    miti[B].append(A)

res = [-1]*N
res[0] = N
d = deque()
d.append(0)

while True:
    now = d.popleft()
    
    for n in miti[now]:
        if not res[n] < 0:
            continue
        res[n] = now

        d.append(n)

    if not len(d):
        break

if -1 in res:
    print("No")
else:
    print("Yes")
    print("\n".join(str(r+1) for r in res[1:]))


Measured memory_bytes: 41556
a, b, c = gets.chomp.split(' ').map(&:to_i)
executed = Hash.new(false)
current = a
find = false
loop do
  mod = current % b
  break if executed[mod]
  executed[mod] = true
  find = true if mod == c
  current += a
end
puts find ? 'YES' : 'NO'

Measured memory_bytes: 1788
#![allow(unused_imports)]
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{fastout, input, marker::*};
use std::cmp::*;
use std::collections::*;
use superslice::*;

#[fastout()]
fn main() {
    input! {
        n: usize, k: usize,
        mut a: [i64; n],
    }
    let m = 1000000007i64;
    let mod_product = |acc: i64, &value: &i64| {
        (acc * value).rem_euclid(m)
    };

    if k == n || k % 2 == 1 && a.iter().all(|v| *v <= 0) {
        a.sort_by_key(|v| -*v);
        let ans = a.iter().take(k).fold(1, mod_product);
        println!("{}", ans);
        return;
    }

    a.sort_by_key(|v| Reverse(v.abs()));
    let mut plus = Vec::new();
    let mut minus = Vec::new();
    for i in 0..n {
        if a[i] >= 0 {
            plus.push(a[i]);
        } else {
            minus.push(a[i]);
        }
    }

    let mut ppos = 0;
    let mut mpos = 0;
    let mut vals = Vec::new();
    let mut retry = false;
    while vals.len() < k {
        if vals.len() < k - 1 && ppos + 1< plus.len() && mpos + 1 < minus.len() {
            if plus[ppos] * plus[ppos+1] < minus[mpos] * minus[mpos+1] {
                vals.push(minus[mpos]);
                vals.push(minus[mpos+1]);
                mpos += 2;
            } else {
                vals.push(plus[ppos]);
                vals.push(plus[ppos+1]);
                ppos += 2;
            }
        } else if vals.len() < k - 1 && mpos + 1 < minus.len() {
            vals.push(minus[mpos]);
            vals.push(minus[mpos+1]);
            mpos += 2;
        } else if ppos < plus.len() {
            vals.push(plus[ppos]);
            ppos += 1;
        } else {
            retry = true;
            break;
        }
    }
    let ans = if !retry {
        vals.iter().fold(1, mod_product)
    } else {
        a.sort_by_key(|v| v.abs());
        assert!(a.iter().filter(|v| **v == 0).count() == 0);
        a.iter().take(k).fold(1, mod_product)
    };
    println!("{}", ans);
}


Measured memory_bytes: 9732
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int a, b, c;

int main() {
	while(~scanf("%d %d %d", &a, &b, &c)) {
		printf("%d", min(a * b, c));
	}
}

Measured memory_bytes: 128
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        h: [usize; n]
    };

    let mut base = h[0];
    let mut count = 1;

    for i in 1..n {
        let x = h[i];
        if base <= x {
            count += 1;
            base = x;
        }
    }

    println!("{}", count);
}


Measured memory_bytes: 2156
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn f(s: &[char]) -> bool {
    let m = s.len();
    for i in 0..m {
        if s[i] != s[m - 1 - i] {
            return false;
        }
    }
    true
}

use std::iter::Iterator;

fn main() {
    input! {
        n: usize,
        m: usize,
        a : [f32; n],
    }

    let limit : f32 = (a.iter().sum::<f32>()) / ((4 * m) as f32);

    let mut cnt = 0;
    for item in a {
        if item >= limit {
            cnt = cnt + 1;
        }
    }

    if cnt >= m {
        println!("Yes");
    }else{
        println!("No");
    }


   
}


Measured memory_bytes: 2184
import sys
input = lambda: sys.stdin.readline().rstrip()
import bisect

A,B,Q = map(int, input().split())

INF = 10 ** 18

s = [-INF] + [int(input()) for _ in range(A)] + [INF]
t = [-INF] + [int(input()) for _ in range(B)] + [INF]

for i in range(Q):
    x = int(input())
    right_s = bisect.bisect_right(s, x)
    right_t = bisect.bisect_right(t, x)

    ans = INF
    
    for S in [s[right_s-1], s[right_s]]:
        for T in [t[right_t-1], t[right_t]]:
            ans = min(ans, abs(x-S) + abs(T-S), abs(x-T) + abs(S-T))

    print(ans)

Measured memory_bytes: 65244
from collections import Counter


def isOk():
    n = int(input())
    d = list(map(int, input().split()))
    m = int(input())
    t = list(map(int, input().split()))

    cd = Counter(d)
    ct = Counter(t)

    ans = "YES"
    for k, v in ct.items():
        if not k in cd:
            ans = "NO"
            break
        if v > cd[k]:
            ans = "NO"
            break
    return ans


print(isOk())


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

int main() {
	int N;
	string s, t;
	cin >> N >> s >> t;
	int i;
	for (i = N; i; i--)
		if (t.substr(0, i) == s.substr(N - i, i))
			break;
	printf("%d\n", 2 * N - i);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <numeric>
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <fstream>
using namespace std;

string add (string a, string b)
{
	reverse (a.begin(), a.end() );
	reverse (b.begin(), b.end() );

	while (a.length() != b.length()){
		if (a.length() > b.length()){
			b += '0';
		}else if (a.length() < b.length() ){
			a += '0';
		} // end if
	} // end while

	int i;
	string res = "";
	int carry = 0;

	for (i = 0; i < a.length(); ++i){
		int an = a[i] - '0';
		int bn = b[i] - '0';
		if (carry == 1){
			++an;
		} // end if
		if (an + bn >= 10){
			carry = 1;
		}else{
			carry = 0;
		} // end if
		res += ((an + bn) % 10) + '0';
	} // end for

	if (carry == 1){
		res += carry + '0';
	} // end if

	reverse (res.begin(), res.end() );
//	cout << res << endl;

	return res;
}

int main()
{
//	cut here before submit 
//	freopen("testcase.secret2", "r", stdin);
	string str = "";
	string sum = "0";

	while (getline (cin, str ) ){
		if (str.empty() ){
			continue;
		} // end if
		int len = str.length();
		int i;

		string num = "";
		for (i = 0; i < len; ++i){
			if (isdigit(str[i]) ){
				num += str[i];
			}else if (!num.empty() ){
				sum = add (sum, num);
				num = "";
			} // end if
		} // end for
		if (!num.empty() ){
			sum = add (sum, num);
		} // end if
	} // end loop

	cout << sum << endl;	
		
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main() {
	//input
	int K;
	string S;
	cin >> K >> S;

	//calculation
	int len = S.size();

	if (len <= K) {
		cout << S << endl;
		return 0;
	}

	string output = "";
	for (int i = 0; i < K; i++) {
		output += S[i];
	}
	output += "...";
	cout << output << endl;


	return 0;
}


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

using namespace std;
float fact(int n)
    {
    int res = 1;
    for(int i = 2; i <= n; i++)
        res*=i;
    return res;
    }
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    long long x[n],y[n],T[n];
    double  f;
    f=fact(n);
    for (int i=0;i<n;i++)
    {
        cin>>x[i]>>y[i];
        T[i]=i;
    }
    double  avg=0;
    double  sum;
    do
    {
    sum=0;
    for(int i=1;i<n;i++)
    {
    sum+=pow(pow((x[T[i]]-x[T[i-1]]),2)+pow((y[T[i]]-y[T[i-1]]),2),0.5);
    }
    avg+=sum/f;
    }while ( next_permutation(T,T+n) );
    cout.precision(12);
    cout<<avg;
    return 0;
}



Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
 
    // Your code here!
    int N,A,B;
    cin >> N >> A >> B;
    int x,y;
    x = A * N;
    y = B;
    int ans;
    ans = min(x,y); 
    cout << ans << endl;
}

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

int main(){
	int N,Q; string S; cin>>N>>Q>>S;

	vector<int> P(N+1), I(N+1);
	for(int i=1; i<=N; ++i){
		if(S[i-1]=='A' && S[i]=='C'){
			P[i] = P[i-1] + 1;
			P[i+1] = P[i];
			I[i] = i;
			I[i+1] = i;
		}
		else{
			P[i] = P[i-1];
			I[i] = I[i-1];
		}
	}

	for(int i=0; i<Q; ++i){
		int l,r; cin>>l>>r;
		int c = P[I[r]] - P[I[l]] + 1;
		if(l!=I[l]) --c;
		if(r==I[r]) --c;
		cout<< c <<endl;
	}

}

Measured memory_bytes: 1792
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var c = Array.ConvertAll(line, int.Parse);
        var q = int.Parse(Console.ReadLine().Trim());
        Console.WriteLine(getAns(c, n, q));
    }
    static int getAns(int[] c, int n, int q)
    {
        var b = new int[n];
        for (int i = 0; i < q; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var t = int.Parse(line[0]);
            var x = int.Parse(line[1]) - 1;
            var d = int.Parse(line[2]);
            if (t == 1)
            {
                b[x] += d;
                if (b[x] > c[x]) return x + 1;
            }
            else
            {
                b[x] -= d;
                if (b[x] < 0) return x + 1;
            }
        }
        return 0;
    }
}



Measured memory_bytes: 22064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

int main() {
  i64 x, a;
  cin >> x >> a;
  i64 y = 10;
  if (x < a) y = 0;
  cout << y << '\n';
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n; cin >> n;
    int arr[n] ={};
    long  double cal = 1.0;
    long  double sum = 0;
    for(int i=0; i<n;i++){
    	cin >> arr[i];
    	cal *=arr[i];
    }

    for(int i=0;i<n;i++){
    	sum += cal/arr[i];
    }

    cout << cal/sum << endl;


    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int n;
vector<int> g[202];
set<int> st;
ll cnt[202];
ll comb[505][505];
ll dp[202][202];

void predfs(int v){
  cnt[v]=1;
  for(int nv : g[v]){
    predfs(nv);
    cnt[v]+=cnt[nv];
  }
}

vector<ll> dfs(int v){
  vector<vector<ll> > a;
  for(int nv : g[v]){
    a.push_back(dfs(nv));
  }
  int m=a.size();
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  rep(i,m){
    rep(j,cnt[v]){
      if(dp[i][j]==0)continue;
      repl(nxt,j,cnt[v]){
        ll add=nxt-j;
        rep(k,a[i].size()){
          if(k<add)continue;
          ll c1=comb[j+add][add];
          ll c2=comb[j][k-add];
          (dp[i+1][nxt]+=((dp[i][j]*a[i][k]%mod)*c1%mod)*c2%mod)%=mod;
        }
      }
    }
  }
  vector<ll> res;
  rep(i,cnt[v]){
    res.push_back(dp[m][i]);
  }
  res.push_back(0);
  for(ll i=cnt[v];i>0;i--)res[i]=res[i-1];
  res[0]=0;
  return res;
}

int main(){

  rep(i,501)comb[i][0]=comb[i][i]=1;
  repl(i,1,501)repl(j,1,501)(comb[i][j]=comb[i-1][j]+comb[i-1][j-1])%=mod;

  cin>>n;
  rep(i,n)st.insert(i);
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    g[a].push_back(b);
    st.erase(b);
  }
  ll r=*st.begin();
  predfs(r);
  vector<ll> a;
  a=dfs(r);
  ll res=0;
  rep(i,n+1)(res+=a[i])%=mod;
  cout<<res<<endl;
  return 0;
}



Measured memory_bytes: 5480
#include <bits/stdc++.h>
using namespace std;
#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define contests_de_diya_kar 0
#define PB push_back
#define MP make_pair
#define int long long
#define MOD ((long long) (1000*1000*1000 + 7))
#define inf (int) 2e15
#define exit(a, b) return cout << a, b;
#define eps (double)1e-8
#define forn(a, b, i) for (int i = a; i < b; i += 1)
#define vi vector<int>
#define vb vector<bool>
#define all(v) v.begin(), v.end()
#define ll long long 
#define pii pair<int, int>
#define mii map<int, int> 
#define print(stuff) cout << stuff << endl
#define len(stuff) stuff.size()

const int MODULO = MOD;
int n;
bool vis[3][1001][4];
int dp[3][1001][4];
bool blocked[3][1001];

int rec (int row, int col, int type) {
	if (vis[row][col][type]) return dp[row][col][type];
	vis[row][col][type] = true;
	if (blocked[row][col]) {
		dp[row][col][type] = 0;
		return 0;
	}
	if (type == 0) {
		if (row >= 1) {
			if (col >= n - 1 && row != 2) {
				dp[row][col][type] = 0;
				return 0;
			}
			dp[row][col][type] += rec(row - 1, col, 2);
			dp[row][col][type] %= MODULO;
		}
	} 
	if (type == 1) {
		if (row <= 1) {
			if (col >= n - 1) {
				dp[row][col][type] = 0;
				return 0;
			}
			dp[row][col][type] += rec(row + 1, col, 3);
			dp[row][col][type] %= MODULO;
		}
	}
	if (type == 2) {
		if (col == 0 && row == 0) {
			dp[row][col][type] = 1;
			return dp[row][col][type];
		}
		if (col >= 1 && row < 2) {
			dp[row][col][type] += rec(row, col - 1, 0);
			dp[row][col][type] %= MODULO;
			dp[row][col][type] += rec(row, col - 1, 1);
			dp[row][col][type] %= MODULO;
		}
	}
	if (type == 3) {
		if (col >= 1 && row >= 1) {
			dp[row][col][type] += rec(row, col - 1, 0);
			dp[row][col][type] %= MODULO;
			dp[row][col][type] += rec(row, col - 1, 1);
			dp[row][col][type] %= MODULO;
		}
		else {
			dp[row][col][type] = 0;
			return dp[row][col][type];
		}
	}
}
signed main () {
	start_routine;
	
	#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#endif 

	int n;
	cin >> n;

	int a;
	int cnt = 0;
	forn(0, n, i) {
		cin >> a;
		while (a % 2 == 0) cnt += 1, a /= 2;
	}

	cout << cnt;
	end_routine;
}


Measured memory_bytes: 256
"""
Asの部分集合Tの部分集合Uについて考える

1. Tに属さない
2. Tに属し、Uに属さない
3. Tに属し、Uに属す

の3通り考えられる。
i番目までにおいて、部分集合Uの和がkになる⇨dp[i][k]

遷移としては
dp[i+1][k] = dp[i][k] * 2 # 1.2
dp[i+1][k+A[i]] += dp[i][k]
"""
n,s = map(int, input().split())
As  = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    a = As[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        if j + a <= s:
            dp[i+1][j+a] += dp[i][j]
        dp[i+1][j] %= mod
    
            

ans = 0
print(dp[n][s]%mod)



Measured memory_bytes: 138772
a = input()
num = []
nn = []
uooo = []
for i in range(len(a)):
    num.append(int(a[i]))
for i in range(len(a)-2):
    nn.append(num[i]*100+num[i+1]*10+num[i+2])
    uo = abs(753 - nn[i] )
    uooo.append(uo)
    
uooo.sort()
print(uooo[0])

Measured memory_bytes: 3064
#![allow(unused)]

fn solve<R: std::io::BufRead>(mut sc: Scanner<R>) {
    let n: usize = sc.get();
    let m: usize = sc.get();

    let mut ds: Vec<usize> =
        (1..=m).map(|d| if d % 2 != 0 { d } else { n - d }).collect();

    for d in 1..=m {
        if d % 2 != 0 {
            let a = n / 2 - d / 2;
            println!("{} {}", a, a + ds[d - 1]);
        } else {
            let a = d / 2;
            println!("{} {}", a, a + ds[d - 1]);
        }
    }
}

macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

//
// Based on EbTech's Scanner https://stackoverflow.com/q/56449027
//
struct Scanner<'a, R: std::io::BufRead> {
    reader: R,
    buf: String,
    iter: std::str::SplitWhitespace<'a>,
}

impl<'a, R: std::io::BufRead> Scanner<'a, R> {
    fn new(reader: R) -> Self {
        Self { reader, buf: String::new(), iter: "".split_whitespace() }
    }

    fn get<T: std::str::FromStr>(&mut self) -> T {
        if let Some(t) = self.iter.next() {
            return t.parse().ok().expect("Parse error")
        }
        self.buf.clear();
        self.reader.read_line(&mut self.buf).expect("I/O error");
        self.iter = unsafe { std::mem::transmute(self.buf.split_whitespace()) };
        self.get()
    }

    fn gets<T: std::iter::FromIterator<char>>(&mut self) -> T {
        use std::io::Read;
        assert_eq!(self.iter.next(), None);
        self.reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap() as char)
            .skip_while(|&c| c.is_whitespace())
            .take_while(|&c| !c.is_whitespace())
            .collect()
    }
}

fn main() {
    let stdin = std::io::stdin();
    solve(Scanner::new(stdin.lock()));
}



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

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            var rl = RL();
            //var sprlst = spr(rl);
            //var intlist = sprlst.Select(x => c2i(x)).ToList();
            var k = c2i(rl);
            //var ls1 = Enumerable.Range(0, 10).Select(x => (long)x);
            var fbsum = (k * (k + 1)) / 2;
            var num3 = (k / 3) * 3; 
            var num5 = (k / 5) * 5;
            var num15 = (k / 15) * 15;
            var ans = fbsum - getsum(num3,3)-getsum(num5,5) +getsum(num15,15);

            bool ret = false;



            Console.WriteLine(ans);
            //Console.ReadLine();
            




        
        }
        static Int64 getsum(Int64 last, int ct) { return (ct + last) * (last / ct) / 2; }
        static string RL() { return Console.ReadLine().Trim(); }
        static IEnumerable<string> spr(string s) { return s.Split(' '); }
        static Int64 c2i(string c) { return Int64.Parse(c); }
        //static double c2d(string c) { return double.Parse(c); }
        static string bool2ret(bool b) { return b ? "Yes" : "No"; }
    }
}


Measured memory_bytes: 27536
#include <iostream>
using namespace std;
 
int main(){
 int n;
  cin >> n;
  int nn = n/1.08;
  if((int)(1.08*nn) == n){
  	cout << nn;
  }else if((int)(1.08*(nn+1)) == n){
   	 cout << nn+1;
  }else{
    cout << ":(";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const lli mod = 1e9 + 7;

int main()
{
  int n, k;
  while (scanf("%d %d", &n, &k) != EOF)
  {
    int lo = 0, hi = n;
    lli los = 0, his = 0;
    for (int i = 0; i < k; i++, lo++, hi--)
    {
      los += lo;
      his += hi;
    }

    lli ans = 1;
    for (int i = k; i <= n; i++, lo++, hi--)
    {
      ans = (ans + max(0LL, (his - los + 1))) % mod;
      los += lo;
      his += hi;
    }
    printf("%lld\n", ans);
  }
  return 0;
}

Measured memory_bytes: 3828
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String upper = line.toUpperCase();
        String lower = line.toLowerCase();
        for (int i = 0; i < line.length(); i++) {
            if (line.charAt(i) == upper.charAt(i)) {
                System.out.print(lower.charAt(i));
            } else {
                System.out.print(upper.charAt(i));
            }
        }
        System.out.println("");
        scanner.close();
    }
}



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

int main() {
 int N; 
  cin >> N;
  vector<int>card(N);
  for(int i=0;i<N;i++){
  cin>>card.at(i);
  }
  
  
 sort(card.begin(),card.end());//小さい順に
 reverse(card.begin(),card.end());//大きい順に
  
 int Alice=0;
 int Bob=0;
   
 for(int i=0;i<N;i++){
 if((i%2)==0){
  Alice+=card.at(i); 
 } 
 else{
  Bob+=card.at(i);
 }  
 }
  cout<<Alice-Bob<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int main() {
    int N; cin >> N;
    vector<string> S(200005); rep(i, N) cin >> S[i];
    map<string, int> m;
    rep(i, N) {
        m[S[i]] = 1;
    }
    cout << m.size() << endl;
}

Measured memory_bytes: 25096
A, B, C, X, Y = map(int, input().split())
ans = 0
if A+B <= 2*C:
    ans += (A+B)*min(X,Y)
else:
    ans += 2*C*min(X,Y)

if X == Y:
    print(ans)
elif X < Y:
    if B <= 2*C:
        ans += B*(Y-X)
    else:
        ans += 2*C*(Y-X)
    print(ans)
else:
    if A <= 2*C:
        ans += A*(X-Y)
    else:
        ans += 2*C*(X-Y)
    print(ans)

Measured memory_bytes: 3064
n = int(input())
A = [*map(int, input().split())] + [0]

yen = 1000
kabu_yen = 0
kabu_n = 0
last_buy = -1
for i in range(1,n+1):
    if A[i-1] < A[i]: # buy : after up
        tanka = A[i-1]
        m = yen // tanka
        cost = tanka * m
        yen -= cost
        kabu_yen += cost
        kabu_n += m

    elif A[i-1] > A[i]: # sell: after down
        yen += A[i-1] * kabu_n
        kabu_yen = 0
        kabu_n = 0

print(yen)


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

struct edge {
    int from, to;
};

struct graph {
    int n;
    vector<vector<edge>> ev;
    graph(int _n) {
        n = _n;
        ev.assign(n+1, vector<edge>());
    }
    void push_edge(int i, int j) {
        ev[i].push_back({i, j});
    }
};

void tp_dfs(int v, graph &g, vector<bool> &visited, deque<int> &tps) {
    visited[v] = true;
    for (int i = 0; i < g.ev[v].size(); i++) {
        int nextv = g.ev[v][i].to;
        if (visited[nextv]) continue;
        tp_dfs(nextv, g, visited, tps);
    }
    tps.push_front(v);
}

deque<int> TopologicalSort(graph &g) {
    deque<int> tps;
    vector<bool> visited(g.n+1, false);
    for (int i = 1; i <= g.n; i++) {
        if (!visited[i]) {
            tp_dfs(i, g, visited, tps);
        }
    }
    return tps;
}

int main() {
    int n, m; cin >> n >> m;
    graph g(n);
    for (int i = 0; i < m; i++) {
        int p, q; cin >> p >> q;
        g.push_edge(p, q);
    }
    deque<int> tps = TopologicalSort(g);
    vector<int> pathlen(n+1, 1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int v = tps[i];
        for (int j = 0; j < g.ev[v].size(); j++) {
            int vv = g.ev[v][j].to;
            pathlen[vv] = max(pathlen[vv], pathlen[v]+1);
            ans = max(ans, pathlen[vv]);
        }
    }
    cout << ans - 1 << endl;
    return 0;
}

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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

vi d_from(int from, vvi& nx) {
    int N = nx.size();
    vi dst(N, N+1);
    queue<ii> q; q.push(ii(0, from));
    while (!q.empty()) {
        ii t = q.front(); q.pop();
        int d = t.first, u = t.second;
        if (dst[u] <= d) continue;
        dst[u] = d;
        for (int v: nx[u]) {
            if (dst[v] <= d+1) continue;
            q.push(ii(d+1, v));
        }
    }
    // cerr << from << " " << dst << endl;
    return dst;
}

bool solve(int N, vi& a, vi& b) {
    vvi nx(N);
    rep(i,N-1){
        nx[a[i]].pb(b[i]);
        nx[b[i]].pb(a[i]);
    }

    vi da = d_from(0, nx), db = d_from(N-1, nx);

    int fennec=0, snuke=0;
    rep(i,N){
        if (da[i] <= db[i]) ++fennec;
        else ++snuke;
    }
    return (fennec > snuke);
}

int main() {
    int N; cin >> N;
    vi a(N-1), b(N-1);
    rep(i,N-1) {
        cin >> a[i] >> b[i]; --a[i]; --b[i];
    }
    cout << (solve(N,a,b) ? "Fennec":"Snuke") << endl;
    return 0;
}


Measured memory_bytes: 7364
from collections import Counter

n = int(input())

if n == 1:
    print(0)
else:
    lis = [i for i in range(n+1)]
    for i in range(2, int(n**0.5) + 1):
        if lis[i] == i:
            lis[i] = i
            for j in range(i**2, n+1, i):
                if lis[j] == j:
                    lis[j] = i
#print(lis)
def bunkai(m):
    ans = []
    now = lis[m]
    cnt = 1
    for i in range(m):
        m = m//lis[m]
        if now == lis[m]:
            cnt += 1
        else:
            ans.append(cnt)
            cnt = 1
            now = lis[m]
        
        if m == 1:
            break
    return ans

ans = 1
for i in range(2,n):
    tmp = 1
    yaku = bunkai(i)
    for i in yaku:
        tmp *= (i +1)
    ans += tmp

print(ans)




Measured memory_bytes: 49036
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define llu unsigned long long int
#define Endl endl
#define mod  998244353
#define mkp make_pair
#define pb push_back
#define cin(n) scanf("%d",&n)
#define cout(n) printf("%d ",n)
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d ",n)
#define bitget(n) __builtin_popcountll(n)
ll dx[] = {1,1,0,-1,-1,-1,0,1};
ll dy[] = {0,-1,-1,-1,0,1,1,1};
ll dxx[] = {1,-1,0,0};
ll dyy[] = {0,0,-1,1};
ll modexpo(ll x,ll y){if(y==0)return 1;if(y%2){ll viky=modexpo(x,y/2);
return (((x*viky)%mod)*viky)%mod;}else{ll viky=modexpo(x,y/2);return (viky*viky)%mod;
}}
bool isvalid(ll x,ll y,ll n, ll m) { return (x>=0&&x<n&&y>=0&&y<m); }

ll ap[100011];

int main() {
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n,m;
    cin>>n>>m;
    multiset<ll>st;
    for(ll i=1;i<=n;i++){
        ll l;
        cin>>l;
        st.insert(l);
    }
    
    ll ans = 0;

    while(m--){

        if(st.size()){

            multiset<ll>::iterator it = st.end();
            it--;
            ll val = (*it);
            st.erase(it);
            if(val<=1){
                continue;
            }
            st.insert(val/2);
        }else{
            break;
            // multiset<ll>::iterator it = st.end();
        }

    }

    for(multiset<ll>::iterator it = st.begin();it!=st.end();it++){

        ans += (*it);
    }

    cout<<ans;

    return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    vector<int> array;
    int a;
    cin >> a;
    array.push_back(a);
    cin >> a;
    array.push_back(a);
    cin >> a;
    array.push_back(a);
    sort(array.begin(), array.end(), greater<int>());
    cout << (array[0] * array[0] == array[1] * array[1] + array[2] * array[2] ? "YES" : "NO") << endl;
  }
}

Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int n, m;
  cin >> n >> m;
  vector<ll> x(n), y(n), z(n);
  rep(i, n) {
    cin >> x[i] >> y[i] >> z[i];
  }
  ll ans = LLONG_MIN;
  rep(i, 2)rep(j, 2)rep(k, 2) {
    vector<ll> score(n);
    ll t = 0;
    rep(l, n) {
      score[l] += i ? x[l] : -x[l];
      score[l] += j ? y[l] : -y[l];
      score[l] += k ? z[l] : -z[l];
    }
    sort(score.rbegin(), score.rend());
    rep(l, m) t += score[l];
    ans = max(ans, t); 
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int cnt = 1;
    string buf = string() + s[0];
    for(int i=1;i<s.size();i++){
        cnt++;
        string nw = string() + s[i];
        if(nw == buf){
            if(i == s.size()-1)
                cnt--;
            i++;
            nw += s[i];
        }
        buf = nw;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <limits.h>
#define N 200

int matrix(int[] ,int);
int min(int ,int);

main(){
  int a[N],i,n,o;
  scanf("%d",&n);

  for(i=1;i<n;i++){
    scanf("%d %d",&a[i],&o);
  }
  scanf("%d %d",&a[i],&a[i+1]);

  matrix(a,n+2);
  return 0;
}


int matrix(int A[],int x){
  int i,j,n,o,p,q;
  int B[N][N];
  
  n = x - 1;
  
  for(i = 1; i <= n; i++){
    B[i][i] = 0;
  }
  
  for(o = 2; o <= n; o++){
    for(i = 1; i <= n-o+1; i++){
      
      j = i+o-1;
      B[i][j] = INT_MAX;
      
      for(p = i; p <= j-1; p++){
	q = B[i][p] + B[p+1][j] + A[i-1]*A[p]*A[j];
	B[i][j] = min(B[i][j],q);
      }
    }
  }
  printf("%d\n",B[i][j]);
}

int min(int a,int b){
  
  if(a <= b){
    return a;
  }
  else{
    return b;
  }
}

Measured memory_bytes: 676
N,K = map(int,input().split())
ans = 0
temp_max = 0
temp_min = 0
for i in range(1,N+2):
  temp_max += N-i+1
  temp_min += i-1
  if i  >= K:
    ans += (temp_max - temp_min + 1)
print(ans%(10**9+7))

Measured memory_bytes: 9100
w, h, n = map(int, input().split())

s = [[int(i) for i in input().split()] for j in range(n)]

u_left = 0
v_low = 0
u_right = w
v_high = h

for num in s:
    x = num[0]
    y = num[1]
    a = num[2]
    if a == 1 and x >= u_left:
        u_left = x
    elif a == 2 and x <= u_right:
        u_right = x
    elif a == 3 and y >= v_low:
        v_low = y
    elif a == 4 and y <= v_high:
        v_high = y

s = (u_right-u_left)*(v_high-v_low)
if u_left < u_right and v_low < v_high:
    print(s)
else:
    print(0)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <functional>
#include <chrono>
#include <cstring>
#include <limits.h>

using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<lint> vl;
typedef pair<lint,lint> pll;

#define mpr make_pair


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

    lint n, m, s; cin>>n>>m>>s;
    vector<vector<pair<lint, pair<lint, lint>>>> mp(n+1); // son, coin, time
    for (lint i=0; i<m; ++i){
        lint u, v, a, b;
        cin>>u>>v>>a>>b;
        mp[u].push_back({v, {a,b}});
        mp[v].push_back({u, {a,b}});

    }
    vl c(n+1); vl time(n+1);
    for (int i=1; i<=n; ++i){
        cin>>c[i]>>time[i];
    }
    lint maxcoin = (n+5)*50;
    vector<vl> dp(n+1, vl(maxcoin+1, LONG_LONG_MAX));

    queue<pll> bfs;
    auto push = [&](lint city, lint coin, lint time){
        //if (coin > maxcoin) return;
        coin = min(coin, maxcoin);
        if (time < dp[city][coin]){
            dp[city][coin] = time;
            bfs.push({city, coin});
        }
    };

    push(1, s, 0);
    while (!bfs.empty()) {
        pll p = bfs.front(); bfs.pop();
        //move
        lint city = p.first;
        lint coin = p.second;
        lint curtime = dp[city][coin];
        for (pair<lint, pair<lint, lint>> str : mp[city]){
            lint son = str.first;
            lint cost = str.second.first;
            lint time = str.second.second;
            if (coin >= cost){
                push(son, coin - cost, time + curtime);
            }
        }
        //change
        push(city, coin + c[city], curtime + time[city]);

    }
    for (int i=2; i<=n; ++i){
        lint res = LONG_LONG_MAX;
        for (int c=0;c<=maxcoin; ++c){

            res = min(res, dp[i][c]);
        }
        cout<<res<<"\n";
    }


}


Measured memory_bytes: 5356
import sys
sys.setrecursionlimit(500000)

N = int(input())
global ans
ans = []
def dfs(now,rank,root_,m):
    root = root_[:]
    if rank == N:
        root.append(now)
        ans.append(''.join([chr(i+ord('a')) for i in root]))
    else:
        root.append(now)
        for i in range(m+2):
            dfs(i,rank+1,root,max(m,i))

dfs(0,1,[],0)
ans.sort()
print(*ans,sep='\n')

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

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

	int N;
	cin >> N;
	if (N % 2 == 0) cout << N / 2 - 1 << endl;
	else cout << N / 2 << endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int H, W;
    cin >> H >> W;
    auto c = make_v<ll>(10, 10);
    auto distance = make_v<ll>(10, 10); //distance[i][j]は数字iを数字jに変えるときの最小コスト
    rep(i, 10)
    {
        rep(j, 10)
        {
            cin >> c[i][j];
        }
    }
    distance = c;
    rep(k, 10)
    {
        rep(i, 10)
        {
            rep(j, 10)
            {
                chmin(distance[i][j], distance[i][k] + distance[k][j]);
            }
        }
    }

    ll ans = 0;
    rep(i, H)
    {
        rep(j, W)
        {
            int A;
            cin >> A;
            if (A != -1)
                ans += distance[A][1];
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define forn(i,n) for(int i = 0; i < (int) n; i++)
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;
typedef long long ll;

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

  int d = 1;
  ll cnt = 0;
  ll p26 = 26;

  while (n > cnt + p26) {
    cnt += p26;
    p26 *= 26;
    d++;
  }

  n -= cnt;
  n--;
  vector<int> v;
  forn(i, d) {
    v.push_back(n % 26);
    n /= 26;
  }

  reverse(all(v));

  for(int x : v) cout << char('a' + x);
  cout << "\n";
}


Measured memory_bytes: 3628
//#include<cstdio>
//#include<cassert>
//#include<iostream>
//#include<cstring>
//#include<algorithm>
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((int)1e9 + 5)
#define MAXL ((ll)3e18 + 7)
#define MAX_X ((ll)1e5 + 2)
#define pi (2.0*acos(0))
#define M ((int)1e6 + 7)
#define MOD ((int)1e9 + 7)
#define NN ((int)3e6 + 7)
#define N ((int)2e5 + 5)
#define eps (0)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define logn 29
#define endl "\n"
#define mp make_pair
#define BUCK 105
#define RIG ((idx<<1)|1)
#define LEF (idx<<1)
//#define int ll


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

/*fast io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/




typedef tree < int,  null_type,  less < int >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).


int arr[N] , nxt[N] , pos[N];


int main()
{
    fastio;
    int n ;
    cin>>n;
    for(int i = 1 ; i<=n ; i++){
        cin>>arr[i];
        pos[arr[i]] = i;
    }
    nxt[n] = n+1;
    for(int i = n-1 ; i>0; i--){
        if(pos[i+1]<pos[i]) nxt[i] = i+1;
        else nxt[i] = nxt[i+1];
    }
    int ans = n+1-nxt[1];
    for(int i = 1 ; i<n ; i++){
        ans = min(ans , i + n+1 - nxt[i+1]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2560
import java.io.*;
import java.lang.*;
import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static int typeList[];
	public static int types;
	public static int minCount;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int change, i;
		change = sc.nextInt();
		types = sc.nextInt();
		
		typeList = new int[types];
		for(i = 0; i < types; i++){
			typeList[i] = sc.nextInt();
		}
		Arrays.sort(typeList);
		minCount = change / typeList[types - 1] + change % typeList[types - 1];
		
		Main.check(change, 0, types - 1);
		System.out.println(minCount);
	}
	public static void check(int remChanges, int count, int typeIndex){
		if(typeIndex == 0){
			// type must be 1
			if(remChanges + count < minCount){
				minCount = remChanges + count;
				//System.out.println(minCount);
			}
			return;
		}
		if(count > minCount){
			return;
		}
		int tmp, uses;
		
		for(uses = Math.min(remChanges / typeList[typeIndex], minCount - count); uses >= 0; uses--){
			tmp = uses * typeList[typeIndex];
			if(tmp == remChanges){
				if(count + uses < minCount){
					minCount = count + uses;
				//System.out.println(minCount);
				}
				return;
			}
			Main.check(remChanges - tmp, count + uses, typeIndex - 1);
		}
		return;
	}
}

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

using namespace std;

int main()
{
    int n;
    double p[3001];

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> p[i];

    double dp[n+1][n+1];

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            dp[i][j] = 0.0;
        }
    }

    dp[0][0] = 1.0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            dp[i][j] += (dp[i-1][j] * (1.0 - p[i]));

            if (j)
                dp[i][j] += (dp[i-1][j-1] * p[i]);
        }
    }

    double ans = 0.0;

    for (int i = 0; i <= n; i++)
    {
        if (i > n-i)
        {
            ans = ans + dp[n][i];
        }
    }

    cout << fixed << setprecision(12) <<  ans << "\n";

    return 0;

}

Measured memory_bytes: 70656