akhauriyash/Code-Regression huggingface dataset:
fn main() {
    let stdin = std::io::stdin();

    let mut buf = String::new();
    stdin.read_line(&mut buf).ok();
    let _n: i32 = buf.trim().parse().unwrap();

    buf.clear();
    stdin.read_line(&mut buf).ok();
    let hs: Vec<i32> = buf.split_whitespace().map(|w| w.parse().unwrap()).collect();

    let mut last = std::i32::MAX;
    for &h in hs.iter().rev() {
        if last >= h {
            last = h;
        } else if last == h - 1 {
            last = h - 1;
        } else {
            println!("No");
            std::process::exit(0);
        }
    }
    println!("Yes");
}


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

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

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

int main(){
    int A, B, C, N, M ,K;
    int flag = 0;
    int sum = 0;
    int i = 0;
    vector<int> X;
    string s, s1;
    cin >> A;
    X.push_back(A);
    while(1){
        if(A%2 == 0) A /= 2;
        else A = 3*A + 1;
        X.push_back(A);
        for(int j = 0; j < X.size()-1; j++){
            if(A == X.at(j)) {
                flag = 1;
                break;
            }
        }
        if(flag == 1) break;
        i++;
    }

    cout << X.size() << endl;

//    vector<int> X();

//    for(int i = 0; i < ; i++){}
//    for(int j = 0; j < ; j++){}

//    cout <<  << endl;
}

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

