akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;
bool IsPrime[1300000];
vector<int> Prime;

void calc()
{
	memset(IsPrime, 1, sizeof(bool) * 1300000);
	for(int i = 2; i < 1300000; ++i)
	{
		if(IsPrime[i])
		{
			Prime.push_back(i);
			for(int j = 2 * i; j < 1300000; j += i)
			{
				IsPrime[j] = false;
			}
		}
	}
}

void solve()
{
	calc();
	int n;
	while(cin >> n, n)
	{
		if(IsPrime[n])
		{
			cout << 0 << endl;
		}
		else
		{
			int pos = 0;
			while(Prime[pos] < n)
			{
				pos++;
			}
			cout << Prime[pos] - Prime[pos - 1] << endl;
		}
	}
}

int main()
{
	solve();
	return(0);
}

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

#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

constexpr int MAX_W = 100000;

struct Node {
    int parent = -1;
    int left_child = -1;
    int right_brother = -1;

    Node() : parent(-1), left_child(-1), right_brother(-1) {}
    Node(int p, int l, int r) : parent(p), left_child(l), right_brother(r) {}
    Node(Node& n) {
        parent = n.parent;
        left_child = n.left_child;
        right_brother = n.right_brother;
    }
};

void get_depth(const vector<Node>& nodes, vi& depth, int id, int d) {
    depth[id] = d;
    if (nodes[id].left_child != -1) {
        get_depth(nodes, depth, nodes[id].left_child, d + 1);
    }
    if (nodes[id].right_brother != -1) {
        get_depth(nodes, depth, nodes[id].right_brother, d);
    }
}

string get_children(const vector<Node>& nodes, int id) {
    if (nodes[id].left_child == -1) { return "[]"; }

    vi c = {nodes[id].left_child};
    while (nodes[c.back()].right_brother != -1) {
        c.push_back(nodes[c.back()].right_brother);
    }

    int n = c.size();
    string str = "[";
    rep(i, 0, n) {
        str += to_string(c[i]);
        if (i != n - 1) { str += ", "; }
        else { str += "]"; }
    }
    return str;
 }

string get_state(const vector<Node>& nodes, int id) {
    if (nodes[id].parent == -1) { return "root"; }
    if (nodes[id].left_child == -1) { return "leaf"; }
    return "internal node";
}

int get_root(const vector<Node>& nodes) {
    int id = 0;
    while (nodes[id].parent != -1) {
        id = nodes[id].parent;
    }
    return id;
}

void print(const vector<Node>& nodes, int id) {
    cout << nodes[id].parent << " " << nodes[id].left_child;
    cout << " " << nodes[id].right_brother << endl;
}

int main() {
    int n;
    cin >> n;
    vector<Node> nodes(n);

    rep(i, 0, n) {
        int id, k;
        cin >> id >> k;

        int prev = -1;
        rep(j, 0, k) {
            int c;
            cin >> c;

            if (j == 0) {
                nodes[id].left_child = c;
            } else {
                nodes[prev].right_brother = c;
            }
            nodes[c].parent = id;
            prev = c;
        }
    }

    vi depth(n, 0);
    get_depth(nodes, depth, get_root(nodes), 0);
    rep(i, 0, n) {
        cout << "node " << i << ": parent = " << nodes[i].parent;
        cout << ", depth = " << depth[i];
        cout << ", " << get_state(nodes, i);
        cout << ", " << get_children(nodes, i) << endl;
    }

    return 0;
}


Measured memory_bytes: 6028
/*
 *  author : Atul Anand   
 *  created on : Thu Apr 02 2020
 */

import java.io.*;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException {
        int N = in.nextInt();
        int D = in.nextInt();
        double X[][] = new double[N][D];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < D; j++){
                X[i][j] = in.nextDouble();
            }
        }
        int ans = 0;
        for(int i = 0; i < N; i++){
            for(int j = i + 1; j < N; j++){
                if(IntegerDistance(X[i], X[j], D)){
                    ans++;
                }
            }
        }
        println(ans);
        in.close();
        out.close();
    }

    static boolean IntegerDistance(double a[], double b[], int D){
        double dist = 0;
        for(int i = 0; i < D; i++){
            dist += (a[i] - b[i]) * (a[i] - b[i]);
        }
        dist = Math.sqrt(dist);

        if(Math.floor(dist) == dist){
            return true;
        }

        return false;
    }

    static int MIN = Integer.MIN_VALUE;
    static int MAX = Integer.MAX_VALUE;
    static Reader in = new Reader();
    static PrintWriter out = new PrintWriter(System.out);

    static void read(int arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextInt(); 
    	} 
    }
    
    static void read(long arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextLong(); 
    	} 
    }
    
    static void read(String arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.next(); 
    	} 
    }
    
    static void print(Object O) {  
    	out.print(O); 
    }
    
    static void println(Object O) { 
    	out.println(O); 
    }
    
    static void println(int arr[]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		print(arr[i]+" "); 
    	} 
    	println(""); 
    }

    static void println(int arr[][]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		println(arr[i]); 
    	}
    }
    
    static void debug(Object O) { 
    	System.out.println(O); 
    }
}

