akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define INF (2000000001)
#define X first
#define D second
typedef pair<int,int> P;
int N,M;
vector<P> R[152];
int dp[151][11][1001];
inline int ab(int a){ return a>0?a:-a; }
int solve(int no,int id,int m){
  if( no >= N ) return 0;
  if(dp[no][id][m]!=-1) return dp[no][id][m];
  int ret=INF;
  for(int i=0;i<(int)R[no].size();i++){
    ret = min(solve(no+1,i,m)+(R[no-1][id].D+R[no][i].D)*ab(R[no-1][id].X-R[no][i].X),ret);
  }
  if(m < M){
    if(no + 1 >= N)
      ret = 0;
    else
      for(int i=0;i<(int)R[no+1].size();i++){
	ret = min(solve(no+2,i,m+1)+(R[no-1][id].D+R[no+1][i].D)*ab(R[no-1][id].X-R[no+1][i].X),ret);
    }
  }
  //  printf("%d %d %d %d  %d\n",no,id,m,ret);
  return dp[no][id][m]=ret;
}
int main(){
  while(1){
    scanf("%d %d",&N,&M);
    if(!N&&!M) break;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++){
      int k;
      scanf("%d",&k);
      for(int j=0;j<k;j++){
	int x,d;
	scanf("%d %d",&x,&d);
	R[i].push_back(P(x,d));
	///	printf("%d %d\n",R[i][j].X,R[i][j].D);
      }
    }
    int res=INF;
    for(int i=0;i<(int)R[0].size();i++){
      res = min(res,solve(1,i,0));
    }
    if(M>0){
      for(int i=0;i<(int)R[1].size();i++){
	res = min(res,solve(2,i,1));
      }      
    }
    printf("%d\n",res);
    for(int i=0;i<N;i++) R[i].clear();
  }
}

Measured memory_bytes: 7724
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int D;
int C[30];
int S[400][30];
int last[400][30];

ll score(vector<int>& t)
{
  ll s = 0LL;
  REP(i,t.size()){
    s += S[i][t[i]];
    REP(j,26) last[i+1][j] = last[i][j];
    last[i+1][t[i]] = i+1;
    REP(j,26){
      s -= C[j] * (i+1-last[i+1][j]);
    } 
  }
  return s;
}

ll score_2(vector<int>& t, ll before, int d, int old, int q)
{
  ll s = before;
  s += S[d][q] - S[d][old];
  FOR(i,d,D){
    if(t[i]==old) break;
    s += C[old] * ((i+1) - last[i+1][old]);
    s -= C[old] * ((i+1) - last[d][old]);
  }
  FOR(i,d,D){
    if(i!=d && t[i]==q) break;
    s += C[q] * ((i+1) - last[i+1][q]);
    s -= C[q] * ((i+1) - (d+1));
  }

  return s;
}

vector<int> init(void)
{
  vector<int> t;
  REP(d, D){
    ll max_sc = LLONG_MIN;
    int ind = 0;
    REP(i,26){
      t.push_back(i);
      ll sc = score(t);
      if(max_sc<sc){
        max_sc = sc;
        ind = i;
      }
      t.pop_back();
    }
    t.push_back(ind);
  }
  return t;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  random_device rnd;
  mt19937 mt(rnd());
  uniform_int_distribution<> rand365(0, 364);
  uniform_int_distribution<> rand26(0, 25);
  uniform_int_distribution<> rand2(0, 1);
  uniform_int_distribution<> rand360(0, 359);
  uniform_int_distribution<> rand4(0, 3);

  cin >> D;
  REP(i,26) cin >> C[i];
  REP(i,D) REP(j,26) cin >> S[i][j];

  auto T = init();
  ll max_score = score(T);
  
  int ti = clock();
  while(clock() - ti < 190 * CLOCKS_PER_SEC / 100){ 
    REP(loop,100){
      int cmd = rand2(mt);
      if(cmd==0){
        int d = rand365(mt);
        int q = rand26(mt);
        int old = T[d];
        T[d] = q;
        ll tmp = score_2(T, max_score, d, old, q);
        if(max_score<tmp){
          max_score = tmp;
          FOR(i,d,D){
            if(T[i]==old) break;
            last[i+1][old] = last[d][old];
          }
          FOR(i,d,D){
            if(i!=d && T[i]==q) break;
            last[i+1][q] = (d+1);
          }
        }else{
          T[d] = old;
        }
      }else{
        int d1 = rand360(mt);
        int d2 = d1 + rand4(mt);
        swap(T[d1],T[d2]);
        ll tmp = score(T);
        if(max_score<tmp){
          max_score = tmp;
        }else{
          swap(T[d1], T[d2]);
          REP(i,D) REP(j,64) last[i+1][j] = last[i][j];
        }
      }
    }
  }
  REP(i,D) cout << T[i]+1 << '\n';
  return 0;
}


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

using namespace std;

int main()
{
    char s[15], t[15];
    cin >> s >> t;
    int flag = 0;
    if(strlen(s) != strlen(t)-1) flag = 1;
    else{
        for(int i = 0; i < strlen(s); i++){
            if(s[i] != t[i]){
                flag = 1;
                break;
            }
        }
    }
    if(flag == 1) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3624
/*{{{*/
#include <bits/stdc++.h>
#ifdef _GLIBCXX_DEBUG
int c_;
#define cout (c_?cerr:cout)
#define debug(...) {if(!c_)cerr<<"\033[96;1m";++c_;\
__VA_ARGS__;--c_; if(!c_)cerr<<"\033[0m";}
#else
#define debug(...)
#endif
#define st first
#define nd second
#define all(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()
#define dump(...) debug(print(#__VA_ARGS__, __VA_ARGS__))
#define dump_range(...) debug(cerr<<#__VA_ARGS__<<": ";print_range(__VA_ARGS__))
using namespace std; using ll = long long; 
template< typename t > using V = vector< t >; void print(){cout<<'\n';}
template< typename t, typename... v > void print(const t& a, v&&... b)
{cout << a << ' '; print(b...);}
template< typename t > void print_range(t a, const t& b)
{while (a!=b) cout << (*a++) << ' '; cout << '\n';}
/*}}}*/