int main() {
    long long N;
    cin >> N;
    string res = "";
    while (N) {
        --N;
        res += (char)('a' + (N % 26));
        N /= 26;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
}

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

int main(){
    string s;
    cin >> s;
    ll n = s.size(),ans=(n*(n-1))/2+1;
    map<char,ll> mp;
    for(int i = 0;i < 26;i ++){
        for(int j = 0;j < n;j ++){
            if(s[j]=='a'+i) mp['a'+i] ++;
        }
    }
    for(auto ite = mp.begin();ite != mp.end();++ite){
        ans -= (ite->second*(ite->second-1))/2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
// 文字列関連の問題初めて自力ACできるかも…!!
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

int main() {
  int n, m;
  cin >> n;
  vector<string>s(n);
  rep(i,n) cin >> s[i];
  cin >> m;
  vector<string>t(m);
  rep(i,m) cin >> t[i];
  int ans = -100;
  for(int i = 0; i < n; i++) {
    int tmp = 0;
    for(int j = 0; j < n; j++) {
      if(s[i] == s[j]) tmp++;
    }
    for(int j = 0; j < m; j++) {
      if(s[i] == t[j]) tmp--;
    }
    ans = max(ans,tmp);
  }
  if(ans < 0) cout << 0 << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    long long int n,i,odd=0,ara[100005];
    scanf("%lld",&n);
    for(i=0;i<n;i++)
    {
        scanf("%lld",&ara[i]);
        if(ara[i]%2==1)
            odd++;
    }
    if(odd%2==0)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> A(100050);
  for (int i = 1; i <= N; i++){
    cin >> A.at(i);
  }
  
  int B = 1,C;
  bool D = false;
  int j;
  for( j = 1; j <= N; j++){
    C = A.at(B);
    if (C == 2){
      D = true;
      break;
    }
    B = C;
  }
  cout << (D ? j : -1) << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;

int ans[105][105];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int r, c, n;
    cin >> r >> c >> n;
    map<int, int> freq;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        freq[i + 1] = x;
    }
    int cnt = 1;
    for(int i = 0; i < r; i++){
        if(i % 2 == 0){
            for(int j = 0; j < c; j++){
                ans[i][j] = cnt;
                freq[cnt]--;
                if(freq[cnt] == 0) cnt++;
            }
        }
        else{
            for(int j = c - 1; j >= 0; j--){
                ans[i][j] = cnt;
                freq[cnt]--;
                if(freq[cnt] == 0) cnt++;
            }
       }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }



    return 0;
}


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

using namespace std;

const int N = 60;

int n, p;
long long dp[N][2];

int main() {
  scanf("%d %d", &n, &p);
  dp[0][0] = 1, dp[0][1] = 0;
  for (int i = 1; i <= n; i++) {
    int u;
    scanf("%d", &u);
    dp[i][0] = dp[i - 1][0] + dp[i - 1][u % 2];
    dp[i][1] = dp[i - 1][1] + dp[i - 1][(u % 2) ^ 1];
  }
  cout << dp[n][p];
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
using LP=pair<ll,ll>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int A,B;
    cin>>A>>B;
    if(B%A==0)cout<<A+B<<endl;
    else cout<<B-A<<endl;
}

Measured memory_bytes: 3520
import bisect

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0
for i in range(n-2):
    e1 = ll[i]
    for j in range(i+1, n-1):
        e2 = ll[j]
        comb = bisect.bisect_left(ll, e1+e2)
        comb -= (j+1)
        ans += max(comb,0)

print(ans)



Measured memory_bytes: 74540
n = gets.to_i

building = {}
building["1"] = {"1" => [0,0,0,0,0,0,0,0,0,0],
                 "2" => [0,0,0,0,0,0,0,0,0,0],
                 "3" => [0,0,0,0,0,0,0,0,0,0]}
building["2"] = {"1" => [0,0,0,0,0,0,0,0,0,0],
                 "2" => [0,0,0,0,0,0,0,0,0,0],
                 "3" => [0,0,0,0,0,0,0,0,0,0]}
building["3"] = {"1" => [0,0,0,0,0,0,0,0,0,0],
                 "2" => [0,0,0,0,0,0,0,0,0,0],
                 "3" => [0,0,0,0,0,0,0,0,0,0]}
building["4"] = {"1" => [0,0,0,0,0,0,0,0,0,0],
                 "2" => [0,0,0,0,0,0,0,0,0,0],
                 "3" => [0,0,0,0,0,0,0,0,0,0]}

i = 0
while true do
   if i == n
      break
   end
   b, f, r, v = gets.split.map(&:to_i)
   building["#{b}"]["#{f}"][r - 1] += v
   i += 1
end

building["1"].each do |key, val|
   val.each do |nop|
      print " #{nop}"
   end
   puts
end
puts "####################"
building["2"].each do |key, val|
   val.each do |nop|
      print " #{nop}"
   end
   puts
end
puts "####################"
building["3"].each do |key, val|
   val.each do |nop|
      print " #{nop}"
   end
   puts
end
puts "####################"
building["4"].each do |key, val|
   val.each do |nop|
      print " #{nop}"
   end
   puts
end

Measured memory_bytes: 8860
package main

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

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func solve(N int, A []int, B []int, C []int) int {
	K := 3
	as := [][]int{A, B, C}
	dp := make([][]int, N+1) // dp[i][j]: 表示第i天, 参加活动j
							 // 获取到的幸福感
	for i := range dp {
		dp[i] = make([]int, K)
	}

	for i:=1; i<=N; i++ {
		for k:=0; k<3; k++ {
			for kk:=0; kk<3; kk++ {
				if kk == k {
					continue
				}
				dp[i][k] = max(dp[i][k], dp[i-1][kk]+as[kk][i-1])
			}
		}
	}

	ans := 0
	for i:=0; i<K; i++ {
		ans = max(ans, dp[N][i])
	}
	return ans
}

func readLineNum(bf *bufio.Reader) int {
	line, _ := bf.ReadString('\n')
	line = strings.Trim(line, "\n")
	N, _ := strconv.Atoi(line)
	return N
}

func readLineNums(bf *bufio.Reader) []int {
	line, _ := bf.ReadString('\n')
	line = strings.Trim(line, "\n")
	fields := strings.Split(line, " ")
	nums := []int{}
	for _, field := range fields {
		num, _ := strconv.Atoi(field)
		nums = append(nums, num)
	}
	return nums
}

func main() {
	bf := bufio.NewReader(os.Stdin)
	N := readLineNum(bf)
	A, B, C := []int{}, []int{}, []int{}
	for i:=0; i<N; i++ {
		ns := readLineNums(bf)
		A = append(A, ns[0])
		B = append(B, ns[1])
		C = append(C, ns[2])
	}
	fmt.Println(solve(N, A, B, C))
}


Measured memory_bytes: 10112
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*
    I LOVE CLARICE STARLING

     ♥LOVE♥        ♥LOVE♥
  ♥LOVE♥♥LOVE♥  ♥LOVE♥♥LOVE♥
♥LOVE♥♥LOVE♥♥LOVE♥♥LOVE♥♥LOVE♥
   ♥LOVE♥♥LOVE♥♥LOVE♥♥LOVE♥
      ♥LOVE♥♥LOVE♥♥LOVE♥
         ♥LOVE♥♥LOVE♥
            ♥LOVE♥
               ♥


    EXPLAINATION BELOW->
   
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
void solve()
{
    int k,a,b,i;cin>>k>>a>>b;
    foe(i,a,b)
    {
        if(i%k==0){cout<<"OK\n";return;}
    }
    cout<<"NG\n";
}
int main()
{
   fastio
   solve();
  return 0;
}
//map<ll,ll,greater<int>> to sort in descending order ,in iterator declaration no greater<int>
//if you want to apply lowerbound on set use s.lower_bound(key),not the one used for vector
/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/


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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

int main()
{

    string a;
    int s=INT_MAX,e=0;
    cin>>a;
    rep(i,a.size()){
        if(a[i]=='A')s=min(s,i);
        if(a[i]=='Z')e=max(e,i);
    }
    cout<<e-s+1<<endl;
    return 0;
}

Measured memory_bytes: 640
import sys


def input(): return sys.stdin.readline().strip()


def resolve():
    def main():
        s = input()
        k = int(input())
        if int(s[0]) != 1:
            return s[0]
        else:
            cnt = 0
            for i in s:
                if int(i) == 1:
                    cnt += 1
                    if cnt >= k:
                        return 1
                else:
                    if cnt >= k:
                        return 1
                    else:
                        return i

    print(main())
resolve()

Measured memory_bytes: 38256
n, k = list(map(int, input().split()))
li = list(map(int, input().split()))
li.sort()

ar = []
tmp = -1
for a in li:
    if a != tmp:
        tmp = a
        ar.append(1)
    else:
        ar[-1] += 1
ar.sort()

if len(ar) <= k:
    print(0)
else:
    print(sum(ar[:-k]))

Measured memory_bytes: 24748
<?php

function dfs($v, $count, $sum, $n, $k, $s) {
  if ($count == $k) {
    if ($sum == $s) return 1;
    else return 0;
  }
  if ($v > $n || $sum > $s) return 0;
  
  $res = 0;
  
  for ($i = $v + 1; $i <= $n; $i++) {
    $res += dfs($i, $count + 1, $sum + $i, $n, $k, $s);
  }

  return $res;
}

while (fscanf(STDIN, "%d%d%d", $n, $k, $s) && ($n | $k | $s)) {
  print dfs(0, 0, 0, $n, $k, $s) . "\n";
}

Measured memory_bytes: 6592
input_list = list(map(int, input().split()))
input_list.sort()
max_num = input_list[2]
second = input_list[1]
min_num = input_list[0]

count = 0
margin = max_num - second
margin2 = max_num - min_num

if margin % 2 == 0:
    count += margin / 2

else:
    count += margin // 2
    if margin2 % 2 == 0:
        count += 1
        margin2 -= 1

    else:
        count += 1
        margin2 -= 1

if margin2 % 2 ==0:
    count += margin2 / 2

else:
    count += margin2 // 2
    count += 2

print(int(count))






Measured memory_bytes: 3064
#include <iostream>
#include <string.h>
#include <string>
#include <stdio.h>
using namespace std;
int main() {
	string w[3]={"the","this","that"},st;
	int wn[3]={3,4,4},k,i,j,s,f;
	while(getline(cin,st)) {
    k=0; 
	while(k<st.size()) {
		for (i=0;i<3;i++) {
			s=0; f=0;
			if (st.size()<k+wn[i]) break;
			for (j=0;j<wn[i]-1;j++) if (((w[i][j]-w[i][j+1]+26) % 26)==((st[k+j]-st[k+j+1]+26) % 26)) s++;
			if (s==wn[i]-1)  { f=1; i=5;}
		}
		if (f==1) break;
		for (k;st[k]>='a' && st[k]<='z' ; k++);
		k++;
	}
	if (f==0) cout << st; else {
		for (i=0;i<st.size();i++) 
			if ((st[i]>='a' && st[i]<='z')) cout << (char)(((st[i]-st[k]+'t')-97+26) % 26 + 97) ; 
		    else cout << st[i];
	}
	cout << endl;
	}
	return 0;
	}

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

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  ll ans = n/(a+b)*a;
  ll res = n%(a+b);
  if(res < a) ans += res;
  else ans += a;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 	long long int n,i;
 	cin>>n;
 	long long int a[n],freq[n+1];
 	for(i=0;i<n-1;i++)
 	{
 		cin>>a[i];
	 }
 	for(i=0;i<n+1;i++)
 	{
 		freq[i]=0;
	}
	for(i=0;i<n-1;i++)
	{
		freq[a[i]]++;
	}
	for(i=1;i<=n;i++)
	{
		cout<<freq[i]<<"\n";
	}
  
  return 0;
}
    

Measured memory_bytes: 6720
#include<iostream>
#include<string>
#include <vector>

using namespace std;

int main()
{
	int N,flag;

	cin >> N;

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

	cout << "No";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define nmax 100005

using namespace std;
char a[nmax],b[nmax],aux;
int n,m;
int main()
{
    cin>>a>>b;
    m=strlen(a);
    n=strlen(a);
    while(n--)
    {
        if(strcmp(a,b)==0)
        {
            cout<<"Yes"<<'\n';
            return 0;
        }
        aux=a[0];
        strcpy(a,a+1);
        a[m-1]=aux;
    }
    cout<<"No"<<'\n';
    return 0;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[100005];
vector<int> v;
int n;

LL pw[100005], idx[100005];
LL val[100005], sum[100005];
LL diff[400005];
int b = 200000;
LL cal(LL x){
	LL res = 0, ans = 0;
	for(int i=1;i<=n;i++){
		if(a[i] <= x) val[i] = 1;
		else val[i] = -1;
		sum[i] = sum[i-1] + val[i];
		diff[sum[i]+b]++;
		if(sum[i] > 0) res++;
	}
	int cnt = 1;
	for(int i=1;i<=n;i++){
		ans += res;

		if(a[i] <= x) res--;
		diff[sum[i]+b]--;

		if(a[i] <= x){
			res -= diff[cnt+b];
			cnt += val[i];
		}
		else{
			cnt += val[i];
			res += diff[cnt+b];
		}
	}
	return ans;
}

int main(){
	scanf("%d", &n);
	LL m = (LL)n*(n+1)/2;
	LL h = m/2+1;

	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	int lo = 0, hi = v.size()-1, ans = -1;
	while(lo <= hi){
		int mid = (lo+hi)/2;
		int val = v[mid];
		if(cal(val) >= h) ans = val, hi = mid-1;
		else lo = mid+1;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 6008
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
#define ll long long
typedef unsigned long long ull;
typedef long double ld;

#define pii         pair<ll ,ll >
#define vi          vector<ll >
#define vii         vector<pii>
#define mi          map<ll ,ll >
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define pb          push_back
#define hell        1000000007
#define rep(i,a,b)  for(ll int i=a;i<b;i++)
#define take        rep(i,0,n) cin>>v[i];
#define MAXN        1000005


#define allr(c) (c).rbegin(),(c).rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}


void solve()
{
	ll n;
	cin>>n;
	ll t=0;
	vector<vector<ll> >ncr(n+10,vector<ll>(n+10));
	for(ll i=0;i<=n;i++)
	{
		ncr[i][0]=1;
		ncr[i][i]=1;
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<i;j++)
		{
			ncr[i][j]=add(ncr[i-1][j],ncr[i-1][j-1]);
			
		}
	}
	for(ll i=1;i<=n/3;i++)
	{
		ll k=n;
		ll z=n-i*3;
		t=add(t,ncr[z+i-1][i-1]);
	}
	cout<<t<<endl;
}

int main()
    {
    	ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
      
        ll t;
        
        t=1;
        
    
   // cin>>t;
        while(t--)
        solve();
    }

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

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define ALL(x) (x).begin(),(x).end()

using ll = long long;
using ull = unsigned long long;
 
const ll INF = 1LL<<60;
const int MINF = 1e9;
const int MOD = 1e9+7;

using vi = vector<int>;
using vii = vector<vi>;

template<typename T,typename U> bool chmax(T& a, U b) { if (a < b) { a = b; return true; } return false; }
template<typename T,typename U> bool chmin(T& a, U b) { if (a > b) { a = b; return true; } return false; }

template<typename T>
T GCD(T a,T b){ return b ? GCD(b,a%b) : a ;}
template<typename T>
T LCM(T a,T b){ return a*b / GCD(a,b) ;}

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

    int n;cin >> n;
    vi a(100001);
    rep(i,n){
        int t;cin >> t;
        a[t]++;
    }
    ll ans = 0;
    for(int i=2;i<=100000;i++){
        int tmp = a[i-2] + a[i-1] + a[i];
        chmax(ans,tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define NIL -1

using namespace std;

struct Node {
  int parent = NIL, left = NIL, right = NIL;
} T[100];
int n, D[100], root;

int getHeight (int u) {
  int h1 = 0, h2 = 0;

  if (T[u].left == NIL && T[u].right == NIL)
    return 0;
  if (T[u].left != NIL)
    h1 = getHeight(T[u].left) + 1;
  if (T[u].right != NIL)
    h2 = getHeight(T[u].right) + 1;

  // cout << u << " " << h1 << " " << h2 << endl;

  return max(h1, h2);
}

void setDepth (int u, int n) {
  D[u] = n;

  if (T[u].left != NIL)
    setDepth(T[u].left, n + 1);
  if (T[u].right != NIL)
    setDepth(T[u].right, n + 1);
}

void print() {
  for (int i = 0; i < n; i++) {
    int degree = 0;

    cout << "node " << i << ": ";
    cout << "parent = " << T[i].parent << ", ";
    // 输入兄弟节点
    if (T[i].parent != NIL && T[T[i].parent].left != NIL && T[T[i].parent].left != i)
      cout << "sibling = " << T[T[i].parent].left << ", ";
    else if (T[i].parent != NIL && T[T[i].parent].right != NIL && T[T[i].parent].right != i)
      cout << "sibling = " << T[T[i].parent].right << ", ";
    else
      cout << "sibling = -1, ";
    
    if (T[i].left != NIL)
      degree++;
    if (T[i].right != NIL)
      degree++;
    cout << "degree = " << degree << ", ";

    cout << "depth = " << D[i] << ", ";
    cout << "height = " << getHeight(i) << ", ";

    if (T[i].parent == NIL)
      cout << "root" << endl;
    else if (T[i].left != NIL || T[i].right != NIL)
      cout << "internal node" << endl;
    else
      cout << "leaf" << endl;

    // getHeight(i);
  }
}

int main () {
  int id, left, right;

  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> id >> left >> right;

    T[id].left = left;
    T[id].right = right;
    
    if (left != NIL)
      T[left].parent = id;
    if (right != NIL)
      T[right].parent = id;
  }

  for (int i = 0; i < n; i++) {
    if (T[i].parent == NIL) {
      root = i;
      break;
    }
  }

  setDepth(root, 0);

  print();

  return 0;
}



Measured memory_bytes: 3088
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long int ll;
ll a[100100],b[100100];
ll result = 1;
ll mod = 998244353;
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        b[a[i]]++;
    }
    if(a[0] != 0){
        cout << '0' << endl;
        return 0;
    }
    for(int i = 1; i < n; i++){
        result =result * b[a[i]-1] % mod;
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 2296
#include <bits/stdc++.h> 
using namespace std; 
#define ll long long
const ll mod = 1e9+7;
const ll INF = 1LL<<60;
const double pi=3.1415926536;
#define fo(i,n) for( ll int i=0;i<n;++i)
#define fos(j,i,n) for(ll int j=i;j<n;++j)
#define N 100004
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define abs(x) ((x)<0?(-(x)):(x))
#define dis(k) cout << k << endl
#define forr(i,n) for( ll int i= n-1;i>=0;--i)
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl;
#define ve vector
#define fi first
#define se second
#define setzero(a) memset(a,0,sizeof(a))
#define setinf(a) memset(a,0x7F,sizeof(a))
typedef ve< ll > vi;
typedef ve< vi > vvi;
typedef pair< ll ,ll > ii;


//weird debugging stuff
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


/*Don't just sit and hope that God will solve this
fucking do something, try to observe or solve it a different way.
Use that pen and paper.
If nothing works take a deep breath and start again.*/


void solve(){
	ll n;
	cin >> n;
	vi a(n);
	vi dp(n,0);
	fo(i,n) cin >> a[i];
	dp[1]=abs(a[1]-a[0]);
	fos(i,2,n) {
		dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1]));
	}
	dis(dp[n-1]);
			
	
}

int main(){
	fast;
	int t=1;
	int tt=1;
	//cin >> t;

	while(t--){
		//cout << "Case #" << tt << ": " ;
		tt++;
		solve();
	}
	return 0;
}



Measured memory_bytes: 4716
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

void solve(){
    int ans = 0;
    for(int i=1;i<=5;i++){
        int x;
        cin >> x;
        if(x == 0) ans = i;
    }
    cout << ans << endl;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    // int T; cin >> T; REP(t,T) solve();
}

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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

void solve();

int main(void){
    int N, K; cin >> N >> K;
    int H[N]; rep(i, N) cin >> H[i];
    int dp[N]; dp[0] = 0; dp[1] = abs(H[1] - H[0]);
    for(int i = 2; i < K && i < N; i++){
        int mincost = pow(10, 9);
        for(int j = 1; j <= i; j++){
            int val = dp[i-j] + abs(H[i] - H[i-j]);
            if(val < mincost) mincost = val;
        }
        dp[i] = mincost;
    }

    for(int i = K; i < N; i++){
        int mincost = pow(10, 9);
        for(int j = 1; j <= K; j++){
            int val = dp[i-j] + abs(H[i] - H[i-j]);
            if(val < mincost) mincost = val;
        }
        dp[i] = mincost;
    }
    cout << dp[N-1] << endl;
    return 0;
}

void solve(){}

Measured memory_bytes: 1024
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef vector<vector<P>> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<ll> vec;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30);
const int INF = (1LL << 60);
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    string s,t,u;
    int a,b;
    cin>>s>>t>>a>>b>>u;
    if(s==u){
        cout<<a-1<<" "<<b<<endl;
    }
    else{
        cout<<a<<" "<<b-1<<endl;
    }
    
}