class Reader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    Reader() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    String next() throws IOException {
        while (!tokenizer.hasMoreTokens() ) { 
            tokenizer = new StringTokenizer(reader.readLine()); 
        }
        return tokenizer.nextToken();
    }

    int nextInt() throws IOException { 
        return Integer.parseInt(next()); 
    }
    
    double nextDouble() throws IOException { 
        return Double.parseDouble(next());
    }
    
    long nextLong() throws IOException { 
        return Long.parseLong(next()); 
    }
    
    String nextLine() throws IOException { 
        return reader.readLine(); 
    }
    
    void close() throws IOException { 
        reader.close(); 
    }
}

Measured memory_bytes: 22356
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const ll maxn=2e5+111;
ll a[maxn];
map<ll,ll> mp1,mp2;
int main(){
    //printf("%lld",1000ll*1000*1000*1000*1000-999ll*999*999*999*999);
    ll n;
    scanf("%lld",&n);
    ll b=0;
    ll ans1,ans2;
    while(1){
        ll bb=b*b*b*b*b;
        ll xx=n+bb;
        ll hh=pow(xx,1.0/5);
        if(hh*hh*hh*hh*hh==xx){
            ans1=hh,ans2=b;
            break;
        }
        xx=n-bb;
        hh=pow(xx,1.0/5);
        if(hh*hh*hh*hh*hh==xx){
            ans1=hh,ans2=-b;
            break;
        }
        
        ++b;
    }
    printf("%lld %lld\n",ans1,ans2);

    return 0;
}
/*
4990009995001
*/

Measured memory_bytes: 4216
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
ll mod = 998244353;

int N;
int a[300];

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

ll fact[200200];
ll invfact[200200];

inline ll take_mod(ll a){
    return (a % mod + mod) % mod;
}

inline ll add(ll a, ll b){
    return take_mod(a+b);
}

inline ll sub(ll a, ll b){
    return take_mod(a-b);
}


inline ll mul(ll a, ll b){
    return take_mod(a * b);
}

inline ll pow(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return pow(x, mod-2);
}

// nは上限
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}

// nは上限
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}

ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}

ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}

ll dp[310][110000];
ll dp2[310][110000];


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


    for(int i = 0; i <= N; i++){
        fill(dp[i], dp[i]+N+1, 0);
    }

    dp[0][0] = dp2[0][0] = 1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= s; j++){
            if(j - a[i] >= 0) {
                dp[i + 1][j] = (dp[i+1][j] + dp[i][j-a[i]]) % mod;
                dp2[i + 1][j] = (dp2[i+1][j] + dp2[i][j-a[i]]) % mod;
            }
            dp[i+1][j] = (dp[i+1][j] + mul(dp[i][j], 2)) % mod;
            dp2[i+1][j] = add(dp2[i+1][j], dp2[i][j]);
        }
    }

    ll res = 1;
    for(int i = 0; i < N; i++){
        res = (res * 3) % mod;
    }

    if(s % 2 == 0){
        dp[N][s/2] = sub(dp[N][s/2], dp2[N][s/2]);
    }
    for(int i = s; i >= (s+1)/2; i--){
        res = sub(add(res, mod), dp[N][i] * 3);
    }

    cout << res << endl;


    return 0;
}


Measured memory_bytes: 519424
using System;
using System.Linq;

namespace _0599
{
	class Program
	{
		static void Main(string[] args)
		{
			int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int[] manju = new int[x[0]];
			for (int i = 0; i < x[0]; i++) manju[i] = int.Parse(Console.ReadLine());
			Array.Sort(manju); Array.Reverse(manju);
			int[] dp = new int[10101];
			for (int i = 1; i < 10101; i++) dp[i] = 1000000000;
			for (int i = 0; i < x[1]; i++)
			{
				int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
				for (int j = 10010; j >= 0; j--)
				{
					if (j >= a[0]) dp[j] = Math.Min(Math.Min(dp[j], dp[j + 1]), dp[j - a[0]] + a[1]);
					else dp[j] = Math.Min(dp[j], dp[j + 1]);
				}
			}
			int ret = 0; int sum = 0;
			for (int i = 0; i < x[0]; i++)
			{
				sum += manju[i];
				ret = Math.Max(ret, sum - dp[i + 1]);
			}
			Console.WriteLine(ret);
		}
	}
}


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

long long gcd(long long a, long long b) {
  return b != 0 ? gcd(b, a % b) : a;
}
long long lcm(long long a, long long b) {
  return a * b / gcd(a, b);
}

int calc(int a, int m)
{
	int cnt=1, p=a%m;
	while(p!=1)
	{
		p=(a*p)%m;
		cnt++;
	}
	
	return cnt;
}

