akhauriyash/Code-Regression huggingface dataset:
from collections import deque

n = int(input())
m = [[0 for j in range(n)] for i in range(n)]
color = [0 for i in range(n)]
q = deque()
dist = [-1 for i in range(n)]


def bfs(s):
    color[s], dist[s] = 1, 0
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for v in range(n):
            if m[u][v] == 1 and color[v] == 0:
                color[v], dist[v] = 1, dist[u] + 1
                q.append(v)

        color[u] = 2


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(2, len(data)):
            m[data[0]-1][data[j]-1] = 1

    bfs(0)

    for i in range(n):
        print(i+1, dist[i])


if __name__ == '__main__':
    main()



Measured memory_bytes: 6100
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int i = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define MP make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1 << 30;
const ll LINF = 1LL << 61;
const int MOD = 1e9 + 7;

int main() {
    int x;
    cin >> x;
    if(x < 1200) {
        cout << "ABC" << endl;
    } else {
        cout << "ARC" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

int dp[350][350];

int main(){
  int n;
  while(true){
    cin >> n;
    if(n == 0)return 0;
    vector<int> w(n);
    for(int i = 0; i < n; ++i){
      cin >> w[i];
    }

    fill((int*)dp, (int*)dp + sizeof(dp) / sizeof(int), 0);
    for(int width = 2; width <= n; ++width){
      for(int l = 0; l < n; ++l){
        int r = l + width;
        if(r > n)continue;
        if(dp[l + 1][r - 1] == width - 2 && abs(w[l] - w[r - 1]) <= 1)dp[l][r] = width;
        else{
          for(int i = l; i <= r; ++i){
            dp[l][r] = max(dp[l][r], dp[l][i] + dp[i][r]);
          }
        }
      }
    }

    cout << dp[0][n] << endl;

  }

  return 0;
}



Measured memory_bytes: 3480
#include<stdio.h>



int main(void){
  int N, i;
  long long T, t[200001], ans;
  scanf("%d%lld", &N, &T);
  for(i = 0; i < N; i++){
    scanf("%lld", &t[i]);
  }
  ans = T;
  for(i = 1; i < N; i++){
    ans += ((T < t[i] - t[i-1])? T : t[i] - t[i-1]);
   }
   printf("%lld\n",ans);
   return 0;
}


Measured memory_bytes: 1664
package main

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

func main() {
	scanner := makeWordScanner()
	a := eGetInt(scanner)
	b := eGetInt(scanner)
	c := eGetInt(scanner)
	d := eGetInt(scanner)
	turn := 0
	for a > 0 && c > 0 {
		if turn%2 == 0 {
			c = c - b
		} else {
			a = a - d
		}
		turn++
	}
	if a <= 0 {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
const (
	TooLarge = math.MaxInt64
	TooSmall = math.MinInt64
)

func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeCharScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanRunes)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetInt64(r *bufio.Scanner) int64 {
	line := eGetLine(r)
	return eAtoInt64(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetInt64s(r *bufio.Scanner) []int64 {
	fields := eGetFields(r)
	ints := make([]int64, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoInt64(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func eAtoInt64(s string) int64 {
	n, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func pow(a, n int) int {
	if n == 0 {
		return 1
	}
	if n == 1 {
		return a
	}
	if n%2 == 1 {
		return pow((a*a), n/2) * a
	}
	return pow((a * a), n/2)
}
func powMod(a, n, mod int) int {
	if n == 0 {
		return 1 % mod
	}
	if n == 1 {
		return a % mod
	}
	if n%2 == 1 {
		return powMod((a*a)%mod, n/2, mod) * a % mod
	}
	return powMod((a*a)%mod, n/2, mod)
}

func factoricalMod(n, count, mod int) int {
	if count == 1 {
		return n % mod
	}
	return (n % mod) * (factoricalMod(n-1, count-1, mod)) % mod
}

func combinationMod(n, a, mod int) int {
	x := factoricalMod(n, a, mod)
	y := factoricalMod(a, a, mod)
	y = powMod(y, mod-2, mod)
	return ((x % mod) * (y % mod)) % mod
}
func countBitOfOn(i, numbits int) int {
	count := 0
	var bit uint64
	for bit = 0; bit < uint64(numbits); bit++ {
		t := 1 << bit
		if i&t > 0 {
			count++
		}
	}
	return count
}

type ints []int

func ToString(slice []int) string {
	format := fmt.Sprint(slice)
	return fmt.Sprint(format[1 : len(format)-1])
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

// {{{
template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar[0].size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}
// }}}
/* vim:set foldmethod=marker: */

int main(int argc, char const* argv[])
{
    int n,k;
    cin >> n >> k;

    vi L(n);
    for (int i = 0; i < n; i++) {
        cin >> L[i];
    }
    sort(all(L),greater<int>());

    int ans=0;
    for (int i = 0; i < k; i++) {
        ans += L[i];
    }
    cout << ans << endl;

    return 0;
}

// sortの仕方
// int a[N];
// array<int,N> ar;
// vector<int> v;
//
// sort(a, a+N); // 配列
// sort(ar.begin(), ar.end()); // array
// sort(v.begin(), v.end()); // vector 昇順
// sort(v.begin(), v.end(), greater<int>()); // 降順

// Template
// template <class T>
// T foomax(T x, T y){
//   if (x > y){
//     return x;
//   }else{
//     return y;
//   }
// }

// string を int に変換 stoi("1010")
// int を string に変換 to_string(1010)


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

int main()
{
	int A, B;

	cin >> A >> B;
	for (int i = 1; i <= 3; i++)
	{
		if (i != A && i != B)
		{
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int n, a[100][100], b[101], tate[101][101];

int main(){
	cin >> n;
	rep(i, n) rep(j, n){
		cin >> a[i][j];
		tate[i + 1][j] = tate[i][j] + a[i][j];
	}
	int mx = -2 * inf;
	
	rep(j, n) rep(i, j + 1){
		memset(b, 0, sizeof(b));
		rep(k, n) b[k + 1] = b[k] + tate[j + 1][k] - tate[i][k];
		
		rep(l, n) rep(k, l + 1) mx = max(mx, b[l + 1] - b[k]);
	}
	cout << mx << endl;
	
	return 0;
}

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

// A <= C <= B
// B <= C <= A
int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if ((A <= C && C <= B) || (B <= C && C <= A)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3520
N, x = map(int, input().split())
array = list(map(int, input().split()))
a = sorted(array, reverse=False)
#print(a)
answer = 0
for i in range(N):
    x -= a[i]
    if x < 0:
        break
    answer += 1
    if i == N-1 and x != 0:
        answer -= 1
        break
    if x < a[i]:
        break
print(answer)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
long long a[200000],c[200000],n;
long long lowbit(long long x)
{
	return x&(-x);
}
void update(long long index,long long max_value)
{
	while(index<=n)
	{
		c[index]=max(c[index],max_value);
		index+=lowbit(index);
	}
}
long long maxrange(long long index)
{
	long long ret=0;
	while(index)
	{
		ret=max(ret,c[index]);
		index-=lowbit(index);
	}
	return ret;
}
int main()
{
	long long i,t,s,ans=0;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&s);
		t=maxrange(a[i]-1);
		update(a[i],t+s);
		ans=max(ans,t+s);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
using namespace std;
int main(){
  int n, i;
  double k=0.0;
  cin >> n;
  int a[n];
  for(i=0; i<n; i++){
    cin >> a[i];
    k+=1.0/a[i];
  }
  cout << 1.0/k << endl;
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(N: int, B: "List[int]"):
    a=[100001]*N
    for i in range(N-1):
        a[i]=min(a[i],B[i])
        a[i+1]=min(a[i+1],B[i])
    print(sum(a))
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    B = [int(next(tokens)) for _ in range(N - 1)]  # type: "List[int]"
    solve(N, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
N,A,B,C = map(int,input().split())
L = list(int(input()) for i in range(N))

def f(cur,a,b,c) :
    if cur == N :
        if min(a,b,c) > 0 :
            return abs(a-A) + abs(b-B) + abs(c-C) - 30
        else :
            return float("inf")
    ret0 = f(cur+1,a,b,c)
    ret1 = f(cur+1,a+L[cur],b,c) + 10
    ret2 = f(cur+1,a,b+L[cur],c) + 10
    ret3 = f(cur+1,a,b,c+L[cur]) + 10
    
    return min(ret0,ret1,ret2,ret3)

print(f(0,0,0,0))


Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        for(int i = 1; i <= b; i++){
            if(a * i % b == c){
                System.out.println("YES");
                System.exit(0);
            }
        }
        System.out.println("NO");
    }
}

Measured memory_bytes: 22228
<?php
/*
    Problem URL : https://beta.atcoder.jp/contests/abc064/tasks/abc064_b

    Score  :
    Result :
    Time   : ms
    Memory : KB
 */

// define('DEBUG', true);
define('DEBUG', false);

ini_set('error_reporting', E_ALL & ~E_NOTICE);

fscanf(STDIN, "%d", $N);
$a = explode(" ", trim(fgets(STDIN)));

echo (max($a) - min($a)) . PHP_EOL;


Measured memory_bytes: 4604
import math
A,B=map(int,input().split())
cost_A=math.ceil(A/0.08)
cost_B=B*10
if cost_B<cost_A:
    ans=cost_B
    while math.floor(ans*0.08) < A:
        ans+=1
        if math.floor(ans*0.1) >B:
            ans=-1
            break
elif cost_A<cost_B:
    ans=cost_A
    while math.floor(ans*0.1)<B:
        ans+=1
        if math.floor(ans*0.08) >A:
            ans=-1
            break
else:ans=cost_B
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
 
int n; char a[10005][25],b[25],s[25];
int main(){
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++) scanf("%s",a[i]+1);
	scanf("%s",s+1);
	int lf=0,rg=0;
	for (i=1; i<=n; i++){
		int len=strlen(a[i]+1),j;
		memset(b,0,sizeof(b));
		for (j=1; j<=len; j++) b[j]=((a[i][j]=='?')?'a':a[i][j]);
		if (strcmp(b+1,s+1)<=0) rg++;
		memset(b,0,sizeof(b));
		for (j=1; j<=len; j++) b[j]=((a[i][j]=='?')?'z':a[i][j]);
		if (strcmp(b+1,s+1)<0) lf++;
	}
	printf("%d",++lf);
	while (lf<=rg) printf(" %d",++lf); puts("");
	return 0;
}

Measured memory_bytes: 512
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

#[allow(unused_macros)]
macro_rules! echo {
    ($($e:expr),+) => ( { $(println!("{}", $e))+ } );
}

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

    let size = 10_usize.pow(6);
    let mut dp = vec![0; size + 1];

    for i in a {
        if dp[i] > 1 {
            continue;
        }
        let mut tmp = i;
        let mut times = 1;
        while tmp <= size {
            dp[tmp] += times;
            times += 1;
            tmp += i;
        }
    }

    let mut ans = 0;

    for e in dp {
        if e == 1 {
            ans += 1;
        }
    }

    echo!(ans);
}


Measured memory_bytes: 8896
import sys
S = list(input())

#奇数
odd_list = ['R','U','D']
#偶数
even_list = ['L','U','D']

for i in range(len(S)):
	#偶数
	if (i+1) % 2 == 0:
		if S[i] not in even_list:
			print('No') 
			sys.exit()
	#奇数
	else:
		if S[i]  not in odd_list:
			print('No')
			sys.exit()

print('Yes')

Measured memory_bytes: 3060
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<complex>
#include<sstream>
#include<climits>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MAX_HW = 100;
int H, W, N;
int a[MAX_HW*MAX_HW];
int field[MAX_HW][MAX_HW];

int main() {
  cin >> H >> W >> N;
  rep(i,N) cin >> a[i];

  int count = 0;
  for (int i = 0; i < H; ++i) {
    if (i%2 == 0) {
      for (int j = 0; j < W; ++j) {
        field[i][j] = count+1;
        a[count]--;
        if (a[count] == 0) ++count;
      }
    } else {
      for (int j = W-1; j >= 0; --j) {
        field[i][j] = count+1;
        a[count]--;
        if (a[count] == 0) ++count;
      }
    }
  }

  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      printf("%d%c", field[i][j], j+1 == W ? '\n' : ' ');
    }
  }

  return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
// #include "prettyprint.hpp"

bool isGood(int a[], int b[], int size) {
  int sum = 0;
  for (int i = 0; i < size; i++) {
    sum += (a[i] - b[i]) * (a[i] - b[i]);
  }

  int temp = (int)sqrt(sum);
  return temp * temp == sum;
}

int main() {
  int N, D;
  cin >> N >> D;
  int X[N][D];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < D; j++) {
      cin >> X[i][j];
    }
  }

  int count = 0;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (isGood(X[i], X[j], D)) count += 1;
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <string>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

constexpr long long mod = 1e9 + 7;

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	vector<long long> a(n + 1), pre_sum(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		pre_sum[i] = pre_sum[i - 1] + a[i];
	}

	long long sum = 0;
	for (int i = 1; i < n; ++i) {
		sum += a[i] * ((pre_sum[n] - pre_sum[i]) % mod);
		sum %= mod;
	}

	cout << sum << "\n";

	return 0;

}

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

int main() {
  int N;
  cin>>N;
  ll ans=0;
  rep(i,N) {
    ll a;
    cin>>a;
    while(a%2==0){
      a /= 2;
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 1000000000;
typedef double D;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
//typedef pair<int, int> P;

/** Problem0557 : A First Grader **/
int main()
{
	int N, num[100], a;
	long long int dp[21][100] = {0};
	
	cin>>N;
	rep(i, N-1) {
		cin>>num[i];
	}
	cin>>a;
	
	dp[num[0]][0] = 1;
	
	REP(i, 1, N-1) {
		rep(j, 21) {
			int b = j + num[i];
			int c = j - num[i];
			if (0<=b && b<=20)
				dp[b][i] += dp[j][i-1];
			if (0<=c && c<=20)
				dp[c][i] += dp[j][i-1];
		}
	}
	
	cout << dp[a][N-2] << endl;
}

Measured memory_bytes: 1180
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,(v).size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,const T&t,const U&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(const T&...t){_print(cout,t...);}template<class...T>void dprint(const T&...t){_print(cerr,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#endif
template<class T>bool chmax(T&a,const T&b){bool x=a<b;x?a=b:b;return x;}template<class T>bool chmin(T&a,const T&b){bool x=a>b;x?a=b:b;return x;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>class iterable{static false_type c(string v);template<class U>static auto c(U v)->decltype(all(v),true_type());static false_type c(...);public:const static bool value=decltype(c(declval<T>()))::value;};
template<class T,typename=enable_if_t<iterable<T>::value>>ostream&operator<<(ostream&o,const T&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int n,m,r;
    cin>>n>>m>>r;
    vi q(r);
    cin>>q;
    REP(i,r)--q[i];
    vvi g(n,vi(n,INF));
    REP(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        g[a-1][b-1]=c;
        g[b-1][a-1]=c;
    }
    REP(k,n){
        REP(i,n){
            REP(j,n){
                chmin(g[i][j], g[i][k]+g[k][j]);
            }
        }
    }
    sort(all(q));
    ll ans=INF;
    do{
        ll s=0;
        REP(i,r-1){
            s+=g[q[i]][q[i+1]];
        }
        chmin(ans, s);
    }while(next_permutation(all(q)));
    cout<<ans<<endl;
}


Measured memory_bytes: 384
G = [nil, nil, nil,
  %w(
    a..
    a..
    .bb
  ),
  %w(
    aabc
    ddbc
    efgg
    efhh
  ),
  %w(
    abbcc
    ad..e
    fd..e
    f.ggh
    iijjh
  ),
  %w(
    aabc..
    ddbc..
    ..eefg
    ..hhfg
    ij..kk
    ij..ll
  ),
  %w(
    aabbcc.
    ..de..f
    ..de..f
    gh....i
    gh....i
    jj..kkl
    ..mmnnl
  )
]
N=gets.to_i
A=N.times.map{?. * N}
def w x,j
  G[x].each do |g|
    s = ?. * N
    s[j,x] = g
    puts s
  end
end
if N==2
  p -1
elsif N==3
  w 3,0
else
  m=N%4+4
  w m,0
  (N/4-1).times do |j|
    w 4,m+j*4
  end
end

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

string S;
int N;

void solve() {
  int same_num = 0;
  if (N % 2) {
    char center = S[N / 2];
    int left = N / 2 - 1;
    int right = N / 2 + 1;
    while (left >= 0 && right < N && S[left] == center && S[right] == center) {
      same_num++;
      left--;
      right++;
    }
  } else {
    if (S[(N - 1) / 2] == S[N / 2]) {
      same_num++;
      char center = S[N / 2];
      int left = N / 2 - 2;
      int right = N / 2 + 1;
      while (left >= 0 && right < N && S[left] == center && S[right] == center) {
        same_num++;
        left--;
        right++;
      }
    }
  }
  cout << (N + 1) / 2 + same_num << endl;
}

int main() {
  cin >> S;
  N = S.size();

  solve();
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/

// 123456789
// 255456376
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	vi a(m);
	vi b={100,2,5,5,4,5,6,3,7,6};
	cin>>a;
	sort(all(a),[&](int x,int y){return b[x]<b[y] or (b[x]==b[y] and x<y);});
	vi x;
	rep(i,m){
		if(i+1<=m-1 and b[a[i]]==b[a[i+1]])continue;
		x.push_back(a[i]);
	}
	m=x.size();
	a=x;

	vvi dp(n+1,vi(m,0));
	rep(i,n)dp[i+1][0]=-1;
	rep(j,m){
		rep(i,n+1){
			if(dp[i][0]==-1)continue;
			if(i+b[a[j]]>n)continue;
			//puta(j,i,",",dp[i+b[a[j]]],",",dp[i],",",j);
			int cdig=0,ndig=1;
			bool ok=true;
			rep(k,m){
				cdig+=dp[i+b[a[j]]][k];
				ndig+=dp[i][k];
			}
			if(ndig<cdig)continue;
			rrep(num,10){
				if(find(all(a),num)==a.end())continue;
				int c=find(all(a),num)-a.begin();
				if(dp[i+b[a[j]]][c]==dp[i][c]+(c==j?1:0))continue;
				if(dp[i+b[a[j]]][c]>dp[i][c]+(c==j?1:0))ok=false;
				break;
			}
			if(!ok)continue;
			dp[i+b[a[j]]]=dp[i];
			dp[i+b[a[j]]][j]++;
		}
	}
	// puta(a);
	// puta(dp[n]);
	rrep(num,10){
		if(find(all(a),num)==a.end())continue;
		int c=find(all(a),num)-a.begin();
		rep(j,dp[n][c]){
			cout<<num;
		}
	}
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  int sum = 0;
  for(int i = 0; i < N; i++){
    int ri, li;
    cin >> ri >> li;
    sum += li - ri + 1;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;

map<int,int> w;

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	fore(i,0,n){
		int k;
		scanf("%d",&k);
		w[k]++;
	}
	vector<pair<int,int> > v(w.begin(),w.end());
	fore(i,0,SZ(v))swap(v[i].fst,v[i].snd);
	sort(v.begin(),v.end());reverse(v.begin(),v.end());
	int r=0;
	for(int i=SZ(v)-1;i>=k;--i)r+=v[i].fst;
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 11136
ans= [0]*(6*10**4+10)
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            ans[i**2+j**2+k**2+i*j+j*k+k*i] += 1
n = int(input())
for i in range(1,n+1):
    print(ans[i])

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

vector <long long> dp;
vector <long long> PS;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long n, k;
	cin >> n >> k;
	dp.push_back(1);
	string s;
	cin >> s;
	for (long long i = 1; i < n; i++){
		if (s[i] != s[i - 1]){
			dp.push_back(1);
		}
		else{
			dp[dp.size() - 1] ++;
		}
	}
	PS.resize(dp.size() + 1);
	for (long long i = 1; i <= dp.size(); i++)
		PS[i] = PS[i - 1] + dp[i - 1];
	if (dp.size() <= 2 * k || (dp.size() == 2 * k + 1) && s[0] == '1'){
		cout << n;
		return 0;
	}
	long long ans = 0;
	for (long long i = 0; i < dp.size(); i++){
		if (s[0] == i % 2 + '0'){
			if (i + 2 * k > dp.size()){
				ans = max(ans, PS[dp.size()] - PS[i]);
				// break;
			}
			else
				ans = max(ans, PS[i + 2 * k] - PS[i]);
		}
		else{
			if (i + 2 * k + 1 > dp.size()){
				ans = max(ans, PS[dp.size()] - PS[i]);
				// break;
			}
			else
				ans = max(ans, PS[i + 2 * k + 1] - PS[i]);
		}
	}
	cout << ans;
}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define DISP1(as)		for(auto it : as) cout<<it.f<<" "<<it.s<<") ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	2e+5 + 99;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, k, l, q, x, y, m;
string s, t;

ll rem;
ll cnt[3];


// < ----------- func eh ---------------- ? //

bool isprime(ll n) {
	if(n == 1) return true;
	for(ll i=2;i*i<=n;i++) {
		if(n%i==0) return false;
	}
	return true;
}


vll factors(ll n) {
	vll f;
	for(ll i=1;i*i<=n;i++) {
		if(n%i==0) {
			f.pb(i);
			if(i*i != n) f.pb(n/i);
		}
	}

	sort(all(f));
	return f;
}

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n >> m ;
	ll val = __gcd(n,m);

	vll f = factors(val);
	ll cnt = 1;

	for(ll i=1;i<f.size();i++) if(isprime(f[i])) cnt++;

	cout<<cnt;
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		try (Scanner sc = new Scanner(System.in)) {
			int c0[] = new int[3];
			int c1[] = new int[3];
			int c2[] = new int[3];
			for (int i = 0; i < 3; i++) {
				c0[i] = sc.nextInt();
			}
			for (int i = 0; i < 3; i++) {
				c1[i] = sc.nextInt();
			}
			for (int i = 0; i < 3; i++) {
				c2[i] = sc.nextInt();
			}
			
			int x[] = new int[6];
			int y[] = new int[6];
			for (int i = 0; i < 3; i++) {
				x[i] = c0[i] - c1[i];
				x[i + 3] = c1[i] - c2[i];
			}
			for (int i = 0; i < 2; i++) {
				y[i] = c0[i] - c0[i + 1];
				y[i + 2] = c1[i] - c1[i + 1];
				y[i + 4] = c2[i] - c2[i + 1];
			}
			
			boolean result = true;
			if (x[0] == x[1] && x[1] == x[2]) {} else {
				result = false;
			}
			if (x[3] == x[4] && x[4] == x[5]) {} else {
				result = false;
			}
			if (y[0] == y[2] && y[2] == y[4]) {} else {
				result = false;
			}
			if (y[1] == y[3] && y[3] == y[5]) {} else {
				result = false;
			}
			
			if (result) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
			
		}

	}

}

Measured memory_bytes: 21972
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp
N = ir()
INF = 10 ** 8
dp = [INF] * (N+1)
dp[0] = 0
for i in range(5, 0, -1):
    num = 9 ** i
    for j in range(N):
        if j+num <= N:
            dp[j+num] = min(dp[j+num], dp[j]+1)

for i in range(6, 0, -1):
    num = 6 ** i
    for j in range(N):
        if j+num <= N:
            dp[j+num] = min(dp[j+num], dp[j]+1)

num = 1
for j in range(N):
    dp[j+num] = min(dp[j+num], dp[j]+1)

answer = dp[N]
print(answer)


Measured memory_bytes: 41584
#coding:utf-8
N = int(input())
T = []
class Tree:
    def __init__(self,ID,l=None,r=None,p=-1):
        self.ID = ID
        self.l = l
        self.r = r
        self.p = p

    def makeTree(self):
        for i in range(N):
            T.append(Tree(i))


def preParse(tree):
    if tree == None:
        return
    else:
        ID = tree.ID
        global preList
        preList.append(ID)
        preParse(tree.l)
        preParse(tree.r)
        
def inParse(tree):
    if tree == None:
        return
    else:
        ID = tree.ID
        global inList
        inParse(tree.l)
        inList.append(ID)
        inParse(tree.r)

def posParse(tree):
    if tree == None:
        return
    else:
        ID = tree.ID
        global posList
        posParse(tree.l)
        posParse(tree.r)
        posList.append(ID)
        
    
trees = [list(map(int,input().split())) for i in range(N)]
Tree.makeTree(Tree)
for i in range(N):
    ID,l,r = trees[i]
    tree = T[ID]
    if l != -1:
        T[l].p = tree
        tree.l = T[l]
    if r != -1:
        T[r].p = tree
        tree.r = T[r]
    
for i in range(N):
    if T[i].p == -1:
        parent = T[i]

preList = []
inList = []
posList = []
preParse(parent)
inParse(parent)
posParse(parent)

def convert(List, order):
    a =  " " + " ".join([str(num) for num in List])
    print("{}".format(order))
    print(a)
convert(preList, "Preorder")
convert(inList, "Inorder")
convert(posList, "Postorder")



Measured memory_bytes: 5620
<?php
list($n,$d)=explode(" ",trim(fgets(STDIN)));
if($d==1){
	echo $n*($n-1)/2;
}else{
	$ans=0;
	$i=0;
	while($i<$n){
		$x[]=explode(" ",trim(fgets(STDIN)));
		++$i;
	}
	$i=0;
	while($i<$n-1){
		$j=$i+1;
		while($j<$n){
			$l=0;
			$k=0;
			while($k<$d){
				$l+=pow(($x[$i][$k]-$x[$j][$k]),2);
				++$k;
			}
			$l=sqrt($l);
			if($l==floor($l)){
				++$ans;
			}
			++$j;
		}
		++$i;
	}
	echo $ans;
}

Measured memory_bytes: 4728
#include <iostream>
#include <vector>
#include <cmath>
#include <typeinfo>
#include <set>
#include <bitset>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;



int main(){
  int s,w;
  cin >> s >> w;
  if(s>w){
    cout << "safe" << endl;
  }else{
    cout << "unsafe" << endl;
  }
}

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

int main() {
    int D;
    cin >> D;
    vector<int> c(26);
    vector<vector<int>> s(D, vector<int>(26));
    rep(i, 26) cin >> c[i];
    rep(i, D) {
        rep(j, 26) { cin >> s[i][j]; }
    }

    vector<int> t(D);
    rep(i, D) cin >> t[i];

    vector<int> ans(D);
    vector<ll> Cost(26, 0);
    rep(i, 26) Cost[i] = c[i];
    ll v = 0;
    rep(i, D) {
        vector<ll> X(26);
        // rep(j, 26) X[j] = s[i][j] + Cost[j];
        // auto it = max_element(X.begin(), X.end());
        int index = t[i] - 1;
        // ans[i] = index + 1;
        Cost[index] = 0;
        v += s[i][index];
        rep(j, 26) {
            v -= Cost[j];
            Cost[j] += c[j];
        }
        cout << v << endl;
    }
    // rep(i, D - 1) cout << ans[i] << " ";
    // cout << ans[D - 1] << endl;
}

Measured memory_bytes: 3680
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    string s,t;
    cin >>s;
    cin>>t;
    int ans;
    char a;


    for(int k=0;k<s.size();k++){
        ans=0;
for(int i=0;i<s.size();i++){
    if(s[i]==t[i]){
    ans++;}
}

if(ans==s.size()){
    break;
}
a=t[t.size()-1];
for(int l=t.size()-1;l>=1;l--){
    t[l]=t[l-1];
}
t[0]=a;

    }

if(ans==s.size()){
    cout <<"Yes"<<endl;
}
    else{
        cout <<"No"<<endl;
    }
 return 0;
}

Measured memory_bytes: 256
open Core
open Stdio
open Bigarray

let scan_line fo g = Caml.Scanf.sscanf In_channel.(input_line_exn stdin) fo g
let scan_line_1 fo = scan_line fo (fun a -> a)
let scan_line_2 fo = scan_line fo (fun a b -> (a,b))
let scan_line_3 fo = scan_line fo (fun a b c -> (a,b,c))
let scan_line_4 fo = scan_line fo (fun a b c d -> (a,b,c,d))

let money_inf = 50 * 50
let dist_inf = Int64.(10L ** 15L)
type edge_t = { cod : int; unchin : int; jikan : Int64.t }

let n, m, s = scan_line_3 "%d %d %d"
let s = min money_inf s

let edges = Array.create ~len:n []

let () =
    for i = 1 to m do
        let u, v, un, ji = scan_line_4 "%d %d %d %Ld" in
        let u = u - 1 in let v = v - 1 in
        edges.(u) <- { cod = v; unchin = un; jikan = ji } :: edges.(u);
        edges.(v) <- { cod = u; unchin = un; jikan = ji } :: edges.(v)
    done

let maisu_jikan_s =
    Array.init n
    ~f:begin fun _ ->
        let x, y = scan_line_2 "%d %Ld" in
        let x = min x money_inf in
        (x,y)
    end

let used = Array2.create int8_signed c_layout n (money_inf+1)
let () = Array2.fill used 0
let res = Array2.create int64 c_layout n (money_inf+1)
let () = Array2.fill res dist_inf

(* cf. https://ocaml.janestreet.com/ocaml-core/latest/doc/core_kernel/Core_kernel/Map/index.html *)
module Dijk = struct
    module T = struct
        type t = int64 * int * int
        let compare = Tuple3.compare ~cmp1:Int64.compare ~cmp2:compare ~cmp3:compare
        let sexp_of_t = Tuple3.sexp_of_t Int64.sexp_of_t Int.sexp_of_t Int.sexp_of_t
    end
    include T
    include Comparator.Make(T)
end

let dijk () = let rec loop mins =
    match Set.min_elt mins with
    | None -> ()
    | Some ((dist, v, money) as tup) ->
        let mins = Set.remove mins tup in
        if used.{v, money} <> 0 then loop mins else begin
        used.{v, money} <- 1 (* true *);
        res.{v, money} <- Int64.min res.{v, money} dist;
        (* 銀貨に交換 *)
        let mins =
            let dist = Int64.(dist + snd maisu_jikan_s.(v)) in
            let money = money + fst maisu_jikan_s.(v) in
            if money <= money_inf && used.{v, money} = 0
            then Set.add mins (dist, v, money) 
            else mins
        in
        (* 別の都市に移動 *)
        let mins = List.fold edges.(v) ~init:mins ~f:begin fun mins e ->
            let dist = Int64.(dist + e.jikan) in
            let v = e.cod in
            let money = money - e.unchin in
            if money >= 0 && used.{v, money} = 0
            then Set.add mins (dist, v, money) 
            else mins
        end in
        loop mins end
    in loop (Set.singleton (module Dijk) (0L, 0, s))

let () =
    dijk ();
    for v = 1 to n - 1 do
        let res_v = Array2.slice_left res v in
        let rec calc_min acc i =
            if i < Array1.dim res_v
            then calc_min Int64.(min acc res_v.{i}) (i+1)
            else acc
        in
        printf "%Ld\n" @@ calc_min dist_inf 0
    done


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

int main() {
  int N, K, X, Y;
  cin >> N >> K >> X >> Y;

  int ans = 0;
  if (N <= K) {
    ans = X * N;
  } else {
    ans = X * K + Y * (N - K);
  }
  cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF (1LL<<25)     //33554432
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

signed main(void)
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  c = abs(c-a); d = abs(b-d);
  if(c == 0 || d == 0) {
    cout << 0 << endl;
    return 0;
  }

  int x = c, y = d;
  if(x < y) swap(x, y);
  while(y > 0) {
    int r = x%y;
    x = y;
    y = r;
  }
  //cout << x << endl;

  int ans = c + d - x;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>
using namespace std;

typedef long long ll;
/*
typedef struct Name   Name;
struct Name {
    int a[3];
};
*/
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) for (int i = 0; i < (a); i++)
int main()
{
    int X, N,a;
    vector<int> arr;
    cin >> X >> N;
    for(int i = 0; i < N; i++)
    {
        cin >> a;
        arr.push_back(a);
    }
    int dif = 0;

    bool loop = true;

    while(loop)
    {
        if(find(arr.begin(),arr.end(),X-dif) == arr.end())
        {
            cout << X-dif << "\n";
            break;
        }
        if(find(arr.begin(),arr.end(),X+dif) == arr.end())
        {
            cout << X+dif << "\n";
            break;
        }
        dif++;
        
    }
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 5005;

struct Node
{
	int p, h;
	bool operator < (const Node &b) const
	{
		return p + h < b.p + b.h;
	}
} a[MAXN];

LL f[MAXN];
int n;

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		a[i].h = Read(), a[i].p = Read(), f[i] = 1LL << 60;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i ++)
		for (int j = i; j; j --)
			if (f[j - 1] <= a[i].h)
				f[j] = min(f[j], f[j - 1] + a[i].p);
	for (int i = n; ~i; i --)
		if (f[i] ^ 1LL << 60)
			return printf("%d\n", i), 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  cout << max(max(abs(a-b),abs(b-c)),abs(c-a));
}
/*
  for(int i=0;i<4;i++){
    if(s[i]=='-')o----;
    o++;
  }
  cout << o;
}
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,a[100000];
  cin>>n>>a[0];
  for(int i=1;i<n;i++){
    cin>>a[i],a[i]+=a[i-1];
  }
  
  long long ans,s,t[100000],rans=1e18;
  for(int i=0;i<n;i++)t[i]=a[i];

  for(int k=0;k<2;k++){
    ans=0,s=0;
    for(int i=0;i<n;i++)a[i]=t[i];
    if(a[0]==0){
      if(k)a[0]--,s--;
      else a[0]++,s++;
      ans++;
      }
    else if(k==0&&a[0]<0)ans+=1-a[0],s+=1-a[0],a[0]=1;
    else if(k==1&&a[0]>0)ans+=1+a[0],s+=-1-a[0],a[0]=-1;
    for(int i=1;i<n;i++){
      if(a[i-1]<0&&a[i]+s<=0){
	ans+=abs(1-(a[i]+s)),s+=1-(a[i]+s),a[i]=1;
      }
      else if(a[i-1]>0&&a[i]+s>=0){
	ans+=abs(-(a[i]+s)-1),s+=-(a[i]+s)-1,a[i]=-1;
      }
      else a[i]+=s;
    }
    rans=min(rans,ans);
  }
  cout<<rans<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cmath>
#define pb(in,tmp) in.push_back(tmp)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) loop(i,0,b)
#define all(in) in.begin(),in.end()
using namespace std;
int han(int y,int m){
return y%3==0||m%2==1 ? 0 : 1;
}
int main(){
int n;
cin>>n;
rep(k,n){
int y,m,d;
cin>>y>>m>>d;
int co=0;
do{
co++;
d++;
if(d>20-han(y,m)){d=1;m++;}
if(m>10){m=1;y++;}
}while(y!=1000);
cout<<co<<endl;
}
}

Measured memory_bytes: 1160
program skill_up
  implicit none
  integer, parameter :: inf = 1e9
  integer :: n, m, x, c(12) = 0, a(12,12) = 0, i, j, u, ans = inf, tmp, s(12) = 0
  read(*,*) n, m, x
  do i = 1, n
    read(*,*) c(i), a(i,1:m)
  end do
  u = lshift(1,n)-1
  do j = 0, u
    tmp = 0
    s = 0
    do i = 1, n
      if (.not.btest(j,i-1)) cycle
      tmp = tmp+c(i)
      s(1:m) = s(1:m)+a(i,1:m)
    end do
    if (all(s(1:m) >= x)) ans = min(ans,tmp)
  end do
  write(*,'(i0)') merge(-1,ans,ans == inf)
end program skill_up

Measured memory_bytes: 2928
#include <stdio.h>
int main(){
  int r,c,a[101][101],i,j,sum1,sum2,all=0;
  scanf("%d%d",&r,&c);
  for(i=0;i<r;i++){              /* 行列の入力  */
    for(j=0;j<c;j++){
      scanf("%d",&a[i][j]);
    }
  }                        

  for(i=0;i<r;i++){      /* ここから  */
    a[i][c]=0;
  }

  i=r;
  for(j=0;j<=c;j++){
    a[r][j]=0;
  }                      /* ここまで初期化 */

  for(i=0;i<r;i++){
    sum1=0;
    for(j=0;j<c;j++){
      sum1+=a[i][j];
      printf("%d ",a[i][j]);   /*  行と行の和の出力 */
    }
    printf("%d",sum1);
    printf("\n");
  }

  

for(j=0;j<c;j++){
  sum2=0;
  for(i=0;i<r;i++){
    sum2+=a[i][j];
      }
  a[r][j]=sum2;
  printf("%d ",sum2);
 }
  
  for(j=0;j<c;j++){
    all+=a[r][j];
  }
      printf("%d",all);


    printf("\n");

    return 0;
  }
  

Measured memory_bytes: 640
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
var nm=(Arr.shift()).split(" ").map(Number);
var n=[];
for(var i=0;i<nm[0];i++){
   n.push([i+1,Arr.shift()-0,0]);
}
for(var i=0;i<nm[1];i++){
   var v=Arr.shift()-0;
   for(var j=0;j<nm[0];j++){
      if(n[j][1]<=v){
         n[j][2]++;
         break;
      }
   }
}
n.sort(function(a,b){
   a=a[2];
   b=b[2];
   return b-a;
});
console.log(n[0][0]);

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

int main()
{
    ll n;
    cin >> n;
    vector<ll> h(n);
    rep(i, n) cin >> h[i];
    int pre = -999;
    rep(i, n)
    {
        if (pre <= h[i] - 1)
        {
            pre = h[i] - 1;
        }
        else if (pre <= h[i])
        {
            pre = h[i];
        }
        else
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll n = 0;
  cin >> n;
  vector<ll> a(n);
  for(int i = 0;i < n;i++)cin >> a[i];
  vector<ll> c;
  c.push_back(a[0]);
  for(int i = 1;i < n;i++){
    //if(i == 5)cout << c.size()<< " " << c[0] << " " << c[1] << " " << c[2] << endl;
    
    ll pushnum = 0;
    ll popit = lower_bound(c.begin(),c.end(),a[i]) - c.begin();
    if(popit == 0)pushnum = a[i];
    else{
      pushnum = a[i];
      c.erase(c.begin() + popit - 1);
    }
    
    ll pushit = lower_bound(c.begin(),c.end(),pushnum) - c.begin();
    c.insert(c.begin() + pushit,pushnum);
  }
  //cout << c[0] << " " << c[1] << " " << c[2] << endl;
  cout << c.size() << endl;
}

Measured memory_bytes: 4996
use proconio::input;

fn main() {
    input! {
        n: i64
    }

    const DIVISOR: i64 = 1000000007;

    if n == 1 {
        println!("{}", 0);
        return;
    }

    let mut a = 1;
    let mut b = 1;
    let mut c = 1;
    for _ in 0..n {
        a = a * 10 % DIVISOR;
        b = b * 9 % DIVISOR;
        c = c * 8 % DIVISOR;
    }

    let mut ans = (a - b * 2 + c) % DIVISOR;
    if ans < 0 {
        ans = ans + DIVISOR;
    }

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


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

int main(void){

    int K; cin >> K;
    string S; cin >> S;

    if(S.size() <= K){
        cout << S << endl;
    }
    else{
        cout << S.substr(0, K) + "..." << endl;
    }

    return 0;
}

Measured memory_bytes: 3588