Measured memory_bytes: 256
package main

import(
    "fmt"
)



func main() {
    var a,s,c string
    fmt.Scan(&a,&s,&c)
    fmt.Printf("A%cC", s[0])
}





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
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  vector<int> l(m,0);
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++){
      int a;
      cin>>a;
      l[a-1]++;
    }
  }
  int ans=0;
  for(int i=0;i<m;i++){
    if(l[i]==n)
    ans++;
  }
  cout<<ans;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

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

    rep(i, 1, 10) {
        if (N % i == 0 && N / i <= 9) {
            write("Yes");
            return 0;
        }
    }
    write("No");
}

Measured memory_bytes: 256
N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]

for cx in range(101):
    for cy in range(101):
        H = -1
        ok = True
        for x, y, h in P:
            if h == 0:
                continue
            Hi = abs(x-cx) + abs(y-cy) + h
            if H == -1:
                H = Hi
                continue
            if Hi != H:
                ok = False
                break
        if not ok:
            continue
        for x, y, h in P:
            if h != max(H-abs(cx-x)-abs(cy-y), 0):
                ok = False
        if ok:
            print(cx, cy, H)
            break
    if ok:
        break

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;

int main(){
    int N, M;
    cin >> N >> M;
    int hw = 0;
    rep(i, M){
        int a;
        cin >> a;
        hw+=a;
    }
    if(N-hw>=0){
        cout << N-hw << endl;
    }
    else cout << "-1" << endl;
    return 0;
 }


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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PI acos(-1.0)
#define sq(n) (n)*(n)