int main()
{
	while(1)
	{
		int a[3],m[3],f[3];
		for(int i=0; i<3; i++)
			cin >> a[i] >> m[i];
			
		if(a[0]==0) break;
			
		for(int i=0; i<3; i++)
			f[i]=calc(a[i], m[i]);
		
		cout << lcm(f[0], lcm(f[1], f[2])) << endl;
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;


int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

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

	vector<Int> s(N + 1);
	for (int i = 0; i < N; i++) {
		s[i + 1] = s[i] + a[i];
	}

	
	map<Int, Int> b;
	for (int i = 0; i < N+1; i++) {
		b[s[i]]++;
	}

	Int ans = 0;
	for (auto x:b) {
		Int num = x.second;
		ans += num * (num - 1) / 2;
	}

	cout << ans;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 4;
const int INF = 1e9;
int arr[MAXN];
int dp[MAXN];
int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> arr[i];
    for(int i = 0; i < n; i++) dp[i] = INF;
    dp[0] = 0;
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= k && i - j >= 0; j++){
            dp[i] = min(dp[i], dp[i - j] + abs(arr[i] - arr[i - j]));
        }
    }
    cout << dp[n - 1] << '\n';
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;

namespace CP
{
    class Atria
    {
        static void Main(string[] args)
        {
            int n = int.Parse(ReadLine());
            int[] p = ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] q = ReadLine().Split(' ').Select(int.Parse).ToArray();
            var s = new List<int>();
            for (int i = 0; i < n; i++)
            {
                s.Add(i + 1);
            }
            var parm = Permutation<int>.Make(s).ToList();
            int pb = -1;
            int qb = -1;
            int j = 0;
            while (pb == -1 || qb == -1)
            {
                if (parm[j].SequenceEqual(p))
                {
                    pb = j;
                }
                if (parm[j].SequenceEqual(q))
                {
                    qb = j;
                }
                j++;
            }
            WriteLine(
                Abs(pb - qb)
                );
        }
    }
    static class Permutation<T>
    {
        private static void Search(List<T[]> perms, Stack<T> stack, T[] a)
        {
            int N = a.Length;
            if (N == 0)
            {
                perms.Add(stack.Reverse().ToArray());
            }
            else
            {
                var b = new T[N - 1];
                Array.Copy(a, 1, b, 0, N - 1);
                for (int i = 0; i < a.Length; ++i)
                {
                    stack.Push(a[i]);
                    Search(perms, stack, b);
                    if (i < b.Length) { b[i] = a[i]; }
                    stack.Pop();
                }
            }
        }
        /// <summary>
        /// 配列を与えるとList<T>で順列組み合わせを返す。
        /// </summary>
        /// <param name="src"></param>
        /// <returns></returns>
        public static IEnumerable<T[]> Make(IEnumerable<T> src)
        {
            var perms = new List<T[]>();
            Search(perms, new Stack<T>(), src.ToArray());
            return perms;
        }
    }
}


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

int n, m, q;
int ans = 0;
vector<int> a, b, c, d;

void dfs(int l, vector<int> arr){
    if(arr.size() == n){

        //printf("\nA: ");
        //for(auto e : arr) printf("%d ", e);
        //printf("\n");

        int sum = 0;
        for(int j = 0; j < q; j++){
            if(arr[b[j]-1] - arr[a[j]-1] == c[j]){
                sum += d[j];
                
                //printf("A[%d] - A[%d] = %d, c[%d] = %d, d[%d] = %d\n",
                //    b[j]-1, a[j]-1, arr[b[j]-1] - arr[a[j]-1], j, c[j], j, d[j]);
                //printf("sum = %d\n", sum);
            }
        }
        ans = max(ans, sum);
    } else {
        for(int j = l; j <= m; j++){
            arr.push_back(j);
            dfs(j, arr);
            arr.pop_back();
        }
    }
}

int main(){
    cin >> n >> m >> q;
    a.resize(q);
    b.resize(q);
    c.resize(q);
    d.resize(q);
    for(int i = 0; i < q; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    vector<int> arr;
    dfs(1, arr);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3532
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define N 220
#define INF 0x3f3f3f3f

int d[N][N];
int a[N];

void floyd(int n) {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    int n, m, r;
    while (scanf("%d%d%d", &n, &m, &r) != EOF) {
        for (int i = 0; i < r; ++i) scanf("%d", &a[i]); sort(a, a + r);
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) d[i][j] = (i == j ? 0 : INF);
        for (int i = 0; i < m; ++i) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w); d[u][v] = d[v][u] = w;
        }
        int res = INF;
        floyd(n);
        do {
            int tmp = 0;
            for (int i = 1; i < n; ++i) tmp += d[a[i - 1]][a[i]];
            res = min(res, tmp);
        } while (next_permutation(a, a + r));
        printf("%d\n", res);
    }
    return 0;
}


Measured memory_bytes: 512
import math

a, b, x = map(int,input().split())
if (a**2)*b == x:
    print(0)