constexpr int maxn = 1e5;

int n, k;
ll tb[maxn];

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

    cin >> n >> k;

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

    ll res = 1e15;

    for (int l = 0; l < 2; ++l)
    {
        int pt = 0;
        while (pt < n and tb[pt] < 0)
            ++pt;

        dump_range(tb, tb + n);

        for (int i = 0; i < k; ++i)
        {
            int lo = pt - i;
            if (lo < 0) break;
            ll sum = 0;
            sum += (lo == pt? 0 : -tb[lo]) * 2;
            int q = k - i;
            int hi = pt + q - 1;
            if (hi >= n) continue;
            sum += (hi == pt - 1? 0 : tb[hi]);
            res = min(res, sum);
        }

        for (int i = 0; i < n; ++i)
            tb[i] = -tb[i];

        reverse(tb, tb + n);
    }

    print(res);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int mx=100010;
int arr[mx][3],n;
int dp[mx][3];
int f(int pos,int ty){
	if(pos==n)return 0;
	int &ans=dp[pos][ty];
	if(ans^-1)return ans;
	for(int i=0;i<3;i++){
		if(ty^i || !pos){
			ans=max(ans,f(pos+1,i)+arr[pos][i]);
		}
	}
	return ans;
}

int main(int argc, char const *argv[])
{
	memset(dp,-1,sizeof dp);
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			cin>>arr[i][j];
		}
	}
	cout<<f(0,0)<<endl;

	return 0;
}

Measured memory_bytes: 10368
<?php


[$N] = fscanf(STDIN, "%d");

$list = array_fill(1,1000000,0);
for($i=1;$i<=1000;$i++){
    for($j=$i;$j<=1000000;$j++){
        if($i * $j > 1000000){
            break;
        }
        if($i === $j){
            $list[$i * $j]++;
        }else{
            $list[$i * $j]+=2;
        }

    }
}
$ans = 0;
for($i=1;$i<$N;$i++){
    $ans += $list[$i];
}

echo $ans;

Measured memory_bytes: 47228
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s;
    getline(cin, s);
    int i = 0;
    while (s[i]){
        if (s[i] >= 65 && s[i] <= 90)
            s[i] += 32;
        else if (s[i] >= 97 && s[i] <= 122)
            s[i] -= 32;
        i++;
    }
    cout << s << endl;
}



Measured memory_bytes: 3200
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        try(Scanner sc = new Scanner(System.in)){
            while(true){
                int n =sc.nextInt();
                if(n == 0){
                    break;
                }
                int[] scores = new int[n];
                for(int i=0;i<scores.length;i++){
                    scores[i]=sc.nextInt();
                }
                double average=0,variance=0;
                for(int j=0;j<scores.length;j++){
                    average=average+scores[j];
                }
                average=average/n;
                for(int k=0;k<scores.length;k++){
                    variance=variance+(scores[k]-average)*(scores[k]-average);
                }
                variance=variance/n;
                System.out.println(Math.sqrt(variance));    
            }
        }
    }
}


Measured memory_bytes: 31112
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
  long long A, B, g;
  cin >> A >> B;
  for(long long i=min(A,B); i>=1; i--){
    if(A%i==0 && B%i==0){
      g=i;
      break;
    }
  }
  cout << A*B/g << endl;
  
  return 0;
}

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

typedef long long ll;

#define ri(b,c) for(ll i=(b);i<(c);++i)
#define rj(b,c) for(ll j=(b);j<(c);++j)
#define rk(b,c) for(ll k=(b);k<(c);++k)
#define rl(b,c) for(ll l=(b);l<(c);++l)
#define rr(b,c) for(ll r=(b);r>(c);--r)
#define fcout cout<<fixed<<setprecision(10)
#define a_m a,b,c,d,e,f,g,h,i,j,k,l,m
#define n_z n,o,p,q,r,s,t,u,v,w,x,y,z
#define p50 614889782588491410
#define isprime(a) gcd(p50,a)==1

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

	ll a_m,n_z;
    string ss;
	cin>>ss>>b;


    a=ss.length();
    for(i=0;i<a;i+=b)cout<<ss[i];
    cout<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  char a,b;
  scanf("%c",&a);
  if(a=='A'){
    b='T';
  }
  else if(a=='T'){
    b='A';
  }
  else if(a=='C'){
    b='G';
  }
  else{
    b='C';
  }
  printf("%C",b);
}

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

using namespace std;
using ll = long long;
constexpr ll INF = 1000000000000000000;
constexpr int COINMAX = 2500;