using namespace std;
typedef long long ll;

int main() {
    FAST;

    int n;
    cin >> n;

    bool f = 0;
    while (n) {
        if (n % 10 == 7) {
            f = 1;
            break;
        }
        n /= 10;
    }

    puts(f ? "Yes" : "No");

    return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <string>
using namespace std;
int main(int argc, const char * argv[])
{
    string word;
    //string test = "this";
    //string test2 = "the";
    //string test3 = "that";
    int i;
    while (getline(cin, word)) {
        while (1) {
            for (i = 0; i < word.size(); i++) {
                if (isalpha(word[i])) {
                    word[i]++;
                    if (word[i] == '{') {
                        word[i] = 'a';
                    }
                }
            }
            if (word.find("this") != -1 || word.find("that") != -1 || word.find("the") != -1) {
                break;
            }
        }
        cout << word << endl;
    }
    return 0;
}

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


template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v){
    if(!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}

template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
    out << "[" << p.first << ", " << p.second << "]";
    return out;
}
//---------

int dp[110][10010]; //dp[??????][??????]
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, W;
    cin >> N >> W;
    vector<int> v(N);
    vector<int> w(N);
    memset(dp, 0, sizeof(dp));

    rep(i, 0, N){
        cin >> v[i] >> w[i];
    }

    // for(int i = N-1; i >= 0; i--){
    //     for(int j = 0; j <= W; j++){
    //         if(j < w[i]){
    //             dp[i][j] = dp[i+1][j];
    //         }else{
    //             dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
    //         }
    //     }
    // }


    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= W; j++){
            if(j < w[i-1]){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }

    // rep(i, 0, N+1){
    //     rep(j, 0, W+1){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    cout << dp[N][W] << endl;
}