elif (a**2)*b<2*x:
    print(90-math.degrees(math.atan((a**3)/(2*((a**2)*b-x)))))
else:
    print(90-math.degrees(math.atan((2*x)/(a*(b**2)))))

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <istream>

using namespace std;

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

int main(){
	int n,m;
	cin >> n >> m;
	int x[100000];
	for(int i=0;i<m;i++) cin >> x[i];
	sort(x, x+m) ;

	int d[100000];
	for (int i = 0; i < m-1; i++) d[i] = x[i+1] - x[i];
	sort(d,d+(m-1));

	ll ans = 0;
	for (int i = 0; i < m - n; i++){
		ans += (ll) d[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include<math.h>

int main(void){
int a, b, C;
double S, L, h, c;
double rad;
double PI = acos(-1);

scanf("%d %d %d", &a, &b, &C);

rad = C * PI / 180;

S = (a*b*sin(rad))/2;

c = sqrt(a*a+b*b-2*a*b*cos(rad));
L = a + b + c;

h = 2*S/a;

printf("%0.8f\n", S);
printf("%0.8f\n", L);
printf("%0.8f\n", h);

return 0;

}


Measured memory_bytes: 2116
#include <cmath>
#include<vector>
#define rep(i, n) for (int i=0;i<n;i++)
#include <map> 
#include<algorithm>
#include <numeric>
#include<iostream>
#include<deque>
#include<queue>
#include<string>
#include <iomanip>
using namespace std;
typedef long long ll;

vector <int> to[200005]; // vector の配列
vector <int> ans;
void dfs(int v, int p=-1){ //デフォルト因数
    for(int i=0 ;i<to[v].size();i++){
        int u=to[v][i];
        if (u==p) continue;
        ans[u]+=ans[v];
        dfs(u, v);
    }
}
int main(void){
    int n, q;
    cin>>n>>q;
    rep(i, n-1){
        int a, b;
        cin>>a>>b;
        --a;--b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    ans.resize(n);
    rep(i, q){
        int p, x;
        cin>>p>>x;
        --p;
        ans[p]+=x;
    }
    dfs(0);
    rep(i, n){
        cout<<ans[i]<<endl;
    }


    return 0;


}



Measured memory_bytes: 23552
S = gets

n = 0
e = 0
w = 0
s = 0

S.each_char{|c|
	case c
		when 'N' then
			n += 1
		when 'E' then
			e += 1
		when 'W' then
			w += 1
		when 'S' then
			s += 1
	end
}
if(n>0 && e>0 && w>0 && s>0)
	puts "Yes"
elsif((n>0 && s>0 && w == 0 && e == 0)||(n == 0 && s == 0 && e>0 && w>0))
	puts "Yes"
else
	puts "No"
end

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,i,s=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		if(i%3==0||i%5==0)
		{
			continue;
		}
		s=s+i;
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 3644
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def solve(info):
    for Cx in range(101):
        for Cy in range(101):
            height = abs(Cx - info[0][0]) + abs(Cy - info[0][1]) + info[0][2]
            flag = True
            for x,y,h in info[1:]:
                val = max(height - abs(Cx - x) - abs(Cy - y), 0)
                if h == val:
                    continue
                else:
                    flag = False
                    break
            if flag:
                return Cx, Cy, height

def Main():
    n = read_int()
    info = [tuple(read_ints()) for _ in range(n)]
    info.sort(key=lambda x: x[2], reverse=True)

    print(*solve(info))

if __name__ == '__main__':
    Main()

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

#define FOR( i, m, n )   for( int i = m; i < n; i++ )
#define REP( i, n )      FOR( i, 0, n )
#define ALL( a )         (a).begin(), (a).end()

typedef long long ll;

int main(){
  int a, b, c; cin >> a >> b >> c;

  if( b - a == c - b ){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
n, k = map(int, input().split())
cnt = 0
ans = 0
a = 0
b = 0
for i in range(1, n+1):
    if i % k == 0:
        a += 1
    elif i % k == k / 2:
        b += 1
ans = a**3 + b**3
print(ans)


Measured memory_bytes: 38896
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double K = sc.nextInt();
        int count = 0;
        for(double i = 1; i<=K; i++){
            count += Math.ceil((K - i)/2);
        }
        System.out.print(count);
    }
}


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

int main() {
	int x,y,z;
	cin>>x>>y>>z;
	for(int i=0;i<100000;i++) {
		if(x<(y*i+z*(i+1))) {
			cout<<i-1<<endl;
			break;
		}
	}
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N, M;
  cin >> N >> M;
  
  int ans[M];
  for(int i=0;i<M;i++) ans[i]=0;
  for(int i=0;i<N;i++){
    int K;
    cin >> K;
    for(int j=0;j<K;j++){
      int a;
      cin >> a;
      a--;
      ans[a]++;
    }
  }
  int result=0;
  
  for(int i=0;i<M;i++){
    if(ans[i]==N)
      result++;
  }
  
  cout << result << endl;
  return 0;
}

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

int main(){
	int x;
	cin>>x;
	int x_500 = x/500;
	int x_50 = x%500/5;
	//cout << "500: " + x_500 << endl;
	//cout << "50: " + x_50 << endl;
	//printf("%d\n",x_500);
	//printf("%d\n",x_50);

	int ans = x_500*1000 + x_50*5;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>

typedef long long int ll;

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

const ll MOD = 1000000007;

using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;

	if (a + b == 15)
	{
		cout << "+" << endl;
		return 0;
	}
	if (a*b == 15)
	{
		cout << "*" << endl;
		return 0;
	}
	cout << "x" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <cctype>
#define il inline
#define ll long long
#define rgi register ll
#define maxn 1000010

using namespace std;

ll n, ans;
ll A[maxn], B[maxn], C[maxn];

il ll read()
{
	rgi x = 0, f = 0, ch;
	while(!isdigit(ch = getchar())) f |= ch == '-';
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

int main()
{
	n = read();
	for(rgi i = 1; i <= n + 1; ++i)
		A[i] = read();
	for(rgi i = 1; i <= n; ++i)
		B[i] = read();
	for(rgi i = 1; i <= n + 1; ++i)
	{
		if(B[i] + C[i] >= A[i])//defeat all
		{
			ans += A[i];
			if(C[i] >= A[i])
				C[i + 1] = B[i];
			else
				C[i + 1] = B[i] + C[i] - A[i];
		}
		else//not defeat all
			ans += (B[i] + C[i]);
	}
	printf("%lld", ans);
	return 0;
}


Measured memory_bytes: 9088
k, n = map(int, input().split())
a = list(map(int, input().split()))
max = 0
len = [0] * n
for i in range(n):
    if i == 0:
        len[i] = a[i]
    else:
        len[i] = a[i] - a[i - 1]
        if len[i] >= len[max]:
            max = i
print(min((k - a[max]) + a[max - 1], a[n - 1] - a[0]))

Measured memory_bytes: 77516
#include <bits/stdc++.h>
using namespace std;
const int N = 2005, MOD = 1e9 + 7;
int C[N][N], pre[N][N], dp[N][N];
int main() {
	for (int i = 0; i < N; ++ i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++ j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
	}
	int R, B;
	scanf("%d%d", &R, &B);
	for (int r = 0; r <= R; ++ r) {
		for (int b = r + 1; b <= B; ++ b) {
			pre[r][b] = C[b - 1][r];
		}
	}
	for (int k = 0; k < 2; ++ k) {
		for (int b = 0; b <= B; ++ b) {
			for (int r = 1; r <= R; ++ r) {
				(pre[r][b] += pre[r - 1][b]) %= MOD;
			}
		}
	}
	for (int r = 0; r <= R; ++ r) pre[r][0] = 1;
	int ans = 0;
	for (int r1 = 0; r1 <= R; ++ r1) {
		for (int b1 = 1; b1 <= B; ++ b1) {
			int r = R - r1 - (B - b1);
			if (r >= 0) (ans += 1LL * C[B - 1][b1 - 1] * pre[r][B - b1] % MOD) %= MOD;
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 33024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define INF 1e10
#define MOD 1e9+7
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; }
using Graph = vector<vector<int>>;
int fg(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}
signed main(){
 int a,b;
 cin>>a>>b;
 int sum=0;
 for(int i=b;i<=a+1;i++){
   sum+=(a-i+1)*i+1;
   sum=sum%1000000007;
 }
  cout<<sum;
}


Measured memory_bytes: 3636
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();

        for (int i = 0; i < B; i++) {
            if (B <= A * i - i + 1) {
                System.out.println(i);
                return;
            }
        }
    }
}

Measured memory_bytes: 21844
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    ll k;
    cin >> s >> k;
    ll cnt=0;
    string m;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1') cnt++;
        else {
            m=s[i];
            break;
        }    
    }
    if(cnt>=k){
        cout << 1 << endl;
    }
    else{
        cout << m <<endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define max(x,y) ((x)>(y)?(x):(y))

int gcd(int n,int m){
  int a;
  if(n > m){a = n;n = m;m = a;}
  if(m % n == 0){return n;}
  return gcd(m%n,n);
}

int main(){
  int N,i;
  int A[100000],max1,max2;
  scanf("%d",&N);
  for(i = 0;i < N;i++){
    scanf("%d",&A[i]);
  }
  max1 = gcd(A[0],A[1]);
  if(N > 2){max2 = max(gcd(A[0],A[2]),gcd(A[1],A[2]));}else{max2 = max(A[0],A[1]);}
  for(i = 2;i < N;i++){
    max2 = max(gcd(max2,A[i]),max1);
    max1 = gcd(A[i],max1);
  }
  printf("%d\n",max2);
  return 0;
}

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

#[allow(dead_code)]
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)*}
    };
}

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

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

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

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

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

fn main() {
    input!{
        n: usize,
        d: usize,
        xxx: [[isize; d]; n],
    }
    let f = |ls: &Vec<isize>, rs: &Vec<isize>| {
        let v = ls.iter().zip(rs.iter()).map(|(&l, &r)| (l - r) * (l - r)).fold(0, |sum, a| sum + a);
        (v as f64).sqrt()
    };
    let mut cnt = 0;
    for left in 0 .. n - 1 {
        for right in left + 1 .. n {
            let v = f(&xxx[left], &xxx[right]);
            let vi = v.round();
            // println!("v: {}, vi: {}, left: {}, right: {}", v, vi, left, right);
            if v == vi {
                cnt += 1;
            }
        }
    }
    println!("{}", cnt);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(a); ++i)
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */

typedef tuple<ll, ll, ll> T;
// get<K>(tuple型の変数)

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

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

    int ans = 0;
    ans += b[0]+b[n-2];

    for(int i=1; i<=n-2; ++i) ans += min(b[i], b[i-1]);
    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

//ここから

void solve(){
  int a,b;
  cin>>a>>b;
  if(a==1)a+=13;
  if(b==1)b+=13;
  if(a>b)cout<<"Alice";
  else if(a<b)cout<<"Bob";
  else cout<<"Draw";
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


Measured memory_bytes: 384
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class D
{
	public static readonly bool SHEEP = false;
	public static readonly bool WALF = true;

	public static void Main()
	{
		int N = GetInt();
		string s = GetString();

		bool[] ans = new bool[N];
		for(int i = 0; i <= 1; i++)
		{
			for(int j = 0; j <= 1; j++)
			{
				ans[0] = (i == 0);
				ans[1] = (j == 0);
				if(verify(s, N, ref ans))
				{
					for(int k = 0; k < N; k++)
						Console.Write((ans[k] == SHEEP) ? 'S' : 'W');
					Console.WriteLine();
					return;
				}
			}
		}
		Console.WriteLine(-1);
	}

	private static bool verify(string s, int N, ref bool[] ans)
	{
		for(int i = 1; i < N-1; i++)
			ans[i+1] = ans[i-1] ^ (s[i] == 'o') ^ (ans[i] == SHEEP);

		if(((s[N-1] == 'o') ^ (ans[N-1] == SHEEP)) != (ans[N-2] ^ ans[0]))
			return false;

		if(((s[0] == 'o') ^ (ans[0] == SHEEP)) != (ans[N-1] ^ ans[1]))
			return false;

		return true;
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

Measured memory_bytes: 13120
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char x = sc.next().charAt(0);
        char y = sc.next().charAt(0);

        if (x < y) {
            System.out.println("<");
        } else if (x > y) {
            System.out.println(">");
        } else {
            System.out.println("=");
        }
    }

}


Measured memory_bytes: 22100
#include<iostream>

using namespace std;

int main(){
    int N=0, max=0, C[20], V[20];

    cin >> N;

    for(int i=0; i<N; ++i)
      cin >> V[i];

    for(int i=0; i<N; ++i)
      cin >> C[i];

    for(int i=0; i<N; ++i){
        if(C[i] > V[i])
          continue;
        else
          max += V[i] - C[i];
    }

    cout << max << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
/* vector <vector <ll>> v(2e6);
 vector <bool> vis(2e6,false);
 vector <bool> vis2(2e6,false);
 vector <bool> res(2e6,false);
 long long s=0;
  bool flag=true;
void dfs(int x,int n)
{
      vis[x]=true;
      if(x==n-1)
        s++;
    for(int i=0;i<v[x].size()&&flag;i++)
        {
            if(!vis[v[x][i]])
           {
               dfs(v[x][i],n);
           }
           else if(v[x][i]==n-1)
            s++;
        }
}
*/
 
int main()
{
 ll t,n,m,k,x,l,r,i,sum=0,y,sx,sy,ex,ey,ans=0;
cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  for(int i=1;i<n;i++)
   {
     if(arr[i]<arr[i-1])
     {
       ans+=arr[i-1]-arr[i];
       arr[i]=arr[i-1];
     }
  }
  cout<<ans;
}

Measured memory_bytes: 4368
fun main() {
    val n = readLine()!!.toLong()

    val list = mutableListOf<Int>()
    var m = n
    var factor = 2L
    while (factor * factor <= n) {
        var count = 0
        while (m % factor == 0L) {
            m /= factor
            count += 1
        }
        if (count > 0) {
            list.add(count)
        }

        factor += 1
    }
    if (m != 1L) {
        list.add(1)
    }

    val max = list.map { it }.max() ?: 0
    val triangular = (1..max).map {
        it * (it + 1) / 2
    }

    println(list.map { value ->
        val index = triangular.indexOfLast { value >= it }
        if (index == -1) {
            0
        } else {
            index + 1
        }
    }.sum())
}

Measured memory_bytes: 36104
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) cin >> a[i];
  vector<vl> dp(n + 5, vl(3, -1e18));
  int k = n % 2 + 1;
  dp[0][k] = 0;
  rep(i, n) rep(j, 3) {
    if(dp[i][j] == -1e18) continue;
    if(j == 2) dp[i + 2][0] = max(dp[i + 2][0], dp[i][j]);
    if(j >= 1) dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j]);
    dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i]);
  }
  ll ans = -1e18;
  rep2(i, n, n + 2) rep(j, 2) ans = max(ans, dp[i][j]);
  cout << ans << endl;
}