int main() {
	int n, m, s; scanf("%d %d %d", &n, &m, &s);
	vector<vector<pair<int, pair<int, int>>>> graph(n);
	for (int i = 0; i < m; ++i) {
		int u, v, a, b; scanf("%d %d %d %d", &u, &v, &a, &b);
		graph[--u].emplace_back(--v, make_pair(a, b));
		graph[v].emplace_back(u, make_pair(a, b));
	}
	vector<int> coinGain(n), coinTime(n);
	for (int i = 0; i < n; ++i) scanf("%d %d", &coinGain[i], &coinTime[i]);

	s = min(s, COINMAX - 1);
	vector<vector<ll>> dist(n, vector<ll>(COINMAX, INF));
	dist[0][s] = 0;
	set<pair<ll, pair<int, int>>> toVisit;
	for (int i = 0; i < n; ++i) {
		for (int c = 0; c < COINMAX; ++c) toVisit.emplace(dist[i][c], make_pair(i, c));
	}
	while (!toVisit.empty()) {
		ll dtc; int cv, ccoin;
		forward_as_tuple(dtc, tie(cv, ccoin)) = *toVisit.begin(); toVisit.erase(make_pair(dtc, make_pair(cv, ccoin)));
//		if (dtc < 20) printf("visiting %d %d at %lld\n", cv, ccoin, dtc);
		if (dtc == INF) continue;
		for (auto v_c_t : graph[cv]) {
			int nv, ncoin, nt;
			forward_as_tuple(nv, tie(ncoin, nt)) = v_c_t;
			int newCoinCount = ccoin - ncoin;
			if (newCoinCount < 0) continue;
			if (dtc + nt < dist[nv][newCoinCount]) {
				toVisit.erase(make_pair(dist[nv][newCoinCount], make_pair(nv, newCoinCount)));
				toVisit.emplace(dist[nv][newCoinCount] = dtc + nt, make_pair(nv, newCoinCount));
			}
		}
		int buyCount = min(ccoin + coinGain[cv], COINMAX - 1);
		if (dtc + coinTime[cv] < dist[cv][buyCount]) {
			toVisit.erase(make_pair(dist[cv][buyCount], make_pair(cv, buyCount)));
			toVisit.emplace(dist[cv][buyCount] = dtc + coinTime[cv], make_pair(cv, buyCount));
		}
	}
	for (int i = 1; i < n; ++i) printf("%lld\n", *min_element(begin(dist[i]), end(dist[i])));
	return 0;
}


Measured memory_bytes: 12140
package main

import (
    "fmt"
)

func main() {
    var h, w, n, r, c int
    fmt.Scan(&h, &w, &n)
    fmt.Scan(&r, &c)

    var s, t []byte
    fmt.Scan(&s)
    fmt.Scan(&t)

    var ok bool
    var left, right, up, down int
    for i := 0; i < n; i++ {
        switch s[i] {
        case 'L':
            left++
        case 'R':
            right++
        case 'U':
            up++
        case 'D':
            down++
        }
        if left >= c || right >= w-c+1 || up >= r || down >= h-r+1 {
            ok = true
        }
        switch t[i] {
        case 'L':
            if c+right > 1 {
                right--
            }
        case 'R':
            if c-left < w {
                left--
            }
        case 'U':
            if r+down > 1 {
                down--
            }
        case 'D':
            if r-up < h {
                up--
            }
        }
    }

    if ok {
        fmt.Println("NO")
    } else {
        fmt.Println("YES")
    }
}


Measured memory_bytes: 3712
import math
A,B,H,M=map(int,input().split())

theta_h=M/30*math.pi
theta_m=(H/6+M/360)*math.pi
#print(theta_h,theta_m)

ans=A**2+B**2-2*A*B*(math.sin(theta_h)*math.sin(theta_m)+math.cos(theta_h)*math.cos(theta_m) )
print(ans**(1/2))

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

int main (){
	int n, i, max, min;
	int A[101];
	int sum;
	while (cin >> n && n > 0){
		sum = 0;
		for (i = 0; i < n; i++){
			cin >> A[i];
		}
		max = min = A[0];
		for (i = 0; i < n; i++){
			if (max < A[i]){
				max = A[i];
			}
			if (min > A[i]){
				min = A[i];
			}
			sum += A[i];
		}
		sum -= max;
		sum -= min;
		cout << sum / (n - 2) << endl;
	}

	return 0;
}


Measured memory_bytes: 3104
n=input()
ln=len(n)
nn=[-1,-1,-1]
nnn=[0,0,0]
j=0
for i in range(ln):
  if n[i]!="0":
    nn[j]=i
    nnn[j]=int(n[i])
    j+=1
    if j==3:
      break

s=[9*(ln-1),81*(ln-1)*(ln-2)//2,729*(ln-1)*(ln-2)*(ln-3)//6]
s[0]+=nnn[0]
s[1]+=(nnn[0]-1)*9*(ln-1)+(0 if nn[1]==-1 else nnn[1]+9*(ln-nn[1]-1))
s[2]+=(nnn[0]-1)*81*(ln-1)*(ln-2)//2
s[2]+=(0 if nn[1]==-1 else (nnn[1]-1)*9*(ln-nn[1]-1)+81*(ln-nn[1]-1)*(ln-nn[1]-2)//2)+(0 if nn[2]==-1 else nnn[2]+9*(ln-nn[2]-1))

k=int(input())
print(s[k-1])

Measured memory_bytes: 62128
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

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)*}
    };
}

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)*}
    };

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

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, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input!{
        a: i64,
        b: i64,
        c: i64,
        d: i64,
        e: i64,
        k: i64,
    }
    let mut cnt = 0;
    if b - a > k {
        cnt += 1
    };
    if c - a > k {
        cnt += 1
    };
    if d - a > k {
        cnt += 1
    };
    if e - a > k {
        cnt += 1
    };
    if (a - d).abs() > k {
        cnt += 1
    };
    if (b - c).abs() > k {
        cnt += 1
    };
    if (b - d).abs() > k {
        cnt += 1
    };
    if (b - e).abs() > k {
        cnt += 1
    };
    if (c - d).abs() > k {
        cnt += 1
    };
    if (c - e).abs() > k {
        cnt += 1
    };
    if (d - d).abs() > k {
        cnt += 1
    };
    println!("{}", if cnt == 0 { "Yay!" } else { ":(" });
}


Measured memory_bytes: 4352
public class Main {
	public static void main(String[] args) {
		java.util.Scanner s = new java.util.Scanner(System.in);
		int a = s.nextInt();
		int b = s.nextInt();
		int c = s.nextInt();
		int cap = a - b;
		if(cap>= c) {
			System.out.println(0);
		}else {
			System.out.println(c-cap);
		}
	}
}