Measured memory_bytes: 5508
#include <iostream>
#define MAXN 200000
using namespace std;
int main(){
	int N, input;
	int arr[MAXN+1] = {0};
	cin >> N;
	for(int i=1; i<N; i++){
		cin >> input;
		arr[input]++;
	}
	for(int i=1; i<=N; i++)
		cout << arr[i] << endl;
}
		


Measured memory_bytes: 4416
#最小の2 ** Xを求める
import  math

def divide_by_two(i, k):
    if i % 2 == 0:
        i = i /2
        k += 1
        k = divide_by_two(i, k)
    else:
        return k
    
    return k
            

N = int(input())
line_number = list(map(int, input().split()))

min = math.log2(10**9)


for i in range(N):
    k = divide_by_two(line_number[i], 0)
    
    if k <= min:
        min = k
        
print(min)

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

int main(){
  ll N;
  cin >> N;
  if (N==1) {
    cout << "0" << endl;
    return 0;
  }
  ll ans=0;
  ll sq=sqrt(N);
  for(ll i=1;i<=sq;i++){
    if(N%i==0) {
      ll m=N/i-1;
      if(N/m == N%m) ans+=m;
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll D[100005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, N) {
        cin >> D[i];
    }
    sort(D, D + N);

    cout << D[N / 2] - D[N / 2 - 1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
const int INF = numeric_limits<int>::max();

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

int main()
{
    int a, b , c, k; cin >> a >> b >> c >> k;
    while (a >= b && k > 0) {
        b *= 2;
        k--;
    }
    while (b >= c && k > 0) {
        c *= 2;
        k--;
    }
    if (k >= 0 && b > a && c > b)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3680
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
#include <map>
#include <climits>
#include <sstream>
using namespace std;

#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second
#define mkp make_pair

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
static const int INF=1<<24;

template <class T>
void initvv(vector<vector<T> > &v,int a,int b, const T  &t = T()){
	v.assign(a,vector<T>(b,t));
}

int main(){
	int n;
	while(cin>>n,n){
		vector<vint> vv;
		initvv(vv,n+1,n+1);
		rep(i,n){
			rep(j,n){
				cin>>vv[i][j];
			}
		}
		rep(i,n){
			int S=0;
			rep(j,n){
				S+=vv[i][j];
			}
			vv[i][n]=S;
			// cout<<S<<endl;
		}
		rep(i,n+1){
			int S=0;
			// cout<<0<<endl;
			rep(j,n){
				S+=vv[j][i];
				// cout<<j<<endl;
			}
			vv[n][i]=S;
			// cout<<S<<endl;
		}
		rep(i,n+1){
			rep(j,n+1){
				printf("%5d",vv[i][j]);
			}
			cout<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

ll mdpow(ll x,ll k){
	ll res=1;
	while(k!=0){
		if(k&1)res=res*x%MOD;
		x=x*x%MOD;
		k=k>>1;
	}
	return res;
}

ll d,s;
vl l;
int dp[301][301*301][2];

int dfs(int div,int rem,int flag){
	int& ret=dp[div][rem][flag];
	if(dp[div][rem][flag]<0){
		if(div==d){
			ret=(flag?-1:1)*mdpow(rem,d);
		}
		else{
			ret=dfs(div+1,rem,flag);
			if(rem>=l[div])ret+=dfs(div+1,rem-l[div],1-flag);
		}
	}
	ret=((ret%MOD)+MOD)%MOD;
	return ret;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>d;
	l.resize(d);
	rep(i,d)cin>>l[i];
	cin>>s;
	memset(dp,-1,sizeof(dp));
	dfs(0,s,0);
	cout<<dp[0][s][0]<<endl;
}



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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

ll N;
vector<P> v;

int main(){
    cin >> N;
    for(int i=0;i<N-1;i++){
        ll s,t;
        cin >> s >> t;
        v.push_back({min(s,t),max(s,t)});
    }
    ll ans = 0;
    for(ll i=1;i<=N;i++){
        ans += i * (N-i+1);
    }
    for(auto &e : v){
        ans -= e.first * (N-e.second+1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7432
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {

    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        boolean[] AC = new boolean[N];
        int[] WA = new int[N];
        int acc = 0;
        int wac = 0;
        for (int i = 0; i < M; i++) {
            int p = sc.nextInt()-1;
            boolean ac = sc.next().equals("AC");

            if (AC[p])
                continue;
            if (ac) {
                acc++;
                wac += WA[p];
                AC[p]=true;
            } else {
                WA[p]++;
            }
        }
        System.out.println(acc + " " + wac);
    }
}


Measured memory_bytes: 62616
N = int(input())
B = [int(x) for x in input().split()]
A = [B[0]]
for n in range(1,N-1):
    A.append(min(B[n-1],B[n]))
A.append(B[N-2])
res = 0
for x in A:
    res += x
print(res)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main() {
  int r, d ,x;
  cin>>r>>d>>x;
  
  for(int i = 0; i < 10; i++) {
  		cout<<x * r - d<<endl;
    	x = x * r -d;
  }
  return 0;
}

Measured memory_bytes: 256
s = input()
t = input()

cnd = []
for i in range(len(s) - len(t) + 1):
    if all(s[i + j] == t[j] or s[i + j] == '?' for j in range(len(t))):
        cnd.append(i)

if cnd:
    x = [s[:k] + t + s[k + len(t):] for k in cnd]
    x = [v.replace('?', 'a') for v in x]
    print(sorted(x)[0])
else:
  	print('UNRESTORABLE')
    

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

// header area
void dfs(int keta, string tmp, vector<string> &dfs_753, int N){
    if(keta>=10) return;

    if(keta>0){
        bool flag3 = tmp.find('3')!=string::npos;
        bool flag5 = tmp.find('5')!=string::npos;
        bool flag7 = tmp.find('7')!=string::npos;
        if(N>=stoi(tmp) && flag3 && flag5 && flag7){
            // cout << "tmp: "<< tmp <<  endl;
            dfs_753.push_back(tmp);
        }
    }
    for(char i:{'3', '5', '7'}){
        dfs(keta+1, tmp+i, dfs_753, N);
    }
}

int main(){
    int N; cin >> N;
    vector<string> dfs_753;

    dfs(0, "", dfs_753, N);    // N以下、10桁までの値の列挙

    cout << dfs_753.size() << endl;

    return 0;
}

Measured memory_bytes: 2044
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		Scanner in = new Scanner(System.in);

		long X, Y;

		X = in.nextLong();
		Y = in.nextLong();

		int ans = 0;
		long X_i = X;
		while(X_i <= Y) {
			ans++;
			X_i *= 2;
		}

		System.out.println(ans);

	}

}


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

signed main(){
  
  int n;
  cin>>n;
  
  if( n % 2 == 0 ) cout << 0.5000000 << endl;
  else{
    cout << 1.0 * ( n / 2 + 1 ) / n << endl;;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <set>

int main(int argc, char *argv[]) {
  int n, m;
  std::cin >> n;
  std::set<int> a, b;
  int x;
  for (int i = 0; i < n; ++i) {
    std::cin >> x;
    a.insert(x);
  }
  std::cin >> m;
  for (int i = 0; i < m; ++i) {
    std::cin >> x;
    b.insert(x);
  }

  std::set<int> res;
  std::set_union(a.begin(), a.end(), b.begin(), b.end(),
                 std::inserter(res, std::end(res)));
  for (auto &v : res)
    std::cout << v << std::endl;
}



Measured memory_bytes: 40592
import sys
def input():
    return sys.stdin.readline()[:-1]

N,K = map(int,input().split(' '))
l = list(map(int, input().split()))
L = sorted(l, reverse=True)
cnt = 0

for i in range(N):
    k = L[i]
    if i<K:
        continue
    cnt += k
print(cnt)

Measured memory_bytes: 26024
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	int s[101];
	int sum;
	
	while(scanf("%d", &n), n != 0){
		sum = 0;
		for (int i = 0; i < n;i++) scanf("%d", &s[i]);
		
		sort(s, s + n);
		
		for (int i = 1; i < n-1; i++){
			sum += s[i];
		}
		
		printf("%d\n", sum/(n-2));
	}
}

Measured memory_bytes: 2620
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

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

  int N, M;
  cin >> N >> M;
  int sx, sy, ex, ey;
  cin >> sx >> sy >> ex >> ey;
  sx--, sy--, ex--, ey--;
  vector<string> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  deque<pair<pair<int, int>, int>> dq;
  dq.push_back({{sx, sy}, 0});
  vector<vector<int>> dist(N, vector<int>(M, -1));
  dist[sx][sy] = 0;
  while (!dq.empty()) {
    int x = dq.front().first.first;
    int y = dq.front().first.second;
    int d = dq.front().second;
    dq.pop_front();
    if (dist[x][y] != d) {
      continue;
    }
    for (int i = -2; i <= 2; i++) {
      for (int j = -2; j <= 2; j++) {
        int nx = x + i, ny = y + j;
        if (abs(i) + abs(j) == 1 && 0 <= nx && nx < N && 0 <= ny && ny < M && A[nx][ny] != '#') {
          if (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y]) {
            dist[nx][ny] = dist[x][y];
            dq.push_front({{nx, ny}, dist[nx][ny]});
          }
        }
        if (0 <= nx && nx < N && 0 <= ny && ny < M && A[nx][ny] != '#') {
          if (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y] + 1) {
            dist[nx][ny] = dist[x][y] + 1;
            dq.push_back({{nx, ny}, dist[nx][ny]});
          }
        }
      }
    }
  }
  cout << dist[ex][ey] << "\n";
  return 0;
}


Measured memory_bytes: 8688
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use nalgebra::max;

fn main() {
    input! {
    n: usize,
    v: [usize; n]
    }
    let mut ec = vec![0; 100005];
    let mut oc = vec![0; 100005];
    for i in 0..n {
        if i % 2 == 0 {
            ec[v[i]] += 1;
        } else {
            oc[v[i]] += 1;
        }
    }
    let (mut em, mut om) = (0, 0);
    let (mut sem, mut som) = (0, 0);
    for i in 0..100005 {
        if ec[em] <= ec[i] {
            sem = em;
            em = i;
        } else if ec[sem] < ec[i] {
            sem = i;
        }
        if oc[om] <= oc[i] {
            som = om;
            om = i;
        } else if oc[som] < oc[i] {
            som = i;
        }
    }
    let ans = ec.iter().sum::<usize>() + oc.iter().sum::<usize>()
        - if em == om {
        max(ec[em] + oc[som], ec[sem] + oc[om])
    } else {
        ec[em] + oc[om]
    };
    println!("{}", ans);
}


Measured memory_bytes: 4872
# include <iostream>
# include <math.h>

using namespace std;

int main()
{
	long long int X, K, D;

	cin >> X >> K >> D;

	double help;

	if (X < 0)
		X = abs(X);

	help = (double)X / (double)D;

	if (X == D)
	{
		if (K % 2 == 0)
			cout << abs(X);
		else
			cout << 0;
	}
	else
	{
		if (floor(help) > K)
		{
			for (int i = 0; i < K; i++)
			{
				X -= D;
			}
		}
		else
		{
			help = floor(help);
			
			if ((K - (int)help) % 2 != 0)
			{
				help++;
			}

			for (int i = 0; i < help; i++)
			{
				X -= D;
			}
		}

		cout << abs(X) << endl;
	}

	return 0;
}

Measured memory_bytes: 3744