Measured memory_bytes: 15616
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}

P dequeue(){
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}

int min (int a, int b){ return a < b ? a: b;}

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);
  for( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1; tail = n + 1;

  while(head != tail){
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;
    if( u.t > 0) enqueue(u);
    else {
      printf("%s %d\n", u.name, elaps);
    }
  }

  return 0;
}




Measured memory_bytes: 11852
#include <stdio.h>
void solve(char a, char b) {
	char ans;
	if (a == 'H') {
		ans = b;
	}
	else if (b == 'H'){
		ans = 'D';
	}
	else {
		ans = 'H';
	}

	printf("%c\n", ans);
}

int main()
{
	char a, b;
	scanf("%c %c", &a, &b);
	solve(a, b);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
/*******  All Required define Pre-Processors and typedef Constants *******/
#define mem(a, b) memset(a, (b), sizeof(a))
#define rep(i, k) for (int i = 0; i < k; i++)
#define repA(i, a, n) for (int i = a; i <= (n); ++i)
#define repD(i, a, n) for (int i = a; i >= (n); --i)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define INF 1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define LLINF 1e14
#define sz(a) int(a.size())
#define ff first
#define ss second
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vp;
typedef vector<vp> vvp;
 
int main(int argc, char const *argv[])
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        string s, t; cin >> s >> t;
        int ff = 1;
        ll ans = 0;
        int tpos = 0;
        int spos = 0;

        vvi lpos(300, vi(0));
        rep(i, sz(s)){
        	lpos[s[i]].pb(i);
        }	

        while(1){
        	while(tpos < sz(t)){
        		char c = t[tpos];
        		int id = lower_bound(all(lpos[c]), spos) - lpos[c].begin();
        		if(id == sz(lpos[c])) break;
        		// cout << id << " "  << lpos[c][id] << '\n';
        		spos = lpos[c][id] + 1;
        		tpos++;
        	}

        	if(tpos == sz(t)){
        		break;
        	}

        	if(!sz(lpos[t[tpos]])){
        		ff = 0;
        		break;
        	}

        	// cout << "here\n";

        	ans += sz(s);
        	spos = 0;
        }

        cout << (ff == 1 ? ans + spos : -1) << endl;
		return 0;    
}