Measured memory_bytes: 21844
N,K=map(int,input().split())
h=list(map(int,input().split()))

#dp[i]はh[i]までにかかるコストの最小値
dp=[float('inf') for _ in range(N)] 
dp[0]=0

for i in range(N-1):
    for j in range(1,min(K+1,N-i)):
        dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[N-1])


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

#define int long long

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

const int maxn = 5e5+10;
const int inf = 1e9;
const lf eps = 1e-8;

int n,q,d,a[maxn],b[maxn],dis[maxn];

signed main() {
    read(n),read(d);dis[0]=d;
    for(int i=1;i<=n;i++) read(a[i]),dis[i]=min(dis[i-1],abs(dis[i-1]-a[i]));
    for(int i=n;i;i--) b[i]=b[i+1]+a[i]*(a[i]/2<=b[i+1]);read(q);
    for(int i=1,x;i<=q;i++) read(x),puts(dis[x-1]>b[x+1]?"YES":"NO");
    return 0;
}


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

int main(){
  int a,b,c,d,e;
  cin >> a >> b >> c >> d >> e;
  int N=5;
  
  //注文してから届くまでの時間
  vector<int> Time = {a,b,c,d,e};
  //注文してから次に注文できるまでの時間
  vector<int> index = {0,1,2,3,4};
  
  int BestTime = (int)1e9;//←10^9(double)
  
  //indexの中身が
  //0,1,2,3,4
  //0,1,2,4,3
  //:
  //4,3,2,1,0
  //の全探索ができる
  do {
    int NowTime=0;
    for (int i=0;i<N;++i){
      //10で割り切れるようになるまで1を足し続ける
      while (NowTime%10!=0) NowTime++;
      NowTime+=Time[index[i]];
    }
    BestTime=min(BestTime,NowTime);
  }
  while (next_permutation(index.begin(),index.end()));
  cout << BestTime << endl;
}
//全探索による解法
    
  

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

int main()
{
    int N, M;
    cin >> N >> M;

    vector<vector<int> > data(N, vector<int>(M+1));
    for (int i=0; i<N; i++) {
        cin >> data.at(i).at(0);
        for (int j=1; j < data.at(i).at(0) + 1; j++) {
            cin >> data.at(i).at(j);
        }
    }
    
    int count = 0;
    for (int k=1; k<M+1; k++) {
        int Ncount = 0;
        for (int i=0; i<N; i++) {
            for (int j=1; j < data.at(i).at(0) + 1; j++) {
                if (data.at(i).at(j) == k) {
                    Ncount++;
                }
            }
        }
        if (Ncount == N) {
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long

lin n, k;

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

    if (k == 0)
    {
        lin nn = n * n;
        cout << nn << endl;
        return 0;
    }

    // right-top
    lin result = (n - k + 1) * (n - k) / 2;

    loop(i, k + 1, n + 1)
    {
        int full = (n + 1) / i - 1;
        result += full * (i - k);

        int rest = n - (full + 1) * i + 1;
        if (rest > k)
            result += (rest - k);
    }

    cout << result << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < N; i++) {
      int A = sc.nextInt();
      max = Math.max(max, A);
      min = Math.min(min, A);
    }
    System.out.println(max - min);
  }
}


Measured memory_bytes: 21844
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <complex>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;

int main() {
	ll n;
	cin >> n;
	cout << (n < 1000 ? "ABC" : "ABD") << endl;
	return 0;
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/abc125/tasks/abc125_c
#include <iostream>
#include <vector>
//#include <numeric>
using namespace std;
//解説みた
int gcd(int a,int b)
{
	if (a%b==0)
	{
		return(b);
    }
	else
	{
		return(gcd(b,a%b));
    }
}


int CheckGcd(int a,int b){
    while (true){
        if (a>b){
            a-=b;
        }else if(b>a){
            b-=a;
        }else{
            return a;
        }
    }
}

int getMax(int a,int b,int c){
    if(a>=b){
        if(c>=a){
            return c;
        }else if(b>=c){
            return a;
        }
    }else{
        if(c>=b){
            return c;
        }
    }
    return b;
}

int Check3Gcd(int a,int b, int c){
    int d1,d2,d3;
    int b1=b;
    d1=CheckGcd(a,b);
    d2=CheckGcd(b,c);
    d3=CheckGcd(a,c);
    return getMax(d1,d2,d3);
}

int main(){
    int N;
    cin >> N;
    int *V = new int[N];
    for(int i = 0; i<N;i++){
    cin >> V[i];
    }
    if(N==2){
        if(V[0]>V[1]){
            cout<<V[0]<<endl;
        }else{
            cout << V[1]<<endl;
        }
        return 0;
    }

    int *L = new int[N-1];
    int *R = new int[N-1];
    L[0]=gcd(V[0],V[1]);
    R[0]=gcd(V[N-1],V[N-2]);
    for(int i=1;i<N-4;i++){
        L[i]=gcd(L[i-1],V[i+1]);
        R[i]=gcd(R[i-1],V[N-2-i]);
    }
    L[N-3]=V[0];
    R[N-3]=V[N-1];
    for(int i=1;i<N-2;i++){
        L[N-3]=gcd(L[N-3],V[i]);
        R[N-3]=gcd(R[N-3],V[N-i-1]);
    }

    L[N-2]=V[0];
    R[N-2]=V[N-1];
    for(int i=1;i<N-1;i++){
        L[N-2]=gcd(L[N-2],V[i]);
        R[N-2]=gcd(R[N-2],V[N-i-1]);
    }

    int Max=0;
    for(int i=0;i<N-4;i++){
        if (Max<gcd(L[i],R[N-i-5])){
            Max=gcd(L[i],R[N-i-5]);
        }
    }

    if(Max<gcd(L[N-3],V[N-1]))Max=gcd(L[N-3],V[N-1]);
    if(Max<gcd(R[N-3],V[0]))Max=gcd(R[N-3],V[0]);
    if(Max<L[N-2])Max=L[N-2];
    if(Max<R[N-2])Max=R[N-2];



/*
    for(int i=0;i<N-1;i++){
        cout<<L[i]<<",";
    }
    cout<<gcd(L[N-3],V[N-1]);
    cout <<endl;
    for(int i=0;i<N-1;i++){
        cout<<R[i]<<",";
    }
    cout<<gcd(R[N-3],V[0]);
    cout <<endl;
    */
    

    cout << Max << endl;
    return 0;

}

Measured memory_bytes: 1408
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  std::vector<std::pair<int,int>> robot;
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    robot.push_back(std::make_pair(x,y));
  }
  std::sort(robot.begin(), robot.end());

  std::vector<int> min(n+1),max(n+1);
  for(int i=1;i<=n;i++){
    min[i]=i;
    max[i]=i;
  }

  for(auto r:robot){
    int u=r.second;
    int l=r.second+1;
    min[u]=std::min(min[u],min[l]);
    max[u]=std::max(max[u],max[l]);
    min[l]=min[u];
    max[l]=max[u];
  }

  for(int i=1;i<n;i++){
    cout<<max[i]-min[i]+1<<" ";
  }
  cout<<max[n]-min[n]+1<<endl;



  return 0;
}


