akhauriyash/Code-Regression huggingface dataset:
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextLine() int {
	scanner.Scan()
	val, _ := strconv.Atoi(scanner.Text())
	return val
}

func insertionSort(A []int, n int, g int, cnt int) ([]int, int) {
	for i := 0; i < n; i++ {
		v := A[i]
		j := i - g
		for j >= 0 && A[j] > v {
			A[j+g] = A[j]
			j = j - g
			cnt++
		}
		A[j+g] = v
	}
	return A, cnt
}

func shellSort(A []int, n int) {
	G := makeGSlice(len(A))
	sort.Sort(sort.Reverse(sort.IntSlice(G)))
	m := len(G)
	cnt := 0
	for i := 0; i < m; i++ {
		A, cnt = insertionSort(A, n, G[i], cnt)
	}

	fmt.Println(m)
	printG(G)
	fmt.Println(cnt)
	printA(A)
}

func makeGSlice(m int) []int {
	h := 1
	var G []int
	for h <= m {
		G = append(G, h)
		h = 3*h + 1
	}
	return G
}

func printG(G []int) {
	for i := 0; i < len(G); i++ {
		if i > 0 {
			fmt.Printf(" ")
		}
		fmt.Printf("%d", G[i])
	}
	fmt.Printf("\n")
}

func printA(A []int) {
	for i := 0; i < len(A); i++ {
		fmt.Printf("%d\n", A[i])
	}
}

func main() {
	n := nextLine()

	A := make([]int, n)
	for i := 0; i < n; i++ {
		A[i] = nextLine()
	}

	shellSort(A, n)
}



Measured memory_bytes: 17448
n,m=map(int,input().split())
mod=10**9+7
a=[False]*(n+1)
for i in range(m):
  a[int(input())]=True
fib=[0]*(n+1)
fib[0]=1
fib[1]=[1,0][a[1]]
for i in range(2,n+1):
  if a[i]:
    fib[i]=0
  else:
    fib[i]=(fib[i-1]+fib[i-2])%mod
print(fib[n])

Measured memory_bytes: 44888
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cstdlib>
#define rep(i,n) for(int i = 0;i<(n);i++);
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 10010010010;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll gcd(ll a, ll b) {//a>b
	if (a < b)swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}
int main() {
	ll N;
	cin >> N;
	map<ll, ll> hito;
	ll n = 0;
	for (int i = 0; i < N; i++)hito[i + 1] = 0;
	for (int i = 0; i < N - 1; i++) {
		cin >> n;
		hito[n]++;
	}
	for (auto x : hito) {
		cout << x.second << endl;
	}
}

Measured memory_bytes: 16064
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