Measured memory_bytes: 1228
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <utility>
#include <cctype>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#define LL long long
#define LB long double
#define x first
#define y second
#define Pair pair<int,int>
#define pb push_back
#define pf push_front
#define mp make_pair
#define LOWBIT(x) x & (-x)
using namespace std;
 
const int MOD=1e9+7;
const LL LINF=2e17;
const int INF=1e9;
const int magic=348;
const long double eps=1e-15;
const double pi=3.14159265;
 
inline int getint()
{
    char ch;int res;bool f;
    while (!isdigit(ch=getchar()) && ch!='-') {}
    if (ch=='-') f=false,res=0; else f=true,res=ch-'0';
    while (isdigit(ch=getchar())) res=res*10+ch-'0';
    return f?res:-res;
}

int p[1048],n;
int dp[1048],son[1048][5048];
int head[100048],nxt[200048],to[200048],tot=1;
inline void addedge(int s,int t)
{
	to[++tot]=t;nxt[tot]=head[s];head[s]=tot;
}

inline void dfs(int cur)
{
	int i,j,y,cc=0;
	for (i=head[cur];i;i=nxt[i]) dfs(to[i]);
	for (i=head[cur];i;i=nxt[i])
	{
		y=to[i];cc++;
		for (j=0;j<=5000;j++) son[cc][j]=INF;
		for (j=0;j<=5000;j++)
		{
			if (j>=p[y]) son[cc][j]=min(son[cc][j],son[cc-1][j-p[y]]+dp[y]);
			if (j>=dp[y]) son[cc][j]=min(son[cc][j],son[cc-1][j-dp[y]]+p[y]);
		}
	}
	dp[cur]=INF;
	for (i=0;i<=p[cur];i++) dp[cur]=min(dp[cur],son[cc][i]);
}