Measured memory_bytes: 5552
using System;

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        line = Console.ReadLine().Trim().Split(' ');
        var p = int.Parse(line[0]);
        var q = int.Parse(line[1]);
        var r = int.Parse(line[2]);
        var ans = (double)(p * b + r * b + a * q) / (q + r);
        Console.WriteLine(ans);
    }
}



Measured memory_bytes: 7860
import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))
    val Array(s, w) = in.readLine().split("\\s+").map(_.toInt)

    out.println(
      if (s <= w) {
        "unsafe"
      } else {
        "safe"
      }
    )

    out.flush()
  }
}


Measured memory_bytes: 54644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fsp(x) fixed << setprecision(x)
#define xout cerr
const ll inf = LLONG_MAX;
const long double pi = acosl(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

vector<ll> bfs(ll m, vector<vector<ll>> &nx, vector<bool> &seen, ll start) {
	queue<ll> task;
	task.push(start);
	seen[start] = true;
	vector<ll> ret = {1, 0};
	ll depth = 1;
	while (task.size()) {
		ll sz = task.size();
		while (sz--) {
			ll x = task.front();
			task.pop();
			for (ll i = 0; i < nx[x].size(); i++) {
				if (!seen[nx[x][i]]) {
					task.push(nx[x][i]);
					seen[nx[x][i]] = true;
					ret[depth % 2]++;
				}
			}
		}
		depth++;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//const ll p = 1e9 + 7;
	//const ll p = 998244353;

	ll h, w;
	cin >> h >> w;
	vector<string> s(h);
	for (ll i = 0; i < h; i++) cin >> s[i];

	ll m = h * w;
	vector<vector<ll>> nx(m, vector<ll>(0));
	vector<ll> d1 = {1, -1, 0, 0}, d2 = {0, 0, 1, -1};
	for (ll i = 0; i < h; i++) {
		for (ll j = 0; j < w; j++) {
			for (ll k = 0; k < 4; k++) {
				if (0 <= i + d1[k] && i + d1[k] < h && 0 <= j + d2[k] && j + d2[k] < w && (s[i][j] ^ s[i + d1[k]][j + d2[k]])) {
					ll a = i * w + j, b = (i + d1[k]) * w + j + d2[k];
					nx[a].push_back(b);
					nx[b].push_back(a);
				}
			}
		}
	}

	vector<bool> seen(m, false);
	ll ans = 0;
	for (ll i = 0; i < h; i++) {
		for (ll j = 0; j < w; j++) {
			if (!seen[i * w + j]) {
				vector<ll> v = bfs(m, nx, seen, i * w + j);
				ans += v[0] * v[1];
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 16768
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MOD = 998244353;
const int mxN = 2e5 + 5;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int n, q;
ll s[4 * mxN], lazy[4 * mxN];
ll powt[mxN];

void build(int id = 1, int l = 0, int r = n){
	if((r - l) < 2){
		s[id] = (powt[l] - (l ? powt[l - 1] : 0) + MOD) % MOD;
		return;
	}
	int mid = (l + r) / 2;
	build(id << 1, l, mid);
	build((id << 1) + 1, mid, r);
	s[id] = (s[id << 1] + s[(id << 1) + 1] + MOD) % MOD;
}
 
void down(int id, int l, int r){
	if(lazy[id]){
		s[id] = (((powt[r - 1] - (l ? powt[l - 1] : 0) + MOD) % MOD) * lazy[id]) % MOD;
		if((r - l) > 1){
			lazy[id << 1] = lazy[id];
			lazy[(id << 1) + 1] = lazy[id];
		}
	}
	lazy[id] = 0;
}
 
void increase(int x, int y, ll u, int id = 1, int l = 0, int r = n){
	down(id, l, r);
	if(x >= r || l >= y) return;
	if(x <= l && r <= y){
		lazy[id] = u;
		down(id, l, r);
		return;
	}
	int mid = (l + r) / 2;
	increase(x, y, u, id << 1, l, mid);
	increase(x, y, u, (id << 1) + 1, mid, r);
	s[id] = (s[id << 1] + s[(id << 1) + 1] + MOD) % MOD;
}
 
ll sum(int x, int y, int id = 1, int l = 0, int r = n){
	down(id, l, r);
	if(x >= r || l >= y) return 0;
	if(x <= l && r <= y) return s[id] % MOD;
	int mid = (l + r) / 2;
	return (sum(x, y, id * 2, l, mid) + sum(x, y, id * 2 + 1, mid, r) + MOD) % MOD;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	cin >> n >> q;
	powt[0] = 1;
	ll cur = 1LL;
	repn(i, 1, n){
		powt[i] = (powt[i - 1] + (10 * cur) + MOD) % MOD;
		(cur *= 10) %= MOD;
	}
	build();
	rep(i, q){
		int l, r, d;
		cin >> l >> r >> d;
		l--, r--;
		increase(n - (r + 1), n - l, d);
		cout << sum(0, n) << endl;
	}
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 13432
#B - Shiritori
N = int(input())
S = list(input() for i in range(N))
if len(S) != len(set(S)):
    print("No")
else:
    for i in range(N-1):
        if S[i][-1] == S[i+1][0]:
            pass
        else:
            print("No")
            exit()
    print("Yes")


Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>

using namespace std;

typedef long long ll;

int array2num(int* arg){
	int res=0;
	int mul=1;
	for(int i=8-1;i>=0;i--){
		res += arg[i]*mul;
		mul*=10;
	}
	return res;
}

int main(){

	int men[8];
	int merry[8]={1,2,1,2,1,4,1,4};

	while(~scanf("%d %d %d %d %d %d %d %d",men,men+1,men+2,men+3,men+4,men+5,men+6,men+7)){
		int min_score=numeric_limits<int>::max();
		int res[8];

		for(int i=0;i<8;i++){
			int merry_r[8];
			int count = 0;
			int idx=0;

			for(int j=i;;j++){
				if(j%8==i) count++;
				if(count >=2) break;
				merry_r[idx++]=merry[j%8];
			}

			int score=0;
			for(int j=0;j<8;j++){
				score += men[j]-merry_r[j] >= 0 ? men[j]-merry_r[j] : 0;
			}

			if(score < min_score){
				min_score = score;
				copy(merry_r,merry_r+8,res);
			}

			else if(score == min_score){
				int a = array2num(res);
				int b = array2num(merry_r);
				if(a > b){
					copy(merry_r,merry_r+8,res);
				}
			}
		}

		for(int i=0;i<8;i++){
			printf("%d%s",res[i],i==7 ? "\n" : " ");
		}
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
const long long MOD=1e9+7;
// const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};
#define LOCAL

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const map<T,U> &m){
    os << '{';
    for (auto itr=m.begin();itr!=m.end();++itr){
        os << '(' << itr->first << ',' << itr->second << ')';
        if (++itr!=m.end()) os << ',';
        --itr;
    }
    os << '}';
    return os;
}
template<typename T>
ostream &operator<<(ostream &os,const set<T> &s){
    os << '{';
    for (auto itr=s.begin();itr!=s.end();++itr){
        os << *itr;
        if (++itr!=s.end()) os << ',';
        --itr;
    }
    os << '}';
    return os;
}

void debug_out(){cerr << '\n';}
template<class Head,class... Tail>
void debug_out(Head&& head,Tail&&... tail){
    cerr << head;
    if (sizeof...(Tail)>0) cerr << ", ";
    debug_out(move(tail)...);
}
#ifdef LOCAL
#define debug(...) cerr << " ";\
cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\
cerr << " ";\
debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<typename T> T gcd(T x,T y){return y!=0?gcd(y,x%y):x;}
template<typename T> T lcm(T x,T y){return x/gcd(x,y)*y;}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X,N; cin >> X >> N;
    vector<int> check(110);
    for (int i=0;i<N;++i){
        int p; cin >> p;
        check[p]=1;
    }
    int ans=0,M=INF;
    for (int i=0;i<110;++i) if (!check[i]){
        if (chmin(M,abs(X-i))) ans=i;
    }
    cout << ans << '\n';
}

Measured memory_bytes: 3652
N,K=map(int,input().split())
A=list(map(int,input().split()))
r=[0]
z=[True]*N
x=[-1]*N
x[0]=0
z[0]=False
n=A[0]-1
i=0
while z[n] and i<K:
    i+=1
    r.append(n)
    x[n]=i
    z[n]=False
    p=n
    n=A[n]-1
if i==K:
    print(p+1)
else:
    s=x[n]
    r=r[s:]
    l=len(r)
    t=(K-s)%l
    print(r[t]+1)

Measured memory_bytes: 32556
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;

int main() {
  ll N, K;
  cin >> N >> K;
  vector<ll> A(N);
  for (ll i = 0; i < N; i++) {
    cin >> A[i];
  }

  const ll MAX_DIGIT = 50;
  // dp[i+1][smaller]
  // 上からi桁目まで考えたときのfの最大値
  ll dp[MAX_DIGIT+1][2];
  memset(dp, -1, sizeof(dp));

  dp[0][0] = 0;
  for (ll d = 0; d < MAX_DIGIT; d++) {
    ll offset = MAX_DIGIT - 1 -d;
    ll mask = 1LL << offset;
    // cout << "mask: " << mask << " n; " << n << endl;

    // A で元々 d 桁目にビットが立っているものの個数
    ll num = 0;
    for (ll i = 0; i < N; ++i) {
      if (A[i] & mask) {
        num++;
      }
    }

    // X の d 桁目を 0, 1 にしたときのコスト
    ll cost0 = mask * num;
    ll cost1 = mask * (N - num);

    // cout << "cost0: " << cost0 << endl;
    // cout << "cost1: " << cost1 << endl;

    // smaller -> smaller
    if (dp[d][1] != -1) {
      chmax(dp[d+1][1], dp[d][1] + cost0);
      chmax(dp[d+1][1], dp[d][1] + cost1);
    }

    if (dp[d][0] != -1) {
      // exact -> smaller
      // Kのd桁目が1じゃないと 0 -> 0の遷移(exact -> exact)の遷移になってしまう
      if (K & mask) {
        chmax(dp[d+1][1], dp[d][0] + cost0);
      }

      // exact -> exact
      if (K & mask) {
        chmax(dp[d+1][0], dp[d][0] + cost1);
      } else {
        chmax(dp[d+1][0], dp[d][0] + cost0);
      }
    }
  }

  cout << max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1]) << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define REV(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define ts to_string
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector <string>
#define vvs vector <vector<string>>
#define pq  priority_queue<int>
using ll = long long;
/* ----------------よく使う数字や配列----------------- */
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
const int INF = 2000000000;
constexpr ll mod = 1e9 + 7;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
/*---------------------template----------------------*/
/*----------------------end--------------------------*/
/* --------------------ライブラリ--------------------*/
bool isprime(ll a)//素数判定、primeならtrue,違うならfalse
{
    if (a < 2) return false;
    else if (a == 2) return true;
    else if (a % 2 == 0) return false;
    double m = sqrt(a);
    for (int i = 3; i <= m; i += 2)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    // 素数である
    return true;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
/*---------------------臨時関数----------------------*/
/*----------------------end-------------------------*/
signed main(){
  double A,B,H,M;cin>>A>>B>>H>>M;
  //abs((30*10+0.5*40)-(6*40))
  double kakudo=abs((30*H+0.5*M)-(6*M));
  double C=cos(kakudo*pi/180);
  double ans=A*A+B*B-2*A*B*C;
  cout<<fixed<<setprecision(18)<<sqrt(ans)<<endl;
  
}


Measured memory_bytes: 4152
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200009
#define MOD 1000000007
#define INF 1000000009
#define FOR(x,n) for(int x=0; x<n; x++)
#define FOR1e(x,n) for(int x=1; x<=n; x++)
typedef pair<int, int> ii;
typedef long long ll;

vector<vector<int> > child;
vector<int> dp[MAXN][3];

int rd[MAXN];
int lvlcnt[MAXN];
int pot[MAXN];

int dfs(int v, int lvl) {
	lvlcnt[lvl]++;
	int ans = lvl;
	for (int i = 0; i < child[v].size(); i++)
		ans = max(ans, dfs(child[v][i], lvl+1));
	return ans;
}

void compute(int v) {
	for (int i = 0; i < child[v].size(); i++) {
		compute(child[v][i]);
	}

	if (child[v].size() == 0) {
		rd[v] = v;
	} else {
		rd[v] = rd[child[v][0]];
	}

	int t = 0;
	for (int i = 1; i < child[v].size(); i++) {
		int n1, n2, a, b;
		if (dp[rd[child[v][i]]][0].size() > dp[rd[v]][0].size()) {
			a = rd[child[v][i]]; b = rd[v];
		} else {
			a = rd[v]; b = rd[child[v][i]];
		}
		n1 = dp[a][0].size() - 1; n2 = dp[b][0].size() - 1;
		t = max(t, min(n1, n2) + 1);

		while (n1 >= 0 && n2 >= 0) {
			int a0 = ((long long) dp[a][0][n1]*dp[b][0][n2])%MOD;
			int a1 = ((long long) dp[a][1][n1]*dp[b][0][n2] + (long long) dp[a][0][n1]*dp[b][1][n2])%MOD;
			int a2 = ((long long) dp[a][1][n1]*dp[b][1][n2] + 
					 ((long long) dp[a][2][n1]*(dp[b][0][n2] + dp[b][1][n2] + dp[b][2][n2]))%MOD +
					 ((long long) dp[b][2][n2]*(dp[a][0][n1] + dp[a][1][n1] + dp[a][2][n1]))%MOD)%MOD;

			dp[a][0][n1] = a0; dp[a][1][n1] = a1; dp[a][2][n1] = a2;
			n1--; n2--;
		}
		rd[v] = a;
	}

	for (int i = (int)dp[rd[v]][0].size() - 1; i >= (int)dp[rd[v]][0].size() - t; i--) {
		dp[rd[v]][0][i] += dp[rd[v]][2][i];
		dp[rd[v]][0][i] %= MOD;

		dp[rd[v]][2][i] = 0;
	}
	
	dp[rd[v]][0].push_back(1);
	dp[rd[v]][1].push_back(1);
	dp[rd[v]][2].push_back(0);
}

int main() {
	int n, p;
	scanf("%d", &n);
	child.resize(n+5);

	FOR(x, n) {
		scanf("%d", &p);
		child[p].push_back(x+1);
	}

	pot[0] = 1;
	FOR1e(x, MAXN-1) pot[x] = (pot[x-1]*2)%MOD;

	int lvl = dfs(0, 0);
	ll ans = 0;
	compute(0);
	
	for (int i = 0; i <= lvl; i++) {
		ans += (long long) dp[rd[0]][1].back()*pot[n+1-lvlcnt[i]];
		ans %= MOD;

		dp[rd[0]][1].pop_back();
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 70628
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vel;
typedef vector<str> ves;
#define REP(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rep(i, b) REP(i, 0, b)
const ll mod = 1000000007;
const double pi = 3.14159265358979;

int main() {
    str a, b, c;
    cin >> a >> b >> c;
    cout << a[0] << b[1] << c[2] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;

ll a, b, c;

int main()
{
	cin >> a >> b >> c;
	if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0)
	{
		printf("0\n");
		return 0;
	}
	cout << min(a * b, min(a * c, b * c)) << endl;

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include <cmath>
#include <math.h>

using namespace std;
const long long INF = (long long) (1e18)+1;

int main() {
  // vector<int> nums(5);
  string su;
  cin >> su;

  if (islower(su[0])) {
    cout << 'a' << endl;
  } else {
    cout << 'A' << endl;
  }
  return 0;
}

Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define ull unsigned long long intS
#define rep(i,n) for(int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;


int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    
    int c,a,b;
    
    cin >> c >> a >> b;
    
    cout << a*c/2 << endl;
    
    
    
//////////////////////////////////////////////////////
return 0;}

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

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;

#define endl '\n'
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define int long long
#define pb push_back
#define f(i,l,r) for(ll i=l;i<=r;i++)
#define rf(i,r,l) for(ll i=r;i>=l;i--)
#define Max 5000001
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

#define d0(a) cout<<a<<' ';
#define d1(a) cout<<a<<endl;
#define d2(a,b) cout<<a<<' '<<b<<endl;
#define d3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
#define d4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
#define d5(a,b,c,d,e) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<endl;
#define d6(a,b,c,d,e,f) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<endl;

const ll N=1e5+5,mod=1e9+7,bit=61;



signed main()
{
    fast;

    ll t=1;
    //cin>>t;
    while(t--)
    {
        ll n,m;
        cin>>n>>m;
        ll a[n];
        ll s=0;
        f(i,0,n-1)
        {
            cin>>a[i];
            s+=a[i];
        }
        sort(a,a+n,greater<ll>());
        ld th=(ld)s/((ld)4.0*m);
        ll ans=m;
        f(i,0,m-1)
        {
            if((ld)a[i]<th)
            {
                ans--;
            }
        }
        if(ans>=m)
        {
            d1("Yes");
        }
        else
        {
            d1("No");
        }
    }
    return 0;
}


















Measured memory_bytes: 256
import numpy as np

n,c=map(int,input().split())
d=[]
for _ in range(c):
	d.append([int(i) for i in input().split()])
e=[]
for _ in range(n):
	e.append([int(i) for i in input().split()])
dd=np.matrix(d)

re=np.matrix([[0]*c for _ in range(3)])
for i in range(n):
	for j in range(n):
		re[(i+j)%3,e[i][j]-1]+=1

mul=np.dot(re,dd)
ind=np.argsort(mul)

ans=float('inf')
for i in range(3):
	for j in range(3):
		if ind[0,i]!=ind[1,j]:
			for k in range(3):
				if ind[0,i]!=ind[2,k] and ind[1,j]!=ind[2,k]:
					l=mul[0,ind[0,i]]+mul[1,ind[1,j]]+mul[2,ind[2,k]]
					if ans>l:
						ans=l
print(ans)


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

namespace ABC133
{
    class Program
    {
        static void Main(string[] args)
        {
            var lr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var l = lr[0];
            var r = lr[1];
            if (r - l > 2019)
            {
                r = l + 2019;
            }
            var result = 2018;
            for(int i = l; i < r; i++)
            {
                for(int j = i + 1; j < r + 1; j++)
                {
                    var x = i % 2019;
                    var y = j % 2019;
                    result = Math.Min(result, (x * y) % 2019);
                }
                if (result == 0) break;
            }
            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 13268
fn qa() -> String {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();

    let mut output = String::new();
    for c in input.chars() {
        if c == '9' {
            output.push('1')
        }
        else if c == '1' {
            output.push('9')
        }
        else {
            output.push(c)
        }
    }

    output
}


fn main() {
    println!("{}", qa());
}

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

int time(int x){
    return (x+9)/10*10;
}


int main(void) {
    string  s;
    int a=0,ans=0;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T')a++;
        else a=0;
        if(ans<a)ans=a;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
num = int(input())
num -= 1
print(l[num])

Measured memory_bytes: 2940
package main

import(
    "fmt"
)



func main() {
    var a,b,c string
    fmt.Scan(&a,&b,&c)
    ans := "NO"
    if a[len(a)-1]==b[0] && b[len(b)-1]==c[0]{
        ans = "YES"
    }
    fmt.Println(ans)
}





func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

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

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

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}


Measured memory_bytes: 512
public class Main {
	public static void main(String[] args) throws Exception {
        char c = (char)System.in.read();
        char res = '\0';
        switch (c) {
            case 'A':
                res = 'T';
                break;
            case 'T':
                res = 'A';
                break;
            case 'C':
                res = 'G';
                break;
            case 'G':
                res = 'C';
                break;
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 19412
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;


bool ok(long long a,long long b,long long c){
	if(b * b - 4 * a * c < 0) return false;
	long long sq = sqrt(b * b - 4 * a * c) + 0.5;
	return sq * sq == b * b - 4 * a * c;
}

int main(){
	long long a,b,c;
	while(cin >> a >> b >> c && a){
		if(ok(a,b,c)){
			long long bnbA = 2 * a , bnbB = 2 * a;
			long long A = (-1) * (-b - (long long)(sqrt(b * b - 4 * a * c) + 0.5) );
			long long B = (-1) * (-b + (long long)(sqrt(b * b - 4 * a * c) + 0.5) );
			long long AG = __gcd((long long)abs(A),bnbA) , BG = __gcd((long long)abs(B),bnbB);
			bnbA /= AG , A /= AG;
			bnbB /= BG , B /= BG;
			if( !(bnbA>bnbB||(bnbA == bnbB && A >= B)) ){
				swap(bnbA,bnbB);
				swap(A,B);
			}
			cout << bnbA << " " << A << " " << bnbB << " " << B << endl;	
		}else{
			cout << "Impossible" << endl;
		}
	}
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false); cin.tie(NULL);
#ifndef LOCAL
#define dbg(...) ;
#define endl '\n'
#endif

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



signed main(){
    IOS;
    int a, b;
    cin >> a >> b;
    cout << (a*(a-1)/2 + b*(b-1)/2);
    return 0;
}

Measured memory_bytes: 256