int main(){
    int h, w;
    cin >> h >> w;
	vector<string> s(h);
    for (int i = 0; i < h; i++){
		cin >> s[i];
    }
	
    const int dx[4] = { 0, 0, 1, -1 };
    const int dy[4] = { 1, -1, 0, 0 };

    for (int i = 0; i < h; i++){
        for (int k = 0; k < w; k++){
            if (s[i][k] != '#'){
                continue;
            }
            bool found = false;
            for (int p = 0; p < 4; p++){
                const int x = k + dx[p];
                const int y = i + dy[p];
                if (x >= 0 && x < w && y >= 0 && y < h){
                    if (s[y][x] == '#'){
                        found = true;
                    }
                }
            }
            if (!found){
                cout << "No" << endl;
				return 0;
            }
        }
    }

	cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 256
def popcnt_int(n): # n:int
    return bin(n).count('1')

def popcnt_bin(s): # s:str
    return s.count('1')

def poptimes(n, cnt=1): #:int
    if n==0:
        return cnt
    else:
        n %= popcnt_int(n)
        cnt += 1
        return poptimes(n, cnt)

n = int(input())
s = input()

s_int = int(s,2)
pc = popcnt_bin(s)
pc_plus = s_int % (pc+1)
if  pc != 1:
    pc_minus = s_int % (pc-1)
#print(n,s,s_int,pc,pc_plus,pc_minus)

for i in range(n):
    if s[i] == '1':
        if pc != 1:
            tmp = pc_minus - pow(2, n-i-1, pc-1)
            print(poptimes(tmp % (pc-1)))
        else:
            print(0)
            continue
    
    else:
        tmp = pc_plus + pow(2, n-i-1, pc+1)
        print(poptimes(tmp % (pc+1)))


Measured memory_bytes: 9376
#include <iostream>
#include <vector>

int main(int argc, char const* argv[])
{
  while (true) {
    int N, M, P;
    std::cin >> N >> M >> P;
    if (N == 0 && M == 0 && P == 0)
      break;
    std::vector<int> X(N);
    double pool = 0.0;
    for (int i = 0; i < N; ++i) {
      std::cin >> X[i];
      pool += X[i] * 100;
    }
    if (X[M - 1] == 0) {
      std::cout << 0 << std::endl;
    } else {
      double for_divide = pool - ((double)P / 100.0) * pool;
      std::cout << (int)(for_divide / X[M - 1]) << std::endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1196
package main

import (
	"fmt"
	"sort"
)

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	result := []int{a, b, c}

	sort.Sort(sort.IntSlice(result))

	fmt.Println(result[0], result[1], result[2])
}



Measured memory_bytes: 1176
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a,b;
	cin >> a >> b;
	if((a+b)%3==0 || a%3==0 || b%3==0)	cout << "Possible" << endl;
	else				cout << "Impossible" << endl;
	return 0;
}

Measured memory_bytes: 256
/* package codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		int m=s.nextInt();
		long ans=0;
		if(n==1 && m==1)
		{ans=1000000;}
		else
		{int a=Math.min(n,m);
		int b=Math.max(n,m);
		if(n==1)
		ans+=300000;
		if(n==2)
		ans+=200000;
		if(n==3)
		ans+=100000;
		if(m==1)
		ans+=300000;
		if(m==2)
		ans+=200000;
		if(m==3)
		ans+=100000;
	}
	System.out.println(ans);
}
}

Measured memory_bytes: 21844
s = input(); t = input()
dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
res = ''
i = len(s); j = len(t)
while (i>0) & (j>0):
  if dp[i][j] == dp[i-1][j]: i += -1
  elif dp[i][j] == dp[i][j-1]: j += -1
  else: res = s[i-1] + res; i += -1; j += -1
print(res)
    

Measured memory_bytes: 121436
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using psi=pair<string,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
template<class T>void geti(T&a){for(auto&_:a)cin>>_;}
template<class T>void getii(T&a){for(auto&_:a)geti(_);}
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}
#define dcl(...) ll __VA_ARGS__;get(__VA_ARGS__)
#define dclt(t,...) t __VA_ARGS__;get(__VA_ARGS__)

 
constexpr int gcd(int a,int b){return b?gcd(b,a%b):a;}
constexpr int lcm(int a,int b){return a*b/gcd(a,b);}


int main(){
	dclt(string,s);
	cout<<(count(all(s),'g')-count(all(s),'p'))/2<<endl;
	
}


Measured memory_bytes: 512
// https://atcoder.jp/contests/abc122/tasks/abc122_a
package main

import "fmt"

func main() {
	var s string
	fmt.Scanf("%s", &s)

	pairs := map[byte]byte{
		'A': 'T',
		'T': 'A',
		'C': 'G',
		'G': 'C',
	}

	for _, c := range []byte(s) {
		fmt.Printf("%c", pairs[c])
	}
	fmt.Println()
}


Measured memory_bytes: 512
n,x = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

count = 0

for i in 0 .. n-2
	if a[i] + a[i+1] > x
		dist = a[i] + a[i+1] - x
		if a[i+1] < dist
			a[i] -= dist - a[i+1]
			a[i+1] = 0
			count += dist
		else
			a[i+1] -= dist
			count += dist
		end
	end
end

puts count

Measured memory_bytes: 8588
#include<cstdio>
#include<cmath>
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2e5 + 5, M = 26;
const int Mod = 1e9 + 7;
int Trie[N][M], d[N], val[N], dp[N], f[N], q[N];
int n, len, root, tot;
char s[N];
struct E{int next, to;} edge[N << 1];
int head[N], nedge;
inline int addline(int x, int y){
	edge[++ nedge].next = head[x];
	edge[nedge].to = y;
	head[x] = nedge;

}
int Dfs(int u, int Last){
	f[u] = Last;
	int tmp = Last;
	if (val[u]) tmp = u;
	for (int i = head[u]; i; i = edge[i].next)
		Dfs(edge[i].to, tmp);
}
int Insert(int &u, int dep){
	if (!u) u = ++ tot;
	//printf("%d %d\n",dep,u);
	d[u] = dep;
	//if (dep > 10) return 0;
	if (dep - 1 == len){
		val[u] ++;
		return 0;
	}
	Insert(Trie[u][s[dep] - 97], dep + 1);
}
int Getans(int u, int l){
	if (u == root) return 0;
	//printf("%d %d %d %d\n",u, d[u] - 1, val[u], l);
	dp[l] = (dp[l] + 1ll * val[u] * dp[l - d[u] + 1] % Mod) % Mod;
//	printf("Res:%d %d %d %d\n",dp[1], dp[2], dp[3], dp[4]);
	Getans(f[u], l);
}
int Query(int u, int l){
	//printf("Query:%d %d\n",u,l);
	Getans(u, l);
	if (l == len) return 0;
	Query(Trie[u][s[l + 1] - 97], l + 1);
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%s", s + 1);
		len = strlen(s + 1);
		Insert(root, 1);
	}
	int l = 1, r = 0;
	for (int i = 0; i < M; i++)
		if (Trie[root][i]){
			f[Trie[root][i]] = root;
			q[++r] = Trie[root][i];
		}
		else
			Trie[root][i] = root;
	while (l <= r){
		int u = q[l];
		l ++;
		for (int i = 0; i < M; i++)
			if (Trie[u][i]){
				f[Trie[u][i]] = Trie[f[u]][i];
				q[++ r] = Trie[u][i];
			}
			else
				Trie[u][i] = Trie[f[u]][i];
	}
	//for (int i = 1; i <= tot; i++)
	//	printf("%d ",f[i]);
	//printf("\n");
	//return 0;
	//Dfs(root, root);
	for (int i = 2; i <= tot; i++)
		addline(f[i], i);
	Dfs(1, 1);
	scanf("%s", s + 1);
	len = strlen(s + 1);
	dp[0] = 1;
	Query(root, 0);
	printf("%d\n", dp[len]);
}


Measured memory_bytes: 29412
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		BufferedReader inMsg = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		try {
			while ((line = inMsg.readLine()) != null) {
				Integer totalSecs = Integer.parseInt(line);
				Integer hours = totalSecs / 3600;
				Integer minute = (totalSecs % 3600) / 60;
				Integer sec = totalSecs % 60;
				String tString = String.format("%d:%d:%d", hours, minute, sec);
				
				System.out.println(tString);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

Measured memory_bytes: 24508
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a,b;
        String op;
        while (true) {
            a = sc.nextInt();
            op = sc.next();
            b = sc.nextInt();
            if (op.equals("+")) {
                System.out.println(a + b);
            } else if (op.equals("-")) {
                System.out.println(a - b);
            } else if (op.equals("*")) {
                System.out.println(a * b);
            } else if (op.equals("/")) {
                System.out.println(a / b);
            } else {
                sc.close();
                break;
            }
        }
    }
}


Measured memory_bytes: 26240
// clang-format off
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;

#define DEB(variable) cout << #variable << '=' << variable << endl

#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

using llint = long long int;

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr long long int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;
// clang-format on

int main() {
    string s;
    cin >> s;
    llint d;
    cin >> d;
    llint n = s.size();
    vector<vector<vector<llint>>> dp(n + 1, vector<vector<llint>>(2, vector<llint>(d, 0)));
    for(auto x = 0; x <= (int)(s[0] - '0'); x++) {
        dp[0][(x !=(s[0] - '0')? 1 : 0)][x % d] += 1;
    }
    FOR(i, 1, n) {
        REP(smaller, 2) {
            REP(k, d) {
                REP(l, (smaller ?( 9+1) : (1+(int)(s[i] - '0')))) { 
                    dp[i][smaller || l < (int)(s[i] - '0')][(k + l) % d] += dp[i-1][smaller][k];
                    dp[i][smaller || l < (int)(s[i] - '0')][(k + l) % d] %= mod;
                }
            }
        }
    }
    llint result = (mod+dp[n - 1][0][0] + dp[n - 1][1][0] - 1) % mod;
    cout << result << endl;
    return 0;
}


Measured memory_bytes: 17024
import java.util.Scanner;

public class Main {
    // TODO solve
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final long t1 = scanner.nextInt();
        final long t2 = scanner.nextInt();
        final long tmp1 = scanner.nextLong();
        final long tmp2 = scanner.nextLong();
        final long tmp3 = scanner.nextLong();
        final long tmp4 = scanner.nextLong();

        final long a1;
        final long a2;
        final long b1;
        final long b2;
        if (tmp1 > tmp3) {
            a1 = tmp1;
            a2 = tmp2;
            b1 = tmp3;
            b2 = tmp4;
        } else {
            b1 = tmp1;
            b2 = tmp2;
            a1 = tmp3;
            a2 = tmp4;
        }

        final long distanceInT1 = (a1 - b1) * t1;
        final long distanceInT2 = b2 * t2 + b1 * t1 - (a2 * t2 + a1 * t1);
        if (distanceInT2 == 0) {
            System.out.println("infinity");
            return;
        }
        if (distanceInT2 < 0) {
            System.out.println(0);
            return;
        }
        if (distanceInT1 < distanceInT2) {
            System.out.println(1);
            return;
        }
        if (distanceInT1 % distanceInT2 == 0) {
            System.out.println(2 * (distanceInT1 / distanceInT2));
            return;
        }
        System.out.println(1 + 2 * (distanceInT1 / distanceInT2));
    }
}


Measured memory_bytes: 21844
import queue

H, W = map(int,input().split())

#[y][x]
a = [list(input()) for i in range(H)]
mod = 10**9 + 7

#[y][x]
dp = [[0 for _ in range(W)] for _ in range(H)]

#y
for i in range(H):
    #x
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0 and j == 1:
            if a[i][j] != "#":
                dp[i][j] = 1
            continue
        if i == 1 and j == 0:
            if a[i][j] != "#":
                dp[i][j] = 1
            continue

        if a[i][j] == "#":
            dp[i][j] = 0
        else:
            if i == 0:
                dp[i][j] = dp[i][j-1]
            elif j == 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

print(dp[H-1][W-1] % mod)

Measured memory_bytes: 167132
import std.stdio;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;
 
void main() {
    int N; readf("%d\n", &N);
    string s = readln.chomp;
    static const int C = 10007;
    int[char] m = ['J': 0, 'O': 1, 'I': 2];

    int cache[8][1001];
    memset(cast(void*)cache, -1, cache.sizeof);
    int dfs(int p, int n) {
        if (n == N) return 1;
        if (cache[p][n] >= 0) return cache[p][n];
        int ret = 0;
        for (int i = 1; i <= 7; i++) {
            if ((i & p) && (i & (1 << m[s[n]]))) {
                ret = (ret + dfs(i, n + 1)) % C;
            }
        }
        return cache[p][n] = ret;
    }

    dfs(1, 0).writeln;
}

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

int pon(int n) {
  if(n == 1) {
    return 1;
  } else {
    return n + pon(n - 1);
  }
}

int main() {
  int a, b;
  cin >> a >> b;
  int zu = b - a;
  cout << pon(zu) - b << endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class B {
    static StreamWriter Out = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    static void Main(string[] args) {
        string S;
        Input(out S);
        if(S.Length == 1) {
            Console.WriteLine(int.Parse(S));
        } else {
            bool isComplete = true;
            for(int i = 1; i < S.Length; i++) {
                if(S[i] != '9') {
                    isComplete = false;
                }
            }
            if(isComplete) {
                Console.WriteLine(int.Parse(S[0].ToString()) + 9 * (S.Length - 1));
            } else {
                Console.WriteLine(int.Parse(S[0].ToString()) - 1 + 9 * (S.Length - 1));
            }
        }
        
        Out.Flush();
    }
    static T ChangeT<T>(string s) => (T)Convert.ChangeType(s, typeof(T));
    static void Input<A>(out A a) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
    }
    static void Input<A, B>(out A a, out B b) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
    }
    static void Input<A, B, C>(out A a, out B b, out C c) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
    }
    static void Input<A, B, C, D>(out A a, out B b, out C c, out D d) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
    }
    static void Input<A, B, C, D, E>(out A a, out B b, out C c, out D d, out E e) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
    }
    static void Input<A, B, C, D, E, F>(out A a, out B b, out C c, out D d, out E e, out F f) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
        f = ChangeT<F>(words[5]);
    }
    static void Inputs<T>(out T[] array) {
        array = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries).Select(s => ChangeT<T>(s)).ToArray();
    }
    static void Print<T>(T s) => Out.WriteLine(s);
    static void Print<T>(params T[] s) => Out.WriteLine(string.Join(" ", s));
    static void Print<T>(IEnumerable<T> e) => Out.WriteLine(string.Join(" ", e));
}

Measured memory_bytes: 13268
/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

const ll MAX_N = 400;
ll N;
ll a[MAX_N];
ll dp[MAX_N+1][MAX_N+1]; // dp[l][r]
 
// // i番目以降の品物から重さの総和がj以下になるように選ぶ
void rec(ll l, ll r){
	if (dp[l][r]!=-1) return;
	else{
		if (r-l==0) dp[l][r] = 0;
		else if (r-l==1) dp[l][r] = a[l] + a[r];
		else{
		ll tmp = INF;
			for (ll i = l; i < r; ++i){ // [l-r)-> [l-i)+[i+1-l]
				rec(l, i);
				rec(i+1, r);
				tmp = min(tmp, dp[l][i] + dp[i+1][r]);
			}
		for (ll i = l; i <= r; ++i) tmp += a[i];
		dp[l][r] = tmp;
		}
		// printf("%lld - %lld: %lld\n", l, r, dp[l][r]);
	}
	return;
}
 
 
int main() {
	// 入力
	cin >> N;
	for (ll i = 0; i < N; ++i) cin >> a[i];
 
	// 解法
	// DP
	memset(dp, -1, sizeof(dp));
	rec(0, N-1);

	//出力
	cout << dp[0][N-1] << endl;
}


Measured memory_bytes: 1536
#include<stdio.h>
#include<limits.h>
long long abs(long long n){
	if(n>=0) return n;
	else return -n;
}
int main(){
	int A[200010],n,i,t;
	long long sum,x,min,a;
  		sum=0;
  		x=0;
  		min=LLONG_MAX;
	  	scanf("%d",&n);
	      for(i=1;i<=n;i++){
	         	scanf("%d",&A[i]);
	         	sum+=A[i];
	      }
	      for(i=1;i<=n-1;i++){
	      	x+=A[i];
	      	a=abs(sum-2*x );
	      	if(a<min) min=a;
	      }
	      printf("%lld\n",min);
	return 0;
}

Measured memory_bytes: 896
import sys
input = sys.stdin.readline

n = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


cnt = 0

for i in range(1, n+1, 2):
    if len(make_divisors(i)) == 8:
        cnt += 1

print(cnt)

Measured memory_bytes: 3064
#include <stdio.h>

int main() {
    int n,u,k,v,i,j;
    
    scanf("%d",&n);
    
    int Adj[n+1][n+1];
    
    for(i=1; i<n+1; i++) {
        for(j=1; j<n+1; j++) {
            Adj[i][j] = 0;
        }
    }
    
    for(i=1; i<n+1; i++) {
        scanf("%d",&u);
        scanf("%d",&k);
        
        for(j=1; j<k+1; j++) {
            scanf("%d",&v);
            Adj[u][v] = 1;
        }
    }
    
    for(i=1; i<n+1; i++) {
        for(j=1; j<n+1; j++) {
            if(j==n) printf("%d\n",Adj[i][j]);
            else printf("%d ",Adj[i][j]);
        }
    }
    
    return 0;
}

Measured memory_bytes: 632
N, X, M = map(int,input().split())
if N==1:
  print(X)
  exit()
a = [X]
sa = set([X])
for i in range(1,N):
  X = (X**2)%M
  if X in sa:
    break
  else:
    a.append(X)
    sa.add(X)

if i==N-1:
  print(sum(a))
  exit()
start = a.index(X)
ans = sum(a[:start])
base = sum(a[start:])
rep = i-start
sets = (N-start)//rep
more = (N-start)%rep
ans += base*sets + sum(a[start:start+more])
print(ans)

Measured memory_bytes: 13652
#include <iostream>
#include <cstring>

using namespace std;

static constexpr long long MOD = 1000000000 + 7;
static long long C[2001][2001];

static long long nCr(int n, int r) {
    if (n == r) {
	return 1;
    }
    if (r == 1) {
	return n;
    }
    if (n < r || n < 0 || r < 0) {
	return 0;
    }
    if (C[n][r] != -1) {
	return C[n][r];
    }
    return C[n][r] = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % MOD;
}

int main()
{
    int N, K;
    cin >> N >> K;
    memset(C, -1, sizeof(C));
    for (int i = 1; i <= K; i++) {
	cout << (nCr(N - K + 1, i) * nCr(K - 1, i - 1)) % MOD << endl;
    }
    return 0;
}


Measured memory_bytes: 31616
import sys
from collections import defaultdict
from queue import Queue

def main():
    # n = int(input())

    n, m = [int(s) for s in input().split()]

    # edge = defaultdict(bool)

    # あるノードと接続しているノード一覧
    edge_to_k = defaultdict(set)

    for i in range(m):
        a, b = [int(s) for s in input().split()]
        # edge[(a, b)] = True
        # edge[(b, a)] = True

        edge_to_k[a].add(b)
        edge_to_k[b].add(a)

    # 道しるべ
    ans = {}
    ans[1] = 1 # 便宜的

    queue = Queue()
    queue.put(1)

    while(not queue.empty()):
        to_node = queue.get()

        # 取り出した部屋につながる部屋にもし道しるべが付いていない場合、道しるべを付ける
        for k in edge_to_k[to_node]:
            if k not in ans:
                sys.stderr.write('on {}. put {}\n'.format(to_node, k))
                queue.put(k)
                ans[k] = to_node

    print('Yes')
    for i in range(2, n+1):
        print(ans[i])

    return 0

if __name__ == '__main__':
    sys.exit(main())


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

#define f first
#define s second
#define ll long long
#define pb push_back
#define mp make_pair
#define inp(x) cin>>x
#define print(x) cout<<x
#define pii pair<int,int>
#define pll pair<ll,ll>
#define gcd(a,b) __gcd(a,b)
#define reset(d,val) memset(d,val,sizeof(d))
#define sort(v) sort(v.begin(),v.end())
#define sort_arr(arr,i,f) sort(arr+i,arr+f)
#define pq priority_queue<int,vector<int>,greater<int> >
#define pq1 priority_queue<pll,vector<pll>,greater<pll> >

const int mod = 1e9+7;

std::map<int, std::vector<int> >adjlist;
int ans = 0;
int vis[100005],in[100005],out[100005],dp[100005];
std::vector<int>topsort;
int n,m;

void dfs() {
	queue<int>q;
	for (int i = 1; i <=n; ++i)
	{
		if(in[i]==0) q.push(i);
	}
	while(!q.empty()){
		int x = q.front();
		topsort.pb(x);
		q.pop();
		for(int i=0;i<adjlist[x].size();i++){
			in[adjlist[x][i]]--;
			if(in[adjlist[x][i]]==0) q.push(adjlist[x][i]);
		}
	}
}

int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	int u,v;
	memset(vis,0,sizeof(vis));
	for (int i = 0; i < m; ++i)
	{
		cin>>u>>v;
		adjlist[u].pb(v);
		in[v]++;
		out[u]++;
	}
	dfs();
	for (int i = topsort.size()-1; i>=0 ; i--)
	{
		for(int j=0;j<adjlist[topsort[i]].size();j++){
			dp[topsort[i]] = max(dp[topsort[i]],1+dp[adjlist[topsort[i]][j]]);
		}
	}
	for (int i = 1; i <=n; ++i)
	{
		ans = max(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 13304
N, K, Q = tuple(map(int, input().split()))
A = [int(input()) for _ in range(Q)]
points = [0] * N
for a in A:
    points[a-1] += 1
for p in points:
    if K - (Q - p) > 0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 8592
#include <bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define FOD(i,a,b) for(int i=a; i>=b; i--)
#define pa pair<int,int>
#define fi first
#define se second
#define MOD xxx
#define getbit(n,i) ((n>>(i-1))&1)
#define offbit(n,i) ((n^(1<<(i-1))
#define onbit(n,i) (n|(1<<(i-1)))
#define cntone(x) (__builtin_popcount(x))

using namespace std;
int a,b,c;
int main()
{
    cin >> a >> b >> c;
    if(a+b+c>=22) cout << "bust";
    else cout << "win";
	return 0;
}


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

int main() {
  int N, W;
  cin >> N >> W;
  vector<int> v(N), w(N);
  for (int i = 0; i < N; i++)
    cin >> v[i] >> w[i];

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


Measured memory_bytes: 6828
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(n,v) cout<<#v<<":";for(int i=0;i<n;i++)cout<<v[i]<<" ";cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/*考察
1回の操作で今の数以下Aiの倍数になるから単調性はあるわけで、
小さいほうの値は愚直に求まる
大きいほうの値はそこからニブタンすればいいと思いました
 */

int k;
vector<ll> a;
ll m=2,M=-1;
void solve(ll l,ll r){
    if(l>r) return;
    ll mid=(l+r)/2;
    ll hito=mid;
    for(int i=0;i<k;i++){
        hito-=hito%a[i];
    }
    if(hito==2){
        M=max(mid,M);
        solve(mid+1,r);
    }
    else{
        solve(l,mid-1);
    }
}

int main(){
    cin>>k;
    a.resize(k);
    rep(i,k) cin>>a[i];
    for(int i=k-1;i>=0;i--){
        ll y=(m+a[i]-1)/a[i];
        m=y*a[i];
    }
    solve(m,LINF);
    if(M<0) cout<<-1<<endl;
    else cout<<m<<' '<<M<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(){
    string S;
    cin >> S;
    int a = 0, b = 0, c = 0;
    for(int i = 0; i < S.size(); i++){
        if(S[i] == 'a') a++;
        if(S[i] == 'b') b++;
        if(S[i] == 'c') c++;
    }
    if(max(a, max(b, c)) - min(a, min(b, c)) >= 2) cout << "NO" << endl;
    else cout << "YES" << endl;
}

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


int main()
{
    string number;
    cin >> number;
    cout << count(ALL(number), '1') << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
#include <fstream>
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (1 << 30);
const ll inf = (1LL << 60LL);
const int  maxn = 1e7 + 5;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    ll A, B, C;
    cin >> A >> B >> C;
    ll ret = 0;
    ll sum = A + B;
    ret += min(C, sum);
    ret += B;
    if(C > A + B){
        ret ++;
    }
    cout << ret << endl;
    return 0;
    if(A + B < C){
        ll p = C - A - B;
        C -= p;
//        cout << p << endl;
        C += B + 1;
        cout << C;
    }
    else if(A + B == C){
        cout << C + B << endl;
    }
    else{
        cout << A + C << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>
#include <utility>
#include <sstream>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) x.begin(),x.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

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

    vector<ll>A(N);

    for(ll i = 0;i < N;i++)
        cin >> A.at(i);

    ll ans = 0;

    for(ll i = 0;i < N;i++){
        ans += A.at(i) - 1;
    }

    cout << ans << endl;


}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
typedef vector <int> vi;
typedef double ld;
#define X first
#define Y second
#define mk make_pair
#define pb push_back
#define Rep(i, n) for(int i = 0; i < int(n); i ++)
#define Rep1(i, n) for(int i = 1; i <= int(n); i ++)
#define all(x) (x).begin(), (x).end()
const int MOD = (int) 1e9 + 7;
const int base = 31;
void MAIN();
int main(){
    //freopen("input.txt", "r", stdin);
    ios:: sync_with_stdio(false); cin.tie(0);
    MAIN();
    return 0;
}
////////////////////////////////////////////////////////////////////////

const int N = 1 << 12;

int n, m, h;
vector <ii> G[N];
int d[N];

void MAIN(){
    cin >> n >> m >> h;
    Rep1(i, m){
        int u, v, c;
        cin >> u >> v >> c;
        G[u].pb(ii(v, c));
        G[v].pb(ii(u, c));
    }
    int ans = 0;
    priority_queue <ii> q;
    memset(d, 0x3f, sizeof d);
    while(h --){
        int u;
        cin >> u;
        d[u] = 0;
        q.push(ii(-d[u], u));
    }
    while(!q.empty()){
        int u = q.top().Y, r = -q.top().X; q.pop();
        if(d[u] != r) continue;
        ans = d[u];
        Rep(i, G[u].size()){
            int v = G[u][i].X, c = G[u][i].Y;
            if(d[v] > d[u] + c){
                d[v] = d[u] + c;
                q.push(ii(-d[v], v));
            }
        }
    }
    Rep1(u, n) Rep(i, G[u].size()){
        int v = G[u][i].X, c = G[u][i].Y;
        if(abs(d[u] - d[v]) <= c) ans = max(ans, (d[u] + d[v] + c + 1) / 2);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4236
#include<bits/stdc++.h>
#define fastio     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x)   cerr<<#x<<": "<<x<<endl;
#define all(x)     (x).begin() , (x).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl       '\n'
#define MAX        1000000
typedef long long int ll;
using namespace std;


const ll mod = 1e9+7;
const double eps = 1e-9;




void solve(){
    int h,n;
    cin>>h>>n;
    int tt=0;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        tt+=t;
    }
    cout<< ((tt>=h) ? "Yes" : "No") << endl;
}





int main(){
    fastio
    int test=1;
    while(test--)
        solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vll vector <ll>
#define vvi vector <vector <int> >
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 5e5+100;
const ll INF = 1e9;
const ll kek=998244353;
const ll mod1=1e9+7;
const ll mod2=2e9+11;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    bool ok=true;
    int i=0;
    if (n%2!=0)
        cout<<"No";
    else
    {
        while (i<n/2&&s[i]==s[i+n/2])
            i++;
        if (i==n/2)
            cout<<"Yes";
        else
            cout<<"No";
    }}

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

using namespace std;

int main(int argc, char const *argv[]) {
	int n;
	std::cin >> n;
	int count = 0;
	for (size_t i = 0; i < n; i++) {
		int a,b;
		std::cin >> a >> b;
		count += (b-a+1);
	}
	std::cout << count << '\n';
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<ll> a(n+1), b(n);
    rep(i,n+1) cin >> a[i];
    rep(i,n) cin >> b[i];

    ll carry = 0, ans = 0;
    rep(i,n){
        if(a[i] < b[i]){
            ans += a[i];
            carry = b[i] - a[i];
            if(carry > a[i+1]){
                ans += a[i+1];
                a[i+1] = 0;
            }
            else{
                ans += carry;
                a[i+1] = a[i+1] - carry;
            }
        }
        else{
            ans += b[i];
            carry = 0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
s = S()
ans = 0
rem = 0
if p == 2 or p == 5:
    for i in range(n - 1, -1, -1):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()


k = 1
for i in range(n - 1, -1, -1):
    d = int(s[i])
    rem = (k * d + rem) % p
    k = k * 10 % p
    ans += D[rem]
    D[rem] += 1


print(ans)


Measured memory_bytes: 44488
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	int n,m;
	cin >> n >> m;
	int l=0,r=1e9;
	for (int i=0; i<m; i++){
		int x,y;
		cin >> x >> y;
		if (l<x) l=x;
		if (r>y) r=y;
	}
	if (r-l<0) cout << 0;
	else cout << r-l+1;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
const int MOD=1000000007;

//コンビネーションを10^9+7で割った余りを求める
const int MAX = 1000000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    int n;
    cin>>n;
    COMinit();
    string s;
    cin>>s;
    vector<int> alp(26);
    map<int,int> p;
    rep(i,n){
        alp[s[i]-'a']++;
    }
    int exist=0;
    rep(i,26){
        if(alp[i]>=1){
            exist++;
        }
        //cout<<alp[i]<<" ";
        p[alp[i]]++;
    }
    //cout<<endl;
    int64_t ans=1;
    rep(i,26){
        ans *= (alp[i]+1);
        ans %=MOD;
    }
    cout<<(ans%MOD)-1<<endl;
}

Measured memory_bytes: 23936
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <set>
#include <chrono>
#include <queue>
#include <string>
#include <cassert>
#include <bitset>
#include <stack> 

#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define BASE 77747
#define PI acos(-1.0)
#define MAXLEN 29

using namespace std;

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

double dp[301][301][301];
int n;
int arr[4];

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d", &n);
	for (int i = 0; i < 4; i++) arr[i] = 0;
	for (int i = 0; i < n; i++) {
		int tt;
		scanf("%d", &tt);
		arr[tt]++;
	}
	for (int i = 0; i <= arr[3]; i++) {
		for (int j = 0; j <= arr[2] + arr[3]; j++) {
			for (int k = 0; k <= arr[1] + arr[2] + arr[3]; k++) {
				if (i == 0 && j == 0 && k == 0) {
					dp[i][j][k] = 0;
					continue;
				}
				double ss = 0;
				if (i > 0) 
					ss += i * 1.0 / n * dp[i - 1][j + 1][k];
				if (j > 0)
					ss += j * 1.0 / n * dp[i][j - 1][k + 1];
				if (k > 0)
					ss += k * 1.0 / n * dp[i][j][k - 1];
				dp[i][j][k] = (ss + 1) * n / (i + j + k);
			}
		}
	}
	printf("%.11f\n", dp[arr[3]][arr[2]][arr[1]]);
	return 0;
}

Measured memory_bytes: 213248
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <string>
#include <cstring>
#include <numeric>
#include <iomanip>
using namespace std;
//
const int inf=1e9+7;//0x3f
//
struct BIT{
	//
	int size=1;
	vector<int> node;
	//セグ木を構築
	BIT(int n){
		while(size<n){
			size<<=1;
		}
		node.resize(size+1,0);
	}
	//k番目の値にa加算
	void add(int k,int a){
		k++;
		while(k<=size){
			node[k]+=a;
			k+=k&-k;
		}
	}
	//[0,k)の範囲内の区間和を求める
	int query(int k){
		int res=0;
		while(k){
			res+=node[k];
			k-=k&-k;
		}
		return res;
	}
	//
};
int main(){
	long long N,K;
	cin>>N>>K;
	vector<long long> A(N+1),a(N+1);
	A[0]=0LL;
	for(int i=1;i<N+1;i++){
		cin>>A[i];
		A[i]-=K;
		A[i]+=A[i-1];
	}
	a=A;
	sort(A.begin(),A.end());
	A.erase(unique(A.begin(),A.end()),A.end());
	BIT bit((int)A.size());
	long long ans=0;
	for(int i=0;i<N+1;i++){
		int idx=lower_bound(A.begin(),A.end(),a[i])-A.begin();
		ans+=bit.query(idx+1);
		bit.add(idx,1);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<vector>

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

using namespace std;

const int INF = 10000;

int main()
{
	
	int n;

	cin >> n;

	vector<int> V;
	rep(i, n) {
		int t;
		cin >> t;
		V.push_back(t);
	}

	int maxV = V[0], minV = V[0];
	p sum = 0;
	rep(i, n) {
		maxV = max(maxV, V[i]);
		minV = min(minV, V[i]);
		sum += V[i];
	}

	cout << minV << " " << maxV << " " << sum << endl;

	return 0;
}



Measured memory_bytes: 3272
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <cmath>
#include <functional>

typedef long long ll;
using namespace std;


int main(){
    ll n, d;
    cin >> n >> d;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        if(a*a + b*b <= d*d) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793




int main(){
    int n;
    cin >> n;
    int ans=(n-1)/2;
    cout << ans << endl;
}

Measured memory_bytes: 3640
package main

import "fmt"

func main() {
	xs := make([]int, 3)
	var max, sum int
	for i := range xs {
		fmt.Scan(&xs[i])
		sum += xs[i]
		if xs[i] > max {
			max = xs[i]
		}
	}
	fmt.Println(sum - max)
}


Measured memory_bytes: 512
n, t = map(int, input().split())
def f(i, j):
    return 60*j[0]+j[1]-60*i[0]-i[1]
res = []
tmp = input().split()
name, bef = tmp[3], list(map(int, tmp[2].split(":")))
for i in range(n-1):
    tmp = input().split()
    aft = list(map(int, tmp[0].split(":")))
    tim = f(bef, aft)
    if tim >= t : res.append([name, str(tim)])
    name, bef = tmp[3], list(map(int, tmp[2].split(":")))
print(len(res))
if len(res) != 0 : print("\n".join([" ".join(x) for x in res]))


Measured memory_bytes: 5612
#include<iostream>

using namespace std;

int main() {
	int n, i, j, q;
	int a[10000], b[500];
	int count = 0;
	cin >> n;
	for (i = 0;i < n;++i)cin >> a[i];
	cin >> q;
	for (i = 0;i < q;++i)cin >> b[i];
	for (i = 0;i < q;++i) {
		for (j = 0;j < n;++j) {
			if (b[i] == a[j]) { 
			++count;
			break;
			}
		}
	}
	cout << count << endl;
	return 0;
}



Measured memory_bytes: 3100
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Program{
  static void Main(){
    var n = int.Parse(ReadLine());
    var result = 0;
    
    if(n % 2 != 0){
    	result +=1;
    }
    Write(n/2+result);
  }
}

Measured memory_bytes: 17476
n = gets.to_i
t, a = gets.split.map(&:to_i)
h = gets.split.map(&:to_i)
ans = -1
val = 10000000000
n.times do |i|
    tmp = t - h[i] * 0.006
    tmp = (a - tmp).abs
    if tmp < val
        val = tmp
        ans = i + 1
    end
end
p ans

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

#define rep(i,m,n) for(int i=m;i<n;i++)
#define ll long long
#define MOD 1000000007

int main(int argc, char *argv[]) {

  int n,l;
  cin >> n >> l;

  int a,b;

  if(l*(l+n-1) < 0) {
    a = l; b = l+n-1;
  }else if(l >= 0) {
    a = l+1; b = l+n-1;
  }else {
    a = l; b = l+n-2;
  }
  cout << (a+b)*(b-a+1)/2;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef bool boool;
typedef long long ll;
#define vl vector<ll>
#define vb vector<boool>
#define vs vector<string>
#define vp vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define vvp vector<vector<pair<ll, ll>>>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define rep1(i, n) for (long long i=0; i<(long long)(n); i++)
#define rep2(i, s, e) for (long long i=(s); i<(long long)(e); i++)
#define GET_MACRO(_1,_2,_3,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

int main() {
    int n;
    cin >> n;
    vp vec(n);
    rep(i, n){
        ll a, b;
        cin >> a >> b;
        vec[i] = make_pair(a, b);
    }
    rep(i, n-2){
        if(vec[i].first == vec[i].second && vec[i+1].first == vec[i+1].second && vec[i+2].first == vec[i+2].second){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b, a % b);
}

using Graph = vector<vector<int>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}

typedef pair<int,int> P;

bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}
int factorial(int a){
  int res = 1;
  while(a){
    res *= a;
    a--;
  }
  return res;
}

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

Measured memory_bytes: 256