int main ()
{
	int i,x;n=getint();
	for (i=2;i<=n;i++) x=getint(),addedge(x,i);
	for (i=1;i<=n;i++) p[i]=getint();
	dfs(1);
	if (dp[1]<INF) printf("POSSIBLE\n"); else printf("IMPOSSIBLE\n");
	return 0;
}


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

const int MD = 998244353;
int mod_mult(ll a, ll b) {
	return (a * b) % MD;
}

const int MX = 100005;

int cnt[MX];

int main()
{
	int n;
	ignore = scanf("%d", &n);
	
	for (int i = 1; i <= n; i++) {
		int d;
		ignore = scanf("%d", &d);
		if (i == 1 && d != 0) {
			printf("0\n");
			return 0;
		}
		if (i > 1 && d == 0) {
			printf("0\n");
			return 0;
		}
		
		cnt[d]++;
	}
	
	int ans = 1;
	for (int d = 2; d < n; d++) {
		for (int i = 0; i < cnt[d]; i++) {
			ans = mod_mult(ans, cnt[d - 1]);
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 640
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextUint64() uint64 {
	sc.Scan()
	i, e := strconv.ParseUint(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextFloat64() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	a, b := nextInt(), nextString()
	b2 := strings.ReplaceAll(b, ".", "")
	b3, _ := strconv.Atoi(b2)
	fmt.Println(a * b3 / 100)
}


Measured memory_bytes: 1772
N=int(input())
S=str(input())
x = 0
max_num = 0
for i in range(N):
  if S[i] == 'I': x = x + 1
  if S[i] == 'D': x = x - 1
  if max_num < x:
    max_num = x
print(max_num)

Measured memory_bytes: 2940
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
  
  int x, k;
  rd(x); rd(k);
  auto r=readln.split.to!(int[]);
  int q; rd(q);

  int u=x, l=0;
  int j=0, p=0;
  int d=0, e=-1;
  while(q--){
    int t, a; rd(t, a);
    while(j<k && r[j]<=t){
      int dd=(r[j]-p)*e;
      p=r[j++]; e*=-1;
      u=min(x, max(0, u+dd));
      l=max(0, min(x, l+dd));
      d+=dd;
    }
    int y=a+d;
    y=min(u, max(l, y));
    y+=(t-p)*e;
    writeln(min(x, max(0, y)));
  }

}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}

Measured memory_bytes: 6068
# import functools
N = int(input())
A = list(map(int,input().split()))

Con = 10**18

ans = 1
if A.__contains__(0):
    print(0)
else:
    for i in A:
        if ans <=Con:
            ans*=i
        else:
            break
    print(ans if ans<=Con else "-1")



Measured memory_bytes: 21756
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            Node node = new Node(scanner);
            nodes[node.id] = node;
        }

        for (Node node : nodes) {
            if (node.left != -1)
                nodes[node.left].parent = node.id;
            if (node.right != -1)
                nodes[node.right].parent = node.id;
            if (node.left != -1 && node.right != -1) {
                nodes[node.left].sibling = node.right;
                nodes[node.right].sibling = node.left;
            }
        }
        for (Node node : nodes) {
            int parent = node.parent;
            while (parent != -1) {
                node.depth++;
                parent = nodes[parent].parent;
            }
        }
        for (Node node : nodes)
            node.height = calculateHeight(nodes, node.id);

        for (Node node : nodes)
            print(node);

    }

    private static int calculateHeight(Node[] nodes, int id) {
        int h1 = 0;
        int h2 = 0;
        if (nodes[id].left != -1)
            h1 += calculateHeight(nodes, nodes[id].left) + 1;
        if (nodes[id].right != -1)
            h2 += calculateHeight(nodes, nodes[id].right) + 1;
        return Math.max(h1, h2);
    }

    public static void print(Node node) {
        System.out.println(
               "node " + node.id + ": " +
               "parent = " + node.parent + ", " +
               "sibling = " + node.sibling + ", " +
               "degree = " + node.degree + ", " +
               "depth = " + node.depth + ", " +
               "height = " + node.height + ", " +
               getTypeName(node)
               );
    }

    private static String getTypeName(Node node) {
        if (node.parent == -1) {
            return "root";
        }
        if (node.degree == 0) {
            return "leaf";
        }
        return "internal node";
    }

    private static class Node {
        int id;
        int left;
        int right;
        int parent  = -1;
        int sibling = -1;
        int degree  = 0;
        int depth   = 0;
        int height  = 0;

        Node(Scanner scanner) {
            id    = scanner.nextInt();
            left  = scanner.nextInt();
            right = scanner.nextInt();
            if (left != -1) degree++;
            if (right != -1) degree++;
        }
    }
}



Measured memory_bytes: 26276
S = str(input())
l = [chr(i) for i in range(97,97+26)]

flag = True
for s in l:
  if s not in S:
    ans = S + s
    flag = False
    break
    
if flag:
  if S == 'zyxwvutsrqponmlkjihgfedcba':
    ans = -1
  else:
    while flag:
      num = ord(S[-1])
      S = S[:-1]
      for n in range(num+1, 123):
        if chr(n) not in S:
          ans = S + chr(n)
          flag = False
          break
    
print(ans)

Measured memory_bytes: 9108